Модели параллельных вычислений и DVM технология разработки параллельных программ (1158289)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

WinterSchool – 2006 - 5 - 21.9.2019

Лабораторный практикум

"Модели параллельных вычислений и DVM‑технология разработки параллельных программ"

Общее описание лабораторного практикума

Цели и задачи практикума:

Приобретение навыков разработки и отладки параллельных программ типовых вычислительных алгоритмов в модели DVM (модель параллелизма по данным и параллелизма задач).

План выполнения лабораторного практикума:

Практикум включает:

1. Проведение лекционных занятий (6 час). Лекционные занятия включают следующие темы:

• сравнительный анализ моделей параллельного программирования вычислительных задач;

• краткое введение в методы распараллеливания программ в модели DVM;

• краткое введение в методы отладки правильности и производительности параллельных программ в модели DVM.

Полностью методические материалы изложены в руководствах [1,2], которые предоставляются участникам до начала проведения школы.

1. Проведение практического занятия (2 часа) по распараллеливанию существующих ("старых") последовательных программ.

2. Проведение практического занятия (2 часа) по разработке параллельных программ с использованием двух уровней параллелизма модели DVM.

На каждом практическом занятии участники школы выполняют одно задание.

По завершении разработки программ участники проводят эксперименты по достижению максимальной производительности на определенном количестве процессоров с варьированием виртуальной решетки процессоров.

Необходимое оборудование и ПО:

Вычислительный кластер МВС15000 (МСЦ), ANT (НИВЦ МГУ), система DVM .

Необходимый уровень подготовки:

Для успешного выполнения практикума предполагается наличие следующих знаний:

• Знание языков программирования Си и Фортран,

• Предварительное ознакомление с методикой разработки и отладки программ в системе DVM [1,2].

Методические рекомендации по выполнению:

Весь материал, необходимый для выполнения практикума, содержится в лекционном курсе и методических пособиях [1,2]. Полезная дополнительная информация может быть найдена в материалах [3,4,5].

Планируемый результат:

• Параллельные программы (2 программы для каждого участника),

• Результаты выполнения экспериментов по оценке производительности (таблицы и графики времен выполнения, эффективности),

• Выводы по полученным результатам (объяснение убывания или возрастания производительности параллельной программы при варьировании виртуальной решетки процессоров).

Практическое занятие 1. Распараллеливание итерационных алгоритмов

Цель:

• Получить навыки распараллеливания существующих ("старых") программ на языках Фортран и Си без изменения последовательной программы.

• Оценить производительность параллельной программы при разном количестве процессоров. Для определенного количества процессоров получить максимальную производительность вариацией виртуальной решетки процессоров.

Выполнение задания

Каждому участнику школы предоставляется из следующих последовательных программ:

Последовательные программы на языке Fortran

Последовательные программы на языке C

где

• adi - метод попеременных направлений,

• jac - релаксация Якоби,

• redb - метод красно-черного упорядочивания переменных,

• sor - последовательная верхняя релаксация.

Распараллеливание осуществляется с помощью анализа последовательной программы, аналогично анализу распараллеливающего компилятора. Поэтому не предполагается знания указанных алгоритмов. Т.к. фрагменты параллельных программ этих алгоритмов даны в описании языков Fortran-DVM и C‑DVM, то предполагается быстрое написание параллельной программы. Главное внимание в первой части практикума уделяется освоению функциональной отладки и отладки производительности.

Функциональная отладка (отладка правильности параллельной программы) базируется на использовании двух методов отладки – динамическом контроле корректности и сравнении результатов последовательного и параллельного выполнения. Эти результаты должны совпадать с точностью 10^-5.

Отладка производительности.

Для оценки производительности параллельной программы необходимо оперировать характеристиками производительности выполнения DVM-программы, которые выдаются в файл статистики анализатором производительности.

При решении реальных задач, время выполнения инициализации и выдачи результатов пренебрежимо мало по сравнению с основным вычислительным циклом. Поэтому достаточно оперировать только характеристиками основного цикла. Для этого основной итерационный цикл необходимо описать интервалом оценки производительности (см.[1,2]).

Практическое занятие 3. Двухуровневый параллелизм в модели DVM – параллелизм по данным и параллелизм задач

Цель:

• Приобрести навыки двухуровневого распараллеливания и балансировки загрузки процессоров.

• Достичь максимальной производительности для определенного количества процессоров с помощью балансировки загрузки.

Макет многоблочной задачи

При математическом моделировании объектов сложной формы часто применяется многоблочный метод. Область (объект) моделирования разделяется на подобласти, называемые блоками. Каждый блок представлен структурной (логически - прямоугольной) сеткой. Вычисления в каждом блоке могут выполняться независимо, за исключением корреляции значений на границах смежных блоков.

В многоблочном методе явно существуют два уровня параллелизма: между блоками и между точками сетки внутри каждого блока.

