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

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

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

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

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

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

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

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

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

Алгоритмы

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

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

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

Порядок фаз

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

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

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

Типы

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

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

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

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