автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Гибридная модель параллельного программирования DVM/OpenMP

Российская академия наук Институт прикладной математики им М В. Келдыша

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

Бахтин Владимир Александрович

Гибридная модель параллельного программирования БУМ/ОрепМР

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

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

□03168883

Москва - 2008 год

003168883

Работа выполнена в Институте прикладной математики им МВ Келдыша РАН

Научный руководитель - доктор физико-математических наук Крюков Виктор Алексеевич

Официальные оппоненты

- доктор физико-математических наук, член-корреспондент РАН Воеводин Владимир Валентинович,

- кандидат физико-математических наук Ефимкин Кирилл Николаевич

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

Защита состоится «10» июня 2008 г в 11 часов на заседании Диссертационного совета Д 002 024 01 в Институте прикладной математики им МВ Келдыша РАН по адресу 125047, Москва, Миусская пл, 4.

С диссертацией можно ознакомиться в библиотеке Института прикладной математики им МВ Келдыша РАН

Автореферат разослан «7» мая 2008 г Ученый секретарь диссертационного совета,

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

ТА Полилова

Общая характеристика работы Объект исследования и актуальность темы

Последние годы связаны с резким изменением направления развития процессоров - появлением многоядерных и многопоточных процессоров Их эффективное использование требует повсеместного перехода с последовательных программ на параллельные программы Для высокопроизводительных вычислений на кластерах и многопроцессорных ЭВМ с массовым параллелизмом (МРР) теперь требуется более глубокое распараллеливание, обеспечивающее, по крайней мере, два уровня параллелизма - уже привычный параллелизм между узлами кластера и дополнительный параллелизм между ядрами в узле В настоящее время такой двухуровневый параллелизм наиболее легко и естественно выражать посредством использования между узлами модели передачи сообщений MPI, а внутри узлов - модели общей памяти Pthreads, или более высокоуровневой и более подходящей для вычислительных программ модели ОрепМР Однако, необходимость более глубокого распараллеливания и использования гибридной модели MPI/OpenMP, т е двух разных моделей программирования и соответствующих им разных инструментальных средств еще более усложняет и без того нелегкую работу по созданию параллельных программ Поэтому проблема автоматизации создания параллельных программ становится в настоящее время чрезвычайно актуальной

В 1994 году в ИПМ им M В Келдыша РАН была предложена новая модель (DVM-модель) параллельного программирования, позволившая существенно автоматизировать разработку MPI-программ для кластеров Однако широкое распространение SMP-кластеров (кластеров, использующих в качестве узлов мультипроцессоры) требовало расширения DVM-модели для более эффективного использования их двухуровневого параллелизма

Цель работы

Целью данной работы являлась разработка гибридной модели DVM/OpenMP, которая позволит упростить создание программ для параллельных систем на базе многоядерных процессоров

Научная новизна работы

Предложена новая модель и новый язык параллельного программирования - гибридная модель DVM/OpenMP и язык Fortran-DVM/OpenMP, позволяющие разрабатывать эффективные, переносимые программы для SMP-кластеров и высокопроизводительных систем с многоуровневым параллелизмом

Разработан компилятор, преобразующий параллельные программы на языке Fortran-DVM/OpenMP в программы на стандартном языке Fortran ОрепМР, выполняющиеся в узлах SMP-кластера и взаимодействующие между собой посредством MPI

Практическая значимость

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

Разработанный язык и компилятор используются на факультете ВМиК МГУ при проведении практикума по технологиям параллельного программирования, а также служат базой для распараллеливающего компилятора с языка Фортран, создаваемого в рамках программы Союзного государства "ТРИАДА", и системы автоматизации распараллеливания Фортран-программ, создаваемой в рамках программы №14 Президиума РАН

Апробация работы и публикации

Основные результаты диссертации были доложены на российских и международных научных конференциях и семинарах [1, 2, 3, 4, 6] и опубликованы в трудах этих конференций Имеется одна публикация [5] в журнале из списка ВАК

Структура и объем работы

Диссертация состоит из введения, четырех глав, заключения, списка литературы (47 наименований) и приложения Общий объем работы составляет 122 страницы, работа содержит 17 иллюстраций и 6 таблиц.

Содержание работы

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

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

В течение нескольких десятилетий развитие ЭВМ сопровождалось удвоением их быстродействия каждые 1.5-2 года Это обеспечивалось и повышением тактовой частоты и совершенствованием архитектуры (параллельное и конвейерное выполнение команд) Однако постепенно аппаратные возможности параллельного выполнения команд последовательной программы достигли своего предела (кризис ILP - Instruction Level Parallelism), а дальнейшее повышение частоты стало практически невозможно из-за резкого повышения потребления и выделения энергии. Использовать эффективно постоянно возрастающее количество элементов микросхемы не удается из-за того, что практически достигнут предел логической сложности процессоров, а

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

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

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

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

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

Необходимо отметить, что есть еще одна причина необходимости распараллеливания последовательных программ — появление многопоточных процессоров и ядер Это вызвано постоянно возрастающим разрывом между быстродействием процессора и латентностью памяти, выражающимся в том, что для выборки из памяти одного операнда требуется время, превосходящее в сотни раз время выполнения одной команды процессора До поры до времени с этим противоречием боролись путем наращивания кэш-памяти Но, как уже было отмечено выше, такое наращивание для многих программ уже не приносит желаемого эффекта И тогда возникла идея - использовать подход, аналогичный мультипрограммированию, посредством которого в 60-е годы прошлого века боролись с противоречием между высоким быстродействием процессора и низкой скоростью внешних устройств ЭВМ Чтобы многопоточный процессор не простаивал в ожидании получения ответа от памяти, он на это время переключается на другие программы (другие потоки) Если таких параллельно выполняемых потоков будет много (сотни), то можно

обеспечить полную загрузку процессора Конечно, для этого нужна соответствующая суммарная пропускная способность каналов доступа к памяти

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

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

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

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

Основными недостатками MPI являются

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

• сложность написания программ, способных выполняться при произвольных размерах массивов и произвольном количестве процессов -делает практически невозможным повторное использование имеющихся MPI-программ при создании новых более сложных программ,

• сложность выражения многоуровневого параллелизма программы,

• MPI-программы, как правило, неспособны эффективно выполняться на кластерах, у которых процессоры имеют разную производительность

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

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

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

