Система автоматизации распараллеливания отображения на мультипроцессор (стр. 3 из 9)
Для распараллеливания циклов существует директива DO (см. Рис. 4). В качестве "ключей" можно указать описатели PRIVATE(список), FIRSTPRIVATE(список), SHARED(список), ключ REDUCTION, а также ключи ORDERED и SCHEDULE.
Ключ SCHEDULE используется для указания дисциплины планирования выполнения цикла нитями и имеет вид: SCHEDULE(тип[,M])
Он указывает, каким образом итерации цикла будут распределены для выполнения между нитями бригады. В качестве параметра "тип" можно указать следующие:
· STATIC [,m] - блочно-циклическое распределение итераций: первый блок из m итераций выполняет первая нить, второй блок - вторая и т.д. до последней нити, затем распределение снова начинается с первой нити; по умолчанию значение m равно 1;
· DYNAMIC [,m] - динамическое распределение итераций с фиксированным размером блока: сначала все нити получают порции из m итераций, а затем каждая нить, заканчивающая свою работу, получает следующую порцию опять-таки из m итераций;
· GUIDED [,m] - динамическое распределение итераций блоками уменьшающегося размера; аналогично распределению DYNAMIC, но размер выделяемых блоков все время уменьшается, что в ряде случаев позволяет аккуратнее сбалансировать загрузку нитей;
· RUNTIME - способ распределения итераций цикла выбирается во время работы программы в зависимости от значения переменной OMP_SCHEDULE.
·
Еслив OpenMP-директиве END DO задано NOWAIT, вконцецикланитинесинхронизируются. Ключ REDUCTION директивы !$OMP PARALLEL DO обозначаетредукционнуюпеременную(см. Рис. 5).
В OpenMP имеется также возможность использовать сокращения, позволяющие объединять инструкции PARALLEL/END PARALLEL и DO/ENDDO в пару PARALLEL DO/END PARALLEL DO.
Директива SECTIONS (см. Рис. 6) используется для распределения работы между нитями в "неитерационном" случае. Ключи, как и ранее, могут указывать на тип переменных (PRIVATE, FIRSTPRIVATE и т.д.), а также содержать ключ REDUCTION. OpenMP-конструкция SECTIONS позволяет нескольким нитям выполнять параллельно обычный линейный участок программы на Фортране, разбитый на "секции" - блоки операторов языка. Эти секции могут содержать в себе, в частности, вызовы фортрановских подпрограмм.
Богатые возможности предоставляют средства OpenMP и для синхронизации. Соответствующие директивы позволяют, в частности, установить барьер (!$OMP BARRIER) или обеспечить синхронизацию (!$OMP ATOMIC), предохраняющую от одновременной записи несколькими нитями в одно и то же поле оперативной памяти. Это позволяет предотвратить ситуацию гонки. Другая полезная директива, о которой стоит упомянуть - это !$OMP FLUSH. Она заставляет в соответствующей точке программы получить "согласованное" между нитями состояние оперативной памяти (при этом переменные из регистров будут записаны в память, сбросятся буферы записи и т.д.). Пара директив MASTER: END MASTER выделяет участок кода, который будет выполнен только нитью-мастером. Остальные нити пропускают данный участок и продолжают работу с выполнения оператора, расположенного следом за директивой END MASTER. С помощью директивы CRITICALоформляется критическая секция программы. В каждый момент времени в критической секции может находиться не более одной нити (см. Рис. 7). Если критическая секция уже выполняется какой-либо нитью P0, то все другие нити, выполнившие директиву для секции с данным именем, будут заблокированы, пока нить P0 не закончит выполнение данной критической секции. Как только P0 выполнит директиву END CRITICAL, одна из заблокированных на входе нитей войдет в секцию. Если на входе в критическую секцию стояло несколько нитей, то случайным образом выбирается одна из них, а остальные заблокированные нити продолжают ожидание. Все неименованные критические секции условно ассоциируются с одним и тем же именем.
Директива ORDERED заставляет коды Fortran, заключенные внутри пары ORDERED/END ORDERED, выполняться в "естественном" порядке (в той, в которой итерации цикла выполняются при нормальном последовательном выполнении). Эта пара директив может присутствовать только в динамической области действия директивы DO (или PARALLEL DO), в которой указан ключ ORDERED. Такие директивы могут использоваться для организации печати в нормальной - скажем, по возрастанию счетчика цикла- последовательности [2].
1.3 Распараллеливание для OpenMP
Преобразование последовательной программы в параллельную – процесс нетривиальный, неоднозначный и неформальный. Распараллеливание в OpenMP- программу, в конечном счете, сводится к принятию решения по распределению нитей и вычислений и расстановке в текст программы соответствующих OpenMP-директив. Разные способы объявления данных, распределения вычислений и синхронизации нитей могут иметь разную эффективность, причем эффективность конкретного распределения может зависеть как от конфигурации системы, так и от размера задачи.
Из этого следует, что:
· трудно рассчитывать на создание системы полностью автоматизирующей это преобразование, т.е. распараллеливание представляется как итерационный процесс взаимодействия пользователя с системой;
· система не должна ограничивать выбор, а по возможности, должна и подсказывать варианты распараллеливания;
· система должна допускать вмешательство пользователя, т.е. принятие решений самим пользователем;
1.4 Cуть и актуальность проблемы
Преимущества OpenMP:
1) Разработчик не создает новую параллельную программу, а просто последовательно добавляет в текст последовательной программы OpenMP-директивы.
2) OpenMP - достаточно гибкий механизм, предоставляющий разработчику большие возможности контроля над поведением параллельного приложения.
3) Предполагается, что OpenMP-программа на однопроцессорной платформе может быть использована в качестве последовательной программы, т.е. нет необходимости поддерживать последовательную и параллельную версии. Директивы OpenMP просто игнорируются последовательным компилятором.
4) Одним из достоинств OpenMP его разработчики считают поддержку так называемых "orphan" (оторванных) директив, то есть директивы синхронизации и распределения работы могут не входить непосредственно в лексический контекст параллельной области.
5) OpenMP - стандарт, который разработан представительным форумом (HP, IBM, Intel, SGI, Sun, Fujitsu, NEC) для программирования мультипроцессоров и DSM-систем
6) Поддерживается в компиляторах языков Fotran, C, C++ для всех основных типов процессоров.
Однако, "легкость" программирования на OpenMP возможно еще упростить, за счет "системы автоматизации распараллеливания". Если "последовательный" программист будет видеть анализ своей программы и рекомендации по распараллеливанию, "умственные затраты" на вставку распараллеливающих директив сведутся к минимуму или пропадут вообще. Другой вариант использования системы - анализ эффективности уже распараллеленной программы или сравнение ее с другими вариантами распараллеливания. В этом случае заметно облегчается поиск оптимального распараллеливания. Таким образом, при существовании такой системы любой последовательный программист сможет без дополнительной подготовки преобразовывать свой код к "параллельному" варианту. Это особенно актуально для программистов, производящих сложные вычисления, занимающие огромное количество времени. Использование мультипроцессорных систем должно дать заметное ускорение таких вычислений.
2. Цели дипломной работы
2.1 Цели проекта "Система автоматизации распараллеливания"
Данная дипломная работа является лишь частью проекта автоматизации распараллеливания программ, поэтому сначала остановимся на проекте.
Рис. 8. Проект: Система автоматизации распараллеливания.
На Рис. 8 схематически показаны составляющие проекта: "Анализ программы", "Эксперт для мультипроцессора" (OpenMP) и "Эксперт для кластера" (DVM).
Пользователь создает последовательную программу на языке Fortran. В итоге работы системы, пользователь получает информацию для анализа:
· дерево циклов; для каждого цикла – его параметры и атрибуты (результаты анализа);
· описания данных;
· описание использования массивов в циклах и найденные зависимости;
· список предложенных (в том числе рассмотренных, но отвергнутых) вариантов распределения (задача "Эксперта");
· созданные и модифицируемые пользователем наборы конфигураций целевой машины и размеров задач;
· для каждого предложенного варианта распараллеливания (всех конфигураций и размеров) и каждого цикла и всей программы, как корня дерева циклов, – оценки времени выполнения и качества распараллеливания для данного варианта (задача "Эксперта");
Программа, поступая в систему автоматизации распараллеливания, проходит анализ, на основании которого формируется База Данных, в которую входят: дерево циклов; описания массивов, описание использования массивов в циклах; дополнительные комментарии.
С информацией из базы данных "Эксперты" ищут самые оптимальные способы распараллеливания и добавляют информацию о них в базу данных. Код программы на выходе системы не изменяется, а всего лишь добавляются комментарии, где рекомендуется вставить директивы OpenMP или DVM (возможно несколько лучших вариантов), насколько будут эффективны эти вставки, а также информация из анализа.