Структурно-предикативная система построениявнутреннего представления программ,ориентированного на оптимизациюи распараллеливание

На правах рукописи

Тапкинов Батр Юрьевич

СТРУКТУРНО-ПРЕДИКАТИВНАЯ СИСТЕМА ПОСТРОЕНИЯ
ВНУТРЕННЕГО ПРЕДСТАВЛЕНИЯ ПРОГРАММ,
ОРИЕНТИРОВАННОГО НА ОПТИМИЗАЦИЮ
И РАСПАРАЛЛЕЛИВАНИЕ

05.13.11 – Математическое и программное обеспечение

вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ

диссертации на соискание ученой степени

кандидата технических наук

Ростов-на-Дону – 2006

Работа выполнена на кафедре информатики и вычислительного эксперимента факультета математики, механики и компьютерных наук Ростовского го­су­дарственного университета.

Научный руководитель - кандидат технических наук,

доцент,

Крицкий Сергей Петрович

Официальные оппоненты - доктор технических наук,

профессор,

Белявский Григорий Исаакович

кандидат технических наук,

доцент,

Лазарева Светлана Александровна

Ведущая организация - Южно-Российский государственный

технический университет (Новочеркасский

политехнический институт),

г. Новочеркасск

Защита состоится « 1 » марта 2007 г. в 11.00 час. на заседании диссер­тационного совета К.212.208.04 по физико-математическим и техническим наукам в Южном Федеральном университете по адресу: 344090, г. Ростов-на-Дону, пр. Стачки, 200/1, корп. 2, ЮГИНФО, к. 206

С диссертацией можно ознакомиться в научной библиотеке ЮФУ по адресу: г. Ростов-на-Дону, ул. Пушкинская, 148.

Автореферат разослан « 31 » января 2007 г.

Ученый секретарь

диссертационного совета,

кандидат физико-математических наук Муратова Г.В.

Общая характеристика работы

Актуальность темы. Развитие вычислительных систем, появление новых аппаратных плат­форм и процессоров обуславливают необходимость разработки новых компи­ля­торов. Разработка эффективного компилятора – это трудоем­кий и достаточно длительный процесс.

Одним из ответственных этапов разработки компилятора является проектирование внутреннего представления программ для исходного языка. От внутреннего представления будут зависеть важные свойства компилятора, такие как переносимость на другие платформы, модифицируемость, скорость работы, качество кода и т.д.

Существует большое количество моделей для представления программ, как чисто теоретических, так и широко применяемых на практике:

• постфиксная нотация;
• трехадресный код;
• синтаксическое дерево;
• другие граф-модели.

Внутренние представления в современных компиляторах, как правило, реализуются в виде таких структур, как списки и деревья. В некоторых системах оптимизации и распараллеливания программ, таких как Polaris1, SUIF/SUIF22, ОРС3, внутреннее представление программ реализовано в виде иерархии классов на объектно-ориентированном языке. Основное преимущество представления в таком виде – это простота проектирования, модифицируемость и расширяемость.

За преобразование исходной программы во внутреннее представление отвечает анализирующая часть компилятора или парсер. Разработка парсера с нуля является очень трудоемкой задачей и может занять много времени. Поэтому, чтобы ускорить и облегчить процесс его разработки, как правило, используются специальные инструменты, так называемые генераторы компиляторов (Lex/YACC, Flex/Bison). Но даже при использовании генераторов компиляторов за разработчиком парсера остается решение основной задачи – описание синтаксиса и семантики исходного языка с помощью некоторого формализма.

Сегодня для решения этой задачи чаще всего используются атрибутные грамматики4, которые позволяют описывать синтаксис и семантику языка благодаря наличию атрибутов, связанных с каждым грамматическим символом, и семантических правил, вычисляющих эти атрибуты. В атрибутной грамматике обязательно должен быть задан правильный порядок выполнения семантических правил, связанных с узлами дерева разбора. Установление этого порядка является нетривиальной задачей, решение которой требует от программиста дополнительных временных затрат и отвлекает от решения основной задачи. Кроме того, при использовании атрибутной грамматики построение внутреннего представления программы, отличного от дерева разбора, нужно описывать в процедурном виде.

В 1980 году Ф. Перейрой и Д. Уорреном были описаны грамматики DCG5 (Definite Clause Gram­mars), относящиеся к классу логических грамматик. Сейчас эти грамматики неизменно включаются во все развитые системы программирования на языке Пролог. Эти грамматики в отличие от атрибутных грамматик, не требуют задания строгого порядка выполнения семантических правил. Однако построение семантической структуры программы с помощью DCG, как и в атрибутных грамматиках, нужно описывать в процедурном виде (на языке Пролог).

В 2003 году Крицким С.П. были описаны структурные предикативные грамматики6 (СП-грамматики), основанные на понятии структурного графа программы и расширяющие DCG процедурой унификации вершин структурного графа и термов. Эти грамматики обладают всеми возможностями DCG и при этом позволяют описывать построение семантической структуры программы и работу с ней в непроцедурном виде. Однако эти грамматики не нашли широкого применения из-за отсутствия их реализации, разработка которой представляется актуальной задачей развития систем построения компиляторов.