Первая попытка стандартизовать такую модель привела к появлению в 1990 году проекта языка PCF Fortran (проект стандарта ХЗН5) Однако этот проект тогда не привлек широкого внимания и, фактически, остался только на бумаге Но спустя несколько лет ситуация сильно изменилась - успехи в развитии элементной базы сделали очень перспективным и экономически выгодным создавать мультипроцессоры Крупнейшие производители компьютеров и программного обеспечения объединили свои усилия и в октябре 1997 года выпустили описание языка Fortran OpenMP - расширение языка Фортран 77 Позже вышли аналогичные расширения языков Си, Си++ и Фортран 90/95

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

Главными недостатками OpenMP являются.

• OpenMP рассчитан на мультипроцессоры и DSM-системы (системы с распределенной памятью, на которых смоделирована общая память) и изначально не ориентирован на кластеры,

• на DSM-системах большого размера (64 и выше), например SGI Altix, эффективность ОрепМР-программ невысока, что заставляет программистов использовать MPI;

• организация взаимодействия потоков через общие переменные, а не через передачу сообщений, часто приводит к трудно обнаруживаемым ошибкам (race condition - условия гонок), а необходимые для поиска таких ошибок средства отладки - либо отсутствуют вообще, либо мало доступны

Гибридная модель MPI/OpenMP

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

Такой подход имеет преимущества с точки зрения упрощения программирования в том случае, когда в программе есть два уровня

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

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

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

Прежде всего, отметим, что для MPI-программ создается ситуация, аналогичная ситуации с последовательными программами Если последовательные программы будут выполняться все медленнее по мере появления новых процессоров (из-за увеличения количества ядер и снижения быстродействия одного ядра), то и MPI-программы будут выполняться все медленнее, если не увеличивать количество MPI-процессов в них. Но увеличение количества процессов означает для большинства таких программ добавление новых уровней параллелизма А сложность выражения многоуровневого параллелизма - это известный недостаток MPI. Кроме того, поскольку при распараллеливании программы прежде всего использовался ее крупнозернистый параллелизм (подзадачи, самые объемлющие циклы), то теперь надо добавлять уровни мелкозернистого параллелизма, для которого наиболее подходит модель общей памяти и ОрепМР, а модель передачи сообщений может оказаться уже неэффективной

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

оптимизацию не могут делать компиляторы с последовательных языков для MPI-процессов

Следующее очень важное преимущество ОрепМР - отсутствие дублирования данных, используемых разными потоками При использовании MPI происходит дублирование в MPI-процессах следующих данных.

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

распределенных между разными процессами,

• используемых в пользовательской программе буферов для обмена

данными между процессами,

• системных буферов, используемых библиотекой MPI

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

Использование ОрепМР в узлах может быть обеспечено двумя способами - либо применением гибридных моделей (объединение ОрепМР с другими моделями, например с MPI), либо использованием языков программирования, компиляторы с которых будут генерировать для узлов код на ОрепМР

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

С этой точки зрения проанализированы модели и языки программирования, позволяющие создавать программы для кластеров - модель параллелизма по данным (язык HPF - High Performance Fortran), DVM-модель (языки Fortran-DVM и C-DVM), модель PGAS (язык Co-Array Fortran) Этот анализ показывает, что наиболее перспективной представляется гибридная модель программирования DVM/OpenMP, получающаяся путем объединения моделей DVM и ОрепМР

Вторая глава посвящена описанию гибридной модели параллельного программирования DVM/OpenMP и языка Fortran-DVM/OpenMP Отмечены основные достоинства новой модели по сравнению с моделями ОрепМР, MPI, DVM и MPI/OpenMP

Рассматривается вычислительная сеть, каждый узел которой является мультипроцессором или многоядерным процессором (рис. 1)

Рис. 1. Вычислительная сеть

Для разработки гибридной модели DVM/OpenMP, которая позволила бы создавать программы, эффективно выполняющиеся на данной вычислительной сети, исследуются следующие три подхода к объединению моделей DVM и ОрепМР:

1. Расширение языка Fortran ОрепМР директивами для распределения данных (DISTRIBUTE и ALIGN) и специальными клаузами для уточнения ОрепМР-директив распределения вычислений (ОрепМР + подмножество DVM). Вместо DVM-директив распределения вычислений, используются ОрепМР-директивы, которые дополнены информацией о том, на каких узлах требуется выполнить эти вычисления и какие межпроцессорные взаимодействия необходимо провести до выполнения этих вычислений (спецификации SHADOW_RENEW, REMOTE ACCESS).

Достоинства данного подхода:

• для ОрепМР-программиста - сравнительно небольшие добавления к стандартному языку Fortran ОрепМР;

• параллельная программа на новом языке Fortran-DVM/OpenMP является программой на стандартном языке Fortran ОрепМР.

Недостатки данного подхода:

• имеющиеся программы на языке Fortran-DVM уже не являются программами на новом языке Fortran-DVM/OpenMP;

• требуется серьезная переработка компилятора Fortran-DVM, поскольку помимо изменения синтаксиса DVM-директив, также требуется обеспечить корректную работу с DVM-директивами, заданными в параллельной области.

2. Расширение языка Fortran-DVM при помощи ОрепМР-спецификаций, которые позволили бы автоматически преобразовывать существующие DVM-программы в программы, использующие MPI для взаимодействия между узлами и ОрепМР для распределения вычислений внутри узла (DVM + подмножество ОрепМР).

В DVM-программе имеется информация:

• о циклах, которые можно выполнять параллельно (отмечены при помощи директивы PARALLEL ON),

• о редукционных операторах в цикле (отмечены при помощи спецификации REDUCTION),

• о приватных переменных в циклах (отмечены при помощи спецификации NEW),

• о циклах, в которых есть зависимость по данным (отмечены при помощи спецификации ACROSS)

Используя эту информацию, для некоторых DVM-программ можно получить соответствующие программы на языке Fortran-DVM/OpenMP автоматически Все распределенные при помощи директив DISTRIBUTE и ALIGN массивы должны быть общими для всех нитей на узле (описаны при помощи спецификации SHARED) Все приватные переменные должны быть описаны при помощи спецификации PRIVATE Все циклы, витки которых можно выполнять параллельно, можно распределить между нитями, используя директиву PARALLEL DO Для циклов со спецификацией ACROSS необходимо организовать конвейерное выполнение

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

Добавление в программу на языке Fortran-DVM спецификаций для определения класса переменных (PRIVATE, SHARED, THREADPRIVATE), а также спецификаций для инициализации значений приватных переменных (FIRSTPRIVATE, LASTPRIVATE, COPYIN, COPYPRIVATE), позволяют получать без сложного межпроцедурного анализа корректные программы, использующие MPI для взаимодействия между узлами и ОрепМР для распределения вычислений внутри узла

Преимущества данного подхода

