Lecture_DVM_1 (1158298), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

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

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

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

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

Обобщение и стандартизация моделей параллелизма по данным привели к созданию в 1993 году стандарта HPF (High Performance Fortran) - расширения языка Фортран 90. Аналогичные расширения были предложены для языка Си и Си++.

Краткий обзор возможностей HPF.

Как уже было сказано выше, прежде всего программист должен распределить данные между процессорами. Это распределение производится в два этапа. Сначала с помощью директивы ALIGN задается соответствие между взаимным расположением элементов нескольких массивов, а затем вся эта группа массивов с помощью директивы DISTRIBUTE отображается на решетку процессоров. Это отображение, например, может осуществляться следующим образом: каждый массив разрезается несколькими гиперплоскостями на секции примерно одинакового объема, каждая из которых будет расположена на своем процессоре. Заданное распределение данных может быть изменено на этапе выполнения программы с помощью операторов REALIGN и REDISTRIBUTE.

В HPF реализуется параллелизм следующих конструкций языка Фортран 90/95: операции над секциями массивов, DO циклы, оператор и конструкция FORALL.

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

Оператор и конструкция FORALL могут рассматриваться как обобщение и расширение операций над секциями массивов.

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

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

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

2.3. Гибридная модель параллелизма по управлению с передачей сообщений. OpenMP+MPI

Модель параллелизма по управлению (в западной литературе используется и другое название – модель разделения работы, work-sharing model) возникла уже давно как модель программирования для мультипроцессоров. На мультипроцессорах в качестве модели выполнения используется модель общей памяти. В этой модели параллельная программа представляет собой систему нитей, взаимодействующих посредством общих переменных и примитивов синхронизации. Нить (по-английски ”thread”) – это легковесный процесс, имеющий с другими нитями общие ресурсы, включая общую оперативную память.

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

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

Однако, спустя несколько лет ситуация сильно изменилась. Во-первых, успехи в развитии элементной базы сделали очень перспективным и экономически выгодным создавать мультипроцессоры. Во-вторых, широкое развитие получили мультикомпьютеры с DSM (distributed shared memory - распределенная общая память), позволяющие программам на разных узлах взаимодействовать через общие переменные также, как и на мультипроцессорах (Convex Exemplar, HP 9000 V-class, SGI Origin 2000). В-третьих, не оправдались надежды на то, что HPF станет фактическим стандартом для разработки вычислительных программ.

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

Краткий обзор возможностей OpenMP

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

Программа начинает свое выполнение как один процесс, называемый главной нитью. Главная нить выполняется последовательно, пока не встретится первая параллельная область программы. Параллельная область определяется парой директив PARALLEL и END PARALLEL. При входе в параллельную область главная нить порождает некоторое число подчиненных ей нитей, которые вместе с ней образуют текущую группу нитей. Все операторы программы, находящиеся в параллельной конструкции, включая и вызываемые изнутри нее процедуры, выполняются всеми нитями текущей группы параллельно, пока не произойдет выход из параллельной области или встретится одна из конструкций распределения работы - DO, SECTIONS или SINGLE.

Конструкция DO служит для распределения витков цикла между нитями, конструкция SECTIONS – для распределения между нитями указанных секций программы, а конструкция SINGLE указывает секцию, которая должна быть выполнена только одной нитью.

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

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

При параллельной области можно указать классы используемых в ней переменных (общие или приватные).

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

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

Интересно, что подход OpenMP является диаметрально противоположным к подходу HPF:

• Вместо параллелизма по данным – параллелизм по управлению;

• Вместо изощренного статического анализа для автоматического поиска операторов, способных выполняться параллельно – явное и полное задание параллелизма программистом;

• Вместо языка, требующего специального HPF-компилятора даже для работы на последовательной ЭВМ – язык, позволяющий на последовательной ЭВМ компилироваться и выполняться в стандартной среде языка Фортран.

Объединение подходов OpenMP и MPI

Успешное внедрение OpenMP на мультипроцессорах и DSM-мультикомпьютерах резко активизировало исследования, направленные на поиски путей распространения OpenMP на мультикомпьютеры, кластеры и сети ЭВМ. Эти исследования сосредоточились, в основном, на двух направлениях:

• Расширение языка средствами описания распределения данных;

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

Первое направление представляется гораздо более перспективным для кластеров и сетей ЭВМ, однако трудно ожидать появления в ближайшие годы время стандарта нового языка (расширенного OpenMP).

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

Такой подход имеет преимущества с точки зрения упрощения программирования в том случае, когда в программе есть два уровня параллелизма – параллелизм между подзадачами и параллелизм внутри подзадачи. Такая ситуация возникает, например, при использовании многообластных (многоблочных) методов решения вычислительных задач. Программировать на MPI сами подзадачи гораздо сложнее, чем их взаимодействие, поскольку распараллеливание подзадачи связано с распределением элементов массивов и витков циклов между процессами. Организация же взаимодействия подзадач таких сложностей не вызывает, поскольку сводится к обмену между ними граничными значениями. Нечто подобное программисты делали раньше на однопроцессорных ЭВМ, когда для экономии памяти на каждом временном шаге выполняли подзадачи последовательно друг за другом.

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

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

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

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

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

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

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

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

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

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

Большое влияние на разработку этого подхода оказали работы по языку Fortran D [15], по языку PCF Fortran, а также участие авторов в создании управляемой виртуальной памяти для ЭВМ БЭСМ-6 [16].

Краткий обзор возможностей языков Fortran-DVM и C-DVM

Программа на языках Fortran-DVM и C-DVM, помимо описания алгоритма обычными средствами языков Фортран 77 или Си, содержит правила параллельного выполнения этого алгоритма.

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

• распределение элементов массива между процессорами;

• распределение витков цикла между процессорами;

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

• организация эффективного доступа к удаленным (расположенным на других процессорах) данным;

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

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

Характеристики

Список файлов лекций