Исследование информационных зависимостей программ для распараллеливающих преобразований

• Автор: Шульженко, Александр Михайлович
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2006
• Место защиты: Ростов-на-Дону
• Количество страниц: 202 с.

Введение
1 Информационная зависимость в программе. Основные способы ее определения и представления

1.1 Информационная зависимость и некоторые ее представлении

1.1.1 Модель рассматриваемых программ линейный класс

1.1.2 Вхождения переменных, итерационное пространство

1.1.3 Информационная зависимость по памяти

1.1.4 Информационная зависимость по значению v,

1.1.5 Сравнение представлений информационной зависимости

1.2 Графовые модели информационной зависимости

1.2.1 Граф информационных зависимостей

1.2.2 Решетчатый граф

1.2.2.1 Опорные пространства. Порядок исполнения операторов
1.2.2.2 Максимальные и минимальные решетчатые графы
1.2.2.3 ростые и элементарные решетчатые графы
1.2.2.4 Хранение решетчатых графов
1.2.3 Развертка решетчатого графа таймированис,
Основные способы нахождения информационных зависимостей
1.3.1 Неравенства Банержи и ПОД тест
1.3.2 Методы построения решетчатых графов В. В. Воеводина и П. Фотрье . i
1.3.3 Омега Тест
1.3.4 Сравнение методов нахождения информационных зависимостей
1.3.4.1 Неравенства Банержи и точные методы
1.3.4.2 Метод В. В. Воеводина, метод П. Фотрье и Омега тест
2 Анализ и преобразования программ, основанные на решетчатом
2.1 Автоматическое распознавание циклов в программе
2.1.1 Определение цикла по решетчатому графу
2.1.2 Распознавание циклов по решетчатому графу. Связь между минимальными
решетчатыми графами и носителями зависимости по значению
2.1.3 Определение циклов и их связь с циклами по решетчатому графу
2.1.4 Алгоритм распознавания циклов в программе
2.1.5 Циклы и внешние переменные
2.1.6 Сравнение с другими методами распознавания циклов
2.2 Расщепление многомерных гнезд циклоп
2.2.1 Примеры рассматриваемых видов расщеплении
2.2.2 Построение расщепления в виде последовательности тесных гнезд циклов
2.2.2.1 Проверка существования дуги решетчатого графа между вершинами из заданных выпуклых множеств
2.2.2.2 Использование расщепления для непосредственного распараллеливания
2.2.3 Построение расщепления в виде структуры произвольно вложенных циклов
2.2.3.1 Использование расщепления для непосредственного распараллеливания
общий случай
2.2.4 Сравнение различных видов расщеплений
2.3 Подстановка переменных и экспансии массивов
2.3.1 Подстановка переменных
2.3.2 Экспансия массивов
3 Программная реализация построения графовых моделей информационных зависимостей и преобразований программ, их использующих
3.1 Анализ информационных зависимостей в ОРС
3.1.1 Построение расширенной информации о вхождениях
3.1.2 Реализация графа информационных зависимостей на основе неравенств Банержи
3.1.3 Реализация решетчатых графов. Выбор способа построения
3.1.3.1 Тестирование правильности построения решетчатого графа
3.1.3.2 Экспериментальные данные о времени построения решетчатых графов
3.1.4 Реализация построения графа информационных зависимостей на основе
решетчатых графов
3.1.5 Реализация разметки РагРо циклов в программе
3.2 Преобразования программ, основанные на решетчатом графе, в ОРС
3.2.1 Реализация расщепления гнезда циклов. Выбор метода генерации границ циклов
3.2.2 Подстановка переменных и экспансия массивов
Заключение
Литература


Затем указывается, какие решетчатые нужно использовать для определения циклов, итерации которых можно выполнять одновременно. Приводится сравнение полученного метода с другими методами определения РагОо циклов. Во втором параграфе приводятся методы различных видов расщеплений многомерных гнезд циклов. Указывается, как эти методы, вместе с методом определения РагОо циклов, могут быть использованы для распараллеливания гнезд циклов. Выполняется сравнение различных методов расщеплений указываются достоинства и недостатки. В последнем параграфе второй главы описываются методы выполнения подстановки индексных переменных и экспансии массивов в многомерных циклах. Третья глава посвящена программной реализации разработанных в диссертации методов, которая была выполнена автором в рамках проекта ОРС. Здесь описываются наиболее важные аспекты, лежащие в основе этой программной реализации. Приводятся необходимые алгоритмы и структуры данных. Указывается связь данной программной реализации с модулями других разработчиков ОРС. В ней также приводятся копии экранных форм ОРС, демонстрирующих некоторые реализованные автором возможности системы. Информация данной главы может быть необходима как настоящим, так и будущим разработчикам ОРС. В заключении приводится краткое описание полученных результатов, и подводятся итоги проделанной автором работы. Автор диссертации выражает глубокую признательность своему научному руководителю, д. Штейнбергу Б . Я. за переданную школу и оказанную помощь. Автор признателен к. Михалковичу С. С. научный руководитель при получении степени Бакалавра за приобретенный уровень программирования. Автор благодарен Черданцеву Д. Н., Петренко В. В., Макошенко Д. В., НисЗ. Я., Штейнбергу Р. Б., Шилову М. В., Морылеву Р. И., Гуфану К. Ю. и другим разработчикам ОРС, труд которых значительно повысил качество программных разработок автора и помог ему в исследованиях. И, безусловно, автор признателен своей семье за поддержку и сопереживание в его научной работе. ИНФОРМАЦИОННАЯ ЗАВИСИМОСТЬ В ПРОГРАММЕ. Анализ информационной зависимости в программе является неотъемлемой частью любого автоматического выявления параллелизма. Отношения информационной зависимости используются для определения операций, итераций циклов и операторов программы, которые можно исполнять одновременно параллельно. Также, анализ информационных зависимостей является основой для проверки эквивалентности большого количества оптимизирующих и распараллеливающих преобразований программ. Детальный анализ информационных зависимостей, например, с помощью решетчатых графов, позволяет установить порядок, в котором должны исполняться операции программы, и размещение данных, необходимые для достижения максимальной производительности на определенном параллельном компьютере. Возможности любого компилятора зависят от возможностей его анализаторов. Выбор правильного представления информационной зависимости для анализа программ является ключевым моментом разработки компилятора. Для того чтобы представление было целесообразным, оно должно содержать информацию достаточную для обеспечения необходимых оптимизаций и преобразований кода. Кроме этого, оно должно позволять извлекать информацию из достаточно большого класса программ. Информационная зависимость по памяти2, вектор направления, вектор расстояния, носитель уровень зависимости по памяти 8, , , , являются важными представлениями, хорошо зарекомендовавшими себя при распараллеливании и преобразованиях циклов 8, , , , , . Они применимы к большому количеству программ. Однако существуют более тонкие представления информационной зависимости в программе информационная зависимость по значению, вектор направления зависимости по значению, вектор расстояния зависимости по значению, носитель уровень зависимости по значению , , . Хотя известны и другие виды представлений, например, многогранник зависимости , указанные выше представления являются наиболее известными и широко используемыми. В этом разделе мы подробно рассмотрим и сравним эти виды представлений. Но сначала опишем класс рассматриваемых программ и введем необходимые определения.