Оптимизирующие преобразования программ (183,00 руб.)

Стр.3

Стр.4

Стр.5

УДК 004.415.3:519.681.3(075.8) ББК 32.972.11+32.971.32-043я73 Ш88 Института математики, механики и компьютерных наук им. И. И. Воровича Южного федерального университета (протокол № 1 от 11 января 2025 г.) Печатается по решению кафедры алгебры и дискретной математики Рецензенты: Российской таможенной академии, доктор физико-математических наук, доцент О. Е. Кудрявцев; заведующий кафедрой информатики и информационных таможенных технологий Ростовского филиала доцент кафедры информатики и вычислительного эксперимента Южного федерального университета, кандидат физико-математических наук, доцент В. А. Нестеренко Ш88 Штейнберг, Б. Я. Оптимизирующие преобразования программ : учебное пособие / Б. Я. Штейнберг ; Южный федеральный университет. – Ростов-на-Дону ; Таганрог : Издательство Южного федерального университета, 2025. – 122 с. ISBN 978-5-9275-4947-4 В учебном пособии рассматриваются ускоряющие (оптимизирующие и распараллеливающие) преобразования программ. Представленные преобразования иллюстрируются многочисленными примерами преобразований программ языка С. Тематика предлагаемого материала актуальна, поскольку популярные промышленные оптимизирующие компиляторы плохо оптимизируют код. Разрабатываемые программы зачастую используют около 1 % пиковой производительности процессора – это притом, что быстродействие во многих приложениях имеет существенное значение. По этой тематике издано много книг и обзорных статей, часть из которых представлена в списке литературы. Данное учебное пособие отличается строгостью формулировок и обоснований представленных преобразований, основное внимание уделяется преобразованиям циклов. Предназначено для студентов направлений подготовки «Прикладная математика и информатика» и «Фундаментальная информатика и информационные технологии». ISBN 978-5-9275-4947-4 УДК 004.415.3:519.681.3(075.8) ББК 32.972.11+32.971.32-043я73 2 © Южный федеральный университет, 2025 © Штейнберг Б. Я., 2025 © Оформление. Макет. Издательство Южного федерального университета, 2025

Стр.3

ОГЛАВЛЕНИЕ ВВЕДЕНИЕ ................................................................................................................................ 5 1. СВЕДЕНИЯ ИЗ ТЕОРИИ ГРАФОВ ............................................................................ 7 2. ПРЕОБРАЗОВАНИЯ ПРОГРАММ ............................................................................ 9 2.1. Программные зависимости и базовые преобразования ...................... 9 2.1.1. Модель рассматриваемых программ .................................................. 9 2.1.2. Управляющий граф программы ...........................................................10 2.1.3. Информационная зависимость и граф информационных связей .....................................................................15 2.1.4. Граф зависимостей по данным ............................................................21 2.1.5. Решётчатый граф программы ...............................................................21 2.2. Базовые преобразования программ .............................................................23 2.2.1. Базовые понятия о преобразованиях программ ........................23 2.2.2. Пустой оператор. Удаление и вставка операторов ....................24 2.2.3. Удаление мёртвого кода. Поиск и удаление недостижимых и неиспользуемых по управлению операторов .....28 2.2.4. Удаление оператора (заголовка) цикла ...........................................29 2.2.5. Удаление условных операторов ..........................................................32 2.2.6. Приведение выражения к стандартному виду («приведение подобных») ..................................................................................33 2.3. Преобразования линейных участков программы ..................................35 2.3.1. Перестановка фрагментов (блоков) программы .........................35 2.3.2. Подстановка вперёд ..................................................................................43 2.3.3. Вынос вычисления выражений и замена общих подвыражений ..........................................................................................48 2.4. Преобразования циклов .....................................................................................51 2.4.1. Раскрутка цикла ...........................................................................................51 2.4.2. Канонизация циклов .................................................................................55 2.4.3. Перестановка блоков в цикле ..............................................................56 2.4.4. Расщепление цикла ...................................................................................57 2.4.5. Разрыв итераций, гнездование цикла и подобные им преобразования ...............................................................................................59 3

Стр.4

2.4.6. Развёртка цикла ...........................................................................................63 2.4.7. Расщепление вершин (Введение временных массивов)..........65 2.4.8. Растягивание скаляров и расширение массива ...........................66 2.4.9. Разбиение цикла .........................................................................................69 2.4.10. Приведение цикла к разбиваемому виду .....................................73 2.4.11. Использование перестановки операторов для разбиения цикла ............................................................................................73 2.4.12. Использование расщепления вершин для разбиения цикла ............................................................................................76 2.4.13. Повышение размерности массивов для разбиения циклов .........................................................................................78 2.4.14. Слияние циклов ........................................................................................79 2.4.15. Инверсия цикла ........................................................................................82 2.4.16. Вынос оператора из цикла .................................................................85 2.4.17. Индуктивные и охватывающие переменные в цикле .............90 2.5. Преобразования неканонических циклов .................................................95 2.5.1. Сдвиги границ циклов ..............................................................................96 2.5.2. Расщепление с перестановкой .............................................................96 2.6. Преобразования функций ..................................................................................97 2.6.1. Инлайнинг ......................................................................................................97 2.6.2. Уменьшение количества параметров функции ............................97 3. РАСПАРАЛЛЕЛИВАНИЕ .............................................................................................99 3.1. Параллельные процессы ....................................................................................99 3.2. Параллельные вычислительные архитектуры .........................................99 3.3. Виды распараллеливания программ ......................................................... 101 3.4. Распараллеливание циклов на архитектуру SIMD ............................... 102 3.5. Распараллеливание конкатенации блоков на архитектуру MIMD ......................................................................................... 107 3.6. Распараллеливание циклов на архитектуру MIMD ............................. 108 3.7. Асинхронное распараллеливание циклов с зависимыми итерациями ............................................................................. 111 3.8. Ошибочные представления о распараллеливании ............................ 114 4. ПРИМЕРЫ КОНТРОЛЬНЫХ ЗАДАНИЙ .......................................................... 117 4.1. Пример контрольного задания на построение графа информационных связей ................................................................................. 117 4.2. Пример тестовых вопросов по преобразованиям программ ........ 118 ЛИТЕРАТУРА ...................................................................................................................... 120 4

Стр.5