WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!

Pages:     |
|
Московский государственный университет им. М.В. Ломоносова

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

Сальников Алексей Николаевич СИСТЕМА РАЗРАБОТКИ И ПОДДЕРЖКИ ИСПОЛНЕНИЯ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ Специальность 05.13.11 – математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

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

Москва – 2007

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

Научные руководители: член-корреспондент РАН, профессор Королёв Лев Николаевич;

к.ф.-м.н., доцент Попова Нина Николаевна.

Официальные оппоненты: д.ф. - м.н. Крюков Виктор Алексеевич, Институт прикладной математики РАН;

к. ф. -м.н. Антонов Александр Сергеевич, Научно-исследовательский вычислительный центр МГУ им. М.В. Ломоносова

Ведущая организация: Институт системного программирования РАН

Защита диссертации состоится «16» февраля 2007 г. в 11.00 часов на заседании диссертационного совета Д 501.001.44 в Московском государственном университете им. М.В. Ломоносова по адресу: 119992 ГСП-2 Москва, Ленинские горы, МГУ им. М.В. Ломоносова, 2-й учебный корпус, факультет ВМиК, аудитория 685.

С диссертацией можно ознакомиться в библиотеке факультета ВМиК МГУ. С текстом автореферата можно ознакомиться на официальном сайте ВМиК МГУ им. М.В. Ломоносова http://www.cmc.msu.ru в разделе «Наука» – «Работа диссертационных советов» – «Д 501.001.44».

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

Учёный секретарь диссертационного совета профессор Н.П. Трифонов 2

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

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

Наиболее популярный способ написания параллельных программ – это создание параллельного программного кода с использованием таких библиотек, как MPI для кластеров и систем с распределённой памятью, а также OpenMP для SMP систем. Эти библиотеки позволяют создавать параллельные программы, которые способны выполняться на многопроцессорных системах с различными архитектурами. Однако добиться переносимости параллельной программы, с точки зрения сохранения эффективности, значительно сложнее. Для этого требуются некоторые навыки в «искусстве программирования» и трудоёмкий предварительный анализ исходного алгоритма для выявления возможностей по распараллеливанию на определённой архитектуре.

Всё сказанное выше и сложность учёта всех особенностей многопроцессорной системы оправдывает создание высокоуровневых средств параллельного программирования, базирующихся на MPI, OpenMP, pthread и облегчающих создание параллельных программ, с учётом особенностей многопроцессорных систем. К таким средствам можно отнести DVM, Cilk, PETSc, mpC и предлагаемый в данной работе «PARUS».

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

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

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

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

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

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

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

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

