WWW.DISS.SELUK.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА
(Авторефераты, диссертации, методички, учебные программы, монографии)

 

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

Жегуло Ольга Анатольевна

ИССЛЕДОВАНИЕ И РЕАЛИЗАЦИЯ

НЕПРОЦЕДУРНЫХ ПРЕОБРАЗОВАНИЙ ПРОГРАММ

ДЛЯ ПОСТРОЕНИЯ РАСШИРЯЕМОЙ СИСТЕМЫ

РАСПАРАЛЛЕЛИВАНИЯ

05.13.11 — Математическое и программное обеспечение вычислительных

машин, комплексов, систем и сетей

АВТОРЕФЕРАТ

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

Ростов-на-Дону – 2007 3

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

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

Официальные оппоненты: доктор технических наук, профессор Бабенко Людмила Климентьевна кандидат технических наук, доцент Крицкий Сергей Петрович

Ведущая организация: НИИ вычислительных, информационных и управляющих систем Южно-Российского государственного технического университета (Новочеркасского политехнического института)

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

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

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

Ученый секретарь диссертационного совета, кандидат физико-математических наук, доцент Муратова Галина Викторовна

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы Со времени постановки проблемы распараллеливания в 60-х гг. прошлого века ею занимались множество исследователей, отечественных и зарубежных. Были получены эффективные инструменты распараллеливания для векторных и некоторых других архитектур. Однако постоянно появляются новые суперкомпьютеры, в основном с распределенной памятью, и для них приходится создавать методы распараллеливания. Разрабатываемые методы распараллеливания программ требуют предварительных экспериментов по их эффективности и применимости к реальным программам.




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

Системы автоматического распараллеливания строятся на основе трансформаций программ, поэтапно применяемых к преобразуемой программе. Трансформации программ подразделяются на процедурные и непроцедурные (схемные).

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

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

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

Абсолютное большинство систем распараллеливания и распараллеливающих компиляторов использует процедурные преобразования программ. Системы прототипирования распараллеливающих компиляторов ПРОГРЕСС (ИСИ СО РАН) и Открытая распараллеливающая система (Б.Я.Штейнберг) также основаны на процедурных трансформациях программ; введение в них новых преобразований весьма трудоемко.

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

В работах А.А. Букатова 1 были предложены язык и организация многоцелевой системы трансформаций программ (МСТП), основанные на схемном описании нелокальных трансформаций программ и допускающие использование алгоритмических средств для выполнения нетривиальных вычислений над параметрами схем. МСТП ориентирована, в частности, на распараллеливание программ, обеспечивает средства Букатов А.А. Разработка средств непроцедурной реализации распараллеливающих преобразований программ // Труды Всероссийской научной конференции "Фундаментальные и прикладные аспекты разработки больших распределенных программных комплексов", Абрау-Дюрсо, 1998, с. 109-116.

достаточно простого расширения и удовлетворяет всем требованиям к системе прототипирования распараллеливающих компиляторов.

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





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

Цель и задачи диссертационной работы Цель работы заключается в том, чтобы показать практическую применимость подхода к построению развиваемой системы распараллеливания программ на основе системы трансформаций программ (СТП), использующей нелокальные схемные распараллеливающие преобразования программ. Для достижения поставленной цели решаются следующие задачи:

1. Развитие языка схемных трансформаций многокомпонентных программных структур для описания в виде схем ряда процедурных действий и повышения общности образцов правил по отношении к текстам преобразуемых программ.

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

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

4. Демонстрация применимости разработанных схемных правил распараллеливающих трансформаций для крайне трудоемкого при отсутствии средств автоматизации распараллеливания примеров программ с помощью макета СТП.

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

Научная новизна работы состоит в следующем:

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

2. Разработано представление на дополненном языке представительного набора преобразований распараллеливания и оптимизации программ на подмножестве языка Фортран по классическим методам Аллена, Кеннеди, Падуа и Вольфа, а также некоторых (перестановка и слияние циклов, параллельное исполнение цикла типа ParDO согласно подходу академика В.В. Воеводина) неклассических распараллеливающих преобразований программ. Для некоторых классических преобразований оптимизации сформулированы отсутствующие в других источниках условия, обеспечивающие семантическую корректность выходной программы.

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

4. Разработано внутреннее представление правил трансформаций программ, совместимое с абстрактным деревом преобразуемой программы2, а также методы трансляции правил трансформации в их внутреннее представление.

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

Практическая ценность состоит в следующем:

1. Предложенные дополнения языка нелокальных схемных правил расширяют его возможности и перспективы его применения для задания различных преобразований программ.

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

3. Созданная экспериментальная расширяемая система распараллеливания может быть использована для разработки и тестирования методов распараллеливания для различных распределенных архитектур и/или классов задач и для быстрого прототипирования распараллеливающих компиляторов.

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

Использование результатов работы Результаты работы использованы в НИР ЮГИНФО № 1.7.43 «Разработка методов, технологии и специальных программных средств удаленного использования вычислительных ресурсов регионального центра высокопроизводительных вычислений в учебном процессе и научных исследованиях» (выполненную в рамках раздела «Освоение и развитие сетевых технологий нового поколения» подпрограммы «Информационные технологии в системе информационного общества» научной отраслевой программы Минобразования РФ «Научное, научно-методическое, материальнотехническое обеспечение развития технологий информационного общества и индустрии образования»).

Лазарева С.А. Использование многоуровневого внутреннего представления в автоматическом распараллеливании программ для многопроцессорных ЭВМ. — Диссертация на соискание степени к.т.-н.

Апробация результатов работы Основные результаты по теме диссертационной работы докладывались и обсуждались на следующих конференциях и семинарах: Всероссийская школа-семинар "Современные проблемы математического моделирования", Новороссийск, 1997;

Всероссийская научная конференция "Высокопроизводительные вычисления и их приложения", Черноголовка, 2000; Первая и Вторая Всероссийские научнотехнические конференции "Методы и средства обработки информации", Москва, 2003, 2005; Всероссийская научная конференция "Научный сервис в сети Интернет:

