Российская академия наук
Институт прикладной математики им. М.В. Келдыша
На правах рукописи
Бахтин Владимир Александрович
Гибридная модель параллельного программирования DVM/OpenMP
Специальность 05.13.11 – математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей
А в т о р е ф е р а т
диссертации на соискание ученой степени
кандидата физико-математических наук
Москва – 2008 год
Работа выполнена в Институте прикладной математики
им. М.В. Келдыша РАН.
Научный руководитель – доктор физико-математических наук
Крюков Виктор Алексеевич
Официальные оппоненты:
– доктор физико-математических наук, член-корреспондент РАН
Воеводин Владимир Валентинович,
– кандидат физико-математических наук
Ефимкин Кирилл Николаевич
Ведущая организация: Институт системного программирования РАН
Защита состоится «10» июня 2008 г. в 11 часов на заседании Диссертационного совета Д 002.024.01 в Институте прикладной математики им. М.В. Келдыша РАН по адресу: 125047, Москва, Миусская пл., 4.
С диссертацией можно ознакомиться в библиотеке Института прикладной математики им. М.В. Келдыша РАН.
Автореферат разослан «7» мая 2008 г.
Ученый секретарь диссертационного совета,
доктор физико-математических наук Т.А. Полилова
Объект исследования и актуальность темы
Последние годы связаны с резким изменением направления развития процессоров – появлением многоядерных и многопоточных процессоров. Их эффективное использование требует повсеместного перехода с последовательных программ на параллельные программы. Для высокопроизводительных вычислений на кластерах и многопроцессорных ЭВМ с массовым параллелизмом (MPP) теперь требуется более глубокое распараллеливание, обеспечивающее, по крайней мере, два уровня параллелизма – уже привычный параллелизм между узлами кластера и дополнительный параллелизм между ядрами в узле. В настоящее время такой двухуровневый параллелизм наиболее легко и естественно выражать посредством использования между узлами модели передачи сообщений MPI, а внутри узлов – модели общей памяти Pthreads, или более высокоуровневой и более подходящей для вычислительных программ модели OpenMP. Однако, необходимость более глубокого распараллеливания и использования гибридной модели MPI/OpenMP, т.е. двух разных моделей программирования и соответствующих им разных инструментальных средств еще более усложняет и без того нелегкую работу по созданию параллельных программ. Поэтому проблема автоматизации создания параллельных программ становится в настоящее время чрезвычайно актуальной.
В 1994 году в ИПМ им. М.В.Келдыша РАН была предложена новая модель (DVM-модель) параллельного программирования, позволившая существенно автоматизировать разработку MPI-программ для кластеров. Однако широкое распространение SMP-кластеров (кластеров, использующих в качестве узлов мультипроцессоры) требовало расширения DVM-модели для более эффективного использования их двухуровневого параллелизма.
Цель работы
Целью данной работы являлась разработка гибридной модели DVM/OpenMP, которая позволит упростить создание программ для параллельных систем на базе многоядерных процессоров.
Научная новизна работы
Предложена новая модель и новый язык параллельного программирования – гибридная модель DVM/OpenMP и язык Fortran-DVM/OpenMP, позволяющие разрабатывать эффективные, переносимые программы для SMP-кластеров и высокопроизводительных систем с многоуровневым параллелизмом.
Разработан компилятор, преобразующий параллельные программы на языке Fortran-DVM/OpenMP в программы на стандартном языке Fortran OpenMP, выполняющиеся в узлах 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 и OpenMP – стандарты, существующие уже свыше 10 лет, и широко используемые для программирования научно-технических приложений для кластеров и мультипроцессоров.
Модель передачи сообщений. MPI
В модели передачи сообщений параллельная программа представляет собой множество процессов, каждый из которых имеет собственное локальное адресное пространство. Взаимодействие процессов – обмен данными и синхронизация – осуществляется посредством передачи сообщений. Обобщение и стандартизация различных библиотек передачи сообщений привели в 1994 году к появлению стандарта MPI (Message Passing Interface). Его широкое внедрение в последующие годы обеспечило коренной перелом в решении проблемы переносимости параллельных программ.
Основными недостатками MPI являются:
Модель параллелизма по управлению. OpenMP
Модель параллелизма по управлению (в западной литературе используется и другое название – модель разделения работы, work-sharing model) возникла уже давно как модель программирования для мультипроцессоров. На мультипроцессорах в качестве модели выполнения используется модель общей памяти. В этой модели параллельная программа представляет собой систему потоков, взаимодействующих посредством общих переменных и примитивов синхронизации. Основная идея модели параллелизма по управлению заключалась в следующем. Вместо программирования в терминах потоков предлагается расширить языки специальными управляющими конструкциями – параллельными циклами и параллельными секциями. Создание и уничтожение потоков, распределение между ними витков параллельных циклов или параллельных секций (например, вызовов процедур) – все это берет на себя компилятор.
Первая попытка стандартизовать такую модель привела к появлению в 1990 году проекта языка PCF Fortran (проект стандарта X3H5). Однако этот проект тогда не привлек широкого внимания и, фактически, остался только на бумаге. Но спустя несколько лет ситуация сильно изменилась – успехи в развитии элементной базы сделали очень перспективным и экономически выгодным создавать мультипроцессоры. Крупнейшие производители компьютеров и программного обеспечения объединили свои усилия и в октябре 1997 года выпустили описание языка Fortran OpenMP – расширение языка Фортран 77. Позже вышли аналогичные расширения языков Си, Си++ и Фортран 90/95.
OpenMP – это интерфейс прикладной программы, расширяющий последовательный язык программирования набором директив компилятора, вызовов функций библиотеки поддержки выполнения и переменных среды.
Главными недостатками OpenMP являются:
Гибридная модель MPI/OpenMP
Успешное внедрение OpenMP на мультипроцессорах, появление SMP-кластеров (узлами которых являются мультипроцессоры), привело к тому, что все шире начал использоваться гибридный подход, когда программа представляет собой систему взаимодействующих MPI-процессов, а каждый процесс программируется на OpenMP.
Такой подход имеет преимущества с точки зрения упрощения программирования в том случае, когда в программе есть два уровня параллелизма – параллелизм между подзадачами и параллелизм внутри подзадач. Такая ситуация возникает, например, при использовании многообластных (многоблочных) методов решения вычислительных задач. Программировать на MPI сами подзадачи гораздо сложнее, чем их взаимодействие, поскольку распараллеливание подзадачи связано с распределением элементов массивов и витков циклов между процессами. Организация же взаимодействия подзадач таких сложностей не вызывает, поскольку сводится к обмену между ними граничными значениями. Нечто подобное программисты делали раньше на однопроцессорных ЭВМ, когда для экономии памяти на каждом временном шаге выполняли подзадачи последовательно друг за другом.
Основной недостаток этого подхода очевиден – программисту надо знать и уметь использовать две разные модели параллелизма и разные инструментальные средства. А вот преимущества гибридного подхода по сравнению с MPI и целесообразность его использования на многоядерных кластерах – это вопрос, по которому единого мнения в программистском сообществе пока нет.
Наша позиция – в ближайшие пять-десять лет никаких реальных альтернатив использованию OpenMP в узлах многоядерного кластера не будет. Попробуем обосновать эту точку зрения.
Прежде всего, отметим, что для MPI-программ создается ситуация, аналогичная ситуации с последовательными программами. Если последовательные программы будут выполняться все медленнее по мере появления новых процессоров (из-за увеличения количества ядер и снижения быстродействия одного ядра), то и MPI-программы будут выполняться все медленнее, если не увеличивать количество MPI-процессов в них. Но увеличение количества процессов означает для большинства таких программ добавление новых уровней параллелизма. А сложность выражения многоуровневого параллелизма – это известный недостаток MPI. Кроме того, поскольку при распараллеливании программы прежде всего использовался ее крупнозернистый параллелизм (подзадачи, самые объемлющие циклы), то теперь надо добавлять уровни мелкозернистого параллелизма, для которого наиболее подходит модель общей памяти и OpenMP, а модель передачи сообщений может оказаться уже неэффективной.
Для многих программ, использующих нерегулярный доступ к данным или содержащих конвейеризуемые циклы с зависимостями, модель OpenMP более эффективна уже сейчас из-за меньшей латентности доступа к данным. В дальнейшем же, специфические особенности многоядерных процессоров (наличие локальных и/или разделяемых ядрами кэш-памятей, аппаратная поддержка барьерной синхронизации) будут учитываться при оптимизации OpenMP-программ компиляторами, которые ориентированы на поддержку продукции конкретных производителей многоядерных процессоров. Такую оптимизацию не могут делать компиляторы с последовательных языков для MPI-процессов.
Следующее очень важное преимущество OpenMP – отсутствие дублирования данных, используемых разными потоками. При использовании MPI происходит дублирование в MPI-процессах следующих данных:
Все эти свойственные MPI затраты дополнительной памяти становятся очень критичными для многоядерных узлов, поскольку имеется явная тенденция к сокращению объема оперативной памяти, приходящейся на одно ядро – ведь объем памяти и быстродействие процессора всегда сбалансированы, исходя из потребностей приложений, а быстродействие процессора будет повышаться за счет увеличения числа ядер в нем.
Использование OpenMP в узлах может быть обеспечено двумя способами – либо применением гибридных моделей (объединение OpenMP с другими моделями, например с MPI), либо использованием языков программирования, компиляторы с которых будут генерировать для узлов код на OpenMP.
Однако следует сразу заметить, что из применяемых на кластерах моделей только модель передачи сообщений реализуется в виде библиотек и может быть объединена с OpenMP без необходимости появления нового языка программирования и новых компиляторов. Поэтому альтернативой гибридному подходу MPI/OpenMP может быть только использование существующего или нового языка программирования, компилятор с которого должен обеспечивать генерацию для узлов программ на OpenMP, взаимодействующих между собой через передачу сообщений.
С этой точки зрения проанализированы модели и языки программирования, позволяющие создавать программы для кластеров – модель параллелизма по данным (язык HPF – High Performance Fortran), DVM-модель (языки Fortran-DVM и C-DVM), модель PGAS (язык Co-Array Fortran). Этот анализ показывает, что наиболее перспективной представляется гибридная модель программирования DVM/OpenMP, получающаяся путем объединения моделей DVM и OpenMP.
Вторая глава посвящена описанию гибридной модели параллельного программирования DVM/OpenMP и языка Fortran-DVM/OpenMP. Отмечены основные достоинства новой модели по сравнению с моделями OpenMP, MPI, DVM и MPI/OpenMP.
Рассматривается вычислительная сеть, каждый узел которой является мультипроцессором или многоядерным процессором (рис. 1).
Рис. 1. Вычислительная сеть
Для разработки гибридной модели DVM/OpenMP, которая позволила бы создавать программы, эффективно выполняющиеся на данной вычислительной сети, исследуются следующие три подхода к объединению моделей DVM и OpenMP:
Достоинства данного подхода:
Недостатки данного подхода:
В DVM-программе имеется информация:
Используя эту информацию, для некоторых DVM-программ можно получить соответствующие программы на языке Fortran-DVM/OpenMP автоматически. Все распределенные при помощи директив DISTRIBUTE и ALIGN массивы должны быть общими для всех нитей на узле (описаны при помощи спецификации SHARED). Все приватные переменные должны быть описаны при помощи спецификации PRIVATE. Все циклы, витки которых можно выполнять параллельно, можно распределить между нитями, используя директиву PARALLEL DO. Для циклов со спецификацией ACROSS необходимо организовать конвейерное выполнение.
Однако для большинства реальных программ такое автоматическое преобразование затруднено. В DVM-программе не достает информации о размноженных (нераспределенных) переменных. Такие переменные могут быть как общими, так и приватными для всех нитей. Для получения корректной программы, необходимо определить класс для каждой такой переменной – требуется проведение межпроцедурного анализа программы, а в некоторых случаях требуется и изменение структуры программы (например, разбиение одного COMMON-блока на несколько блоков).
Добавление в программу на языке Fortran-DVM спецификаций для определения класса переменных (PRIVATE, SHARED, THREADPRIVATE), а также спецификаций для инициализации значений приватных переменных (FIRSTPRIVATE, LASTPRIVATE, COPYIN, COPYPRIVATE), позволяют получать без сложного межпроцедурного анализа корректные программы, использующие MPI для взаимодействия между узлами и OpenMP для распределения вычислений внутри узла.
Преимущества данного подхода:
Недостаток данного подхода, заключается в том, что параллельная программа на новом языке Fortran-DVM/OpenMP не является параллельной программой на стандартном языке Fortran OpenMP.
Для данного похода была реализована экспериментальная версия компилятора, которая автоматически конвертировала существующие программы на языке Fortran-DVM в программы на языке Fortran-DVM/OpenMP. Однако по мере расширения использования OpenMP и появления большого количества приложений, написанных в данной модели – стало понятно, что второй подход тоже не годится.
В п. 2.1 данный подход рассматривается более подробно, описывается гибридная модель параллельного программирования DVM/OpenMP.
Рассмотрим вычислительную сеть,
Рис. 2. Модель DVM/OpenMP
каждый узел которой является мультипроцессором или отдельным процессором (рис. 2). На каждом узле выполняется параллельная программа на языке Fortran OpenMP. Распределение данных и вычислений между узлами, а также доступ к удаленным данным выполняется согласно модели DVM.
В программе на языке Fortran-DVM/OpenMP можно описать следующие уровни параллелизма:
Любые из указанных уровней в программе могут отсутствовать. Если в программе описаны несколько уровней параллелизма, то порядок их вложенности должен соответствовать порядку их перечисления в приведенном выше списке.
Параллелизм распределенных задач реализуется распределением данных и независимых вычислений на секции массива узлов. Параллелизм распределенных многомерных циклов реализуется распределением витков тесно-гнездового цикла между узлами. При этом каждый виток такого параллельного цикла полностью выполняется на одном узле.
В п. 2.2 приведено краткое описание языка Fortran-DVM/OpenMP и примеры программ на этом языке. Синтаксис директив языка Fortran-DVM/OpenMP описан в приложении.
Спецификации параллелизма оформляются как спецкомментарии, что позволяет использовать программу на языке Fortran-DVM/OpenMP как стандартную последовательную, так и стандартную параллельную OpenMP-программу.
Рассмотрим пример параллельной программы на языке Fortran-DVM/OpenMP алгоритма численного решения двухмерного уравнения Лапласа методом Якоби.
PROGRAM JAC_DVM_OpenMP
PARAMETER (L=8, ITMAX=20)
REAL A(L,L), B(L,L)
CDVM$ DISTRIBUTE (BLOCK, BLOCK) :: A
CDVM$ ALIGN B(I,J) WITH A(I,J)
C arrays A and B with block distribution
PRINT *, '********** TEST_JACOBI **********'
!$OMP PARALLEL
DO IT = 1, ITMAX
CDVM$ PARALLEL (J, I) ON A(I, J)
!$OMP DO
DO J = 2, L-1
!$OMP PARALLEL DO
DO I = 2, L-1
A(I, J) = B(I, J)
ENDDO
ENDDO
CDVM$ PARALLEL (J, I) ON B(I, J),SHADOW_RENEW (A)
C Copying shadow elements of array A from
C neighboring nodes before loop execution
!$OMP DO
DO J = 2, L-1
!$OMP PARALLEL DO
DO I = 2, L-1
B(I, J) = (A( I-1, J ) + A( I, J-1 ) +
* A( I+1, J ) + A( I, J+1 )) / 4
ENDDO
ENDDO
ENDDO
!$OMP END PARALLEL
END
При помощи директивы DISTRIBUTE массив A распределяется между узлами. Оператор вида 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). Поскольку массив A распределен, то эти элементы могут находиться на соседних узлах, поэтому перед выполнением цикла необходимо загрузить эти данные – для этого используется спецификация SHADOW_RENEW.
В результате выполнения директивы PARALLEL ON вычисления распределены по узлам. Для распределения этих вычислений внутри узла используются OpenMP-директивы. При помощи директивы PARALLEL создается группа нитей, между которыми при помощи директивы DO и распределяется вся работа (распределяются витки циклов, которые обрабатывают локальную часть массива).
В п. 2.3 описаны преимущества разработанной гибридной модели перед моделями OpenMP, MPI, DVM и MPI/OpenMP.
В п. 2.3.1 описаны достоинства модели DVM/OpenMP по сравнению с моделью OpenMP.
Главное достоинство – способность работать не только на мультипроцессорах и DSM-системах, но и на кластерах, а также больших DSM-системах, на которых OpenMP не эффективен (поэтому на них и используют гибридную модель 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 является стандартной параллельной программой в модели OpenMP, которая может быть преобразована с помощью специального компилятора в программу в модели MPI/OpenMP. Программа же в модели DVM не являлась стандартной параллельной программой, а могла рассматриваться только как стандартная последовательная программа.
В п. 2.3.4 описаны достоинства модели DVM/OpenMP по сравнению с моделью MPI/OpenMP.
Большим достоинством является то, что модели DVM и OpenMP являются очень близкими моделями по содержанию и оформлению спецификаций параллелизма. Обе модели многое унаследовали от проекта стандарта PCF Fortran и исходят из наличия глобального адресного пространства и единого потока управления. Модели MPI и OpenMP не имеют ничего общего ни по содержанию, ни по изобразительным средствам – модель 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 описаны основные преобразования, выполняемые компилятором:
В п. 3.2 приводится схема функционирования компилятора. Подробно описаны преобразования, выполняемые компилятором для директивы PARALLEL ON.
При преобразовании DVM-директив в вызовы функций системы поддержки компилятор анализирует OpenMP-директивы, заданные в программе. В случае если 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 (BT, LU, SP), задачи CONVD и двух программ из пакета “РЕАКТОР”. Приводятся характеристики эффективности выполнения параллельных программ.
В процессе создания языка Fortran-DVM/OpenMP в течение нескольких лет постоянно велась работа по исследованию применимости языка для программирования реальных приложений. Эта работа позволила сделать обоснованный выбор подхода к объединению моделей DVM и OpenMP, найти эффективные решения для компилятора.
В п. 4.1 содержится описание особенностей программирования и характеристик эффективности трех модельных приложений (BT, LU, SP) из пакета тестов NAS, решающих тремя различными методами задачи вычислительной гидродинамики (3D Навье-Стокс).
При создании версии программ на языке Fortran-DVM/OpenMP за основу были использованы MutliZone версии тестов NAS, написанных в гибридной модели MPI/OpenMP. В данных тестах MPI применяется для отображения зон по узлам кластера, а OpenMP – для распределения вычислений внутри зоны. Каждая зона рассчитывается независимо от других, по завершении обсчета зоны осуществляется обмен граничными значениями. Вся работа по отображению зон по узлам и взаимодействию между узлами была переписана на DVM с использованием механизма задач. OpenMP директивы остались без каких либо изменений. Ниже (в табл. 1) приводится информация о размере MPI/OpenMP и DVM/OpenMP-версий тестов NAS в строках (без учета комментариев).
|
Название теста |
MPI/OpenMP |
DVM/OpenMP |
|
BT |
3377 |
3257 |
|
LU |
3431 |
3344 |
|
SP |
3013 |
2887 |
Табл. 1. Размеры MPI/OpenMP и DVM/OpenMP-версий тестов NAS.
На следующих диаграммах (рис. 3-14) показаны времена выполнения тестов NAS класса A на машине Regatta (IBM eServer pSeries 690), установленной в Московском государственном университете им. М. В. Ломоносова. Приводятся времена выполнения тестов в секундах при использовании разного числа нитей и MPI-процессов.
Диаграммы показывают, что гибридные модели DVM/OpenMP и MPI/OpenMP близки по эффективности. На одних и тех же конфигурациях (<число MPI-процессов>х<число нитей>) DVM и MPI-версии тестов ведут себя практически одинаково.
Использование в гибридной модели нитей дает небольшой выигрыш при работе теста SP на 2-х и 4-х процессорах, но при работе на 8-ми процессорах выигрыша уже нет, а на 16-ти процессорах использование нитей даже замедляет выполнение теста.
Для теста LU использование гибридной модели дает выигрыш и по сравнению с MPI (или DVM), и по сравнению с OpenMP – минимальное время на 16 процессорах достигается при использовании 4-х процессоров и 4-х нитей.
В отличие от предыдущих тестов, в которых все зоны имеют один и тот же размер 32x32x16 (для класса A), в тесте BT – все зоны различного размера: от 13x13x16 и до 58x58x16. Поэтому зоны между MPI-процессами распределяются таким образом, чтобы обеспечить их одинаковую загрузку. При увеличении числа MPI-процессов свыше 4-х такая балансировка становится невозможной, поскольку количество зон ограничено (всего 16 зон для класса A). В результате, программа перестает ускоряться. Использование OpenMP дает возможность сократить число MPI-процессов и улучшить балансировку. Минимальное время выполнения теста достигается при использовании 4-х MPI-процессов и 4-х нитей.
Рис. 3. SP на 2-х процессорах |
Рис. 4. SP на 4-х процессорах |
Рис. 5. SP на 8-ми процессорах |
Рис. 6. SP на 16-ти процессорах |
Рис. 7. LU на 2-х процессорах |
Рис. 8. LU на 4-х процессорах |
Рис. 9. LU на 8-ми процессорах |
Рис. 10. LU на 16-ти процессорах |
Рис. 11. BT на 2-х процессорах |
Рис. 12. BT на 4-х процессорах |
Рис. 13. BT на 8-ми процессорах |
Рис. 14. BT на 16-ти процессорах |
В п. 4.2 приводятся особенности программирования задачи CONVD (задачи С.Д. Устюгова), которая считает трехмерную магнитную газодинамику для расчета солнечной конвекции с использованием реалистичной физической модели. Исследуется влияние магнитного поля на тепловую структуру конвективных перемещений в радиационном слое, характерные масштабы развития конвекции и глубина проникновения конвекции. Моделируется развитие конвекции в верхних слоях солнечной фотосферы на размерах локальной супергрануляции. Решаются уравнения полностью сжимаемой радиационной магнитной газодинамики с учетом динамической вязкости и гравитации.
Для получения программы на языке Fortran-DVM/OpenMP использовалась DVM-версия этой программы. В результате преобразования, описанного во второй главе, была получена программа в модели DVM/OpenMP. Размер последовательной программы составляет 3214 операторов языка Fortran, размер DVM-программы – 3380 строк, размер полученной DVM/OpenMP-программы – 3649 строк. Существенное усложнение Fortran-DVM/OpenMP программы объясняется тем, что в задаче имеются циклы с зависимостью по данным, распараллеливание которых на OpenMP требует больших усилий (низкоуровневое распараллеливание).
Данная задача считается в Межведомственном суперкомпьютерном центре РАН на суперкомпьютере "MBC-50К". Задача очень требовательна к объему оперативной памяти. До проведения модернизации суперкомпьютера на вычислительном узле запускались 4 MPI-процесса, которые могли использовать до 4 Гбайт оперативной памяти узла. DVM-версия задачи запускалась на 225 процессорах. После проведения модернизации (использования 4-х ядерных процессоров) – на узле стали запускаться 8 MPI-процессов, а объем оперативной памяти остался прежним. В результате DVM-версия программы перестала работать.
Многие пользователи суперкомпьютерного центра столкнулись с подобной проблемой. Поэтому была реализована возможность задания количества запускаемых на узле MPI-процессов. Однако при уменьшении числа запускаемых на узле MPI-процессов возрастает количество требуемых задачей узлов – время ожидания задачи в очереди увеличивается, а предоставляемые ресурсы используются не полностью.
Версия программы на языке Fortran-DVM/OpenMP использует все ресурсы на узле и поэтому выполняется заметно быстрее (табл. 2).
|
Версия программы |
57 вычислительных узлов |
Время выполнения, сек |
|
DVM-программа |
225 MPI-процессов (задействовано 4 процессора) |
259.50 |
|
DVM/OpenMP-программа |
225 MPI-процессов x 2 нити (задействовано 8 процессоров) |
159.47 |
Табл. 2. Время выполнения задачи CONVD в СКЦ РАН
В п. 4.3 описываются особенности распараллеливания программ, входящих в пакет “РЕАКТОР”.
В п. 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 строк. Применение гибридной модели для этой задачи позволило на суперкомпьютере "MBC-50К" эффективнее использовать ядра узла (из-за отсутствия дублирования информации в памяти, свойственного MPI-модели и DVM-модели), что привело почти к 2-х кратному ускорению программы.
В п. 4.4 описан важный побочный результат проведенного исследования применимости языка – получена уникальная информация о проблемах отладки программ на языках Fortran-DVM/OpenMP и Fortran OpenMP, позволившая сделать вывод о необходимости создания специальных средств отладки и реализации соответствующего специального режима компиляции.
Анализ приведенных в разделах 4.1-4.3 характеристик эффективности позволяет сделать следующие выводы:
В заключении сформулированы основные результаты работы.