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

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

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

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

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

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

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

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

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

Алгоритмы

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

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

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

Порядок фаз

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

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

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

Типы

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

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

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

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

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

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

LLVM llvm-экзегезис должен быть доступен на всех машинах, особенно для сбора информации на машинах, отличных от x86.[6]

Смотрите также

Рекомендации

  1. ^ Су, Цзин-Лун; Цуй, Чи-Инь; Despain, Элвин М. (1994). Методы проектирования и компиляции архитектуры с низким энергопотреблением для высокопроизводительных процессоров (PDF) (Отчет). Лаборатория продвинутой компьютерной архитектуры. ACAL-TR-94-01. (Холодное планирование)
  2. ^ «Параметры x86». Использование коллекции компиляторов GNU (GCC).
  3. ^ «⚙ D85384 [X86] Добавить базовую поддержку параметра командной строки -mtune в clang». reviews.llvm.org.
  4. ^ «Ресурсы по оптимизации программного обеспечения. C ++ и сборка. Windows, Linux, BSD, Mac OS X». Агнер Туман.
  5. ^ «Дампы задержки выполнения инструкций x86, x64, задержки памяти и CPUID». instlatx64.atw.hu. См. Также ссылку «Комментарии» на странице.
  6. ^ "llvm-exegesis - тест машинных инструкций LLVM". Документация по LLVM 12.

дальнейшее чтение