технологии распределенных вычислений", Новороссийск, 2005; II, V, IV и VII международные научно-технические конференции "Интеллектуальные и многопроцессорные системы", 2001, 2003, 2004, 2006.

Публикации По теме диссертации опубликовано 14 печатных работ, в том числе 5 статей, включая 1 статью в журнале, рекомендованном ВАК РФ для публикации результатов докторских диссертаций, 5 тезисов докладов на конференциях и 4 публикации в материалах конференций.

Структура и объем работы Диссертация состоит из введения, четырех глав, заключения и приложения, имеются 3 рисунка. Полный объем диссертации – 109 страниц, библиографический список содержит 123 наименования работ отечественных и зарубежных авторов. В приложении приведена грамматика языка нелокальных схемных трансформаций и 2 акта об использовании результатов работы.

СОДЕРЖАНИЕ РАБОТЫ

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

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

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

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

Основными классами современных параллельных архитектур являются машины с общей и распределенной памятью. Наиболее дешевым и потому распространенным вариантом распределенных систем являются кластеры. Многие современные параллельные системы представляют собой гибридные архитектуры. Распространенными классами параллельных систем являются массивно-параллельные компьютеры (MPP), симметричные мультипроцессорные системы (SMP) системы с неоднородным доступом к памяти (NUMA), параллельные векторные системы (PVP). Большинство компьютеров из списка Top 500 являются системами с распределенной памятью или гибридами этой архитектуры, например, векторно-параллельные.

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

Технологии параллельного программирования в целом можно разделить на следующие классы:

Традиционные последовательные языки, расширенные директивами компилятора, новыми конструкциями, дополнительными служебными функциями, специальными переменными окружения (OpenMP, DVM, mpC, параллельные расширения Фортрана – HPF, Vienna Fortran и другие). Параллельные расширения языков существуют для самых разных классов параллельных архитектур.

Использование библиотек параллельных методов, чаще всего для распределенных архитектур (Aztec, LAPACK, PBLAS, ScaLAPACK и другие).

Системы программирования на основе передачи сообщений. Наиболее распространена технология MPI для распределенных машин.

