Планирование инструкций

редактировать

В информатике планирование инструкций - это оптимизация компилятора используется для улучшения параллелизма на уровне команд, что повышает производительность на машинах с конвейерами команд. Проще говоря, он пытается сделать следующее, не меняя значения кода:

Избегайте остановок конвейера, изменяя порядок инструкций.
Избегайте незаконных или семантически неоднозначных операций ( обычно связаны с небольшими проблемами синхронизации конвейера команд или неблокированными ресурсами).

Остановки конвейера могут быть вызваны структурными опасностями (ограничение ресурсов процессора), опасностями данных (вывод одной инструкции, необходимой другой инструкции) и опасностями управления (ветвление).

Содержание

1 Опасности данных
2 Алгоритмы
3 Порядок фаз
4 Типы
5 Примеры компилятора
6 См. Также
7 Ссылки
8 Дополнительная литература

Опасности данных

Планирование инструкций обычно выполняется для одного базового блока. Чтобы определить, сохраняет ли определенным образом перестановка инструкций блока поведение этого блока, нам нужна концепция зависимости данных. Есть три типа зависимостей, которые также являются тремя опасностями данных :

Чтение после записи (RAW или «Истина»): Инструкция 1 записывает значение, используемое позже инструкцией 2. Инструкция 1 должна идти первой, или Инструкция 2 будет читать старое значение вместо нового.
Запись после чтения (WAR или «Anti»): Инструкция 1 считывает место, которое позже перезаписывается инструкцией 2. Инструкция 1 должна идти первой, или он будет читать новое значение вместо старого.
Запись после записи (WAW или «Вывод»): две инструкции записывают одно и то же место. Они должны располагаться в исходном порядке.

Технически существует четвертый тип, «Чтение после чтения» (RAR или «Ввод»): обе инструкции читают одно и то же место. Входная зависимость не ограничивает порядок выполнения двух операторов, но полезна при скалярной замене элементов массива.

Чтобы убедиться, что мы соблюдаем три типа зависимостей, мы строим граф зависимостей, который представляет собой ориентированный граф, где каждая вершина является инструкцией, а есть ребро из I От 1 до I 2, если I 1 должен стоять перед I 2 из-за зависимости. Если переносимые циклом зависимости не учитываются, граф зависимостей является направленным ациклическим графом. Тогда любая топологическая сортировка этого графа является допустимым расписанием команд. Ребра графа обычно помечены латентностью зависимости. Это количество тактов, которое должно пройти, прежде чем конвейер сможет продолжить выполнение целевой инструкции без остановки.

Алгоритмы

Часто используется простейший алгоритм поиска топологической сортировки, известный как планирование списка. По сути, он несколько раз выбирает источник графа зависимостей, добавляет его в текущее расписание инструкций и удаляет его из графа. Это может привести к тому, что другие вершины станут источниками, которые затем также будут учитываться при планировании. Алгоритм завершается, если граф пуст.

Чтобы добиться хорошего графика, следует избегать киосков. Это определяется выбором следующей инструкции для планирования. Часто используется ряд эвристик:

Записываются ресурсы процессора, используемые уже запланированными инструкциями. Если кандидат использует занятый ресурс, его приоритет упадет.
Если кандидат запланирован ближе к своим предшественникам, чем связанная задержка, его приоритет упадет.
Если кандидат лжет на критическом пути графа его приоритет будет повышаться. Эта эвристика обеспечивает некоторую форму упреждения в процессе принятия решений на локальном уровне.
Если выбор кандидата создаст много новых источников, его приоритет повысится. Эта эвристика имеет тенденцию создавать больше свободы для планировщика.

Порядок фаз

Планирование команд может выполняться либо до, либо после выделения регистров, либо до и после него. Преимущество выполнения этого перед распределением регистров состоит в том, что это приводит к максимальному параллелизму. Недостаток выполнения этого до распределения регистров состоит в том, что это может привести к тому, что распределителю регистров потребуется использовать количество регистров, превышающее доступное. Это приведет к появлению кода разлива / заполнения, что снизит производительность рассматриваемого участка кода.

Если в планируемой архитектуре есть последовательности команд, которые имеют потенциально недопустимые комбинации (из-за отсутствия блокировок команд), команды должны быть запланированы после выделения регистров. Этот второй проход планирования также улучшит размещение кода разлива / заполнения.

Если планирование выполняется только после распределения регистров, тогда будут возникать ложные зависимости, вносимые распределением регистров, которые ограничивают количество перемещений инструкций, возможное для планировщика.

Типы

Существует несколько типов планирования инструкций:

Локальное (базовое) планирование: инструкции не могут перемещаться через границы базового блока.
Глобальное планирование: инструкции могут перемещаться через границы базового блока.
Планирование по модулю: алгоритм для генерации программной конвейерной обработки, который является способом повышения параллелизма на уровне команд путем чередования различных итераций внутреннего цикла .
Планирование трассировки : первый практический подход к глобальному планированию, планирование трассировки пытается оптимизировать путь потока управления, который выполняется наиболее часто.
Планирование суперблоков: упрощенная форма планирования трассировки, которая не выполняет попытка объединить пути потока управления на «боковых входах» трассы. Вместо этого код может быть реализован с помощью более чем одного расписания, что значительно упрощает генератор кода.

Примеры компиляторов

Коллекция компиляторов GNU - это компилятор, который, как известно, выполняет планирование инструкций с использованием -march(набор инструкций и планирование) или -mtune(только планирование) флаги. Он использует описания задержек выполнения инструкций и то, какие инструкции могут выполняться параллельно (или, что эквивалентно, какой «порт» каждый использует) для каждой микроархитектуры для выполнения задачи. Эта функция доступна почти для всех архитектур, поддерживаемых GCC.

До версии 12.0.0 планирование инструкций в LLVM / Clang могло принимать только -march( называется target-cpuна языке LLVM) как для набора команд, так и для планирования. Версия 12 добавляет поддержку -mtune(tune-cpu) только для x86.

Источники информации о задержке и использовании портов включают:

GCC и LLVM ;
Агнер Фог, который собирает обширные данные для архитектуры x86 ;
InstLatx64, который использует AIDA64 для сбора данных о процессорах x86.

LLVM llvm -exegesisдолжен использоваться на всех машинах, особенно для сбора информации на машинах, отличных от x86.

См. также

Ссылки

Дополнительная литература

Фишер, Джозеф А. (1981). «Планирование трассировки: метод глобального уплотнения микрокода». Транзакции IEEE на компьютерах. 30 (7): 478–490. doi : 10.1109 / TC.1981.1675827.(Планирование трассировки )
Николау, Александру; Фишер, Джозеф А. (1984). «Измерение параллелизма, доступного для архитектур с очень длинными инструкциями». Транзакции IEEE на компьютерах. 33(11).(Планирование перколяции)
Бернштейн, Дэвид; Родех, Майкл (июнь 1991). «Глобальное планирование инструкций для суперскалярных машин» (PDF). Материалы конференции ACM, SIGPLAN '91 по проектированию и реализации языков программирования. (Глобальное планирование)
Кордес, Питер. «сборка - переупорядочивание инструкций в x86 / x64 asm - оптимизация производительности с новейшими процессорами». Переполнение стека.