Компиляторы
Планирование инструкций
LOAD из L1 кеша занимает 4 такта. Если следующая инструкция использует загруженные данные - 3 такта простоя. Умный планировщик вставляет независимые инструкции в этот пробел - и программа становится быстрее без изменения алгоритма. На in-order CPU (ARM Cortex-M) это разница между 6 и 2 тактами на итерацию.
- **Apple M1/M2** имеет ROB на 630 entries против 224 у Intel Skylake. Это позволяет скрывать latency memory access 100-300 тактов (L3 cache miss), выполняя другие вычисления. Benchmarks показывают M1 особенно эффективен на workloads с нерегулярными паттернами памяти.
- **GCC `sched.cc`** - 6000 строк планировщика с поддержкой list scheduling, modulo scheduling для циклов, и speculative scheduling. Содержит модели латентностей для 50+ архитектур.
- **Intel Itanium** (EPIC архитектура) был полностью in-order VLIW: компилятор должен был явно указать параллельные инструкции через bundle slots. ICC (Intel C Compiler) для Itanium достигал 95% пика FLOPS - нереальный результат для универсального компилятора.
Pipeline Hazards
Процессорный конвейер выполняет несколько инструкций одновременно на разных стадиях. Pipeline hazard - ситуация, когда следующая инструкция не может начаться сразу из-за зависимости от результата предыдущей. Это вызывает stall (остановку конвейера) - потерянные такты.
Современные x86 процессоры (Intel Skylake+) реализуют out-of-order execution с 200+ entry reorder buffer - процессор сам переставляет инструкции при выполнении. Но компилятор всё равно планирует: хорошо запланированный код оставляет меньше работы для OOO, что снижает энергопотребление и улучшает предсказуемость производительности. На in-order CPU (ARM Cortex-M, embedded) планирование компилятора критично.
Что такое RAW hazard?
Instruction Reordering
Instruction scheduling - перестановка инструкций для скрытия latency. Если LOAD занимает 4 такта, можно выполнить 4 независимые инструкции пока ждём результата. Планировщик строит DAG зависимостей и топологически сортирует с учётом latency.
GCC использует `sched.cc` - 6000-строчный планировщик с моделями латентностей для каждой архитектуры. LLVM - `MachineScheduler.cpp`. Латентности берутся из machine description (`SchedModel` в `.td` файлах). Для ARM Cortex-A72 в LLVM это `AArch64SchedA72.td` - 2000 строк описания latency каждой инструкции для каждого execution port.
Почему планировщик переставляет LOAD инструкции в начало блока?
Software Pipelining
Software pipelining - трансформация цикла, при которой инструкции из разных итераций перекрываются во времени. Это позволяет скрыть latency через перекрытие цикла с собственным следующим витком - аналог конвейера, но на уровне программы.
Software pipelining особенно важен для VLIW (Very Long Instruction Word) архитектур где нет аппаратного OOO. Intel Itanium (IA-64) был VLIW процессором и полностью зависел от компилятора (Intel ICC) для пайплайнинга. Модуло-планирование (modulo scheduling) - алгоритм software pipelining для циклов: находит минимальный initiation interval (II) такой что все зависимости удовлетворены.
Что такое initiation interval (II) в software pipelining?
Out-of-Order и Superscalar
Out-of-Order (OOO) execution - процессор сам переставляет инструкции во время выполнения, используя hardware переименование регистров и reorder buffer (ROB). Superscalar - несколько instruction decode/execute units работают параллельно. Оба механизма скрывают latency аппаратно.
Apple M1/M2 имеют ROB на 630 entries (Skylake: 224) - больший буфер позволяет скрывать большую latency. Это одна из причин исключительной производительности M1 при L2/L3 cache miss (100+ тактов): M1 может запустить сотни инструкций пока ждёт памяти. Компилятор, знающий модель OOO процессора, может генерировать код, лучше использующий параллелизм - LLVM использует `SchedMachineModel` с информацией о портах.
Что даёт register renaming в OOO процессоре?
Итоги
- **Pipeline hazards** (RAW, WAR, WAW) вызывают stall. RAW самый частый: читаем регистр до того как предыдущая инструкция записала его.
- **List scheduling** - жадный топологический обход DAG зависимостей с приоритетом по critical path. Скрывает latency inserting independent instructions.
- **Software pipelining** перекрывает итерации цикла: LOAD для итерации i+1 выполняется пока вычисляется итерация i. Даёт 2-4x ускорение на in-order CPU.
- **OOO + superscalar** скрывают hazards аппаратно. Register renaming устраняет WAR/WAW. Компилятор всё равно планирует - для энергоэффективности и in-order CPU.
Связанные темы
Планирование инструкций - последняя оптимизационная фаза перед выводом asm:
- Выбор инструкций — Планировщик работает после instruction selection - переставляет уже выбранные машинные инструкции
- Целевые архитектуры — Латентности и execution ports зависят от целевой архитектуры - планировщик использует machine model
- Оптимизации циклов — Software pipelining - частный случай loop optimization и instruction scheduling вместе
Вопросы для размышления
- Skylake имеет 8 execution ports. Оптимальный код должен равномерно загружать все порты. Как компилятор знает, какие инструкции идут на какой порт - и может ли код вообще достичь теоретического пика?
- Software pipelining требует prologue и epilogue для 'раскрутки' и 'доделки' цикла. Если N (число итераций) мало - overhead превышает выигрыш. Как компилятор решает применять ли software pipelining?
- Современные CPU предсказывают ветвления с точностью >99%. Как это взаимодействует с instruction scheduling - нужно ли планировать код в обеих ветках отдельно или как единый поток?