Специальные языки параллельного программирования (Occam, MC#, Тсистема, НОРМА, Adl, Erlang, Linda, Sisal, ZPL и другие).

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

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

В этой области было выполнено множество работ как в бывшем СССР и России, так и за рубежом. Среди исследователей можно отметить Л. Лемпорта, У. Банержи, Р.

Алена, К. Кеннеди, Д. Кука, Д. Падуа, М. Вольфа, В.Е. Котова, В.А. Вальковского, В.В. и Вл.В. Воеводиных и многих других. Для некоторых суперкомпьютеров, в частности, векторных и конвейерных, были созданы коммерческие распараллеливающие компиляторы. Существует несколько весьма эффективных исследовательских инструментальных систем распараллеливания. Тем не менее, на тему распараллеливания ежегодно продолжают появляться десятки работ. Отчасти это обусловлено постоянным появлением новых параллельных архитектур.

Методы распараллеливания можно классифицировать по способу выполнения, уровню распараллеливания, методу выявления параллельного кода.

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

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

Практика показала, что ручное распараллеливание не только значительно более трудоемко, чем автоматическое, но бывает даже менее эффективным.

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

Распараллеливание на уровне операторов и команд выполняют для конвейерных архитектур, а также для VLIW-машин; для этих архитектур существуют эффективные распараллеливатели. В стадии исследований находится Открытая система распараллеливания, ориентированная, в частности, на макроконвейерный суперкомпьютер с программируемой архитектурой, создаваемый в НИИ МВС, Таганрог.

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

Основой распараллеливания является анализ зависимостей по данным. Методом выявления параллелизма на основе анализа индексных выражений были предложены Л. Лемпортом, В.А. Вальковским Очень популярной для анализа возможности распараллеливания является идея различных графов зависимостей по данным (ГЗД). Теория зависимостей по данным сформировалась в работах Д. Кука, У. Банержи, М. Вольфа, Р. Аллена и К. Кеннеди.

Дугами ГЗД являются 4 типа зависимостей: истинная (потоковая), по входу, по выходу и антизависимость, а вершинами — операторы; в европейской и японской школах в качестве вершин рассматривают отдельные вхождения переменных. Направления зависимостей отражают разницу между номерами итераций, порождающих зависимость в цикле. На основе ГЗД и его вариантов было выполнено множество работ по векторизации программ; использовался данный граф и для предварительной оптимизации.

Более удобный анализ зависимостей по управлению совместно с зависимостями по данным можно выполнять по графу программных зависимостей Дж. Ферранте, К.

Оттенштейна и Д. Уоррена.

Академик В.В. Воеводин создал методику распараллеливания на основе анализа решетчатого графа, идея которого была предложена А.П. Ершовым. Решетчатый граф содержит информационные связи 4 типов и строится на основе анализа индексных выражений. Возможность параллельного исполнения определятся путем анализа разверток — функционалов, построенных по коэффициентам решетчатого графа.

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

Решетчатый граф является гораздо более тонким и мощным инструментом анализа зависимостей, чем его предшественники, но более сложен в построении. Формулировки условий преобразований на его основе нетривиальны. Иногда возможность распараллеливания по этому графу проще определить визуально.

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

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

Во втором пункте первой главы рассматриваются средства распараллеливания программ с точки зрения реализуемых ими технологий преобразований программ и возможности расширения диапазона применяемых методов.

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

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

Зарубежные исследования преобразований программ также начались с оптимизации и трансляции. В конце 60-х гг. было заложено направление синтеза программ, иначе называвшееся трансформационным программированием; к началу 80-х в этой области было получено много результатов. В начале 20-го века к области трансформаций программ за рубежом стали причислять многие другие научные направления, от компиляции и суперкомпиляции до реинжениринга программного обеспечения.

Одним из приложений трансформаций является автоматическое распараллеливание программ.

Введем основные понятия из области трансформаций программ. (Заметим, что в этой области отсутствует устоявшаяся терминология.) Трансформация программы — это действие по преобразованию одной программы в другую. Более строго, трансформация (преобразование) программы — это частичное отображение одного формального описания программы в другое. Формальное описание алгоритма или отношения, которые реализуют данное отображение программ, называют правилом трансформации (иногда также трансформацией программы). Языки исходной и целевой программ могут различаться или быть одинаковыми. Для трансформации может быть сформулировано предикатное контекстное условие (условие применимости), которое ограничивает область действия отображения программами определенного класса.

Трансформации программ (правила трансформаций) подразделяются на процедурные и непроцедурные. Процедурное описание преобразования представляет собой алгоритм (программу) получения результата, непроцедурное описание — пару схем заменяемого и заменяющего фрагментов (схемное правило). Под схемой понимают некую модель программы. Чаще всего схема записана на специальном языке трансформаций программ. Мы используем определение схемы как исходного текста программы, параметризованного по некоторым вложенным синтаксическим компонентам.

Преобразование программ согласно правилам трансформации обеспечивается трансформационными системами (системами трансформаций программ, СТП).

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

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

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

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

Большинство средств распараллеливания использует преобразования программ в алгоритмической, процедурной форме. К ним относится и система V-ray Вл.В. Воеводина.

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

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

Распараллеливающая СТП MT1 (университет г. Дельфта) использует правила на параметризованном языке С. Они наглядны, но строго локальны и не могут включать процедурных частей. Условия применимости правил включают условия на графе зависимостей некоторого вида.

Непроцедурные распараллеливающие преобразования, заданные на абстрактном дереве программы, используют системы распараллеливания PARAMAT и ее наследница SPARAMAT. К.Кесслер выявил 150 содержательных шаблонов программирования, ставших основой для правил трансформации. Образцами в правилах служат параметризованные абстрактные синтаксические деревья. Схемные правила допускают нелокальность, но трудны для понимания.

Некоторые универсальные ТС и средства преобразования текстов используют интересные с точки зрения нашей задачи решения.

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

То же самое относится и к регулярным выражениям как средству преобразования произвольных текстов. Регулярные выражения очень похожи на шаблоны на уровне синтаксиса, предоставляют сходные синтаксические средства (например, идентификатор, число, нечто идущее после указанной конструкции, именование найденных фрагментов и т.д.) Но в них нет дополнительной семантической разметки. Например, нельзя найти условный оператор общего вида или оператор вообще, объект определенного типа.

Распространенный и применяемый для задания трансформаций во множестве областей непроцедурный язык Stratego задает преобразования на уровне абстрактного дерева программы. Преобразования могут быть нелокальными, как и в системе PARAMAT, но слишком громоздки.

Чисто синтаксические языки разметки (XML, XSLT) во-первых, задают только локальные преобразования, во-вторых, не учитывают семантику.

Преобразования рассредоточенных в тексте программы, но объединенных по смыслу фрагментов выполняют в аспектно-ориентированном подходе к программированию (АОП). В АОП связанные по смыслу части программы, рассредоточенные в ее тексте, объединяются в аспект, который преобразуется в процессе построения программы или ее сопровождении.

АОП активно развивается и успешно применяется при создании реальных, в том числе коммерческих программных систем.

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

Во второй главе описан язык схемных трансформаций многокомпонентных программных структур и выполненные автором расширения базового языка.

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

Общий вид нелокального схемного правила трансформации следующий:

правило = ‘rule’ имя-правила [ ‘(‘ список-параметров-правила ’)’ ] ‘:’ [ ‘var’ описание-переменных-правила ’;’ ] составной-входной-образец ‘&&’ [ условие-применимости ] ‘=’ составной-выходной-образец Составной образец представляет собой упорядоченный набор простых образцов, связанных общими параметрами либо семантическими отношениями.

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

схемный-образец = ‘’ идентифицирующее-выражение ‘’ : схема.

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

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

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

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

С помощью операций before() и after() можно задать положение идентифицируемой конструкции до или соответственно после аргумента этих операций.

идентифицирующее-выражение = синтакс-тип [‘:’ псевдоним-конструкции] | [синтакс-тип] ( псевдоним-конструкции | ‘$’имя-параметра ) { ‘.’отношение} [ ‘:’ псевдоним-конструкции] | [синтакс-тип] ( ‘before’ | ‘after’ ) '(' ( псевдоним-конструкции | ‘$’имя-параметра ) {‘.’отношение} ')' [‘:’ псевдоним-конструкции ].

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

Те преобразования, вход и выход которых невозможно изобразить ни в виде схем, Отформатировано: Цвет шрифта:

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

Условие применимости — логическое выражение, которое включает кванторы всеобщности и предикаты, зависящие от входных параметров правила. Компоненты условия применимости соединены логическими операциями & ("и"), or ("или"), not ("нет"). В состав условия также входят операции сравнения и проверки на равенство, операции присваивания и арифметические вычисления. Условие применимости включает вычисление выходных параметров правила с помощью предикатов, арифметических выражений и функций.

Применение правила происходит следующим образом:

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

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

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

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

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

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

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

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

1. Простой образец может содержать вложенные вызовы других преобразований.

apply(правило, множество-синтаксических-конструкций) обозначает применение правила в пределах заданных синтаксических конструкций. Правило задается по имени или в виде схем заменяемого и заменяющего фрагментов, если условие применимости отсутствует и эти схемы в сумме не длиннее одной строки.

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

схема-конструкции = $ all параметр-образца in множество $ схемы-конструкций 3. Идентифицирующие выражения могут относиться не только к простому образцу в целом, но и к вложенным в него синтаксическим конструкциям. Таким способом можно задать синтаксический тип, семантические связи, а также псевдоним для синтаксических конструкций внутри образца.

схема-конструкции = идентифицирующее-выражение : схемы-конструкций.

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

схема-конструкции ’{‘ синтакс-тип ’}’.

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

rule имя-правила (параметры-правила):

[var описание переменных правила;] простой-образец && часть1-условия-применимости простой-образец && часть2-условия-применимости простой-образецN && частьN-условия-применимости = составной-выходной-образец 6. Добавлена возможность удаления фрагмента кода путем указания пустого выходного образца.

7. Введена инструкция условной вставки синтаксической конструкции:

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

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

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

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

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

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

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

В качестве языка входной программы выступает ограниченное подмножество Фортрана 77, выходной — Фортран с параллельными конструкциями. Во входном языке отсутствуют подпрограммы и функции, COMMON-блоки, операторы ввода/вывода.

Приведем примеры правил трансформации.

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

label — метка;

var — переменная;

num_expr — числовое выражение;

assign — оператор присваивания;

loop — оператор цикла;

stmt_seq — последовательность операторов;

В условиях применимости приведенных правил использованы следующие базовые предикаты:

nested(L, Nest) — цикл L является вложенным в гнездо циклов Nest.

level(L, Nest, M) — цикл L является циклом вложенности M в гнезде циклов Nest.

no_jumps(L) — нет переходов (goto разных видов) извне внутрь цикла L, а также в теле цикла, передач управления на следующую итерацию и аварийных выходов из цикла.

substmt(S1, S2) — оператор S1 содержится в операторе S2. Это возвратный предикат, то есть при каждом следующем вызове выдает новое возможное значение своего первого параметра, пока все его значения не будут исчерпаны.

stmt_type(S1, Name) — оператор S1 является оператором типа Name (например, do).

dep(S1, S2, Type, Dir) — между операторами S1 и S2 существует зависимость по данным типа Type с вектором направления Dir. Данный предикат задан на графе зависимостей по данным.

full_reachable_c(S1, S2) — S2 достижим по управлению из S1 по любому из путей на управляющем графе, ведущих из S1 в S2.

unchanged_between(v, S1, S2) — переменная v не изменяется на участке программы на всех путях передачи управления от оператора S1 до оператора S2.

linear(expr, id, a, b) — выражение expr линейно относительно переменной id с коэффициентами a и b.

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

Предполагается, что циклы уже нормализованы, т.е. их счетчики целые и нижние границы равны 1.

Распознавание индуктивных переменных. Для нахождения зависимостей по данным индексные выражения массивов должны зависеть только от счетчиков циклов. В индексы массивов могут входить переменные, меняющиеся по закону арифметической прогрессии, не являющиеся счетчиками цикла. Такие переменные называются индуктивными. Индуктивную переменную выражают через счетчик цикла и удаляют из тела цикла. После выхода из цикла индуктивной переменной присваивают правильное значение, если ее значение после выхода из цикла используется (существует потоковая зависимость между оператором присваивания индуктивной переменной значения и некоторым другим оператором ниже по тексту программы).

1 continue Преобразованный фрагмент Выходной параметр do 1 i=1, x(1 * (i – 1) + (n – 1)) = y(i) + z(2*i) 1 continue inc = n stmt_seq sts1, sts2, num_expr Ub, inc_expr;

assign: S2 $id=$inc_expr before(L): S1 ($id =$expr1) && full_reachable_c(S1, loop) & linear(inc_expr, $id, 1, $b) & unchanged_between($id, S1, S2) & no_jumps(L) & $id_v = $b*($Ub) + ($expr1) do $label $i =1 to $Ub apply (($id = $b*($i-1) + ($expr1)), $sts1) apply (($id = $b*$i + ($expr1)), $sts2) $label: continue ) $ if dep(S2, $id, _, flow) $ $id = $id_v Входной образец данного правила состоит из двух конструкций. Первой является характерное ядро — оператор цикла, второй — инициализация индуктивной переменной этого цикла, причем по тексту программы вторая конструкция следует раньше.

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

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

