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

• Автор: Жегуло, Ольга Анатольевна
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2007
• Место защиты: Ростов-на-Дону
• Количество страниц: 111 с. : ил.

Оглавление
Введение

I Распараллеливание и технологии трансформирования программ

1.1 Технологии параллельного программирования и средства распараллеливания для

современных параллельных ЭВМ

1.1.1 Основные классы параллельных архитектур и технологий параллельного

программирования

1.1.2 Методы и средства распараллеливания программ

1.2 Трансформационный подход к программированию и его применение в

распараллеливании

II Язык схемных трансформаций многокомпонентных программных

структур
.1 Базовый язык схемных трансформаций многокомпонентных программных структур
II. 1.1 Синтаксис
II. 1.2 Порядок применения правила
.2 Развитие языка схемных трансформаций многокомпонентных программных структур
3 Методика написання нелокальных схемных правил трансформации
III Реализация на языке нелокальных схемных трансформаций
распараллеливающих и оптимизирующих преобразований
1.1 Определения зависимостей по данным и управлению, используемых для проверки
условий применимости
III.1.1 Граф зависимостей по управлению
1. Граф зависимостей по данным
1. Решетчатый граф
1.2 Базовые предикаты и функции в условиях применимости правил
1.2.1 Базовые предикаты, заданные на семантическом дереве программы и графе зависимостей
по управлению
Ш.2.2 Базовые предикаты, заданные на графе зависимостей по данным
1.2.3 Базовые предикаты, заданные на решетчатом графе
1.3 Типы параметров правил с образцами на параметризованном Фортране
1.4 Набор классических преобразований распараллеливания и оптимизации
1.4.1 Сценарий применения классических преобразований распараллеливания и оптимизации
1. Протягивание констант
1. Нормализация циклов
1.4.4 Удаление индуктивных переменных. Случай 1
1. Удаление индуктивных переменных. Случай 2
1.4.6 Удаление индуктивных переменных. Случай 3
1.4.7 Удаление охватывающих переменных
Ш.4.8 Слияние циклов классический подход
1.4.9 Перестановка двух циклов
1.4. Коллапс циклов
1.4. Развертка циклов
1.4. Редукция скалярного произведения векторов
1.4. Параллелизация для цикла однократной вложенности
1.4. Параллелизация для гнезда вложенных циклов
III.5 Правила распараллеливания согласно подходу В.В. Воеводина
.5.1 Перестановка циклов для гнезда любой вложенности
Ш.5.2 Слияние циклов подход В.В. Воеводина
III. Параллельное исполнение цикла РаЮО
IV Макет многоцелевой системы трансформаций программ
IV. Возможности макета МСТП
1У.2 Язык сценариев
УЗ Внутренние механизмы и структура макета МСТП
IV.З. 1 Структура макета МСТИ и порядок работы с ним
У.3.2 Внутреннее представление правил и сценариев
У.З.З Механизмы работы трансформационной машины
ГУЗ.ЗЛ Порядок обхода дерева программы
У.2 Алгоритм унификации дерева составного входного образца и дерева программы
Заключение
Литература


Реализация макетной версии системы трансформаций программ, обеспечивающей автоматическое, полуавтоматическое и полностью управляемое пользователем применение непроцедурных правил трансформации к распараллеливаемой программе. Демонстрация применимости разработанных схемных правил распараллеливающих трансформаций для крайне трудоемкого при отсутствии средств автоматизации распараллеливания примеров программ с помощью макета СТП. В диссертационной работе использовались методы трансформаций программ, теории графов, теории трансляции, автоматического распараллеливания программ и теории зависимостей по данным в программах. При реализации макетной версии программной системы использовалась технология логического программирования. Выполнено развитие языка схемных трансформаций многокомпонентных программных структур: разрешено включать процедурные по сути действия непосредственно в состав схемы, выразив их в декларативной форме. В частности, разрешены вложенные вызовы других преобразований, возможно задание семантических связей и ограничений внутри образцов правил. Для минимизации вычислений в случае неудачного сопоставления условие применимости правила может быть разбито на части, связанные с отдельными простыми образцами. Разработано представление на разработанном языке представительного набора преобразований распараллеливания и оптимизации программ на подмножестве языка Фортран по классическим методам Аллена, Кеннеди, Падуа и Вольфа 4, , , ], а также некоторых (перестановка и слияние циклов, параллельное исполнение цикла типа РагИО согласно подходу академика В. В. Воеводина [, ]) неклассичсских распараллеливающих преобразований программ. Для некоторых классических преобразований оптимизации сформулированы отсутствующие в других источниках условия, обеспечивающие семантическую корректность выходной программы. Разработано внутреннее представление правил трансформаций программ, совместимое с абстрактным деревом преобразуемой программы [], а также методы трансляции правил трансформации в их внутреннее представление. Разработаны модифицированные по сравнению с универсальными алгоритмы поиска и унификации сопоставимых фрагментов внутреннего представления программы и многокомпонентного образца. Для большей общности образцов правил синтаксический тип параметра правила должен не совпадать, а быть синтаксически выводим из типа конструкции в программе. В целях экономии при поиске применимого к вершине дерева программы правила рассматриваются только образцы, содержащие вершины искомого типа. Предложенные дополнения языка многокомпонентных схемных правил расширяют его возможности и перспективы его применения для задания различных преобразований программ. Разработанный макет трансформационной системы, который позволяет задавать и применять распараллеливающие и иные преобразования программ в автоматическом, полуавтоматическом и полностью управляемом пользователем режиме, может быть использован для изучения методов и средств распараллеливания программ. Созданная экспериментальная расширяемая система распараллеливания может быть использована для разработки и тестирования методов распараллеливания для различных распределенных архитектур и/или классов задач и для быстрого прототипирования распараллеливающих компиляторов. С помощью разработанной системы распараллеливания возможно создание банка типовых решений при распараллеливании программ для многопроцессорных архитектур; полученную базу знаний можно использовать для обучения. Результаты работы использованы в НИР ЮГИНФО № 1. Разработка методов, технологии и специальных программных средств удаленного использования вычислительных ресурсов регионального центра высокопроизводительных вычислений в учебном процессе и научных исследованиях» (выполненную в рамках раздела «Освоение и развитие сетевых технологий нового поколения» подпрограммы «Информационные технологии в системе информационного общества» научной отраслевой программы Минобразования РФ «Научное, научно-методическое, материально-техническое обеспечение развития технологий информационного общества и индустрии образования»). II, IV, V и VII международные научно-технические конференции "Интеллектуальные и многопроцессорные системы", , , , .