Содержание к диссертации
Введение 4
I Распараллеливание и технологии трансформирования программ 13
1.1 Технологии параллельного программирования и средства распараллеливания для
современных параллельных ЭВМ 13
Основные классы параллельных архитектур и технологий параллельного программирования 13
Методы и средства распараллеливания программ 16
1.2 Трансформационный подход к программированию и его применение в
распараллеливании 19
II Язык схемных трансформаций многокомпонентных программных
структур 27
Н.1 Базовый язык схемных трансформаций многокомпонентных программных структур 27
II. 1.1 Синтаксис 27
И. 1.2 Порядок применения правила 32
Развитие языка схемных трансформаций многокомпонентных программных структур 34
Методика написания нелокальных схемных правил трансформации 43
III Реализация на языке нелокальных схемных трансформаций
распараллеливающих и оптимизирующих преобразований 45
III. 1 Определения зависимостей по данным и управлению, используемых для проверки
условий применимости 45
Граф зависимостей по управлению 45
Граф зависимостей по данным 45
Решетчатый граф 47 II 1.2 Базовые предикаты и функции в условиях применимости правил 48
Ш.2.1 Базовые предикаты, заданные на семантическом дереве программы и графе зависимостей
по управлению 49
Ш.2.2 Базовые предикаты, заданные на графе зависимостей по данным 50
III.2.3 Базовые предикаты, заданные на решетчатом графе 50
Ш.З Типы параметров правил с образцами на параметризованном Фортране 50
Ш.4 Набор классических преобразований распараллеливания и оптимизации 51
Ш.4.1 Сценарий применения классических преобразований распараллеливания и оптимизации 52
Ш.4.2 Протягивание констант 53
Ш.4.3 Нормализация циклов 53
Ш.4.4 Удаление индуктивных переменных. Случай 1 56
Ш.4.5 Удаление индуктивных переменных. Случай 2 58
Ш.4.6 Удаление индуктивных переменных. Случай 3 60
Ш.4.7 Удаление охватывающих переменных 61
Ш.4.8 Слияние циклов (классический подход) 64
Ш.4.9 Перестановка двух циклов 65
Ш.4.10 Коллапс циклов 66
Ш.4.11 Развертка циклов 67
Ш.4.12 Редукция скалярного произведения векторов 68
Ш.4.13 Параллелизация для цикла однократной вложенности 69
Ш.4.14 Параллелизация для гнезда вложенных циклов 71
III.5 Правила распараллеливания согласно подходу В.В. Воеводина 73
Ш.5.1 Перестановка циклов для гнезда любой вложенности 73
Ш.5.2 Слияние циклов (подход В.В. Воеводина) 74
Ш.5.3 Параллельное исполнение цикла ParDO 75
IV Макет многоцелевой системы трансформаций программ 77
IV.1 Возможности макета МСТП 77
IV.2 Язык сценариев 78
IV.3 Внутренние механизмы и структура макета МСТП 79
IV.3.1 Структура макета МСТП и порядок работы с ним 80
IV.3.2 Внутреннее представление правил и сценариев 83
IV.3.3 Механизмы работы трансформационной машины 86
IV.3.3.1 Порядок обхода дерева программы 86
IV.3.3.2 Алгоритм унификации дерева составного входного образца и дерева программы 86
Заключение 90
Литература 92
Приложение А. Грамматика языка схемных трансформаций
многокомпонентных программных структур 105
Приложение Б. Акты об использовании результатов работы 110
Введение к работе
Актуальность темы
Со времени постановки проблемы распараллеливания в 60-х гг. прошлого века ею занимались множество исследователей, отечественных и зарубежных. Были получены эффективные инструменты распараллеливания для векторных и некоторых других архитектур [20, 27, 28, 50, 57, 61]. Однако постоянно появляются новые суперкомпьютеры, в основном с распределенной памятью, и для них приходится создавать методы распараллеливания [22]. Разрабатываемые методы распараллеливания программ требуют предварительных экспериментов по их эффективности и применимости к реальным программам. Распараллеливающий компилятор является длительной в разработке и трудно поддающейся модификации программной системой, и потому существует потребность в быстром прототипировании новых методик распараллеливания последовательных программ.
Системы автоматического распараллеливания строятся на основе трансформаций программ, поэтапно применяемых к преобразуемой программе [43, 26]. Трансформации программ подразделяются на процедурные и непроцедурные (схемные) [26,43,98].
В процедурной форме можно задать любые преобразования, но они не будут наглядными, и для их реализации или модификации потребуются значительные усилия. Непроцедурные трансформации, как правило, более наглядны и потому проще в разработке, хотя и несколько ограничивают круг реализуемых преобразований. Многие распараллеливающие преобразования требуют выполнения довольно сложных вычислений как для определения возможности применения данных преобразований, так и генерации выходной программы.
Распараллеливающие преобразования в системе прототипирования распараллеливающих компиляторов желательно задавать таким образом, чтобы
обеспечить простоту разработки и наглядность данных преобразований. Не-
обходимо иметь возможность описывать нелокальные распараллеливающие преобразования, а также сложные вычисления в составе тех преобразований, где это требуется. Итак, способ задания трансформаций в проектируемой системе распараллеливания должен обеспечивать: задание преобразований на уровне исходных текстов программ, возможность работать с рассредоточенными фрагментами, алгоритмические средства.
Абсолютное большинство трансформационных систем распараллеливания и распараллеливающих компиляторов использует процедурные преобразования программ. Две известных автору системы прототипирования распараллеливающих компиляторов, ПРОГРЕСС (ИСИ СО РАН) и Открытая распараллеливающая система (Б.Я. Штейнберг), также основаны на процедурных трансформациях программ; введение в них новых преобразований весьма трудоемко.
В известных автору системах распараллеливания на основе непроцедурных трансформаций нельзя задать нелокальные преобразования на уровне исходного текста программы. Рассмотренные системы преобразований программ общего назначения и средства преобразования произвольных исходных текстов также не обладают такими возможностями.
В работах А.А. Букатова [9, 10, 64] были предложены язык и организация многоцелевой системы трансформаций программ (МСТП), основанные на схемном описании нелокальных трансформаций программ и допускающие использование алгоритмических средств для выполнения нетривиальных вычислений над параметрами схем. МСТП ориентирована, в частности, на распараллеливание программ, обеспечивает средства достаточно простого расширения и удовлетворяет всем требованиям к системе прототипирования распараллеливающих компиляторов.
Однако А.А. Букатовым не проводились исследования полноты предложенного языка в смысле возможности описания средствами этого языка дос-
таточно полного набора распараллеливающих преобразований и не было программно реализовано выполнение данных преобразований.
Поэтому актуальной задачей является разработка набора схемных трансформаций программ для представительного множества распараллеливающих преобразований (с выполнением необходимого развития языка описания таких преобразований) и разработка макетной версии программной системы, обеспечивающей выполнение указанных трансформаций. Цель и задачи диссертационной работы
Цель работы заключается в том, чтобы показать практическую применимость подхода к построению развиваемой системы распараллеливания программ на основе системы трансформаций программ (СТП), использующей нелокальные схемные распараллеливающие преобразования программ. Для достижения поставленной цели решаются следующие задачи:
Развитие языка схемных трансформаций многокомпонентных программных структур для описания в виде схем ряда процедурных действий и повышения общности образцов правил по отношении к текстам преобразуемых программ.
Разработка непроцедурного описания на полученном языке представительного набора распараллеливающих преобразований.
Реализация макетной версии системы трансформаций программ, обеспечивающей автоматическое, полуавтоматическое и полностью управляемое пользователем применение непроцедурных правил трансформации к распараллеливаемой программе.
Демонстрация применимости разработанных схемных правил распараллеливающих трансформаций для крайне трудоемкого при отсутствии средств автоматизации распараллеливания примеров программ с помощью макета СТП.
Методы исследований
В диссертационной работе использовались методы трансформаций программ, теории графов, теории трансляции, автоматического распараллеливания программ и теории зависимостей по данным в программах. При реализации макетной версии программной системы использовалась технология логического программирования. Научная новизна работы состоит в следующем:
Выполнено развитие языка схемных трансформаций многокомпонентных программных структур: разрешено включать процедурные по сути действия непосредственно в состав схемы, выразив их в декларативной форме. В частности, разрешены вложенные вызовы других преобразований, возможно задание семантических связей и ограничений внутри образцов правил. Для минимизации вычислений в случае неудачного сопоставления условие применимости правила может быть разбито на части, связанные с отдельными простыми образцами.
Разработано представление на разработанном языке представительного набора преобразований распараллеливания и оптимизации программ на подмножестве языка Фортран по классическим методам Аллена, Кеннеди, Паду а и Вольфа 4, 23, 24, 51], а также некоторых (перестановка и слияние циклов, параллельное исполнение цикла типа ParDO согласно подходу академика В.В. Воеводина [21, 22]) неклассических распараллеливающих преобразований программ. Для некоторых классических преобразований оптимизации сформулированы отсутствующие в других источниках условия, обеспечивающие семантическую корректность выходной программы.
Программно реализован макет многоцелевой системы трансформаций программ, способный применять преобразования на дополненном языке нелокальных схемных трансформаций и анализировать возможности рас-
параллеливания программы с помощью специальных модулей вычисления зависимостей по данным.
Разработано внутреннее представление правил трансформаций программ, совместимое с абстрактным деревом преобразуемой программы [47], а также методы трансляции правил трансформации в их внутреннее представление.
Разработаны модифицированные по сравнению с универсальными алгоритмы поиска и унификации сопоставимых фрагментов внутреннего представления программы и многокомпонентного образца. Для большей общности образцов правил синтаксический тип параметра правила должен не совпадать, а быть синтаксически выводим из типа конструкции в программе. В целях экономии при поиске применимого к вершине дерева программы правила рассматриваются только образцы, содержащие вершины искомого типа.
Практическая ценность состоит в следующем:
Предложенные дополнения языка многокомпонентных схемных правил расширяют его возможности и перспективы его применения для задания различных преобразований программ.
Разработанный макет трансформационной системы, который позволяет задавать и применять распараллеливающие и иные преобразования программ в автоматическом, полуавтоматическом и полностью управляемом пользователем режиме, может быть использован для изучения методов и средств распараллеливания программ.
Созданная экспериментальная расширяемая система распараллеливания может быть использована для разработки и тестирования методов распараллеливания для различных распределенных архитектур и/или классов задач и для быстрого прототипирования распараллеливающих компиляторов.
4. С помощью разработанной системы распараллеливания возможно создание банка типовых решений при распараллеливании программ для многопроцессорных архитектур; полученную базу знаний можно использовать для обучения. Использование результатов работы
Результаты работы использованы в НИР ЮГИНФО № 1.7.43 «Разработка методов, технологии и специальных программных средств удаленного использования вычислительных ресурсов регионального центра высокопроизводительных вычислений в учебном процессе и научных исследованиях» (выполненную в рамках раздела «Освоение и развитие сетевых технологий нового поколения» подпрограммы «Информационные технологии в системе информационного общества» научной отраслевой программы Минобразования РФ «Научное, научно-методическое, материально-техническое обеспечение развития технологий информационного общества и индустрии образования»). Апробация результатов работы
Основные результаты по теме диссертационной работы докладывались и обсуждались на следующих конференциях и семинарах:
Всероссийская школа-семинар "Современные проблемы математического моделирования", Новороссийск, 1997;
Всероссийская научная конференция "Высокопроизводительные вычисления и их приложения", Черноголовка, 2000;
Первая и Вторая Всероссийские научно-технические конференции "Методы и средства обработки информации", Москва, 2003, 2005;
Всероссийская научная конференция "Научный сервис в сети Интернет: технологии распределенных вычислений", Новороссийск, 2005;
II, IV, V и VII международные научно-технические конференции "Интеллектуальные и многопроцессорные системы", 2001, 2003, 2004,2006.
Публикации
По теме диссертации опубликовано 14 печатных работ, в том числе 5 статей, включая 1 статью в журнале, рекомендованном ВАК РФ для публикации результатов докторских диссертаций, 5 тезисов докладов на конференциях и 4 публикации в материалах конференций.
В совместной работе [15] автору принадлежит заключение о возможности непроцедурного задания распараллеливающих преобразований программ на основе результатов экспериментов; в работах [41,42, 12] — разработка правил распараллеливающих трансформаций и использованные в определениях некоторых правил расширения языка нелокальных схемных трансформаций программ. В работе [13] — обзор актуальных близких проектов среди технологий распараллеливания и программирования. Объем и структура работы
Основной текст диссертации изложен на 88 страницах, имеются 3 рисунка.
Диссертация состоит из введения, четырех глав, заключения и приложений.
Во введении обрисовано состояние научной области и обоснована актуальность темы диссертации, сформулирована цель и основные задачи проводимых исследований, показана научная новизна и практическая ценность полученных результатов, приведены основные положения, выносимые на защиту и краткое содержание глав диссертации.
Первая глава посвящена обзору подходов к распараллеливанию и применяемых при распараллеливании и в других целях технологий преобразования программ. Дается понятие об основных классах современных параллельных архитектур, технологиях параллельного программирования и способах и методах распараллеливания. Рассматриваются средства распараллеливания программ с точки зрения реализуемых ими технологий преобразований программ и возможности расширения диапазона применяемых методов.
Во второй главе описан язык схемных трансформаций многокомпонентных программных структур и предложены расширения базового языка. Рассматривается базовый язык нелокальных схемных преобразований программ, предложенный А.А. Букатовым. Описывается развитие языка схемных нелокальных преобразований программ, выполненное автором.
В третьей главе представлены распараллеливающие преобразования программ, разработанные на дополненном автором языке схемных трансформаций многокомпонентных программных структур. Приводятся краткие пояснения сути преобразований и тексты схемных правил на данном языке для представительного набора классических преобразований распараллеливания и оптимизации из числа используемых Алленом, Кеннеди, Паду а и Вольфом [4, 23, 24, 51], а также нескольких преобразований согласно подходу академика В.В.Воеводина [21,22].
В четвертой главе описана макетная реализация трансформационной системы распараллеливания, основанная на представленном в предыдущей главе наборе распараллеливающих правил трансформации, выполненная в Пролог-системе Eclipse.
В заключении сформулированы основные результаты исследования. В приложениях содержатся грамматика языка нелокальных схемных преобразований программ и 2 акта об использовании результатов исследования. Основные результаты, выносимые на защиту
1. Развитие языка нелокальных схемных трансформаций программ, состоящее в следующем: расширены управляющие конструкции (в частности, разрешены вложенные вызовы других преобразований), введена возможность задания семантических связей и ограничений непосредственно внутри образцов правил, условие применимости правила может быть разбито на части, последовательно проверяемые после сопоставления соответствующих простых образцов.
Описание на дополненном языке нелокальных схемных трансформаций набора классических преобразований распараллеливания и оптимизации и нескольких распараллеливающих преобразований согласно подходу академика В.В. Воеводина для программ на подмножестве Фортрана. Макет МСТП, который предоставляет возможности автоматического, полуавтоматического и полностью управляемого пользователем выполнения распараллеливающих преобразований программ. Модифицированный алгоритм унификации параметризованного дерева правила и семантического дерева программы.
Экспериментальное обоснование того, что с помощью макета МСТП можно применять распараллеливающие правила трансформации и что с помощью сформулированного набора распараллеливающих преобразований можно осуществить крайне трудоемкое при отсутствии средств автоматизации распараллеливание примеров программ.