Цель работы и задачи исследования. Целью данной диссертационной работы является реализация структурных предикативных грамматик и их использование для построения внутреннего представления программ, ориентированного на их оптимизацию и распараллеливание.

Для достижения поставленной цели решаются следующие задачи:

1. Создание программной реализации СП-грамматик, представления струк­турного графа и алгоритма унификации вершин структурного графа и термов.
2. Применение СП-грамматик для определения и построения внутреннего представления программ, написанных на процедурных языках, в виде структурного графа.
3. Реализация с помощью средств работы со структурным графом алгоритмов построения информационных структур, используемых при оптимизации и распараллеливании, а также набора оптимизирующих и распараллеливающих преобразований.
4. Разработка экспериментальной структурно-предикативной системы для построения внутреннего представления программ, ориентированного на их оптимизацию и распараллеливание.

Методы исследований. В диссертационной работе использовались методы теории трансляции и преобразований программ, элементы теории графов. При реализации программного обеспечения использовались принципы логического программирования.

Научная новизна. Предложены методы и алгоритмы автоматического построения структурного графа и преобразования правил СП-грамматики в правила Пролога. Предложен способ использования унификации вершин структурного графа и термов для построения, анализа и преобразования внутреннего представления программ с целью их оптимизации и распараллеливания.

Практическая ценность. В ходе исследовательской работы была разработана экспериментальная система для построения внутреннего представления программ, которое ориентировано на их оптимизацию и распараллеливание. Эта система может быть использована для обучения, исследований и экспериментов в области преобразований программ.

Программно реализованные СП-грамматики могут быть использованы в качестве инструмента при разработке оптимизирующих и распараллеливающих компиляторов.

Апробация результатов работы. Основные результаты диссертационной работы докладывались и обсуждались на Всероссийской научной конференции “Научный сервис в сети Интернет: технологии параллельного программирования”, г. Новороссийск, 2006 г., на научно-методической конференции “Современные информационные технологии в образовании: Южный федеральный округ”, г. Ростов-на-Дону, 2006г., на научных семинарах кафедр ИВЭ и АДМ мехмата РГУ, на научно-исследовательском семинаре ЮГИНФО РГУ, 2006 г.

Публикации. По результатам выполненных исследований опубликовано 6 печатных работ, в том числе 2 в соавторстве. Из них 3 статьи в российском рецензируемом журнале, 1 статья в сборнике трудов аспирантов РГУ и 2 в тезисах докладов всероссийской и региональной конференций.

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы и приложений. Основной текст работы (без приложений) занимает 111 страниц, и включает 11 рисунков и 22 таблицы. Список литературы содержит 98 наименований.

Содержание работы

Во введении обоснована актуальность проводимых исследований, сформулирована цель диссертационной работы, показана новизна и практическая значимость результатов, указаны положения, выносимые на защиту, и кратко аннотировано содержание глав.

Первая глава посвящена обзору современного состояния исследований в области оптимизации и распараллеливания программ. Рассматриваются различные подходы к распараллеливанию программ, технологии параллельного программирования, различные промежуточные представления программ, используемые при оптимизации и распараллеливании.

Первый раздел данной главы, посвящен подходам к распараллеливанию программ. Рассматриваются 3 основных подхода: «ручное», автоматическое и полуавтоматическое распараллеливание.

Существующие методы автоматического распараллеливания не всегда позволяют получить программу, эффективно работающую на параллельной ЭВМ, а распараллеливание программ вручную или же написание параллельной программы с нуля требует от программиста высокого уровня квалификации и много времени. Поэтому, как показывает практика, из трех подходов к распараллеливанию программ на сегодняшний день самым эффективным является полуавтоматическое распараллеливание, использующее преимущества двух других подходов. При этом подходе требования к уровню квалификации программистов могут быть немного снижены, а использование специализированных параллельных библиотек и систем для анализа и преобразований программ ускоряет и облегчает процесс оптимизации и распараллеливания программ.

Во втором разделе первой главы приводится обзор различных технологий параллельного программирования. Рассматриваются расширения традиционных языков Фортран и Си, такие как HPF (High Performance Fortran), Fortran-DVM, C-DVM, mpC, а также коммуникационные библиотеки и интерфейсы параллельного программирования MPI, OpenMP, PVM. Рассмотренные технологии позволяют использовать для написания программ традиционные последовательные языки, однако не избавляют программиста от необходимости перестроения алгоритмов для их эффективного выполнения на параллельных машинах.

Далее рассматривается альтернативный подход, связанный с использованием специализированных параллельных библиотек, таких как Aztec, ScaLAPACK, ATLAS, PARPACK, которые избавляют программистов от рутинной работы по написанию подпрограмм для решения стандартных задач численных методов и позволяют сконцентрироваться на предметной области.

При обзоре средств автоматического распараллеливания программ упоминаются такие системы, как PIPS, cемейство препроцессоров-векториза­то­ров KAP, VAST/Parallel. Данные системы в значительной степени могут облегчить и ускорить разработку параллельных программ, однако получить с их помощью эффективно работающие параллельные программы не всегда удается.

