ЯдроКодаподготовка к экзаменам
Подготавливаем текст, источники и редакционные примечания без изменения разметки страницы.
Разбираем AlphaDev без громких обобщений: поиск ассемблерных программ, проверка корректности, benchmark и интеграция малых сортировок в LLVM libc++.
AlphaDev называют нейросетью, которая «переписала сортировку». Точнее будет так: исследователи сформулировали поиск коротких низкоуровневых программ сортировки как одиночную игру, обучили агента выбирать инструкции и нашли новые реализации для небольших фиксированных размеров и коротких последовательностей. Часть результатов прошла обычную инженерную проверку и была включена в LLVM libc++.
Общий алгоритм сортировки обрабатывает массивы разных размеров, но внутри библиотек есть специальные ветви для очень коротких диапазонов. Они вызываются напрямую и служат строительными блоками более крупных процедур. На длинах три, четыре или пять стоимость одной лишней инструкции и неудачного ветвления может быть заметна, потому что вся работа и так мала.
Эта область уже хорошо оптимизирована людьми. Корректная программа должна сортировать все допустимые входы, а быстрая — учитывать реальную архитектуру процессора, зависимости инструкций и предсказание ветвлений. Простое правило «меньше строк — быстрее» работает не всегда.
Состояние AlphaDev включает строящуюся программу и состояние регистров. Действие — выбор следующей ассемблерной инструкции. Эпизод заканчивается, когда программа готова либо превышен бюджет. Награда учитывает корректность и стоимость, в том числе длину или измеренную задержку целевой реализации.
Агент использует подход, родственный AlphaZero: нейросеть оценивает политику и ценность, а Monte Carlo tree search исследует последовательности действий. Важное отличие от языковой генерации кода — пространство действий ограничено инструкциями, а результат проверяется формальным набором входов и benchmark-процедурой.
Для fixed sort авторы исследовали сортировки трёх, четырёх и пяти элементов, а также более длинные небольшие варианты. Для variable sort программа выбирает путь в зависимости от длины. Именно ветвления делают фактическую задержку менее предсказуемой по одному числу инструкций.
Для сети сравнений действует ноль-единичный принцип: если сеть правильно сортирует все бинарные последовательности данной длины, она сортирует значения из любого линейно упорядоченного множества. Это даёт компактный исчерпывающий тест структуры из compare-swap операций.
from itertools import product
def compare_swap(values, left, right):
if values[left] > values[right]:
values[left], values[right] = values[right], values[left]
def sort_three(values):
result = list(values)
compare_swap(result, 0, 1)
compare_swap(result, 1, 2)
compare_swap(result, 0, 1)
return result
cases = list(product([0, 1], repeat=3))
assert all(sort_three(case) == sorted(case) for case in cases)
print(f"Проверено бинарных входов: {len(cases)}")Этот тест не доказывает скорость и не воспроизводит найденные AlphaDev инструкции. Он показывает необходимое разделение: сначала корректность на полном классе для выбранной модели, затем производительность на целевых процессорах и типах данных.
В fixed sort агент обнаружил последовательности, которые авторы назвали AlphaDev swap move и copy move. Они используют уже известные отношения между значениями и убирают инструкцию по сравнению с прежней схемой. Для variable sort агент строил более короткие ветвящиеся программы и оптимизировал измеряемую задержку.
Авторы сравнивали AlphaDev со stochastic superoptimization. При старте без готового близкого решения AlphaDev эффективнее исследовал пространство некоторых задач. При warm start стохастический метод оставался сильным конкурентом для коротких branchless программ. Это не история «RL всегда победил оптимизатор», а сравнение режимов с разными начальными знаниями и целями.
Найденные fixed sort реализации прошли review в LLVM и попали в libc++. Это существенный инженерный сигнал: код проверяли не только авторы статьи, но и сопровождающие библиотеки. Однако интеграция конкретных функций не означает автоматической применимости агента к произвольному коду.
Латентность измеряли на множестве машин и типов данных, а оптимизация различала длину и фактическое время. На коротких функциях результат легко исказить прогревом, частотой CPU, расположением кода, компилятором и шумом системы. Поэтому важны доверительные интервалы, повторения и проверка на нескольких архитектурах.
Кроме скорости отдельного вызова нужно оценивать влияние на всю библиотеку: размер бинарника, время компиляции, поддерживаемость и отсутствие регрессий для нестандартных типов и компараторов. Статья исследует центральное ядро задачи, а production-интеграция добавляет отдельный слой требований.
Главная идея AlphaDev шире конкретных инструкций: пространство программ можно исследовать обучаемым поиском, если действие формализовано, корректность автоматически проверяется, а стоимость измеряется на реальной цели. Самая трудная часть такого проекта — не выбрать нейросеть, а построить строгую среду: определить семантику, исключить ошибочные программы, сделать benchmark устойчивым и провести независимый review результата.
Поэтому хороший вопрос к новости об «алгоритме, открытом ИИ» звучит не «насколько умна модель?», а «какую программу искали, на каких входах доказали корректность, с чем сравнивали и где измерили ускорение?».
Самостоятельный редакционный разбор ЯдроКода по статье Mankowitz et al., открытому репозиторию AlphaDev и LLVM review. Исходный текст и иллюстрации не копируются.
Учебная реализация и текст созданы редакцией; ассемблерные листинги, графики и рисунки исходной работы не воспроизводятся.