• для DVM-программиста - сравнительно небольшие добавления к языку Fortran-DVM,

• требуется минимальная модификация компилятора Fortran-DVM,

• имеющиеся программы на Fortran-DVM являются и программами на новом языке Fortran-DVM/OpenMP,

• параллельная программа на новом языке Fortran-DVM/OpenMP является и программой на уже достаточно отработанном языке Fortran-DVM

Недостаток данного подхода, заключается в том, что параллельная программа на новом языке Fortran-DVM/OpenMP не является параллельной программой на стандартном языке Fortran OpenMP.

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

3. Полное объединение языков Fortran-DVM и Fortran OpenMP (полностью DVM + полностью OpenMP). Наличие большого количества реальных приложений на языке Fortran-DVM и на языке Fortran OpenMP говорило в пользу этого подхода. Преимущества данного подхода очевидны:

• имеющиеся программы на языке Fortran-DVM являются и программами на новом языке Fortran-DVM/OpenMP;

• имеющиеся программы на языке Fortran OpenMP являются и программами на новом языке Fortran-DVM/OpenMP;

• параллельная программа на новом языке Fortran-DVM/OpenMP является параллельной программой на стандартном языке Fortran OpenMP;

• параллельная программа на новом языке Fortran-DVM/OpenMP является и программой на уже достаточно отработанном языке Fortran-DVM.

В п. 2.1 данный подход рассматривается более подробно, описывается гибридная модель параллельного программирования DVM/OpenMP.

Рассмотрим вычислительную сеть,

Данные

Данные

Вычисления

OpenMP

Рис. 2. Модель DVM/OpenMP

каждый узел которой является мультипроцессором или отдельным процессором (рис. 2) На каждом узле выполняется параллельная программа на языке Fortran OpenMP Распределение данных и вычислений между узлами, а также доступ к удаленным данным выполняется согласно модели DVM

В программе на языке Fortran-DVM/OpenMP можно описать следующие уровни параллелизма1

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

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

3. Параллелизм конструкций разделения работы ОрепМР (циклы и секции) Эти конструкции могут быть в произвольном порядке вложены друг в друга.

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

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

В п. 2.2 приведено краткое описание языка Fortran-DVM/OpenMP и примеры программ на этом языке Синтаксис директив языка Fortran-DVM/OpenMP описан в приложении

Спецификации параллелизма оформляются как спецкомментарии, что позволяет использовать программу на языке Fortran-DVM/OpenMP как стандартную последовательную, так и стандартную параллельную ОрепМР-программу

Рассмотрим пример параллельной программы на языке Fortran-DVM/OpenMP алгоритма численного решения двухмерного уравнения Лапласа методом Якоби.

PROGRAM JAC_DVM_OpenMP PARAMETER (L=8, ITMAX=20) REAL A(L,L), B(L,L) CDVMS DISTRIBUTE (BLOCK, BLOCK) A CD VMS ALIGN B(I,J) WITH A(I,J) С arrays A and В with block distribution

PRINT * '****♦♦***# TEST JACOBI **********' 'SOMP PARALLEL

DO IT = 1, ITMAX CDVMS PARALLEL (J, I) ON A(I, J) 'SOMP DO

DO J = 2, L-l 'SOMP PARALLEL DO DO I = 2, L-l

A(I, J) = В (I, J) ENDDO ENDDO

CDVM$ PARALLEL (J, I) ON B(I, J),SHADOW_RENEW (A) С Copying shadow elements of array A from

С neighboring nodes before loop execution

'SOMP DO

DO J = 2, L-l '$OMP PARALLEL DO DO I = 2, L-l B(I, J)= (A( 1-1, J ) + A( I, J-l ) + * A( 1+1, J ) + A( I, J+l )) / 4

ENDDO ENDDO ENDDO 'SOMP END PARALLEL END

При помощи директивы DISTRIBUTE массив А распределяется между узлами Оператор вида A(I, J) = B(I, J), выполняемый в цикле, определяет требования по совместному распределению этих массивов Чтобы исключить взаимодействие между узлами при выполнении этого оператора, необходимо распределить A(I,J) и B(I,J) элементы массива на один и тот же узел - для этого используется директива ALIGN Директива PARALLEL ON каждый виток параллельного цикла ставит в соответствие некоторому элементу массива Это означает, что (J,I) виток цикла будет выполняться на том узле, где распределен соответствующий элемент массива - A(I,J) Во втором цикле для вычисления элемента B(I,J) используются элементы A(I-1,J), A(I,J-1), A(I+1,J) и A(I,J+1) Поскольку массив А распределен, то эти элементы могут находиться на соседних узлах, поэтому перед выполнением цикла необходимо загрузить эти данные - для этого используется спецификация SHADOW_RENEW.

В результате выполнения директивы PARALLEL ON вычисления распределены по узлам Для распределения этих вычислений внутри узла используются ОрепМР-директивы При помощи директивы PARALLEL создается группа нитей, между которыми при помощи директивы DO и распределяется вся работа (распределяются витки циклов, которые обрабатывают локальную часть массива)

В п. 2.3 описаны преимущества разработанной гибридной модели перед моделями OpenMP, MPI, DVM и MPI/OpenMP

В п. 2.3.1 описаны достоинства модели DVM/OpenMP по сравнению с моделью OpenMP

Главное достоинство - способность работать не только на мультипроцессорах и DSM-системах, но и на кластерах, а также больших DSM-системах, на которых ОрепМР не эффективен (поэтому на них и используют гибридную модель MPI/OpenMP)

В п. 2.3.2 описаны достоинства модели DVM/OpenMP по сравнению с моделью MPI

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

В п. 2.3.3 описаны достоинства модели DVM/OpenMP по сравнению с моделью DVM

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

В п. 2.3.4 описаны достоинства модели DVM/OpenMP по сравнению с моделью MPI/OpenMP

Большим достоинством является то, что модели DVM и ОрепМР являются очень близкими моделями по содержанию и оформлению спецификаций параллелизма Обе модели многое унаследовали от проекта стандарта PCF Fortran и исходят из наличия глобального адресного пространства и единого потока управления Модели MPI и ОрепМР не имеют ничего общего ни по содержанию, ни по изобразительным средствам - модель MPI исходит из отсутствия единого адресного пространства и единого потока управления, и реализуется в виде библиотеки, а не директив компилятора

И конечно, сохраняются упомянутые выше преимущества DVM перед

MPI.

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