Параллелизация для цикла однократной вложенности. Один из способов использования мультипроцессорности состоит в том, что разные итерации цикла назначают разным процессорам. Такое исполнение цикла называется параллельным (конкуррентным). В различных параллельных расширениях Фортрана независимое исполнение итераций цикла обозначается разными директивами; мы оставим часто употребимое в литературе обозначение doall.

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

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

dep(S1,S1,flow,’=’) — между S1 и S1 существует потоковая зависимость с направлением (=), что не препятствует одновременному выполнению итераций цикла).

rule parallelize1:

var label label, num_expr Ub, stmt_seq body;

loop:L ( do $label $i=1, $Ub && not nested(loop) & not enclosed(loop) & all S1, substmt(S1, $body), S2, substmt(S2, $body), dep(S1, S2,_,’=’) & no_jumps_to($label) = doall $label i=1, $Ub $label: continue Выводы. На дополненном автором языке схемных трансформаций многокомпонентных программных структур удалось представить достаточно широкий класс распараллеливающих преобразований.

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

В рамках данной работы выполнена макетная реализация МСТП в Прологсистеме Eclipse. При построении внутренних представлений программы частично используется (после портирования их автором) код модулей на Arity Prolog, реализованных С.А. Лазаревой.

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

Язык сценариев является суженным подмножеством языка С++, к которому добавлены операции над множествами. Он включает операторы циклов, условные операторы, описания переменных базовых типов, а также типа "множество", операторы применения правил трансформации и вызовы служебных процедур (например, построения графа зависимостей по данным).

Оператор apply_once3 означает применение правила к первой сопоставимой конструкции внутри программы или программной конструкции-аргумента, apply — применение правила до исчерпания возможности (или не будет достигнуто заданное предельное количество проходов), apply_set — асинхронное применение независимого подмножества правил до исчерпания.

Рутинную часть предварительных преобразований (нормализацию циклов и т.п.) следует выполнять автоматически по сценарию, а нетривиальные и нетрадиционные Букатов А.А., Коваль В.В. Методы реализации трансформационной машины в многоцелевой системе преобразований программ // "Искусственный интеллект", журнал Национальной академии наук Украины и Института проблем искусственного интеллекта, 2003, № 3, Донецк: Наука i освiта, С.6-14.

распараллеливающие преобразования удобнее выполнять в режиме советчика или в полностью управляемом пользователем режиме.

Для независимости работы системы от языков входной и выходной программ все манипуляции осуществляются над внутренним представлением, а не над самой программой. Программа хранится в виде абстрактного семантического дерева. Образцы правил трансформации транслируются во внутреннее представление, сопоставимое с внутренним представлением программы — в параметризованные абстрактные семантические деревья. Условия применимости и сценарии применения правил транслируются в текст на языке реализации системы (Пролог). Результат преобразования дерева программы автоматически конвертируется в текст на выходном языке программирования.

Для проверки условий применимости преобразований вычисляется граф зависимостей по данным.

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

Порядок работы с макетом системы распараллеливания:

1) Считывание грамматики входного языка и языка правил.

