Введение
1. Теория графов и графовые представления программ 18
1.1. Необходимые понятия из теории графов 18
1.2. Информационные зависимости в программах 20
1.3. Граф информационных связей 25
1.4. Основные понятия теории решетчатых графов 26
1.4.1. Элементарные решетчатые графы 27
1.4.2. Максимальный и минимальный решетчатые графы 30
1.5. Граф вычислений. 35
1.6. Выводы к первой главе 41
2. Конвейерные вычисления 42
2.1. Конвейерные задержки и интервал инициализации итераций 42
2.2. Вспомогательные утверждения 44
2.3. Алгоритм поиска множества всех элементарных циклов, содержащих данную обратную дугу 47
2.4. Алгоритм вычисления интервала инициализации итераций 49
2.5. Полиномиальный алгоритм вычисления интервала инициализации итераций 53
2.6. Составление расписания для организации конвейерных вычислений одномерного цикла 56
2.6.1. Примеры составления расписания для конвейерных вычислений 56
2.6.2. Вспомогательный алгоритм составления расписания и вычисления буферных задержек на подграфе графа вычислений, который содержит один источник и не содержит обратных дуг 60
2.6.3. Склеивание двух подграфов с рассчитанными расписаниями (вспомогательный алгоритм) 63
2.6.4. Алгоритм составления расписания и вычисления буферных задержек на дугах графа вычислений 67
2.7. Выводы ко второй главе 71
3. Многоконвейерные вычисления 73
3.1. Многоконвейерная модель вычислений 73
3.2. Отображение программ на многоконвейерную модель вычислений 77
3.3. Влияние зависимостей в самом вложенном цикле на задержку в стартах конвейеров 81
3.4. Влияние зависимостей между вхождениями самого вложенного цикла и вхождениями в остальных циклах гнезда на задержку в стартах конвейеров 82
3.5. Составление расписания для вычисления гнезда циклов 92
3.6. Формула вычисления задержки в стартах конвейеров для тесного двумерного гнезда циклов 94
3.6.1. Постановка задачи 94
3.6.2. Случай | A\ * 0, |B| * О 98
3.6.3. Случай | A\ = О, \B\ * 0 102
3.6.4. Случай | A\ * 0, |B| = 0 107
3.6.5. Случай | A\ = 0, \B\ = 0, с12 + с2 Ф 0 111
3.6.6. Случай | A\ = 0, |B| = 0, c\ +c22 =0 115
3.7. Выводы к третьей главе 119
4. Вспомогательные результаты 120
4.1. Линейная форма представления выражений 120
4.2. Система тестирования 122
4.3. Применение автоматического построения графа вычислений к генерации HDL-описаний. Конвертер с языка С в VHDL 129
4.4. Выводы к четвертой главе 131
Заключение 132
Приложение 1 134
Литература 145
