В информатике планирование инструкций — это оптимизация компилятора , используемая для улучшения параллелизма на уровне инструкций , что повышает производительность на машинах с конвейерами команд . Проще говоря, он пытается сделать следующее, не меняя смысла кода:
Остановки конвейера могут быть вызваны структурными опасностями (ограничение ресурсов процессора), опасностями данных (выходные данные одной инструкции необходимы для другой инструкции) и опасностями управления (ветвление).
Планирование инструкций обычно выполняется в одном базовом блоке . Чтобы определить, сохраняет ли перестановка инструкций блока определенным образом поведение этого блока, нам нужна концепция зависимости данных . Существует три типа зависимостей, которые также являются тремя опасностями для данных :
Технически существует четвертый тип: «Чтение после чтения» (RAR или «Ввод»): обе инструкции считываются из одного и того же места. Входная зависимость не ограничивает порядок выполнения двух операторов, но полезна при скалярной замене элементов массива.
Чтобы убедиться, что мы соблюдаем три типа зависимостей, мы строим граф зависимостей, который представляет собой ориентированный граф , в котором каждая вершина является инструкцией и существует ребро от I 1 до I 2 , если I 1 должно предшествовать I 2 из-за зависимость. Если зависимости, переносимые циклом, не учитываются, граф зависимостей представляет собой ориентированный ациклический граф . Тогда любой топологический вид этого графа является допустимым расписанием команд. На краях графика обычно указывается задержка зависимости. Это количество тактов, которое должно пройти, прежде чем конвейер сможет продолжить выполнение целевой инструкции без остановки.
Часто используется простейший алгоритм топологической сортировки, известный как планирование списков . Концептуально, он неоднократно выбирает источник графа зависимостей, добавляет его к текущему расписанию инструкций и удаляет из графа. Это может привести к тому, что другие вершины станут источниками, которые затем также будут учитываться при планировании. Алгоритм завершает работу, если граф пуст.
Чтобы прийти к хорошему графику, следует избегать застоев. Это определяется выбором следующей запланированной инструкции. Обычно используется ряд эвристик:
Планирование инструкций может выполняться либо до, либо после распределения регистров , либо до и после него. Преимущество выполнения этого перед выделением регистров состоит в том, что это приводит к максимальному параллелизму. Недостаток выполнения этого до выделения регистров заключается в том, что это может привести к тому, что распределителю регистров придется использовать количество регистров, превышающее доступное. Это приведет к введению кода заполнения/заполнения, что снизит производительность рассматриваемого раздела кода.
Если планируемая архитектура имеет последовательности команд, которые имеют потенциально недопустимые комбинации (из-за отсутствия взаимоблокировок инструкций), инструкции должны быть запланированы после выделения регистров. Этот второй этап планирования также улучшит размещение кода разлива/заполнения.
Если планирование выполняется только после выделения регистров, то при выделении регистров будут возникать ложные зависимости, которые будут ограничивать количество операций, возможных для планировщика.
Существует несколько типов планирования инструкций:
Коллекция компиляторов GNU — это один из компиляторов, который, как известно, выполняет планирование инструкций с использованием флагов -march
(как набора команд, так и планирования) или -mtune
(только планирования). Он использует описания задержек инструкций и того, какие инструкции могут выполняться параллельно (или, что эквивалентно, какой «порт» каждая использует) для каждой микроархитектуры для выполнения задачи. Эта функция доступна практически для всех архитектур, поддерживаемых GCC. [2]
До версии 12.0.0 планирование инструкций в LLVM /Clang могло принимать только переключатель -march
(называемый target-cpu
на языке LLVM) как для набора команд, так и для планирования. В версии 12 добавлена поддержка -mtune
( tune-cpu
) только для x86. [3]
Источники информации о задержке и использовании портов включают:
LLVM llvm-exegesis
следует использовать на всех машинах, особенно для сбора информации на машинах, отличных от x86. [6]