Исследование разреженной модели базовых блоков для оптимизации потока команд вычислительного конвейера

• Автор: Довгалюк, Павел Михайлович
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2007
• Место защиты: Великий Новгород
• Количество страниц: 130 с. : ил.

Оглавление
Введение

1 Потоки команд в вычислительных процессах как объект исследования

1.1 Математические модели для оптимизации потока команд . .

1.2 Алгоритмы для оптимизации потока команд

1.2.1 Списочный алгоритм оптимизации потока команд . .

1.2.2 Эвристики используемые списочным алгоритмом . .

1.2.3 Существующие расширения списочного алгоритма . .

1.2.4 Стохастические алгоритмы

1.2.5 Оптимизация с помощью целочисленного линейного

программирования

1.3 Проблемы локальной оптимизации потока команд.
1.4 Выводы.
2 Построение математической модели вычислительных процессов в базовых блоках для решения задач оптимизации потока команд
2.1 Задачи оптимизации потока команд.
2.2 Основные особенности целевой архитектуры.
2.3 Анализ существующих математических моделей вычислительных процессов в базовых блоках.
2.4 Разреженная модель вычислительных процессов в базовых блоках.
2.5 Расписания команд для разреженной модели базовых блоков
2.6 Свойства разреженной модели базовых блоков.
2.6.1 Избыточные вершинызадержки
2.6.2 Избыточные зависимости между вершинами
2.6.3 Делимость графа на несколько независимых подграфов
2.6.4 Делимость графа на несколько зависимых подграфов
2.7 Выводы.
3 Применение разреженной модели базовых блоков
3.1 Моделирование распространенных архитектур с помощью
разреженной модели базовых блоков
3.1.1 Моделирование зависимостей по данным между командами .
3.1.2 Моделирование команд, занимающих несколько тактов конвейера
3.1.3 Моделирование команд с ограниченным временем
жизни результата выполнения .
3.1.4 Моделирование неустранимых задержек в командах
перехода.
3.1.5 Моделирование зависимостей по данным между базовыми блоками.
3.2 Преобразования графа, упрощающие его структуру
3.2.1 Объединение узлов
3.2.2 Объединение ребер
3.2.3 Линеаризация подграфоврегионов с единственным
входом и выходом .
3.2.4 Линеаризация подграфоврегионов с побочными входами и выходами
3.3 Алгоритмы оптимизации потока команд.
3.3.1 Списочный алгоритм оптимизации потока команд . .
3.3.2 Оптимизационные эвристики
3.3.3 Подходы, применяемые для получения оптимального
расписания
3.3.4 Алгоритм поиска оптимального расписания команд,
использующий разреженную модель базовых блоков .
3.4 Методика оптимизации .
3.5 Выводы
Исследование разреженной модели базовых блоков
4.1 Описание предлагаемого алгоритма построения расписания .
4.2 Программный комплекс для моделирования работы алгоритмов поиска расписания на разреженной модели базовых блоков
4.3 Исследование разреженной модели для архитектур с жесткими связями между командами.
4.3.1 Способ создания случайных графов.
4.3.2 Метод измерения параметров графов
4.3.3 Результаты сравнения алгоритмов поиска расписаний
4.3.4 Исследование вычислительной сложности предлагаемого алгоритма
4.3.5 Выводы.
4.4 Исследование разреженной модели для архитектур без жестких связей между командами.
4.4.1 Исследование разреженной модели с использованием графов, сгенерированных случайным образом
4.4.2 Способ создания случайных графов.
4.4.3 Метод измерения параметров графов
4.4.4 Результат сравнения списочного алгоритма с предлагаемым алгоритмом поиска расписания.
4.4.5 Применение разреженной модели для архитектуры с максимальной длиной зависимости но данным, равной одному такту.
4.4.6 Применение разреженной модели для архитектуры с максимальной длиной зависимости по данным, равной двум тактам.
4.4.7 Выводы
4.5 Рекомендации по применению алгоритма ДП в компиляторе
4.6 Особенности реализации предлагаемого алгоритма построения расписания
4.7 Выводы
Заключение
Литература


В связи с вышеизложенным, целыо диссертационной работы является является увеличение быстродействия программ за счет их конвейерной оптимизации компилятором. Под конвейерной оптимизацией понимается оптимизация потоков команд за счет их переупорядочения. Каждая инструкция в такой модели представляется в виде узла графа, а зависимости между инструкциями в виде направленных ребер. Для описания такого параметра, как количество тактов, которое должно пройти между двумя командами, используются пометки в виде чисел на ребрах графа. Несмотря на то, что большинство архитектур имеют хотя бы одну из перечисленных особенностей, до сих пор не существует модели, которая бы учитывала их все. Изучение известных математических моделей и разработка новой модели, наилучшим образом подходящей для оптимизации потока команд для архитектур с вышеперечисленными особенностями. Исследование свойств модели, позволяющих осуществить оптимизацию. Разработка алгоритмов оптимизации, решающих поставленную задачу. Разработка методики оптимизации для более эффективного применения алгоритмов. Проверка разработанной модели и алгоритмов на практике. В качестве критерия оптимальности рассматривается длина полученного расписания в тактах конвейера. Оптимальным является расписание с наименьшей длиной, среди всех возможных корректных расписаний. Модель в первую очередь должна быть предназначена для наиболее распространенных архитектур с одним конвейером. Это означает, что в каждый момент на конвейер может поступать только одна инструкция, причем частота поступления не меняется в процессе работы. В первой главе предлагаемого исследования проведен анализ существующих математических моделей вычислительных процессов в базовых блоках, рассмотрены их достоинства и недостатки. Кроме того, рассмотрены известные подходы и алгоритмы оптимизации потока команд. Исходя из этого, определяются требования к разрабатываемой модели и алгоритму оптимизации. Во второй главе строится математическая модель вычислительного процесса в базовом блоке, названная разреженной моделью. Кроме того, рассматриваются основные свойства полученной модели, а также вопросы ее применения для поиска расписаний команд. Также в главе предложен алгоритм поиска оптимального расписания, использующий динамическое программирование, доказана его применимость к разреженной модели, а также то, что он всегда находит оптимальный результат. Кроме того было исследовано поведение алгоритма на графах с различной структурой и предложена методика оптимизации, использующая данный алгоритм. В четвертой главе представлены результаты моделирования работы предложенного в третьей главе алгоритма с использованием динамического программирования, а также ранее известных алгоритмов. Работа алгоритмов опробована на двух наборах графов, сгенерированных случайным образом, и имитирующих две различных архитектуры, а также на графах, полученных из реальных программ. В настоящее время практически все производимые процессоры имеют конвейерную архитектуру. Конвейеризация позволяет более эффективно использовать узлы процессоров за счет их одновременного выполнения ими различных фаз команд параллелизм на уровне инструкций , . Классическая конвейерная теория была разработана в контексте однопроцессорных и векторных архитектур 5, , , . С тех пор архитектуры компьютеров проделали огромный путь развития в сторону сильно конвейеризированных архитектур, что привело к увеличению параллелизма на уровне инструкций. Одновременно развивались и технологии компиляции, такие как программная конвейеризация, которая увеличивает степень параллельности на уровне инструкций для готовой программы 2, 3, 4, , , . В настоящее время широкое распространение получили ШЭСироцсссоры, ставшие развитием конвейерных вычислительных машин. Для максимизации скорости выполнения программ в таких процессорах необходимо, чтобы разные фазы процесса исполнения команд выполнятись одновременно. Для достижения иаилучшего эффекта от конвейеризации необходимо соответствующим образом подготовить код программы.