Для макетирования многоблочного метода возьмем алгоритм релаксации Якоби из первой части практикума. Для ясности изложения будем рассматривать двумерную сетку, но задача практикума будет базироваться на трехмерных блоках.

Пусть задана область моделирования A(1:N, 1:N) и следующее разбиение области на блоки

A(1:N, 1:N1) и A(1:N, N1+1:N)

Изобразим блоки отдельными массивами

A1(1:N, 1:N1+1)

A2(1:N, 1:N2+1), где N2 = N-N1

Блоки можно представить следующей схемой

N

N1

A1

1

1

A2

N2

Заштрихованные строки дублируют строки смежных блоков. Корреляция значений заключается в пересылке строк, выделенных штриховой линией.

Макет многоблочного метода на примере этого разбиения можно описать на языке Фортран следующим образом

REAL A1(N, N1+1), B1(N, N1+1), A2(N, N2+1), B2(N, N2+1), eps

C Инициализация (A1, A2, B1, B2)

. . .

DO it = 1, itmax

eps = 0.

C Корреляция значений на границах

A1(1:N, N1+1) = A2(1:N, 2)

A2(1:N, 1) = A1(1:N, N1)

C Релаксация Якоби по каждому блоку

CALL relax(A1,B1,N,N1+1,eps)

CALL relax(A2,B2,N,N2+1,eps)

IF (eps.LT.maxeps) GOTO 3

ENDDO

3 CONTINUE

Параллелизм задач модели DVM

В данном разделе описываются механизмы параллелизма задач, необходимы для распараллеливания примера макета многоблочного метода.

Описание количества задач (количества блоков)

CDVM$ TASK grid(2)

Описание линейки виртуальных процессоров

CDVM$ PROCESSORS proc( NUMBER_OF_PROCESSORS( ) )

Встроенная функция NUMBER_OF_PROCESSORS( ) выдает количество процессоров, на которых запущена DVM–программа.

NP = NUMBER_OF_PROCESSORS( )

Необходимо разделить общее количество процессоров NP между блоками таким образом, чтобы сбалансировать загрузку процессоров. В данном случае процессоры разделяются пропорционально количеству вычисляемых элементов в блоках A1,A2 (например, NP1+NP2 = NP )

Отображение задач (блоков) на группы (секции) линейки процессоров.

CDVM$ MAP grid(1) ONTO proc(1:NP1)

CDVM$ MAP grid(2) ONTO proc(NP1+1:NP)

Распределение массивов по задачам

CDVM$ DISTRIBUTE ( *, BLOCK ) ONTO grid(1) :: A1,B1

CDVM$ DISTRIBUTE ( *, BLOCK ) ONTO grid(2) :: A2,B2

Спецификация фрагментов последовательной программы для каждой задачи

CDVM$ TASK_REGION grid, REDUCTION (MAX(eps))

CDVM$ ON grid(1)

CALL relax(A1,B1,N,N1+1,eps)

CDVM$ ON grid(2)

CALL relax(A2,B2,N,N2+1,eps)

CDVM$ END TASK_REGION

Балансировка загрузки процессоров

В многоблочной задаче существуют два уровня параллелизма: между блоками (параллелизм задач) и внутри каждого блока (параллелизм по данным).

Возможны следующие варианты распределения блоков по процессорам.

1) Параллелизм по данным. Каждый блок распределяется на все процессоры. Используется только параллелизм внутри каждого блока. Недостаток: при большом количестве процессоров и небольших размерах блоков не все процессоры будут загружены.

2) Параллелизм задач. Каждый блок распределяется на отдельный процессор. При этом на одном процессоре может быть распределено несколько блоков. Недостатки: а) если количество блоков меньше количества процессоров, то не все процессоры будут загружены; б) при большой разнице в размерах между минимальным и максимальным блоком трудно достичь сбалансированной загрузки процессоров.

3) Параллелизм задач и параллелизм по данным. Пусть дано L блоков. Процессоры разделяются на L групп G₁,…,G_L. Блок A_i распределяется на группу процессоров G_i. Пусть S_k -количество элементов на k-ом процессоре.

S_min = min(S_k), S_max = max(S_k).

Группы процессоров необходимо определять таким образом, чтобы минимизировать

d = S_max - S_min.

Литература

1. Параллельное программирование на языке FORTRAN-DVM. Методическое пособие по практикуму для студентов 2-4 курсов. МГУ им. М.В.Ломоносова. Факультет ВMиК. Москва, 2002 г.

2. Параллельное программирование на языке C-DVM. Методическое пособие по практикуму для студентов 2-4 курсов. МГУ им. М.В.Ломоносова. Факультет ВMиК. Москва, 2002 г.

3. Дж. Ортега. Введение в параллельные и векторные методы решения линейных систем. Москва, «Мир», 1991.

4. Описание языка FORTRAN-DVM. http://www.keldysh.ru/dvm

5. Описание языка C-DVM. http://www.keldysh.ru/dvm

Характеристики

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.

Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.

Список файлов лабораторной работы