авторефераты диссертаций БЕСПЛАТНАЯ РОССИЙСКАЯ БИБЛИОТЕКА - WWW.DISLIB.RU

АВТОРЕФЕРАТЫ, ДИССЕРТАЦИИ, МОНОГРАФИИ, НАУЧНЫЕ СТАТЬИ, КНИГИ

 
<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:   || 2 | 3 | 4 |

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

-- [ Страница 1 ] --

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

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

ИССЛЕДОВАНИЕ И РЕАЛИЗАЦИЯ
Непроцедурных преобразований программ
для построения расширяемой системы
распараллеливания

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

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

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

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

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

Букатов Александр Алексеевич

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

Бабенко Людмила Климентьевна

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

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

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

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

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

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

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

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

кандидат физико-математических наук,

доцент Муратова Галина Викторовна

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

Актуальность темы

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

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

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

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

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

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

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

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

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

Цель и задачи диссертационной работы

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

  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-машин; для этих архитектур существуют эффективные распараллеливатели. В стадии исследований находится Открытая система распараллеливания, ориентированная, в частности, на макроконвейерный суперкомпьютер с программируемой архитектурой, создаваемый в НИИ МВС, Таганрог.

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



Pages:   || 2 | 3 | 4 |
 





 
© 2013 www.dislib.ru - «Авторефераты диссертаций - бесплатно»

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