Введение
1 Информационная зависимость в программе. Основные способы ее определения и представления 17
1.1 Информационная зависимость и некоторые ее представления 18
1.1.1 Модель рассматриваемых программ: линейный класс 19
1.1.2 Вхождения переменных, итерационное пространство 22
1.1.3 Информационная зависимость по памяти (memory-based) 23
1.1.4 Информационная зависимость по значению (value-based, data-flow) 31
1.1.5 Сравнение представлений информационной зависимости 35
1.2 Графовые модели информационной зависимости 38
1.2.1 Граф информационных зависимостей 38
1.2.2 Решетчатый граф 40
1.2.2.1 Опорные пространства. Порядок исполнения операторов 40
1.2.2.2 Максимальные и минимальные решетчатые графы 44
1.2.2.3 Простые и элементарные решетчатые графы 51
1.2.2.4 Хранение решетчатых графов 57
1.2.3 Развертка решетчатого графа (таймирование, schedule) 62
1.3 Основные способы нахождения информационных зависимостей 67
1.3.1 Неравенства Банержи и ПОД тест 67
1.3.2 Методы построения решетчатых графов В. В. Воеводина и П. Фотрье (P. Feautrier) 69
1.3.3 Омега Тест 73
1.3.4 Сравнение методов нахождения информационных зависимостей 73
1.3.4.1 Неравенства Банержи и точные методы 74
1.3.4.2 Метод В. В. Воеводина, метод П. Фотрье и Омега тест 83
2 Анализ и преобразования программ, основанные на решетчатом графе 85
2.1 Автоматическое распознавание ParDo циклов в программе 86
2.1.1 Определение ParDo цикла по решетчатому графу 87
2.1.2 Распознавание ParDo циклов по решетчатому графу. Связь между минимальными решетчатыми графами и носителями зависимости по значению 88
2.1.3 Определение ParDo циклов и их связь с ParDo циклами по решетчатому графу 92
2.1.4 Алгоритм распознавания ParDo циклов в программе 94
2.1.5 Циклы ParDo и внешние переменные 95
2.1.6 Сравнение с другими методами распознавания ParDo циклов 97
2.2 Расщепление многомерных гнезд циклов 102
2.2.1 Примеры рассматриваемых видов расщеплений 103
2.2.2 Построение расщепления в виде последовательности тесных гнезд циклов 108
2.2.2.1 Проверка существования дуги решетчатого графа между вершинами из заданных выпуклых множеств 112
2.2.2.2 Использование расщепления для непосредственного распараллеливания 114
2.2.3 Построение расщепления в виде структуры произвольно вложенных циклов 116
2.2.3.1 Использование расщепления для непосредственного распараллеливания: общий случай 124
2.2.4 Сравнение различных видов расщеплений 130
2.3 Подстановка переменных и экспансия массивов 132
2.3.1 Подстановка переменных 132
2.3.2 Экспансия массивов 139
3 Программная реализация построения графовых моделей информационных зависимостей и преобразований программ, их использующих 150
3.1 Анализ информационных зависимостей в ОРС 152
3.1.1 Построение расширенной информации о вхождениях 152
3.1.2 Реализация графа информационных зависимостей на основе неравенств Банержи 156
3.1.3 Реализация решетчатых графов. Выбор способа построения 159
3.1.3.1 Тестирование правильности построения решетчатого графа 163
3.1.3.2 Экспериментальные данные о времени построения решетчатых графов 165
3.1.4 Реализация построения графа информационных зависимостей на основе решетчатых графов 166
3.1.5 Реализация разметки ParDo циклов в программе 170
3.2 Преобразования программ, основанные на решетчатом графе, в ОРС 173
3.2.1 Реализация расщепления гнезда циклов. Выбор метода генерации границ циклов 173
3.2.2 Подстановка переменных и экспансия массивов 177
Заключение 182
Литература