(векторных и графических процессоров, ПЛИС) Кроме того, весьма вероятно, что многоядерные процессоры с большим количеством ядер (свыше 64) будут иметь средства, обеспечивающие быстрые коммуникации между ядрами (например, между их КЭШами) без необходимости обращения к оперативной памяти, высокая латентность которой будет по-прежнему являться узким местом Это потребует создания новых средств передачи сообщений, но эти средства будут слишком кардинально отличаться от MPI, чтобы стало возможным автоматически преобразовать MPI-программы для их использования

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

В третьей главе представлен компилятор с языка Fortran-DVM/OpenMP Приводится схема функционирования компилятора, описываются его отличия от компилятора с языка Fortran-DVM

Программа, написанная на языке Fortran-DVM/OpenMP, компилируется в два этапа На первом этапе используется компилятор Fortran-DVM/OpenMP, который переводит ее в программу на языке Fortran OpenMP, с вызовами функций системы поддержки параллельного выполнения (библиотеки Lib-DVM) На втором этапе полученная программа компилируется штатным Fortran компилятором, поддерживающим стандарт OpenMP, в режиме учета спецификаций OpenMP.

В п. 3.1 описаны основные преобразования, выполняемые компилятором

1 Для каждого распределенного массива на каждом узле компилятор создает локальный массив в соответствии с правилами распределения массива, заданными директивами DISTRIBUTE или ALIGN. Локальный массив создается компилятором с учетом теневых граней, объявленных в директиве SHADOW Память для элементов таких массивов отводится динамически системой поддержки

2 Компилятор преобразует обращения к элементам распределенных массивов - линеаризует каждую ссылку на элемент распределенного массива (обращение к многомерному массиву заменяется на обращение к одномерному локальному массиву)

3 Организует доступ к удаленным элементам распределенных массивов в соответствии с заданными в программе спецификациями

4 Распределяет витки циклов между узлами и определяет подмножество витков цикла, которые необходимо выполнить на данном узле Заменяет глобальные границы циклов на локальные

5 Обеспечивает корректную работу с библиотекой Lib-DVM из разных нитей. При проектировании библиотеки Lib-DVM для компиляторов с языков С-

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

6. Преобразует некоторые ОрепМР-директивы и операторы программы В языке Fortran-DVM/OpenMP предусмотрена возможность распараллеливания циклов с регулярными зависимостями по распределенным массивам Такой цикл, помимо описания синхронизации и взаимодействия процессов на разных узлах кластера средствами DVM (спецификации ACROSS) включает описание синхронизации нитей внутри узла (конвейерный параллелизм) Программист средствами ОрепМР описывает конвейерный параллелизм, исходя из глобальных размеров массива Компилятор преобразует это описание, заменяя глобальный размер распределенного массива размерами его локальных частей. 7 Генерирует OpenMP-указания для служебных переменных, используемых в вызовах функций системы поддержки, для буферизации ввода-вывода и адресации распределенных массивов

В п. 3.2 приводится схема функционирования компилятора Подробно описаны преобразования, выполняемые компилятором для директивы PARALLEL ON

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

Большинство операций библиотеки Lib-DVM являются коллективными (например, создание распределенного массива и его перераспределение), и должно быть вызвано на всех узлах кластера Причем, на любом узле каждую операцию библиотеки Lib-DVM вызывает одна нить, а остальные нити дожидаются выполнения этой операции Это обеспечивается с помощью секции MASTER/END MASTER и директивы синхронизации BARRIER

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

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

(вставка в программу дополнительных функций) была реализована в компиляторе для программ на языках Fortran OpenMP и Fortran-DVM/OpenMP

Большое внимание поддержке отладки объясняется тем, что при использовании OpenMP наиболее часто встречаемая и очень трудно обнаруживаемая ошибка - ошибка типа race condition (конфликт доступа к данным)

Существующие на сегодняшний день инструменты для обнаружения таких ошибок (например, Intel Thread Checker и Sun Studio Thread Analyzer) не всегда доступны пользователю (требуют установки определенного программного обеспечения, как правило, платного) Они накладывают определенные ограничения на используемые в программе конструкции (например, не должны встречаться вызовы функции опроса количества нитей), не могут быть использованы при отладке программ с реальными производственными данными (из-за требуемых дополнительных ресурсов памяти и времени) Необходимо иметь средства отладки, свободные от этих недостатков

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

Предлагается разработать аналогичные средства отладки для программ на языке Fortran OpenMP и Fortran-DVM/OpenMP Наличие такого инструментария существенно упростит внедрение языка Fortran-DVM/OpenMP

Четвертая глава содержит информацию об использовании языка Fortran-DVM/OpenMP для программирования реальных приложений. Описываются особенности программирования тестов NAS (ВТ, LU, SP), задачи CONVD и двух программ из пакета "РЕАКТОР" Приводятся характеристики эффективности выполнения параллельных программ.

В процессе создания языка Fortran-DVM/OpenMP в течение нескольких лет постоянно велась работа по исследованию применимости языка для программирования реальных приложений Эта работа позволила сделать обоснованный выбор подхода к объединению моделей DVM и OpenMP, найти эффективные решения для компилятора

В п. 4.1 содержится описание особенностей программирования и характеристик эффективности трех модельных приложений (ВТ, LU, SP) из пакета тестов NAS, решающих тремя различными методами задачи вычислительной гидродинамики (3D Навье-Стокс)

При создании версии программ на языке Fortran-DVM/OpenMP за основу были использованы MutliZone версии тестов NAS, написанных в гибридной модели MPI/OpenMP В данных тестах MPI применяется для отображения зон по узлам кластера, а ОрепМР - для распределения вычислений внутри зоны Каждая зона рассчитывается независимо от других, по завершении обсчета зоны осуществляется обмен граничными значениями. Вся работа по отображению зон по узлам и взаимодействию между узлами была переписана на DVM с использованием механизма задач ОрепМР директивы остались без каких либо изменений Ниже (в табл. 1) приводится информация о размере MPI/OpenMP и DVM/OpenMP-версий тестов NAS в строках (без учета комментариев)

Название теста MPI/OpenMP DVM/OpenMP

ВТ 3377 3257

LU 3431 3344

SP 3013 2887

Табл. 1. Размеры MPI/OpenMP и DVM/ОрепМР-версий тестов NAS.

На следующих диаграммах (рис. 3-14) показаны времена выполнения тестов NAS класса А на машине Regatta (IBM eServer pSenes 690), установленной в Московском государственном университете им M В Ломоносова Приводятся времена выполнения тестов в секундах при использовании разного числа нитей и MPI-процессов.

Диаграммы показывают, что гибридные модели DVM/OpenMP и MPI/OpenMP близки по эффективности На одних и тех же конфигурациях (<число МР1-процессов>х<число нитей>) DVM и MPI-версии тестов ведут себя практически одинаково.

