Двухуровневый параллелизм в модели DVM – параллелизм по данным и параллелизм задач (1158286)

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

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

Практическое занятие 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), epsb(2)

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

. . .

DO it = 1, itmax

epsb = 0.

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

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

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

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

CALL relax_jacoby(A1,B1,N,N1+1,epsb(1))

CALL relax_jacoby(A2,B2,N,N2+1,epsb(2))

eps = 0.

DO i = 1, 2

eps = max(eps,epsb(i))

ENDDO

IF (eps.LT.maxeps) GOTO 3

ENDDO

3 CONTINUE

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

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

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

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

CDVM$ ON grid(1)

CALL relax_jacoby(A1,B1,N,N1+1,epsb(1))

CDVM$ ON grid(2)

CALL relax_jacoby(A2,B2,N,N2+1,epsb(2))

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.

Задание.

Область моделирования A(N,N) разделяется на 16 блоков разной площади:

n1 n2 n3 n4

где n1:n2:n3:n4 = 1:3:6:10,

N=5000, MAXSTEPS=100, MAXEPS=0.5e-5

Итерационные методы можно упорядочить по возрастанию скорости сходимости: Jacoby, red-black, SOR. Для повышения производительности последовательной программы необходимо решать методом Jacoby 8 блоков с меньшей площадью, а методами red-black и SOR – 8 блоков с большей площадью.

Каждый вариант решает 8 блоков (наименьшей площади) методом Jacoby и 8 блоков (наибольшей площади) методами red-black или SOR.

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

Последовательная и параллельная программа.

Достижение максимальной производительности в варианте: параллелизм задач и параллелизм по данным

Литература

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, так как принтер может начудить со шрифтами.

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