В заключение второй части первой главы приводится обзор средств создания и проектирования параллельных программ. Рассматриваются отечественные проекты Открытая распараллеливающая система (ОРС), системы VRay, ПРОГРЕСС, ТРАНСФОРМ, а также зарубежные системы Parafrase, Polaris, SUIF/SUIF2, PTOOL и другие. Хотя большинство из рассмотренных систем являются исследовательскими, в них используются более сложные методы исследования и преобразования программ, чем те, которые традиционно включаются в компиляторы или системы автоматического распараллеливания. Основной недостаток большинства из рассмотренных систем – это ограниченные возможности расширения. Во-первых, многие системы для построения внутреннего представления программ используют внешние программы или библиотеки (ANTLR, Sage++, Bison, YACC, компиляторы Portland Group Inc.) с готовыми грамматиками языков, что ставит их в зависимость от сторонних разработчиков. Во-вторых, внутреннее представление программ во многих системах ориентировано на конкретный язык, что может вызывать большие трудности при добавлении новых языков. В-третьих, отсутствует поддержка динамически подключаемых библиотек (модулей), вследствие чего для внесения изменений или добавления новых возможностей требуется перекомпиляция всей системы.

В третьем разделе первой главы приводится обзор и анализ различных вариантов внутреннего представления программ. В начале приводятся требования к внутреннему представлению при оптимизации и распараллеливании программ. Затем описываются различные формы внутреннего представления, обычно используемые для оптимизации и распараллеливания программ: управляющий граф, граф зависимости по данным, граф программных зависимостей, решетчатый граф, граф вычислений программы и иерархический граф заданий. Некоторые из этих графов используются в данной работе для демонстрации разработанных методов.

Вторая глава диссертации посвящена подробному описанию формализма СП-грамматик, использованию его для построения семантической структуры программы, а так же реализации СП-грамматик.

В первом разделе второй главы рассматриваются формализмы атрибутных грамматик и грамматик DCG. Приводятся примеры описания семантической структуры выражений с помощью этих грамматик. Далее описывается формализм СП-грамматик. Приводятся определения понятий структурной предикативной грамматики и структурного графа, описывается алгоритм унификации вершин структурного графа и термов.

Структурные предикативные грамматики являются расширением грамматик DCG декларативными средствами определения и анализа семантической структуры в виде графа, в основе которого лежит семантическое дерево программы. Ядром этого расширения является определяемое ниже понятие структурного графа и процедура унификации вершин такого графа и термов, дополняющая обычно используемую в Прологе процедуру унификации термов.

Определение: Структурным графом называется конечный ориентированный упорядоченный граф, удовлетворяющий следующим условиям:

1. Каждая вершина графа помечена либо объектом первичного сорта (ОПС), либо конструктором, либо переменной; сорт метки считается сортом вер­шины; две вершины не могут помечаться одной переменной.
2. Дуги графа соответствуют аргументам конструкторов, т.е. выходят только из вершин, помеченных n-местным конструктором, где n > 0; если тип конструктора f: s1,…,sn  s, то из вершины f выходит n дуг и iая дуга входит в вершину vi сорта si (вершины v1,…,vn не обязательно различны). В этом случае вершину f можно обозначать f (v1,…,vn).

Вершины графа представляются ссылками на записи в базе данных Пролога. Эти ссылки также могут входить в термы. Но в Прологе и DC-граммати­ках ссылка может унифицироваться только сама с собой. В СП-грамматиках с помощью терма можно описать локальную структуру дерева, для чего используется специальный алгоритм унификации вершин структурного графа и термов (таблица 1).

Таблица 1. Алгоритм унификации вершин структурного графа и термов

	Вершина графа	Подтерм	Результат
	f(v1,…,vn)	f(t1,…,tn)	Переход к последовательной унификации вершин v1 и термов t1, и т.д. При этом найденные на каждом шаге под­становки применяются ко всему терму.
	Объект первичного сорта или 0-местный конструктор	Тот же объект или конструктор	Унификация вершины успешно завершена
	Вершина	Та же вершина
	Вершина v сорта s, не являющаяся переменной	Переменная X сорта s	Все вхождения X заменяются на v; в графе вершины X и v отождествляются. При отождествлении вершин в графе они отождествляются и в терме.
	Переменная X сорта s	Вершина v того же сорта
	Переменная X сорта s	Переменная Y сорта s	Отождествление (переименование) всех вхождений этих перемен­ных. В графе это может привести к отождествлению вершин X и Y.
	Переменная X сорта s	Терм T сорта s, не являющийся вершиной или переменной (X может входить в T)	Вершины дерева терма T и графа, помеченные ранее переменной X, отождествляются с корнем дерева терма T. Отождествляются и другие вершины полученного графа, помеченные одной переменной. Остальные вершины дерева, не являвшиеся вершинами графа, становятся новыми вершинами графа.
	В остальных случаях унификация невозможна.