Автоматическое отображение программ на конвейерные и многоконвейерные архитектуры

• Автор: Штейнберг, Роман Борисович
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2012
• Место защиты: Ростов-на-Дону
• Количество страниц: 152 с. : ил.

Оглавление
Список сокращений
Введение
1. Теория графов и графовые представления программ
1.1. Необходимые понятия из теории графов
1.2. Информационные зависимости в программах
1.3. Граф информационных связей
1.4. Основные понятия теории решетчатых графов
1.4.1. Элементарные решетчатые графы
1.4.2. Максимальный и минимальный решетчатые графы
1.5. Граф вычислений
1.6. Выводы к первой главе
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.2. Отображение программ на многоконвейерную модель вычислений

3.3. Влияние зависимостей в самом вложенном цикле на задержку в стартах
конвейеров
3.4. Влияние зависимостей между вхождениями самого вложенного цикла и
вхождениями в остальных циклах гнезда на задержку в стартах конвейеров
3.5. Составление расписания для вычисления гнезда циклов
3.6. Формула вычисления задержки в стартах конвейеров для тесного двумерного
гнезда циклов
3.6.1. Постановка задачи
3.6.2. Случай АфО, |2?| Ф
3.6.3. Случай А = О, В Ф
3.6.4. Случай А Ф 0, В
3.6.5. Случай А = 0, В = 0, с +с% *
3.6.6. Случай А = 0, |В| = 0, с,2 + с22
3.7. Выводы к третьей главе
4. Вспомогательные результаты
4.1. Линейная форма представления выражений
4.2. Система тестирования
4.3. Применение автоматического построения графа вычислений к генерации НПЬ-
описаний. Конвертер с языка С в УНОЬ
4.4. Выводы к четвертой главе
Заключение
Приложение
Литература
Список сокращений
АЛУ - арифметико-логическое устройство
БДОП - быстрое дискретное ортогональное преобразование
ДВОР - диалоговый высокоуровневый оптимизирующий распараллеливатель
МВС - многопроцессорная вычислительная система
ОРС - открытая распараллеливающая система
ПЛИС - программируемая логическая интегральная схема
ПО - программное обеспечение
ПЭ - процессорный элемент
РГА - редуцированный граф алгоритма
ЦЛП - целочисленное линейное программирование
DSP - Digital Signal Processor
FPGA - Field Programmable Gate Array
HDL - Hardware Description Language
VBA - Visual Basic for Applications
VLIW - Very Long Instruction Word

1 1 1 1 1 1 1
Рис. 12. Минимальный снизу решетчатый граф для фрагмента программы
Конец примера.
1.5. Граф вычислений.
В данном параграфе будет введено понятие графа вычислений, которое является основой для организации отображения на конвейерные архитектуры в рамках данной диссертации.
Обозначим через ОР - множество операций (чтения данных, записи данных, арифметические операции) некоторого фрагмента программы. Обозначим через ОР(Б) -множество операций (чтения данных, записи данных, арифметические операции) некоторого оператора 5.
Пусть оеОР - операция. Тогда для о можно определить, какому оператору присваивания она принадлежит. Можно определить опорное пространство (см. [14], [18]), порожденное этим оператором. В случае тесного гнезда циклов опорное пространство оператора совпадает с пространством итераций гнезда циклов, в котором он находится. Напомним, что в целях улучшения ясности изложения в этой главе рассматриваются только тесные гнезда циклов, хотя полученные результаты легко обобщаются на случай нетесных гнезд циклов.
Обозначим через Р1(о) опорное пространство операции о.