Использование в гибридной модели нитей дает небольшой выигрыш при работе теста SP на 2-х и 4-х процессорах, но при работе на 8-ми процессорах выигрыша уже нет, а на 16-ти процессорах использование нитей даже замедляет выполнение теста

Для теста LU использование гибридной модели дает выигрыш и по сравнению с MPI (или DVM), и по сравнению с ОрепМР - минимальное время на 16 процессорах достигается при использовании 4-х процессоров и 4-х нитей

В отличие от предыдущих тестов, в которых все зоны имеют один и тот же размер 32x32x16 (для класса А), в тесте ВТ - все зоны различного размера от 13x13x16 и до 58x58x16 Поэтому зоны меяаду MPI-процессами распределяются таким образом, чтобы обеспечить их одинаковую загрузку. При увеличении числа MPI-процессов свыше 4-х такая балансировка становится невозможной, поскольку количество зон ограничено (всего 16 зон для класса А) В результате, программа перестает ускоряться Использование ОрепМР дает возможность сократить число MPI-процессов и улучшить балансировку Минимальное время выполнения теста достигается при использовании 4-х MPI-процессов и 4-х нитей

1x2 2x1

□ МР1 83,6 90,47

■ ПУМ 66,87 76,35

1x4 2x2 4x1

О МР1 39,56 37,8 41,74

□ ОУМ 36,95 353 36,02

Рис.3. Тест БР на 2-х процессорах

Рис.4. Тест БР на 4-х процессорах

1x8 2x4 4x2 8x1

□ МР1 21,64 21,76 20,87 20,44

□ ПУМ 21,63 19,82 19,2 20,87

1x16 2x8 4x4 8x2 16x1

□ МР1 12,97 11,11 10,98 10 9,92

а БУМ 14,98 12,72 11,44 10,47 10,41

Рис.5. Тест 8Р на 8-ми процессорах

Рис.6. Тест 8Р на 16-ти процессорах

□ МР1 60,13 66,29

□ ОУМ 60,85 71,13

40

30

20

10

0 /А

Рис.7. Тест Ьи на 2-х процессорах

Рис.8. Тест Ьи на 4-х процессорах

35 30 25 20 15 10 5

0 1x8 2x4 4x2 8x1

ОМР1 19,23 31,19 16,83 15,61

■ ОУМ 19^2 31,15 17,86 21,55

Рис. 9. Тест ьи на 8-ми процессорах Рис.Ю.Тест Ш на 16-ти процессорах

100 80 60 40 20 О

Г¡ь

□ МР1

I ОУ'М

1x2

88,53

78,78

2x1

84,24

89,57

50 40 30 20 10 О

□ МР1

I и\'М

1x4

41,75

41,55

2x2

38,13

39,83

4x1

36,54

40,39

Рис. 11. Тест ВТ на 2-х процессорах 40

Рис. 12. Тест ВТ на 4-х процессорах

Рис. 13. Тест ВТ на 8-ми процессорах Рис'14'Тест ВТ на 16"ти "1,оиессоРах

В п. 4.2 приводятся особенности программирования задачи СОЫУО (задачи С.Д. Устюгова), которая считает трехмерную магнитную газодинамику для расчета солнечной конвекции с использованием реалистичной физической

21

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

Для получения программы на языке Fortran-DVM/OpenMP использовалась DVM-версия этой программы В результате преобразования, описанного во второй главе, была получена программа в модели DVM/OpenMP. Размер последовательной программы составляет 3214 операторов языка Fortran, размер DVM-программы - 3380 строк, размер полученной DVM/OpenMP-программы - 3649 строк Существенное усложнение Fortran-DVM/OpenMP программы объясняется тем, что в задаче имеются циклы с зависимостью по данным, распараллеливание которых на ОрепМР требует больших усилий (низкоуровневое распараллеливание)

Данная задача считается в Межведомственном суперкомпьютерном центре РАН на суперкомпьютере "МВС-50К" Задача очень требовательна к объему оперативной памяти До проведения модернизации суперкомпьютера на вычислительном узле запускались 4 MPI-процесса, которые могли использовать до 4 Гбайт оперативной памяти узла DVM-версия задачи запускалась на 225 процессорах После проведения модернизации (использования 4-х ядерных процессоров) - на узле стали запускаться 8 MPI-процессов, а объем оперативной памяти остался прежним В результате DVM-версия программы перестала работать

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

Версия программы на языке Fortran-DVM/OpenMP использует все ресурсы на узле и поэтому выполняется заметно быстрее (табл. 2)

Версия программы 57 вычислительных узлов Время выполнения, сек

DVM-программа 225 МР1-процессов (задействовано 4 процессора) 259 50

DVM/OpenMP-программа 225 МР1-процессов х 2 нити (задействовано 8 процессоров) 159 47

Табл. 2. Время выполнения задачи С01Ч\Т) в СКЦ РАН

В п. 4.3 описываются особенности распараллеливания программ, входящих в пакет "РЕАКТОР".

В п. 43 описываются особенности распараллеливания программ, входящих в пакет "РЕАКТОР"

В п. 4.3.1 описана нестационарная задача DF3D6T, которая предназначена для расчета поведения реактора в процессе вдвигания замедляющих стержней Расчет производится на гексагональной конечноразностной сетке диффузионным методом Размер последовательной программы составляет 17035 операторов языка Fortran, размер DVM-программы - 17152 строк, размер полученной DVM/OpenMP-программы -17324 строк. На тестовых данных эффективность DVM и разработанной DVM/OpenMP версии этой программы практически совпадает.

В п. 4.3.2 описана задача KinXYZ, используемая для расчета нейтронных полей в кинетическом приближении в трехмерной X-Y-Z геометрии Размер последовательной программы составляет 14795 операторов языка Fortran, размер DVM-программы - 14897 строк, размер полученной DVM/OpenMP-программы - 14944 строк Применение гибридной модели для этой задачи позволило на суперкомпьютере "МВС-50К" эффективнее использовать ядра узла (из-за отсутствия дублирования информации в памяти, свойственного MPI-модели и DVM-модели), что привело почти к 2-х кратному ускорению программы

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

Анализ приведенных в разделах 4 1-43 характеристик эффективности позволяет сделать следующие выводы

• эффективность программ в гибридной модели DVM/OpenMP очень мало отличается от эффективности программ в гибридной модели MPI/OpenMP,

• эффективность программ в гибридной модели DVM/OpenMP не уступает эффективности программ в модели DVM,

• использование в узлах модели общей памяти OpenMP позволило получить следующие преимущества

