Оглавление секции
-
Раздел 1. Блочные вычисления
Тема 1.1. Оптимизация использования структуры памяти
Блочное перемножение матриц. Зависимость времени выполнения простых программ от соотношения времени вычислений ко времени обращений к памяти. Множественная сортировка. Неэффективность алгоритма Штрассена.
Тема 1.2. Модель времени выполнения программы на вычислительной системе
Архитектура современных процессоров. Сложность вычислений по обращениям к памяти.
Тема 1.3. Алгоритмы блочных вычислений.
Тайлинг. Решетчатые графы. Косой тайлинг. Слияние циклов для уменьшения кэш-промахов.
Раздел 2. Преобразования программ
Тема 2.1. Графовые модели программ
Управляющий граф программы. Граф вызовов функций. Граф информационных связей. Граф зависимостей по данным.
Тема 2.2. Преобразования линейных участков и циклов
Подстановка. Протягивание констант. Перестановка блоков.
Канонизация цикла. Раскрутка цикла. Развертка цикла. Гнездования цикла. Разбиение цикла. Приведение цикла к разбиваемому виду. Слияние циклов.
Тема 2.3. Распараллеливание циклов
Распараллеливание циклов на архитектуру MIMD.
Распараллеливание циклов на архитектуру SIMD.
Конвейеризация циклов.
Вопросы, выносимые на самостоятельное изучение
Применение преобразований в компиляторах с открытым кодом LLVM, GCC.
Полезные материалы
Учебник по преобразованиям программ
Как из последовательной программы сделать параллельную?
Диалоговый высокоуровневый оптимизирующий распараллеливатель
Быстрые программы = архитектуро-ориентированные алгоритмы и данные
Проблемы создания эффективного параллельного программного обеспечения
Задачи оптимизирующей компиляции для процессоров близкого будущего