Компиляторы
Оптимизации циклов
Наивная матричная транспозиция 1024x1024 работает 50ms. С loop tiling - 5ms. С tiling + SIMD - 1ms. Тот же алгоритм, та же сложность O(N^2), просто другой порядок обращения к памяти. Оптимизации циклов дают 10-50x ускорение на числодробилках - именно здесь компилятор или программист-оптимизатор работают на полную.
- **GCC Graphite** и **LLVM Polly** - полиэдральные оптимизаторы в production компиляторах. Polly при компиляции BLAS-подобных вычислений даёт 5-20x ускорение через автоматический tiling и parallelization.
- **PyTorch и TensorFlow** компилируют NN operations через TVM или XLA - по сути полиэдральные компиляторы специализированные для tensor операций. FlashAttention через Triton использует тайлинг вручную и превосходит наивный PyTorch Attention на 2-4x.
- **Intel MKL** и **OpenBLAS** - рукописные DGEMM с ручным tiling, SIMD и prefetching. Intel MKL достигает 95%+ теоретического пика FLOPs на Xeon - именно потому что loop trансформации выполнены оптимально для конкретного L1/L2/L3 кеша.
Loop Transformations
Трансформации циклов - класс оптимизаций, изменяющих структуру цикла для улучшения производительности. Ключевые трансформации: interchange (перестановка вложенных циклов), tiling (блочная декомпозиция), fusion (слияние), fission (разделение).
Матричное умножение (DGEMM) - эталонный тест loop tiling. Наивная реализация на 1024x1024 матрицах: ~2 GFLOPS. С loop tiling + SIMD: ~100 GFLOPS (50x). OpenBLAS и Intel MKL применяют вручную оптимизированные тайловые циклы с SIMD. Polly (LLVM) автоматически применяет полиэдральные трансформации и даёт 5-20x ускорение на плотных вычислениях.
Почему loop interchange ускоряет работу с матрицами в C?
Loop Unrolling
Loop unrolling - дублирование тела цикла несколько раз, уменьшая количество итераций и накладные расходы на управление циклом (induction variable update, branch). Открывает возможности для instruction-level parallelism.
Полное unrolling (full unroll) - все итерации раскрываются, цикл исчезает. Применимо только когда количество итераций известно при компиляции и невелико. GCC и Clang автоматически раскрывают циклы до 8-16 итераций. Rust `#[unroll]` proc-macro и `std::hint::unreachable_unchecked()` позволяют программисту явно управлять. Перебор с unrolling ухудшает icache performance.
Какой главный риск агрессивного loop unrolling?
Auto-Vectorization
Auto-vectorization - автоматическое преобразование скалярных операций в SIMD инструкции (SSE, AVX на x86; NEON на ARM). Вместо обработки одного элемента за итерацию - 4, 8 или 16 элементов одновременно.
GCC `-fopt-info-vec-missed` показывает все циклы, которые НЕ векторизовались, и почему. Типичные причины: unknown loop count, data dependency, non-unit stride. NumPy и PyTorch используют SIMD через ручные интринсики или через Eigen/xtensor. LLVM Loop Vectorizer работает на IR-уровне и поддерживает interleaved access patterns, masked vectorization (для цикла с условием), и SLP (superword-level parallelism) для не-цикловых операций.
Что мешает векторизации цикла `for (i..n) c[i] = c[i-1] + a[i]`?
Polyhedral Model
Полиэдральная модель (polyhedral model) - математический фреймворк для анализа и трансформации вложенных циклов. Пространство итераций цикла представляется как многогранник (polyhedron), а трансформации - как линейные отображения этого пространства.
TVM (Apache) и Triton (OpenAI) используют полиэдральный подход для генерации эффективных GPU kernel'ов для нейросетей. Triton позволяет писать kernel в Python-подобном синтаксисе, а компилятор автоматически применяет tiling, vectorization и memory coalescing. FlashAttention v2 - реализован на Triton и 2-4x быстрее стандартного PyTorch attention благодаря агрессивному tiling.
Что представляет полиэдр в полиэдральной модели циклов?
Ключевые идеи
- **Loop interchange** меняет порядок вложенных циклов для cache-friendly доступа. Row-major vs column-major - разница в 10-100x на больших матрицах.
- **Loop unrolling** раскрывает тело цикла для уменьшения overhead и открытия ILP. Риск: code bloat и промахи в icache.
- **Auto-vectorization** заменяет скалярные операции на SIMD: 4-16 элементов за итерацию. Требует: нет loop-carried dependency, нет aliasing.
- **Полиэдральная модель** формализует трансформации циклов как линейные отображения пространства итераций. Основа Polly, TVM, Triton.
Связанные темы
Оптимизации циклов - ядро высокопроизводительных вычислений:
- Глобальные оптимизации — LICM - первая loop optimization; dataflow analysis используется для обнаружения loop-carried dependencies
- Выбор инструкций — Векторизованный код требует особого instruction selection для SIMD инструкций
- Планирование инструкций — После unrolling планировщик скрывает latency через reordering инструкций из разных итераций
Вопросы для размышления
- Optimal block size для loop tiling зависит от размера L1/L2 кеша. Как автоматический оптимизатор (Polly, GCC Graphite) узнаёт размер кеша - и что происходит при компиляции cross-platform?
- GPU имеет иную иерархию памяти чем CPU (shared memory, warp execution). Применимы ли те же loop трансформации (tiling, interchange) к GPU kernel'ам - или нужны другие подходы?
- Предикатный SIMD (AVX-512 masked operations) позволяет векторизовать циклы с условием внутри. Как компилятор генерирует маску предикатов из if-условия в теле цикла?