- заметно ускорить решение реальных задач, требующих больших объемов оперативной памяти (за счет ликвидации дублирования информации в памяти, свойственного MPI-модели и DVM-модели),

- заметно ускорить выполнение программы ВТ за счет реализации на OpenMP дополнительного уровня параллелизма (что очень сложно было бы сделать на MPI), позволившей обеспечить лучшую балансировку загрузки процессоров

В заключении сформулированы основные результаты работы

г

Основные результаты работы

1. Предложена новая модель и новый язык параллельного программирования -гибридная модель DVM/OpenMP и язык Fortran-DVM/OpenMP, позволяющие разрабатывать эффективные, переносимые программы для SMP-кластеров и высокопроизводительных систем с многоуровневым параллелизмом

2 Разработан компилятор, преобразующий параллельные программы на языке Fortran-DVM/OpenMP в программы на стандартном языке Fortran OpenMP, выполняющиеся в узлах SMP-кластера и взаимодействующие между собой посредством MPI.

3 Проведено исследование характеристик разработанных на языке Fortran-DVM/OpenMP реальных приложений (тесты NAS и др), подтвердившее применимость языка и эффективность его отображения на SMP-кластеры.

Публикации по теме диссертации

1 В А. Бахтин, H А Коновалов, H В Поддерюгина, С Д Устюгов. Гибридный способ программирования DVM/OpenMP на SMP-кластерах Труды Всероссийской научной конференции "Научный сервис в сети Интернет, технологии параллельного программирования" (сентябрь 2006 г, г. Новороссийск) M Изд-во МГУ, 2006 г, стр 128-130

2 В А Бахтин, H А.Коновалов, В А Крюков, H В Поддерюгина, Ю Л.Сазанов Разработка параллельных программ для решения больших вычислительных задач на SMP-кластерах. Труды Первой Всероссийской научной конференции "Методы и средства обработки информации", г. Москва, 1-3 октября 2003 г, стр 191-196

3 Бахтин В А, Коновалов H А, Крюков В А , Поддерюгина H В Fortran OpenMP/DVM - язык параллельного программирования для кластеров Материалы второго Международного научно-практического семинара "Высокопроизводительные параллельные вычисления на кластерных системах ", г. Нижний Новгород, 26-29 ноября 2002 г, стр 28-30

4 В А Бахтин, H А Коновалов, В А. Крюков Расширение языка OpenMP Fortran для программирования GRID-приложений Труды Всероссийской научной конференции "Научный сервис в сети ИНТЕРНЕТ", г Новороссийск, 23-28 сентября 2002 г., стр 273

5 В А Бахтин, H А Коновалов, В А Крюков Расширение языка OpenMP Fortran для распределенных систем. Вопросы атомной науки и техники сер Математическое моделирование физических процессов 2002 г Вып 4 стр 65-70

6 В.А Бахтин, H А Коновалов, В А Крюков. Расширение языка OpenMP Fortran для распределенных систем Тезисы докладов Международного семинара "Супервычисления и математическое моделирование", г. Саров, 17-21 июня 2002 г., стр 21-22

Введение;.

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

Цель и задачи работы.;.;.

Основные результаты работы.

Ирактинеская1ценность работы.6»

Апробацияфаботы.

Краткое содержание работы.

Глава 1. Модели? и языки параллельного программирования; для SMP-кластеров.

1.1. Модель передачи ¡сообщений; MPI.10s 1.2*. Мо дел б параллелизма по управлению.' OperiMP'.

Г.З. Рибриднаяшодель МР1/ОрепМР!;.18'

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

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

1.6: Язык Go-Array Eortram(CAF).30

1'.Выводы;.3L

Глава 2. Гибридная модель параллельного? программирования

DVM/OpenMP и язык Fortran-DVM/OpenMP.;.

2:1 Гибридная модель параллельного: программирования?; DVM/OpenMP.:.

2.2 Язык Fortran-DVM/OpenMP;.40»

2.2.1 Описание виртуальногомассива узлов.«.

2.2^2 Распределение данных. Директива1 DISTRIBUTE. 42'

212.3-Локализация данных. Директива AblGN.

2.2.4 Распределение витков? параллельного» цикла.,, Директива' PARALLEL ON .•.

2.2.5 Удаленные данные типа SHADOW.

2'.2!6;Удаленные данные:типа ACROSS.

2.2.7 Удаленные данныетипа;1ШМОТЕ.:.

2.2.8 Удаленные данные типа REDWCM0N.

2.2.9 Размноженные по узлам данные.:. 50s

2.2.10 Распределение витков* цикла между нитями внутри узла. Директивы DO и

2.2.11 Распределение витковфаспределенного параллельного цикла между нитями.

2.2.12 Работа с удаленными данными типа ACROSS внутри узла.

2.2.13-Работа с данными типа REDUCTION внутри узла.

2.2.14 Пример параллельной программы в моделях MPI/OpenMP и

DVM/OpenMP.

2.3 Преимущества разработанной гибридной модели перед моделями OpenMP, MPI, DVM и MPI/OpenMP.

2.3.1. Достоинства модели DVM/OpenMP по сравнению с моделью ОрепМР.!.

2.3.2. Достоинства модели DVM/OpenMP по сравнению с моделью MPI.

2.3.3. Достоинства модели DVM/OpenMP по сравнению с моделью DVM.:.

2.3.4. Достоинства модели DVM/OpenMP по сравнению с моделью MPI/OpenMP.

Глава 3. Компилятор с языка Fortran-DVM/OpenMP.

3.1 Основные функции компилятора Fortran-DVM/OpenMP.

3.2 Схема функционирования компилятора.

3.3 Инструментация Fortran-DVM/OpenMP программ.

3.3.1 Передача статической информации о программе.

3.3.2 Схема инструментации программы.

3.3.3 Инструментация ОрепМР-директив.

3.3:4 Инструментация совмещенных ОрепМР-директив.

3.3.5 Инструментация операторов языка Fortran.

3.3.6 Управлению степенью подробности инструментации.

3.3.7 Отличия разработанной инструментации по сравнению с инструментацией, используемой в DVM-системе.

Глава 4. Использование' языка Fortran-DVM/OpenMP для программирования реальных приложений.

4.1. Тесты NAS (ВТ, LU, SP).

4.2. Задача CONVD - расчет солнечной конвекции.

4.3. Особенности распараллеливания программ, использующих пакет «РЕАКТОР».

4.3.1 Нестационарная задача DF3D6T.

4.3.2 Задача KinXYZ.

