Система автоматизации распараллеливания Отображение на SMP-кластер

Оглавление
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.
Данное направление является весьма востребованным по следующим причинам:
- Распараллеливание готовой программы требует от программиста тщательного анализа ее кода (подчас, чужого), что делает процесс распараллеливания достаточно сложным, и подчас приводит к неудовлетворительным результатам. К тому же, в процессе распараллеливания могут быть допущены ошибки. Если бы распараллеливание осуществлялось автоматически, то появление новых ошибок было бы исключено.
- Распараллеливание уже готовых последовательных программ является очень востребованным, особенно в области научного программирования, где за многолетнюю историю жизни языка Fortran была написано огромное количество программ, не потерявших свою актуальность. Таким образом отпала бы необходимость писать все эти программы заново, но уже в параллельном варианте, и появилась бы возможность использовать старые наработки.
- Для различных конфигураций системы и разного размера входных данных, оптимальное распределение вычислений может также отличаться. Человек не всегда способен учесть такие факторы Автоматический распараллеливатель же учитывает конфигурацию кластера при формировании программы, и для нового кластера может формировать наиболее оптимальный код.
Постановка задачи
1.5 Структура "Системы автоматизации распараллеливания"
Данная дипломная работа посвящена разработке блока экспериментальной системы автоматизации распараллеливания, поэтому сначала ознакомимся с её структурой:
Рисунок 1. Экспериментальная система автоматизации распараллеливания
Пользователь создает последовательную программу на языке Fortran. Программа, поступая в систему автоматизации распараллеливания, проходит анализ, на основании которого формируется База данных. В Базу данных входят: дерево циклов; описания массивов, описание использования массивов в циклах; специальные пользовательские комментарии и прочее.
Пользуясь информацией из Базы данных, DVM/OpenMP-эксперт формирует варианты распределения вычислений и данных, и ищет наилучший вариант. Для поиска требуется информация о количестве вычислительных узлов, их производительности, а также латентности вычислительно сети. Далее, База данных подается на вход Генератору, который формирует параллельный код на языке Fortran-DVM/OpenMP. Код программы на выходе системы не изменяется, в него лишь добавляются директивы OpenMP и DVM.
1.6 Цель работы " DVM/OpenMP-эксперт"
К моменту написания работы, Система автоматизации распараллеливания содержала блок, именуемый DVM-экспертом. DVM-эксперт, пользуясь результатами анализа программы, распараллеливает программу на языке Fortran-DVM. Целью дипломной работы является доработка DVM-эксперта до DVM/OpenMP-эксперта.
DVM/OpenMP-эксперт, пользуясь результатами анализа, распараллеливает программу на языке Fortran-DVM/OpenMP и заносит информацию о полученной параллельной программе в Базу данных.
Предыдущие решения "систем автоматизации распараллеливания на SMP-кластер"
В настоящее время имеется только одна развивающаяся система автоматизированного распараллеливания для кластеров – Parawise (системы FORGE Magic/DM и BERT77 уже не развиваются и не поддерживаются). Только для нее имеется информация о применимости для реальных Fortran-приложений и эффективности выполнения распараллеленных программ.
1.7 Система Parawise
Система Parawise является коммерческой системой, созданной компанией Parallel Software Products совместно с NASA Ames на базе системы CAPTools, разработанной в Лондонском университете Гринвича в середине 90-х годов. [3]
Общая схема процесса получения параллельной программы из последовательной состоит из следующих этапов:
o Системе Parawise подаётся на вход программа на языке FORTRAN (F77/F90/F95).
o Пользователь выбирает способы анализа данной программы.
o Parawise анализирует программу и формирует вопросы, на которые пользователь обязан дать ответ для успешного распараллеливания.
o Пользователь следует по построенному системой графу зависимостей, отвечает на поставленные вопросы и участвует в выборе варианта распределения массивов.
o Система создаёт параллельный код программы.
o Пользователь проверяет результаты распараллеливания, и, если они не удовлетворительные, заново отвечает на поставленные вопросы или изменяет программу. [7]
Главным достоинством системы Parawise являются развитые возможности межпроцедурного анализа, которые создавались в течение многих лет. Главный недостаток – программист должен сам принимать ответственное решение о том, какие массивы и каким образом требуется распределить между процессорами. [3]
В отличие от Parawise, DVM/OpenMP-экспертом будет использовать диалог с программистом только для уточнения свойств последовательной программы, а выбор наилучших решений по ее распараллеливанию осуществлять полностью автоматически, без участия программиста. К тому же, DVM/OpenMP-эксперт учитывает вычислительную мощность узлов кластера при распределении работы между процессорами.

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать полную версию