Содержание к диссертации
Введение 7
1 Потоки команд в вычислительных процессах как объект
исследования 11
Математические модели для оптимизации потока команд . . 13
Алгоритмы для оптимизации потока команд 17
Списочный алгоритм оптимизации потока команд . . 17
Эвристики используемые списочным алгоритмом . . 19
Существующие расширения списочного алгоритма . . 20
Стохастические алгоритмы 22
Оптимизация с помощью целочисленного линейного программирования 24
Проблемы локальной оптимизации потока команд 25
Выводы 26
2 Построение математической модели вычислительных про
цессов в базовых блоках для решения задач оптимизации
потока команд 28
Задачи оптимизации потока команд 28
Основные особенности целевой архитектуры 28
Анализ существующих математических моделей вычислительных процессов в базовых блоках 29
Разреженная модель вычислительных процессов в базовых блоках 32
Расписания команд для разреженной модели базовых блоков 36
Свойства разреженной модели базовых блоков 38
Избыточные вершины-задержки 39
Избыточные зависимости между вершинахми 40
Делимость графа на несколько независимых подграфов 41
Делимость графа на несколько зависимых подграфов 42
2.7 Выводы 43
3 Применение разреженной модели базовых блоков 44
3.1 Моделирование распространенных архитектур с помощью
разреженной модели базовых блоков 44
Моделирование зависимостей по данным между командами 44
Моделирование команд, занимающих несколько тактов конвейера 46
Моделирование команд с ограниченным временем жизни результата выполнения 47
Моделирование неустранимых задержек в командах перехода 48
Моделирование зависимостей по данным между базовыми блоками 49
3.2 Преобразования графа, упрощающие его структуру 50
Объединение узлов 50
Объединение ребер 53
Линеаризация подграфов-регионов с единственным входом и выходом 54
Линеаризация подграфов-регионов с побочными входами и выходами 60
3.3 Алгоритмы оптимизации потока команд 63
Списочный алгоритм оптимизации потока команд . . 63
Оптимизационные эвристики бб
Подходы, применяемые для получения оптимального расписания 68
Алгоритм поиска оптимального расписания команд, использующий разреженную модель базовых блоков . 69
Методика оптимизации 77
Выводы 80
4 Исследование разреженной модели базовых блоков 83
Описание предлагаемого алгоритма построения расписания . 83
Программный комплекс для моделирования работы алгоритмов поиска расписания на разреженной модели базовых блоков 86
Исследование разреженной модели для архитектур с жесткими связями между командами 87
Способ создания случайных графов 88
Метод измерения параметров графов 89
Результаты сравнения алгоритмов поиска расписаний 90
Исследование вычислительной сложности предлагаемого алгоритма 93
Выводы 97
4.4 Исследование разреженной модели для архитектур без жест
ких связей между командами 97
Исследование разреженной модели с использованием графов, сгенерированных случайным образом .... 98
Способ создания случайных графов 98
Метод измерения параметров графов 100
Результат сравнения списочного алгоритма с предлагаемым алгоритмом поиска расписания 100
Применение разреженной модели для архитектуры с максимальной длиной зависимости по данным, равной одному такту 105
Применение разреженной модели для архитектуры с максимальной длиной зависимости по данным, равной двум тактам 106
Выводы 110
Рекомендации по применению алгоритма ДП в компиляторе 111
Особенности реализации предлагаемого алгоритма построения расписания 112
Выводы 114
Заключение 117
Литература 220
Введение к работе
Практически все производимые в настоящее время процессоры имеют конвейерную архитектуру (в том числе и процессоры от Intel, AMD, Atmel, Samsung). Следовательно, оптимизация потока команд компилятором имеет большое значение в настоящие дни [27]. Значение данной технологии будет все более возрастать в будущем при увеличении количества функциональных блоков в процессорах.
Конвейеризация это один из наиболее эффективных способов увеличения производительности процессоров. Производительность кода при таком подходе увеличивается за счет того, что в один и тот же момент времени одновременно работают несколько узлов процессора, выполняющие разные фазы команд, поступивших в конвейер.
Определение порядка, в котором будут выполняться команды, является основной задачей компилятора на фазе конвейерной оптимизации. Выбранный порядок выполнения команд не должен нарушать зависимостей, существующих между командами. При этом результирующее время выполнения программы должно быть минимизировано.
В связи с вышеизложенным, целью диссертационной работы является является увеличение быстродействия программ за счет их конвейерной оптимизации компилятором. Под конвейерной оптимизацией понимается оптимизация потоков команд за счет их переупорядочения.
Для описания потока команд в настоящее время используется следую-
щая графовая модель. Каждая инструкция в такой модели представляется в виде узла графа, а зависимости между инструкциями — в виде направленных ребер. Для описания такого параметра, как количество тактов, которое должно пройти между двумя командами, используются пометки в виде чисел на ребрах графа.
Данная модель обладает существенными недостатками, не позволяющими решать задачи оптимизации в архитектурах, имеющих следующие особенности конвейера:
Отсутствие сброса конвейера при выполнении перехода
Наличие команд, занимающих несколько тактов конвейера
Наличие жестких связей по времени между командами
Несмотря на то, что большинство архитектур имеют хотя бы одну из перечисленных особенностей, до сих пор не существует модели, которая бы учитывала их все.
В соответствии с целью исследования были поставлены следующие конкретные задачи:
Изучение известных математических моделей и разработка новой модели, наилучшим образом подходящей для оптимизации потока команд для архитектур с вышеперечисленными особенностями.
Исследование свойств модели, позволяющих осуществить оптимизацию.
Разработка алгоритмов оптимизации, решающих поставленную задачу.
Разработка методики оптимизации для более эффективного применения алгоритмов.
Проверка разработанной модели и алгоритмов на практике.
В качестве критерия оптимальности рассматривается длина полученного расписания в тактах конвейера. Оптимальным является расписание с наименьшей длиной, среди всех возможных корректных расписаний.
Модель в первую очередь должна быть предназначена для наиболее распространенных архитектур с одним конвейером. Это означает, что в каждый момент на конвейер может поступать только одна инструкция, причем частота поступления не меняется в процессе работы.
В первой главе предлагаемого исследования проведен анализ существующих математических моделей вычислительных процессов в базовых блоках, рассмотрены их достоинства и недостатки. Кроме того, рассмотрены известные подходы и алгоритмы оптимизации потока команд. Исходя из этого, определяются требования к разрабатываемой модели и алгоритму оптимизации.
Во второй главе строится математическая модель вычислительного процесса в базовом блоке, названная разреженной моделью. Кроме того, рассматриваются основные свойства полученной модели, а также вопросы ее применения для поиска расписаний команд.
В третьей главе рассматривается моделирование различных аппаратных платформ с помощью разреженной модели, а также доказывается ряд
свойств, ориентированных на решение вопросов оптимизации потока команд. Также в главе предложен алгоритм поиска оптимального расписания, использующий динамическое программирование, доказана его применимость к разреженной модели, а также то, что он всегда находит оптимальный результат. Кроме того было исследовано поведение алгоритма на графах с различной структурой и предложена методика оптимизации, использующая данный алгоритм.
В четвертой главе представлены результаты моделирования работы предложенного в третьей главе алгоритма с использованием динамического программирования, а также ранее известных алгоритмов. Работа алгоритмов опробована на двух наборах графов, сгенерированных случайным образом, и имитирующих две различных архитектуры, а также на графах, полученных из реальных программ.