2) Считывание сценариев.

3) Ввод и синтаксический анализ программы на входном языке и генерация внутреннего представления.

4) Анализ семантического дерева программы и построение графа зависимостей по данным.

3а), 4а) Считывание из файлов сохраненных во время предыдущего сеанса работы данных: внутренних представлений программы, включая граф зависимостей по данным, внутренних представлений правил, а также перечня разрешенных правил для именованного набора фильтров.

5) Запуск сценария преобразования входной программы.

5а) Показ пользователю возможных вариантов преобразования и применение указанных им правил.

6) Перевычисление внутренних представлений после каждого успешно выполненного преобразования или этапа сценария.

7) Генерация текста выходной программы по ее семантическому дереву.

В целом макет МСТП состоит из 1) машины трансформаций внутреннего представления программы, 2) набора правил распараллеливания, 3) модуля анализа зависимостей по данным, 4) модулей, создающих абстрактное внутреннее представление программы и правил и 5) модуля базовых предикатов проверки условий применимости преобразований; эти предикаты в основном специфичны для предметной области (связаны с зависимостями по данным и управлению) 6) переменных окружения, определяющих среду выполнения программы.

Синтаксический анализатор входного языка Синтаксический анализатор Дерево программы зависимостей по Генератор текста на выходном языке Выходная программа Рис. 4. Структура макета МСТП и порядок работы с ним Загрузкой другого набора правил, а также сценария их применения, достигается выбор другой методики распараллеливания. Заменяемыми также являются модули создания внутреннего представления — для настройки на другой язык программирования и модуль анализа зависимостей — в случае изменения методики распараллеливания может потребоваться другой граф зависимостей. Установка переменных окружения также настраивает систему распараллеливания на внешние условия: целевую архитектуру, класс задач и другие требования к выходной программе.

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

Дерево программы состоит из деревьев операторов. Структурой данных, реализующей дерево в макете МСТП, является дерево, хранимое как база вершин дерева.

Каждая вершина дерева представляет собой оператор программы и имеет вид терма:

