Система автоматизации распараллеливания. Отображение на 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-кластер"
- 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-эксперт"
Страницы: 1, 2, 3, 4, 5, 6
|
