Московский Государственный Университет им. М. В. Ломоносова

Факультет Вычислительной Математики и Кибернетики

Кафедра Системного Программирования

Введение в дипломную работу

Диалоговая оболочка системы автоматизации распараллеливания программ

Выполнила:

студентка 528 группы

Кулешова Е.И.

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

профессор, д. ф.-м. н.

Крюков В. А.

Москва, 2004

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

Можно выделить два основных типа архитектур параллельных вычислительных систем: с общей памятью и с распределенной памятью. К системам с общей памятью относятся компьютеры с SMP архитектурой, различные разновидности NUMA систем и мультипроцессорные векторно-конвейерные компьютеры. Характерным словом для этих компьютеров является “единый”: единая оперативная память, единая операционная система, единая подсистема ввода-вывода. Только процессоры образуют множество. Для распараллеливания программ используется механизм порождения нитей – легковесных процессов, для которых не создается отдельного адресного пространства. Нити на многопроцессорных системах распределяются по процессорам.

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

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

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

Существует множество реализаций механизма передачи сообщений, независимых от конкретной платформы. Наиболее известными из них являются EXPRESS компании Parasoft и коммуникационная библиотека PVM (Parallel Virtual Machine), разработанная в Oak Ridge National Laboratory. В 1994 г. был принят стандарт механизма передачи сообщений MPI (Message Passing Interface). Основная цель, которую ставили перед собой разработчики MPI, – это обеспечение полной независимости приложений, написанных с использованием MPI, от архитектуры многопроцессорной системы без какой-либо существенной потери производительности. По замыслу авторов это должно было стать мощным стимулом для разработки прикладного программного обеспечения и стандартизованных библиотек подпрограмм для многопроцессорных систем с распределенной памятью. Реализации MPI успешно работают не только на классических MPP системах, но также на SMP системах и на сетях рабочих станций (в том числе и неоднородных).

MPI – это библиотека функций, обеспечивающая взаимодействие параллельных процессов с помощью механизма передачи сообщений. Поддерживаются интерфейсы для языков C и FORTRAN. В последнее время добавлена поддержка языка C++. Библиотека включает в себя множество функций передачи сообщений типа точка-точка, развитый набор функций для выполнения коллективных операций и управления процессами параллельного приложения. Основное отличие MPI от предшественников в том, что явно вводятся понятия групп процессов, с которыми можно оперировать как с конечными множествами, а также областей связи и коммуникаторов, описывающих эти области связи. Это предоставляет программисту очень гибкие средства для написания эффективных параллельных программ. В настоящее время MPI является основной технологией программирования для многопроцессорных систем с распределенной памятью.

Несмотря на значительные успехи в развитии технологии программирования с использованием механизма передачи сообщений, трудоемкость программирования с использованием этой технологии все-таки слишком велика. Альтернативный подход предоставляет парадигма параллельной обработки данных, которая реализована в языке высокого уровня HPF. От программиста требуется только задать распределение данных по процессорам, а компилятор автоматически генерирует вызовы функций синхронизации и передачи сообщений (модель параллелизма по данным). Для распараллеливания циклов используются либо специальные конструкции языка, либо директивы компилятору, задаваемые в виде псевдокомментариев. Язык HPF реализует идею инкрементального распараллеливания и модель общей памяти на системах с распределенной памятью. Эти два обстоятельства и определяют простоту программирования и соответственно привлекательность этой технологии. Одна и та же программа, без какой-либо модификации, должна эффективно работать как на однопроцессорных системах, так и на многопроцессорных вычислительных системах.

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

Писать параллельные программы с использованием библиотеки MPI довольно трудоемкая задача. MPI можно назвать языком ассемблера параллельного программирования. Одним из средств, облегчающих написание параллельных программ, как раз и являются языки C-DVM и FORTRAN-DVM.

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

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

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

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

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

ParaWise – это система, разработанная Computational Mechanics software для распараллеливания последовательных программ на языках FORTRAN 77 и FORTRAN 90. ParaWise может генерировать код параллельной программы, содержащий вызовы функций библиотеки MPI и/или директивы Open MP. Для распараллеливания последовательной программы ParaWise производит анализ ее кода. ParaWise активно взаимодействует с пользователем в процессе распараллеливания. Код, генерируемый системой ParaWise, отличается от исходного только тем, что в него добавлены вызовы функций библиотеки MPI или директивы OpenMP.

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

Основные три возможности ввода пользовательской информации:

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

2. Вопросы к пользователю в ходе анализа (предполагаются так же варианты ответа)

3. Ключевые вопросы (связаны с обнаружением зависимостей)

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