4.4. Наиболее часто встречаемые ошибки, возникающие при распараллеливании программ в модели DVM/ ОрепМР.

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

Последние годы связаны с резким изменением направления развития процессоров — появлением многоядерных и многопоточных процессоров. Их эффективное использование требует повсеместного перехода с последовательных программ на параллельные программы. Для высокопроизводительных вычислений на кластерах и многопроцессорных ЭВМ с массовым параллелизмом (МРР) теперь требуется более глубокое распараллеливание, обеспечивающее, по крайней мере, два уровня параллелизма - уже привычный параллелизм между узлами кластера и дополнительный параллелизм между ядрами в узле. В настоящее время такой двухуровневый параллелизм наиболее легко и естественно выражать посредством использования между узлами модели передачи сообщений MPI, а внутри узлов - модели общей памяти Pthreads, или более высокоуровневой и более подходящей для вычислительных программ модели ОрепМР. Однако, необходимость более глубокого распараллеливания и использования гибридной модели MPI/OpenMP, т.е. двух разных моделей программирования и соответствующих им разных инструментальных средств еще более усложняет и без того нелегкую работу по созданию параллельных программ. Поэтому проблема автоматизации создания параллельных программ становится в настоящее время чрезвычайно актуальной.

В 1994 году в ИПМ им. М.В.Келдыша РАН была предложена новая модель (DVM-модель) параллельного программирования, позволившая существенно автоматизировать разработку MPI-программ для кластеров. Однако широкое распространение SMP-кластеров (кластеров, использующих в качестве узлов мультипроцессоры) требовало расширения DVM-модели для более эффективного использования их двухуровневого параллелизма.

Цель и задачи работы

Целью данной работы являлась разработка гибридной модели DVM/OpenMP, которая позволит упростить создание программ» для параллельных систем на базе многоядерных процессоров.

В соответствии с этой целью были определены следующие задачи:

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

2. Разработать основные принципы объединения моделей DVM и ОрепМР, язык Fortran-DVM/OpenMP и компилятор с него, преобразующий входную программу в совокупность программ на I языке Fortran ОрепМР, выполняющихся на каждом узле кластера и взаимодействующих посредством библиотеки MPI.

3. Оценить применимость и эффективность, разработанного языка и компилятора.

Основные результаты работы

В работе были достигнуты следующие основные результаты:

1. Предложена новая модель и новый язык параллельного программирования — гибридная модель DVM/OpenMP и язык Fortran-DVM/OpenMP, позволяющие разрабатывать эффективные, переносимые программы для SMP-кластеров и высокопроизводительных систем с многоуровневым параллелизмом.

2. Разработан.компилятор, преобразующий параллельные программы на языке Fortran-DVM/OpenMP* в программы на стандартном языке Fortran ОрепМР, выполняющиеся в узлах SMP-кластера и взаимодействующие между собой посредством MPI.

3. Проведено исследование характеристик разработанных на языке Fortran-DVM/OpenMP реальных приложений (тесты NAS и др.), подтвердившее применимость языка и эффективность его отображения на 8МР-кластеры.

Перечисленные результаты обладают научной новизной.

Практическая ценность работы

Разработанный язык Рог1гап-ОУМ/ОрепМР и компилятор используются для создания программ, способных эффективно выполняться на последовательных ЭВМ, мультипроцессорных ЭВМ с общей памятью, кластерах и БМР-кластерах.

Разработанный язык и компилятор используются на факультете ВМиК МГУ при проведении практикума по технологиям параллельного программирования, а также служат базой для распараллеливающего компилятора с языка Фортран, создаваемого в рамках программы Союзного государства «ТРИАДА», и системы автоматизации распараллеливания Фортран-программ, создаваемой в рамках программы №14 Президиума РАН.

Апробация работы

Основные результаты работы опубликованы [17-19]. Результаты работы обсуждались на следующих конференциях и семинарах:

1. Всероссийская научная конференция «Научный сервис в сети Интернет: технологии параллельного программирования», г. Новороссийск, сентябрь 2006 г.

2. Первая Всероссийская научная конференция «Методьъ и средства обработки информации», г. Москва, октябрь 2003 г.

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

4. Всероссийская научная конференция «Научный сервис в сети ИНТЕРНЕТ», г.Новороссийск, сентябрь 2002 г.

5. Международный семинар «Супервычисления и математическое моделирование», г.Саров, июнь 2002 г.

Краткое содержание работы

В первой главе приводится обзор и анализ подходов к моделям и языкам параллельного программирования. Обосновывается необходимость использования модели ОрепМР в многоядерных узлах кластеров и перспективность предлагаемой гибридной модели программирования DVM/OpenMP, получающейся путем объединения моделей DVM и ОрепМР.

Вторая глава посвящена описанию гибридной модели параллельного программирования DVM/OpenMP и языка, Fortran-DVM/OpenMP. Изложены основные принципы объединения моделей DVM и ОрепМР, отмечены основные достоинства новой модели по сравнению с моделью* MPI/OpenMP. Приведено краткое описание языка Fortran-DVM/OpenMP и примеры программ на этом языке.

В третьей главе представлен компилятор с языка Fortran-DVM/OpenMP. Приводится схема функционирования компилятора, описываются его отличия от компилятора с языка Fortran-DVM.

Четвертая глава содержит информацию об использовании языка Fortran-DVM/OpenMP для программирования реальных приложений. Описываются особенности программирования тестов NAS (ВТ, LU, SP), задачи расчета солнечной конвекции, а также двух программ из пакета «РЕАКТОР». Приводятся, характеристики эффективности выполнения параллельных программ.

В заключении перечисляются основные результаты работы.

Заключение

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

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

В диссертационной работе были достигнуты следующие основные результаты:

1. Предложена новая модель и новый язык параллельного программирования — гибридная модель DVM/OpenMP и язык Fortran-DVM/OpenMP, позволяющие разрабатывать эффективные, переносимые программы для SMP-кластеров и высокопроизводительных систем с многоуровневым параллелизмом.

2. Разработан компилятор, преобразующий параллельные программы на языке Fortran-DVM/OpenMP в программы на стандартном языке Fortran OpenMP, выполняющиеся в узлах SMP-кластера и взаимодействующие между собой посредством MPI.

3. Проведено исследование характеристик разработанных на языке Fortran-DVM/OpenMP реальных приложений (тесты NAS и др.), подтвердившее применимость языка и эффективность его отображения на SMP-кластеры.

