Оглавление
Введение
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 Выводы
Заключение
Литература
- Київ+380960830922