Система автоматизации распараллеливания Отображение на SMP-кластер (стр. 1 из 8)
1.Аннотация
2.Введение
2.1Развитие вычислительной техники. SMP-кластеры.
2.2Параллельное программирование
2.3Модель параллелизма DVM/OpenMP
2.3.1Преимущества DVM/OpenMP
2.4Актуальность работы
3.Постановка задачи
3.1Структура "Системы автоматизации распараллеливания"
3.2Цель работы "DVM/OpenMP-эксперт"
4.Предыдущие решения "систем автоматизации распараллеливания на SMP-кластер"
4.1Система Parawise
5.Исследование и построение решения задачи
5.1Автоматическое распараллеливание программ на DVM и DVM/OpenMP
5.2Структура DVM-эксперта
5.3Структура DVM/OpenMP-эксперта
5.3.1Варианты распараллеливания на OpenMP
6.Практическая реализация
6.1Список используемых терминов
6.2Блок поиска DVM/OpenMP-вариантов
6.2.1Краткий алгоритм работы
6.2.2Входные данные
6.2.3Детальный алгоритм работы
6.2.4Оценочная функция варианта распараллеливания гнезда циклов на DVM/OpenMP.
6.2.4.1Оценка времени выполнения цикла, не распараллеленного на OpenMP.
6.2.4.2Оценка времени выполнения параллельного цикла без конвейера
6.2.4.3Оценка времени выполнения параллельного цикла с конвейером
6.2.4.4Оценка времени выполнения гнезда циклов
6.3Блок поиска наилучшего DVM/OpenMP-варианта
6.3.1Характеристики эффективности параллельной программы
6.3.2Алгоритм пересчета характеристик эффективности
6.4Особенности реализации
6.4.1Классы решаемых задач
6.4.2Специальные комментарии.
6.4.3Аргументы командной строки
6.5Результаты тестирования
7.Заключение
8.Список цитируемой литературы
Приложение А. Графики времен выполнения и ускорений распараллеленных тестовых программ
1. Аннотация
Целью данной работы являлась разработка алгоритма преобразования последовательной программы на языке Fortran в параллельную программу на языке Fortran-DVM/OpenMP. Это преобразование осуществляет блок ("DVM/OpenMP-эксперт") экспериментальной системы автоматизации распараллеливания, используя результаты анализа информационной структуры последовательной программы.
К моменту начала работы над поставленной задачей система автоматизации распараллеливания содержала блок, именуемый "DVM-экспертом", который автоматизирует распараллеливание Fortran-программы на кластер. В рамках дипломной работы DVM-эксперт был доработан до DVM/OpenMP-эксперта, автоматизирующего распараллеливание Fortran-программ на SMP-кластер.
Разработанные алгоритмы были реализованы, включены в состав экспериментальной системы и проверены при распараллеливании тестовых примеров.
1. Введение
1.1 Развитие вычислительной техники. SMP-кластеры
Вычислительная техника в своем развитии по пути повышения быстродействия ЭВМ приблизилась к физическим пределам. Время переключения электронных схем достигло долей наносекунды, а скорость распространения сигналов в линиях, связывающих элементы и узлы машины, ограничена значением 30 см/нс (скоростью света). Поэтому дальнейшее уменьшение времени переключения электронных схем не позволит существенно повысить производительность ЭВМ. В этих условиях требования практики (сложные физико-технические расчеты, многомерные экономико-математические модели и другие задачи) по дальнейшему повышению быстродействия ЭВМ могут быть удовлетворены только путем распространения принципа параллелизма на сами устройства обработки информации и создания многомашинных и многопроцессорных (мультипроцессорных) вычислительных систем. Такие системы позволяют распараллелить выполнение программы или одновременно выполнять несколько программ.
Последние годы во всем мире происходит бурное внедрение вычислительных кластеров. Вычислительный кластер – это мультикомпьютер, состоящий из множества отдельных компьютеров (узлов), связанных между собой единой коммуникационной системой. Каждый узел имеет свою локальную оперативную память. При этом общей физической оперативной памяти для узлов не существует. Если в качестве узлов используются мультипроцессоры (мультипроцессорные компьютеры с общей памятью), то такой кластер называется SMP-кластером.
Привлекательной чертой кластерных технологий является то, что они позволяют для достижения необходимой производительности объединять в единые вычислительные системы компьютеры самого разного типа, начиная от персональных компьютеров и заканчивая мощными суперкомпьютерами. Таким образом, кластеры являются легко-масштабируемыми. Широкое распространение кластерные технологии получили как средство создания систем суперкомпьютерного класса из составных частей массового производства, что значительно удешевляет стоимость вычислительной системы.
В то же самое время, для повышения производительности кластера, в качестве узлов нередко используются мультипроцессоры. Таким образом, теперь программист имеет дело с двумя уровнями параллелизма – параллельное выполнение задач на узлах кластера, и параллельное выполнение подзадач на ядрах мультипроцессора.
1.2 Параллельное программирование
В настоящее время практически все параллельные программы для кластеров разрабатываются с использованием низкоуровневых средств передачи сообщений (MPI). Однако MPI-программы имеют ряд существенных недостатков:
· низкий уровень программирования и как следствие, высокая трудоемкость разработки программ;
· сложность выражения многоуровневого параллелизма программы;
· MPI-программы, как правило, неспособны эффективно выполняться на кластерах, у которых процессоры имеют разную производительность.
В то же время, на текущий момент так и нет и общепризнанного высокоуровневого языка параллельного программирования, позволяющего эффективно использовать возможности современных ЭВМ.
Таким образом, разработка программ для высокопроизводительных кластеров, и в особенности SMP-кластеров, продолжает оставаться исключительно сложным делом, доступным узкому кругу специалистов и крайне трудоемким даже для них.
Попытки разработать автоматически распараллеливающие компиляторы для параллельных ЭВМ с распределенной памятью, проведенные в 90-х годах (например, Paradigm, APC), привели к пониманию того, что полностью автоматическое распараллеливание для таких ЭВМ реальных производственных программ возможно только в очень редких случаях. В результате, исследования в области автоматического распараллеливания для параллельных ЭВМ с распределенной памятью практически были прекращены.
Исследователи сосредоточились на двух направлениях:
o разработка высокоуровневых языков параллельного программирования (HPF, OpenMP-языки, DVM-языки, CoArray Fortran, UPC, Titanium, Chapel, X10, Fortress);
o создание систем автоматизированного распараллеливания (CAPTools/Parawise, FORGE Magic/DM, BERT77), в которых программист активно вовлечен в процесс распараллеливания. [3]
Остановим свое внимание на высокоуровневом языке параллельного программирования DVM/OpenMP.
1.3 Модель параллелизма DVM/OpenMP
В последнее время для вычислительных систем, сочетающих в себе одновременно характеристики архитектур, как с общей, так и с распределенной памятью, используется так называемая "гибридная" модель. При этом программа представляет собой систему взаимодействующих процессов, а каждый процесс программируется на OpenMP. Рассмотрим вычислительную сеть, каждый узел которой является мультипроцессором или отдельным процессором:
На первом этапе определяются массивы, которые могут быть распределены между узлами (распределенные данные). Эти массивы специфицируются DVM-директивами отображения данных. Остальные переменные (распределяемые по умолчанию) отображаются по одному экземпляру на каждый узел (размноженные данные). Распределение данных определяет множество локальных или собственных переменных для каждого узла. Распределив по узлам данные, пользователь должен обеспечить и распределение вычислений по узлам. При этом должно выполняться правило собственных вычислений: на каждом узле выполняются только те операторы присваивания, которые изменяют значения переменных, размещенных на данном узле. В свою очередь, на узле эти вычисления могут быть распределены между нитями средствами OpenMP.
Основным методом распределения вычислений по узлам является явное задание пользователем распределения между узлами витков цикла. При этом каждый виток такого цикла полностью выполняется на одном узле. Выполнение по правилу собственных вычислений операторов вне распределенного параллельного цикла обеспечивается автоматически компилятором, однако это требует существенных накладных расходов.
На следующем этапе необходимо организовать доступ к удаленным данным, которые могут потребоваться при вычислении значений собственных переменных. [4]
1.3.1 Преимущества DVM/OpenMP
Во-первых, DVM/OpenMP является достаточно высокоуровневым языком параллельного программирования, что придает удобство процессу написания параллельных программ.
Во-вторых, DVM/OpenMP-программа – это последовательная программа, снабженная директивами-псевдокомментариями, задающими распределение данных и вычислений. Директивы не видны обычному компилятору. Таким образом программа, написанная на Fortran-DVM/OpenMP может использоваться сразу в четырех качествах:
· Последовательная программа на языке Fortran
· Параллельная Fortran-OpenMP программа для мультипроцессора
· Параллельная Fortran-DVM программа для кластера
· Параллельная Fortran-DVM/OpenMP программа для SMP-кластера
Соответственно, для однопроцессорной системы, мультипроцессора, кластера и SMP-кластера достаточно поддерживать всего одну версию программы.
1.4 Актуальность работы
Работа посвящена написанию системы автоматизации распараллеливания программ. Автоматическое распараллеливание последовательных программ предполагает преобразование существующих последовательных программ в параллельный код. В качестве языка параллельного программирования выбран DVM/OpenMP.