1. Message-Passing 1.terface Forum, Document for a Standard Message-Passing Interface, 1994: Version 1.0) (http://www.unix.mcs.anl.gov/mpi/);

2. High Performance Fortran Forum. High Performance Fortran Language Specification, version 2.0, Rice University, Houston, Tex.,. January 1997. (http://hpff.rice.edu/versions/hpf2/index.htm)

3. OpenMP Consortium: OpenMP Fortran Application Program Interface, Version 1.0; October 1997. (http://www.openmp.org/)

4. OpenMP С and С++ Application Program Interface. Version 1.0 October 1998. (http://www.openmp.org/)

5. Jack Dongarra, Dennis Gannon, Geoffrey Fox, Ken Kennedy. The Impact of Multicore on Computational, Science Software; CTWatch Quarterly The Promise and Perils of the Coming Revolution and Its Impacts, Volume 3,

6. Number 1, February, 2007, pages 3-10 (http://www.ctwatch.Org/quarterly/l

7. John L.Manferdelli. The Many-Core Inflection Point lor Mass Market Computer Systems. CTWatch Quarterly The Promise and Perils of the Coming Revolution and Its Impacts, Volume 3, Number 1, February, 2007, pages 11-17 (http ://www.ctwatch.org/quarterly/)

8. Portable Operating System Interface. ANSI/IEEE POSIX 1003.1-199510: Dave Turek. High Performance Computing and the Implications of Multi-core Architectures. CTWatch Quarterly The Promise and Perils of the Coming

9. Revolution and Its Impacts, Volume 3,Number 1, February, 2007, pages 31-33 nittp://www.ctwatch.org/quarterly/>

10. Robert Alverson, David Callahan, Daniel Cummings, Brian Koblenz, Allan Porterfield, and Burton Smith. The Tera computer system; In Proceedings of the 1990 International Conference on Supercomputing, pages 1-6.

11. Leasure, В., Ed. PCF Fortran: Language Definition, version 3d. The Parallel Computing Forum, Champaign, Aug, 1990.

12. Fortran DVM — язык разработки; мобильных параллельных программ / Н.А. Коновалов, В.А. Крюков, G.H. Михайлов и др. // Программирование. 1995.-№ 1 -С. 49-54. •

13. Коновалов Н.А., Крюков В.А., Сазанов ЮЛ. C-DVM язык разработки мобильных параллельных программ // Программирование. — 1999. — № 1. -С. 54-65. .16; DVM-система. (http://www.keldvsh.ru/dvm/)

14. Бахтин В.А., Коновалов Н:А., Крюков В.А. Расширение языка ОрепМР Fortran для распределенных систем // Вопросы атомной науки и техники. Серия математическое моделирование физических; процессов. — 2002. — Вып.4. С.65-70.

15. Разработка параллельных программ для решения больших вычислительных задач на SMP-кластерах. / В.А. Бахтин, Н.А. Коновалов,

16. В.А. Крюков*и др. // Труды Первой Всероссийской научной конференции «Методы и средства обработки информации». М., 2003. - С. 191-196.

17. Крюков В^А. Разработка параллельных программ для вычислительных кластеров и сетей. // Информационные технологии и вычислительные системы. 2003 - № 1-2. - С. 42-60.

18. Ken Kennedy, Charles Koelbel, Hans Zima. The Rise and Fall of High Performance Fortran: An Historical Object Lesson. Proceedings of the third ACM SIGPLAN conference on History of programming languages 2007, San Diego, California, 2007. Pages: 7-1 7-22.

19. Ray Barriuso and Allan Knies. SHMEM user's guide for C. Technical report, Gray Research Inc., June 1994.

20. Robert W. Numerich and John Reid. Co-array fortran for parallel programming. SIGPLAN Fortran Forum, 17(2):1-31, 1998

21. William W. Carlson, Jesse M. Draper, David E. Culler, Kathy Yelick, Eugene Brooks, and Karen Warren. Introduction to UPC and language specification. Technical Report CCS-TR-99-157,Center for Computer Sciences, Bowie, MD, May 1999.

22. Cray Inc., Seattle, WA. Chapel Specification, 0.4 edition, February 2005. (http://chapel.cs.washington.edu).

23. Sun Microsystems, Inc., Burlington, Massachusets. The Fortress Language Specification, Version 0.707, July 2005.

24. OpenMP Consortium: OpenMP Application Program Interface; Version 2.5, May 2005. (http://www.openmp.org/mp-documents/spec25.pdf)

25. Описание языка Fortran-DVM/OpenMP. Версия 2.0, 2006 (http://www.keldysh.ru/dvm/omp/)

26. Система поддержки выполнения параллельных программ (библиотека Lib-DVM)http://www.keldysh.ru/dvm/dvmhtml 107/rus/sys/libdvm/rtsIDr0.html)

27. Sage++: An object-oriented toolkit and class library for building fortran and С++ restructuring tools / F. Bodin, P. Beckman, D. Gannon et al. // Proceedings. OONSKI '94. Oregon: 1994

28. Intel Corporation. / Intel Thread Checker, (http: / / w w w .intel .com/support/performancetools/threadchecker)

29. Sun Studio Thread Analyzer. (http://developers.sun.com/sunstudio/downloads/tha/)

30. Steven Cameron Woo, Moriyoshi Ohara, Evan Torrie, Jaswinder Pal Singh, and Anoop Gupta. The SPLASH-2 Programs: Characterization and Methodological Considerations. In Proceedings of the 22nd International

31. Symposium on Computer Architecture, pages 24-36, Santa Margherita Ligure, Italy, June 1995. fftp://wwwflash.stanford.edu/pub/splash2/splash2 isca95.ps.Z).

32. James Rose. Intel Tools Make Threading' Easier on Multiple Processors. Intel Software Network. July 14, 2007. (http://softwarecommunity.intel.com/articles/eng/2664.htm)

33. Крюков B.A., Удовиченко, P.B. Отладка DVM программ // Препринт ИПМ им. М.В.Келдыша-РАН. — 1999. -№56.

34. Bernd Mohr, Allen D. Malony, Hans-Christian Hoppe, Frank Schiimbach, Grant Haab, Jay Hoeflinger, Sanjiv Shah. A Performance Monitoring Interface for OpenMP: (http://www.research.ibm.com/actc/proiects/pdf/EWQMP02-POMP.pdf)

35. Интерфейс инструментации Fortran DVM/OpenMP-программ. Версия1 1.2.2, 2007г. (http://www.keldvsh.ru/dvm/omp/QpenMPInstr.doc)

36. A.Voronkov, V.Arzhanov. REACTOR Program System for Neutron-Physical Calculations. Proc. International Topical Meeting: Advances in Mathematics, Computations, and Reactor Physics, USA, Vol5, April 28 — May 2, 1991