Практическая применимость и эффективность созданной системы разработки и исполнения параллельных программ «PARUS» показана на примере решения ряда модельных и актуальных практических задач, в том числе задач биоинформатики, на современных параллельных вычислительных системах. (IBM pSeries 690, МВС-1000м и др.) Система «PARUS», построенная на основе технологии MPI, оформлена как проект с открытым исходным кодом и доступна в Internet ( http://parus.sf.net ).

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

Апробация работы и публикации По теме диссертации опубликовано 12 печатных работ. Результаты диссертации докладывались на объединённом научно-исследовательском семинаре кафедр Автоматизации систем вычислительных комплексов, Алгоритмических языков и Системного программирования ВМиК МГУ под руководством проф. Шура-Бура М.Р., на семинарах факультета ВМиК и научных конференциях:

1. Международный семинар «Супервычисления и математическое моделирование», Российский федеральный ядерный центр – Всероссийской НИИ экспериментальной физики, Саров, 17-21 июня 2002.

2. Всероссийская научная конференция «Научный сервис в сети Интернет», Новороссийск, Россия, 2004.

3. The Fourth International Conference on Bioinformatics of Genome Regulation and Structure (BGRS'2004). Novosibirsk, Russia, July 25-30, 2004.

4. Международная научная конференция студентов, аспирантов и молодых ученых «Ломоносов – 2004», Москва, Россия.

5. Всероссийская научная конференция «Методы и средства обработки информации», Москва, Россия, 2005.

6. Всероссийская научная конференция «Научный сервис в сети Интернет», г. Новороссийск, 19-24 сентября 2005.

7. 13th European PVMMPI Users' Group Meeting (Euro PVM/MPI 2006). Bonn, Germany, September 17-20, 2006.

Структура и объём работы Диссертация состоит из семи глав, где первая глава – введение, списка литературы и четырёх приложений. Объём диссертации – 90 страниц. Список цитируемой литературы включает 81 наименование.

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

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

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

Вторая глава посвящена обзору некоторых известных высокоуровневых средств параллельного программирования. Здесь обсуждаются: DVM-система, созданная в Институте прикладной математики им. М.В. Келдыша РАН, Т-система, основывающаяся на парадигме функционального программирования для обеспечения динамического распараллеливания программ и язык программирования mpC, созданный в институте системного программирования РАН.

В той же главе рассказывается о преимуществах подхода, изложенного в диссертации. В DVM исходный код программы дополняется специальными конструкциями, которые оформлены невидимым образом для компилятора с «чистого» языка программирования, следовательно, предполагается, что для решения соответствующей задачи должна быть создана последовательная программа. В «PARUS» не требуется реализация последовательной программы. Рассмотренные выше системы учитывают гетерогенность с точки зрения производительности процессоров, однако производительность коммуникаций учитывается в недостаточной степени. В разделе диссертации (глава 6), посвящённом тестированию коммуникационной среды, показано, насколько сложно могут себя вести коммуникации в зависимости от варьирования некоторых параметров при передаче данных.

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

На основе результатов тестирования, проведённого с использованием предложенных в «PARUS» средств тестирования, осуществляется балансировка нагрузки на отдельные компоненты многопроцессорной системы с учётом нелинейности скорости передачи данных по коммуникациям от объёма передаваемых данных.

В «PARUS» присутствует анализатор зависимостей по данным. Этот анализатор можно считать прототипом средства для автоматического распараллеливания C-программы. В T-системе допускается наличие только так называемых «чистых функций», то есть функций без побочных эффектов. В отличие от T-системы, где граф строится неявно, в «PАRUS» граф строится явно. Достоинство заключается в том, что разработчик параллельной программы может определять степень параллелизма в программе; определять, насколько вычислительно сложной делать отдельную вершину.

В mpC для задания гетерогенности нужно явно указывать долю вычислений, которая будет помещена на процессор. В «PARUS» производительность процессоров определяется на этапе тестирования многопроцессорной системы, и доля вычислений определяется автоматически в процессе назначения заданий процессорам.

Третья глава посвящена обзору алгоритмов планирования вычислений на многопроцессорных системах. Здесь приводится постановка задачи планирования вычислений. Рассматриваются списочные алгоритмы; алгоритм, основанный на множестве очередей; алгоритм имитации отжига; генетический алгоритм; алгоритм поиска критического пути; алгоритм обратного заполнения; алгоритм управления группами работ с прерываниями. Анализ стратегий планирования показал, что в «PARUS» целесообразно использовать списочные алгоритмы и генетический алгоритм. В текущей реализации в «PARUS» представлено 3 алгоритма планирования вычислений. Все три алгоритма реализованы таким образом, чтобы учитывать гетерогенность многопроцессорной системы как с точки зрения производительности процессоров, так и с точки зрения коммуникаций.

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

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

Второй алгоритм динамически, уже в процессе исполнения параллельной программы, распределяет работы по MPI-процессам. Данный алгоритм можно отнести к классу списочных алгоритмов. Он является совмещением RR алгоритма с алгоритмом назначения кратчайшей работы вперёд. Основное преимущество такого алгоритма заключается в скорости его срабатывания и низкой вычислительной сложности, что очень важно для назначения работ на процессоры в динамике. Идея этого алгоритма близка к идее алгоритма Backfill. Также как и Backfill, он стремится полностью заполнить многопроцессорную систему работами.

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

В четвёртой главе обсуждаются принципы организации системы «PARUS». На вход системе «PARUS» поступает либо ориентированный ациклический граф, либо C-программа, которая затем всё равно преобразуется в ориентированный граф. Алгоритм решаемой задачи представляется в виде ориентированного графа, где в вершинах сосредоточены вычислительные операции (действия над данными), а рёбра задают зависимость по данным.

Таким образом, программа описывается как сеть из вершин-истоков, в которых чаще всего происходит чтение входных данных из файлов, внутренних вершин, где происходит обработка данных, а также вершин-стоков, в которых обычно происходит запись результатов в файлы. С точки зрения эффективности выполнения построенный таким образом граф должен обладать некоторыми особенностями. Вершины графа должны являться полновесными, «тяжёлыми» в вычислительном смысле фрагментами кода. Граф выстраивается по уровням. Номер уровня вершины в графе – максимальная длина пути от вершин истоков до текущей вершины. Вершины графа на каждом уровне независимы между собой и могут быть исполнены параллельно. Таким образом, определённый выше граф задаёт граф-программу.

Pages:     |
|



© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

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