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

кафедра системного программирования

ДИПЛОМНАЯ РАБОТА

Тема: “Предсказание характеристик выполнения DVM-программ”

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

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

Крюков Виктор Алексеевич

Введение.

Важность параллельных программ.

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

Проблемы разработки параллельных программ.

Трудность написания.

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

Функциональная отладка.

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

Отладка эффективности.

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

Глава 1. Параллельные программы и предсказание их выполнения

Модели параллельного программирования

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

Рассмотрим основные модели параллельного программирования:

Модель передачи сообщений. MPI.

В модели передачи сообщений параллельная программа представляет собой множество процессов, каждый из которых имеет собственное локальное адресное пространство. Взаимодействие процессов - обмен данными и синхронизация - осуществляется посредством передачи сообщений. Обобщение и стандартизация различных библиотек передачи сообщений привели в 1993 году к разработке стандарта MPI (Message Passing Interface). Его широкое внедрение в последующие годы обеспечило коренной перелом в решении проблемы переносимости параллельных программ, разрабатываемых в рамках разных подходов, использующих в качестве модели выполнения модель передачи сообщений.

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

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

Модель параллелизма по данным. HPF.

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

Модель параллелизма по данным имеет следующие достоинства.

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

Модель параллелизма по управлению. OpenMP.

Эта модель возникла уже давно как естественная альтернатива явному использованию модели общей памяти при разработке программ для мультипроцессоров. Вместо программирования в терминах нитей предлагалось расширить языки специальными управляющими конструкциями – параллельными циклами и параллельными секциями. Создание и уничтожение нитей, распределение между ними витков параллельных циклов или параллельных секций (например, вызовов процедур) – все это брал на себя компилятор. Первая попытка стандартизовать такую модель привела к появлению в 1990 году проекта языка PCF Fortran (проект стандарта X3H5). Однако этот проект тогда не привлек широкого внимания и, фактически, остался только на бумаге. Возможно, что причиной этого было снижение интереса к мультипроцессорам и всеобщее увлечение мультикомпьютерами и HPF.

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

Крупнейшие производители компьютеров и программного обеспечения объединили свои усилия и в октябре 1997 года выпустили описание языка OpenMP Fortran – расширение языка Фортран 77. Позже вышли аналогичные расширения языков Си и Фортран 90/95.

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

Модель параллелизма по данным и управлению. DVM.

Эта модель, положенная в основу языков параллельного программирования Фортран-DVM и Си-DVM, объединяет достоинства модели параллелизма по данным и модели параллелизма по управлению. Базирующаяся на этих языках система разработки параллельных программ (DVM) создана в Институте прикладной математики им. М.В. Келдыша РАН.

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

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

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

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

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

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