oper(номер_строки_в_программе, метка, тип_оператора(атрибуты_оператора).

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

При поиске применимого правила трансформации дерево программы проходится в глубину, и для каждой вершины делается попытка унификации для всех правил, применимых на данном шаге сценария.

Глубина рекурсивного спуска ограничена синтаксическими типами асинхронно применяемых правил: не глубже самого "мелкого" синтаксического типа. Например, если все правила преобразуют операторы, то на уровень тела цикла спускаться нужно, а на уровень выражений — нет.

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

Алгоритм унификации параметризованного дерева составного входного образца и абстрактного семантического дерева программы Унификация(составной-входной-образец, поддеререво) Итерация по простым образцам /* Если в правиле несколько входных образцов, то после унификации первого из них найденные значения параметров подставляются в следующие образцы. */ Начало цикла Унификация(простой-образец, поддерево) Итерация по списку операторов и идентифицированных конструкций Если оператор имеет идентифицирующее выражение, проинтерпретировать выражение:

Итерация по цепочке отношений от самого вложенного аргумента Если аргумент — псевдоним, извлечь из памяти обозначаемую им конструкцию программы Если отношение между конструкциями, найти по этой связи конструкцию программы Если before/after, то Если идентифицирующее выражение всего простого образца, просмотр дерева вверх/вниз Иначе проверить выполнимость отношения before/after для идентифицированной конструкции Если идентифицирующее выражение присваивает псевдоним идентифицированной конструкции программы, запомнить псевдоним и конструкцию Унификация(идентифицированная-конструкция, текущее поддерево) Результат процедуры Унификация(конструкция, поддерево) Поддерево образца имеет такой тип, что он не может вхо- Неуспех дить в поддерево программы (например, выражение не может включать оператор) Параметр образца и поддерево; синтаксический тип пара- Успех;

метра такой же или является обобщением типа поддерева параметр = поддереву (например, операторами являются присваивание и цикл).

Синтаксический тип поддерева образца одинаков с типом Унификация всех пар поддерева программы или является его обобщением поддеревьев Для некоторых типов синтаксических конструкций (выра- Особый алгоритм сожений, произвольного числа конструкций заданного типа и поставления последовательности операторов) Процедура сопоставления для произвольного числа конструкций заданного типа и последовательности операторов:

Полагаем пустое значение анонимного параметра Если унификация следующих операторов безуспешна, То добавляем к значению следующую конструкцию заданного типа Если такой конструкции нет, неуспех Конец алгоритма После успешной проверки условия применимости получаем имя правила, список пар из вершин синтаксического дерева образца и вершин семантического дерева программы и список значений входных и выходных параметров (нетерминалов правила).

Рассмотрим пример распараллеливания с помощью набора преобразований распараллеливания и оптимизации по методике Аллена-Кеннеди.

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

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

void classic () { int i;

apply_set (normalize1, normalize2); /* нормализация (стандартизация) циклов */ apply_set (induct1, induct2, induct3); /* удаление индуктивных переменных */ apply wraparound; /* удаление охватывающих переменных */ apply_set(loop_fusion, loop_distribution); /* слияние и разбиение циклов*/ apply interchange; /* перестановка циклов */ apply unfold; /* развертка циклов*/ for (i=1; i MaxNest; i++) apply parallelize(M); /* распараллеливание циклов разной вложенности, начиная с самых внешних и кончая самым глубоким уровнем вложенности в программе */ } Для рассматриваемого примера фрагмента кода будут выполнены следующие преобразования:

Нормализация цикла Распознавание индуктивных переменных (2 прохода) Перестановка циклов Параллелизация для гнезда вложенности Исходный фрагмент После преобразований по сценарию ii= xx(ii,jj,1)= x(ii,j,1) xx(ii,jj,2)= x(ii,j,2) Рассмотрим подробнее наиболее интересный промежуточный шаг — параллелизацию цикла для гнезда вложенности 2.

Для исполнения разных итераций цикла разными процессорами итерации должны быть независимы.

do 10 i_new_5=1, do 10 j_new_1=1, xx(i_new_5, j_new_1,1)= x(i_new_5, 2*j_new_1 – 1,1) по j_new_1 при xx(i_new_5, j_new_1,2)= x(i_new_5, 2*j_new_1 – 1,2) j_new_1 = 1, завиS Условие независимости итераций наружного цикла выполнено, в итоге получим следующий распараллеленный код:

doall 10 i_new_5=1, do 10 j_new_1=1, xx(i_new_5, j_new_1,1)= x(i_new_5, 2*j_new_1 – 1,1) xx(i_new_5, j_new_1,2)= x(i_new_5, 2*j_new_1 – 1,2) 10 continue Выводы. С помощью реализованного автором макета МСТП схемные правила распараллеливания можно применять к последовательной программе. Разработанный набор схемных распараллеливающих преобразований позволяет выполнить невозможное вручную распараллеливание фрагментов программ.

В заключении сформулированы основные результаты исследования.

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

Основные результаты, выносимые на защиту 1. Развитие языка нелокальных схемных трансформаций программ, состоящее в следующем: расширены управляющие конструкции (в частности, разрешены вложенные вызовы других преобразований), введена возможность задания семантических связей и ограничений непосредственно внутри образцов правил, условие применимости правила может быть разбито на части, последовательно проверяемые после сопоставления соответствующих простых образцов.

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

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

4. Модифицированный алгоритм унификации параметризованного дерева правила и семантического дерева программы.

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Букатов А.А., Лазарева С.А., Жегуло О.А. Непроцедурное описание распараллеливающих преобразований программ // Тезисы докладов VII Всероссийской школы-семинара "Современные проблемы математического моделирования". — Ростов-на-Дону, 1997. — С.27 29.

2. Жегуло О.А., Букатов А.А. Непроцедурное описание распараллеливающих преобразований программ в виде схематических трансформаций // Труды Всероссийской научной конференции "Высокопроизводительные вычисления и их приложения", г. Черноголовка, 30 октября – 2 ноября 2000 г. — М.: изд-во Московского университета, 2000. — С.147 150.

3. Жегуло О.А. Представление знаний о методах распараллеливания в экспертной системе поддержки распараллеливания программ // Тезисы докладов международной конференции "Интеллектуальные и многопроцессорные системы", пос.

Дивноморское, 1 6 октября 2001 г. — Таганрог: изд-во ТРТУ, 2001. — С.176 178.

4. Жегуло О.А. Представление знаний о методах распараллеливания в экспертной системе поддержки распараллеливания программ // "Искусственный интеллект", журнал Национальной академии наук Украины и Института проблем искусственного интеллекта. — 2001. — № 3. — Донецк: Наука i освiта. — С.323 330.

5. Жегуло О.А. Непроцедурное представление преобразований программ в системе поддержки распараллеливания // В сб. "Компьютерное моделирование. Вычислительные технологии". — Ростов-на-Дону: изд-во ООО "ЦВВР", 2003. — С.27 40.

6. Жегуло О.А. Методы настройки системы автоматического распараллеливания программ на параметры условий применения // Материалы Международной научно-технической конференции "Интеллектуальные и многопроцессорные системы", пос. Дивноморское, Геленджик, Россия, 22 27 сентября 2003 г., т. 2. — Таганрог: изд-во ТРТУ, 2003. — С.68 70.

7. Жегуло О.А. Методы настройки трансформационной системы автоматического распараллеливания программ на параметры условий применения // "Искусственный интеллект", журнал Национальной академии наук Украины и Института проблем искусственного интеллекта. — 2003. — № 3. — Донецк: Наука i освiта. — С.88 94.

8. Жегуло О.А., Букатов А.А. Представление распараллеливающих преобразований программ в виде схемных правил трансформации // Труды Первой Всероссийской научной конференции, 1 3 октября 2003 г. — М.: Издательский отдел факультета вычислительной математики и кибернетики МГУ, 2003. — С.361 367.

9. Жегуло О.А. Реализация экспериментальной системы распараллеливания на основе макета многоцелевой системы трансформаций программ // Материалы Международной научно-технической конференции "Искусственный интеллект.

Интеллектуальные и многопроцессорные системы", 20 25 сентября 2004 г., т. 1. — Таганрог: изд-во ТРТУ, 2004. — С.249 254.

10. Жегуло О.А. Распараллеливание программ в экспериментальной системе, основанной на макете многоцелевой системы трансформаций программ // "Искусственный интеллект", журнал Национальной академии наук Украины и Института проблем искусственного интеллекта. — 2004. — № 4. — Донецк: Наука i освiта. — С.1 14.

11. Букатов А.А., Жегуло О.А., Коваль В.В. Создание системы поддержки распараллеливания программ, основанной на непроцедурном описании распараллеливающих преобразований // Труды Всероссийской конференции "Научный сервис в сети Интернет: технологии распределенных вычислений", Новороссийск. — М:

изд-во МГУ, 2005. — С.69 71.

12. Жегуло О.А. Экспериментальная система распараллеливания на основе макета многоцелевой системы трансформаций программ // Методы и средства обработки информации. Труды второй Всероссийской научной конференции 5-7 октября 2005 г.. М: Издательский отдел факультета вычислительной математики и кибернетики МГУ, 2005. — С.246 251.

13. Букатов А.А., Жегуло О.А. Методики в основе построения расширяемой системы распараллеливания программ на основе непроцедурных трансформаций программ // Материалы Третьей Международной научной молодежной школы "Высокопроизводительные вычислительные системы", Крым. — Таганрог: изд-во ТРТУ, 2006. — С.239 243.

14. Жегуло О.А. Создание экспериментальной системы поддержки распараллеливания программ на основе макета многоцелевой системы трансформаций программ // Известия вузов. Северо-Кавказский регион. Технические науки. — 2006. — Приложение № 10. — с. 5 13.

В совместной работе [1] автору принадлежит заключение о возможности непроцедурного задания распараллеливающих преобразований программ на основе результатов экспериментов; в работах [2], [8], [11] — разработка правил распараллеливающих трансформаций и использованные в определениях некоторых правил расширения языка нелокальных схемных трансформаций программ. В работе [13] — обзор актуальных близких проектов среди технологий распараллеливания и программирования.



 
Похожие работы:

«ЗАКАСОВСКАЯ Елена Владимировна НЕЙРОСЕТЕВОЕ И АЛГЕБРАИЧЕСКОЕ МОДЕЛИРОВАНИЕ В РАСПРЕДЕЛЕННЫХ ВОЛОКОННО-ОПТИЧЕСКИХ ИЗМЕРИТЕЛЬНЫХ СИСТЕМАХ В УСЛОВИЯХ НЕПОЛНОТЫ ДАННЫХ Специальность: 05.13.18 – Математическое моделирование, численные методы и комплексы программ Автореферат диссертации на соискание ученой степени доктора технических наук ВЛАДИВОСТОК – 2011 Работа выполнена в лаборатории прецизионных оптических методов измерений Института автоматики и процессов управления ДВО РАН...»

«АМАМРА РУШДИ АХМАД РАЗРАБОТКА МЕТОДОВ И АЛГОРИТМОВ ТЕМАТИЧЕСКИ ОРИЕНТИРОВАННОГО РАСПРЕДЕЛЕННОГО ПОИСКА ИНФОРМАЦИИ В ГЛОБАЛЬНЫХ СЕТЯХ ТИПА ИНТЕРНЕТ Специальность 05.13.11 – Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук САНКТ-ПЕТЕРБУРГ 2002 Работа выполнена в Санкт-Петербургском Государственном Техническом Университете. Научный руководитель : доктор...»

«Воронин Егор Ильич РАЗРАБОТКА И ИССЛЕДОВАНИЕ МЕТОДОВ РЕШЕНИЯ ЗАДАЧИ МНОГОСЛОЙНОЙ ГЛОБАЛЬНОЙ ТРАССИРОВКИ СБИС НА ОСНОВЕ МОДЕЛЕЙ АДАПТИВНОГО ПОВЕДЕНИЯ ПРИРОДНЫХ СИСТЕМ 05.13.12 – Системы автоматизации проектирования (вычислительная техника и информатика) АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук Таганрог – 2012 Работа выполнена в Южном федеральном университете Научный руководитель : доктор технических наук, профессор Лебедев Борис...»

«НСАНГУ Мушили Мама РАЗРАБОТКА ВЕРОЯТНОСТНЫХ МОДЕЛЕЙ ДЛЯ АНАЛИЗА ПОКАЗАТЕЛЕЙ ЭФФЕКТИВНОСТИ УСТАНОВЛЕНИЯ СЕССИЙ В МУЛЬТИСЕРВИСНОЙ СЕТИ 05.13.17 – Теоретические основы информатики Автореферат диссертации на соискание ученой степени кандидата физико-математических наук Москва – 2012 Работа выполнена на кафедре систем телекоммуникаций Российского университета дружбы народов Научный руководитель : доктор технических наук, профессор Самуйлов Константин Евгеньевич Официальные...»

«БАЛХАНОВ Василий Карлович МОДЕЛИРОВАНИЕ ГЕОМЕТРИЧЕСКИХ И ЭЛЕКТРИЧЕСКИХ ХАРАКТЕРИСТИК ФИЗИКО - ТЕХНИЧЕСКИХ СРЕД ФРАКТАЛЬНЫМ МЕТОДОМ 05.13.18 –Математическое моделирование, численные методы и комплексы программ АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук Иркутск – 2007 Работа выполнена в Отделе физических проблем при Президиуме Бурятского научного центра Сибирского Отделения РАН, г. Улан-Удэ Научный руководитель : доктор технических наук,...»

«Полстьянов Артем Сергеевич Асимптотический и численный анализ периодических решений одного класса моделей с запаздыванием и диффузией Специальность 05.13.18 – математическое моделирование, численные методы и комплексы программ АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук Ярославль – 2012 Работа выполнена на кафедре математического моделирования федерального государственного бюджетного образовательного учреждения высшего...»

«Герасимов Дмитрий Николаевич СИНТЕЗ АДАПТИВНЫХ И ОБУЧАЮЩИХСЯ СИСТЕМ УПРАВЛЕНИЯ ИНЖЕКТОРНЫМИ ДВИГАТЕЛЯМИ ВНУТРЕННЕГО СГОРАНИЯ Специальность 05.13.01 Системный анализ, управление и обработка информации (в технических системах) Автореферат диссертации на соискание ученой степени кандидата технических наук Санкт-Петербург 2009 г. 2 Работа выполнена в Санкт-Петербургском государственном университете информационных технологий, механики и оптики. Научный руководитель : д.т.н.,...»

«Попов Александр Игоревич МАТЕМАТИЧЕСКИЕ МОДЕЛИ И КОМПЛЕКС ПРОГРАММ ДЛЯ ФУНКЦИОНАЛЬНОЙ ДИАГНОСТИКИ БИОМЕДИЦИНСКИХ СИГНАЛОВ ИНФРАНИЗКОЧАСТОТНОГО ДИАПАЗОНА Специальность: 05.13.18 – Математическое моделирование, численные методы и комплексы программ АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук Петрозаводск – 2010 Работа выполнена в Поморском государственном университете имени М.В. Ломоносова. Научный руководитель : доктор технических наук,...»

«Лузгачев Михаил Васильевич Методы анализа вероятностных характеристик модели разделения ресурсов мультисервисной телекоммуникационной сети 05.13.17 – теоретические основы информатики Автореферат диссертации на соискание ученой степени кандидата физико-математических наук Москва – 2010 Работа выполнена на кафедре систем телекоммуникаций Российского университета дружбы народов Научный руководитель доктор технических наук, профессор Самуйлов Константин Евгеньевич Официальные...»

«ЛЫКОВ Иван Александрович Режимы с обострением процессов переноса в атмосфере: особенности математического и численного моделирования методами нелинейной динамики Специальность 05.13.18 Математическое моделирование, численные методы и комплексы программ АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук Екатеринбург 2013 Работа выполнена на кафедре общей и молекулярной физики и в секторе нелинейной динамики НИИ Физики и прикладной...»

«Корныхин Евгений Валерьевич Построение тестовых программ для проверки подсистем управления памяти микропроцессоров 05.13.11 – математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук Москва – 2010 Работа выполнена на кафедре системного программирования факультета вычислительной математики и...»

«Зорин Кирилл Михайлович МОДЕЛЬ И МЕТОДИКА РЕКОНФИГУРАЦИИ ЛОГИЧЕСКОЙ СТРУКТУРЫ ИНТЕГРИРОВАННОЙ ИНФОРМАЦИОННОЙ СИСТЕМЫ Специальность 05.13.01 Системный анализ, управление и обработка информации (технические системы) АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук Санкт-Петербург 2010 Работа выполнена в Санкт-Петербургском государственном электротехническом университете ЛЭТИ им. В. И. Ульянова (Ленина). Научный руководитель : доктор технических...»

«ГИБАДУЛЛИН Руслан Фаршатович СИСТЕМА БАЗ ДАННЫХ КАРТОГРАФИИ С АССОЦИАТИВНОЙ ЗАЩИТОЙ Специальность: 05.13.19 – Методы и системы защиты информации, информационная безопасность АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук Уфа – 2011 Работа выполнена на кафедре компьютерных систем ГОУ ВПО Казанский государственный технический университет им. А. Н. Туполева Научный руководитель д-р физ.-мат. наук, проф. Райхлин Вадим Абрамович Официальные...»

«Климачкова Татьяна Сергеевна ИССЛЕДОВАНИЕ ТЕХНИЧЕСКОЙ УСТОЙЧИВОСТИ И ПРЕДЕЛЬНЫХ СВОЙСТВ УПРАВЛЯЕМЫХ ДИНАМИЧЕСКИХ СИСТЕМ Специальность 05.13.01 – Системный анализ, управление и обработка информации Автореферат диссертации на соискание ученой степени кандидата физико-математических наук Москва – 2009 Работа выполнена в Российской открытой академии транспорта Московского государственного университета путей сообщения Научный руководитель : доктор физико-математических наук...»

«Нагоев Залимхан Вячеславович Методы принятия решений и управления в неструктурированных задачах на основе самоорганизующихся мультиагентных рекурсивных когнитивных архитектур Специальность – 05.13.01 – Системный анализ, управление и обработка информации (вычислительная техника и информатика) Автореферат диссертации на соискание ученой степени доктора технических наук Нальчик – 2013 Диссертация выполнена в ФГБУН Институт информатики и проблем регионального управления...»

«Иванников Александр Фёдорович МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ ВЗАИМОДЕЙСТВИЯ ЭЛЕКТРОМАГНИТНОГО ИЗЛУЧЕНИЯ С ДИСПЕРСНЫМИ ЧАСТИЦАМИ Специальность: 05.13.18 – Математическое моделирование, численные методы и комплексы программ АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата физико-математических наук Москва 2009 2 Работа выполнена в ГОУ ВПО Тверском государственном техническом университете Научный руководитель : кандидат физико-математических наук, доцент Кривенко...»

«Хуршудян Смбат Размикович Оптимизация режимов ПГУ при участии ее в регулировании мощности и частоты в энергосистеме (на примере ПГУ-450) Специальность 05.13.06 Автоматизация и управление технологическими процессами и производствами (по отраслям: энергетика) АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук Москва – 2014 Работа выполнена в Национальном исследовательском университете МЭИ на кафедре Автоматизированных систем управления тепловыми...»

«Гинзгеймер Сергей Александрович МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ ПРОЦЕССОВ ТЕПЛОПЕРЕДАЧИ В СИСТЕМАХ КОНТАКТИРУЮЩИХ СТЕРЖНЕЙ 05.13.18 – математическое моделирование, численные методы и комплексы программ АВТОРЕФЕРАТ диссертации на соискание степени кандидата физико-математических наук Тула – 2006 2 Работа выполнена на кафедре программного обеспечения ЭВМ, информационных технологий и прикл адной математики Калужского филиала Московского государственного технического университета...»

«Станкевич Андрей Сергеевич Методология и технические решения для проведения олимпиад по информатике и программированию Специальность 05.13.06 — Автоматизация и управление технологическими процессами и производствами (образование) АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук Санкт-Петербург 2011 Работа выполнена на кафедре Компьютерные технологии в СанктПетербургском национальном исследовательском университете информационных технологий,...»

«РАДЧЕНКО СЕРГЕЙ АЛЕКСЕЕВИЧ ФОРМИРОВАНИЕ И ПОЗИЦИОНИРОВАНИЕ СИСТЕМЫ ОРГАНИЗАЦИОННО-УПРАВЛЕНЧЕСКОГО ПОВЕДЕНИЯ В МНОГОПРОФИЛЬНОЙ КОМПАНИИ Специальность: 05.13.10 – Управление в социальных и экономических системах (экономические наук и) АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата экономических наук Ростов-на-Дону – 2007 Диссертация выполнена в ГОУ ВПО Ростовский государственный университет путей сообщения Научный руководитель : доктор технических наук, профессор...»








 
© 2013 www.diss.seluk.ru - «Бесплатная электронная библиотека - Авторефераты, Диссертации, Монографии, Методички, учебные программы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.