Большая вычислительная задача Математическая модель (система УРЧП) в подпространстве R 3 t Дискретизация УРЧП - система линейных и нелинейных уравнений (приложение 3D t ) Большая вычислительная задача - приложение 3D t, требующее производительности сотен процессоров

Распараллеливание большой задачи Метод декомпозиции области 3D (параллелизм по данным) операторы (функции) точки (данные) точки (данные) процессоры (процессы)

Параллельное выполнение большой задачи Одна ОПМД-программа выполняется на всех процессорах с локальным подмножеством данных Правило собственных вычислений: OWN(A(i)) - процессор, на который распределен A(i) A(i) = expr i Оператор всегда выполняется на процессоре OWN(A(i)) Проба: свой - чужой оператор по правилу собственных вычислений

Модель передачи сообщений MPI Преобразование последовательной программы в ОПМД-программу (параметр - номер процессора) Описание локальных подмножеств данных для каждого процессора Программирование циклов в локальных индексах для каждого процессора Нелокальные данные - сложный код управления обменом данных ( до 50% последовательной программы) Недостаток - большая трудоемкость и сложность

Основная цель разработки DVM Унифицированный интерфейс больших задач для систем с общей и распределенной памятью Снижение трудоемкости Эффективная переносимость Производительность Предсказуемая производительность

Отображение последовательной программы Массив виртуальных процессоров Массивы Циклы Массив задач Физические процессоры PARALLEL ALIGN DISTRIBUTE MAP

Абстрактная схема распределения данных и витков параллельных циклов Объекты: P-индексное пространство массива виртуальных процессоров, определяется пользователем и задается при запуске программы A i -индексное пространство i-ого массива данных L j -индексное пространство j-ого параллельного цикла

Директивы распределения устанавливают соответствие между точками (элементами) индексных пространств: ALIGN:A i1 =>A i2 Каждой точке (элементу) A i2 ставится в соответствие подмножество точек (элементов) массива A i1 PARALLEL: L j =>A i Каждой точке (элементу) A i ставится в соответствие подмножество точек (витков цикла) L j DISTRIBUTE: A i =>P Каждой точке (виртуальному процессору) P ставится в соответствие подмножество точек (элементов) A i

Распределение данных Распределение массивов между узлами DISTRIBUTE real A(12), B(6), WB(6) integer BS(4) CDVM$DISTRIBUTE A(BLOCK) CDVM$ DISTRIBUTE B(BLOCK) CDVM$ DISTRIBUTE A(MULT_BLOCK(3)) node1 node2 node3 node4 A 1,2,3 4,5,6 7,8,9 10,11,12 B 1,2 3,4 5 6 CDVM$DISTRIBUTE A(GEN_BLOCK(BS)) CDVM$DISTRIBUTE B(WGT_BLOCK(WB,6)) data BS /2, 4, 4, 2/ data WB /1., 0.5, 0.5, 0,5, 0.5, 1./ node1 node2 node3 node4 A 1,2 3,4,5,6 7,8,9,10 11,12 B 1 2,3 4,5 6

Распределение данных Примеры: REAL A( N, N+1 ),X( N ) CDVM$ DISTRIBUTE A ( BLOCK, *) CDVM$ ALIGN X(I) WITH A(I,N+1) REAL A( N, N ), B( N, N) CDVM$ DISTRIBUTE ( BLOCK, BLOCK) :: A CDVM$ ALIGN B(I,J) WITH A(I,J) CDVM$ ALIGN B(I,J) WITH A(J,I)

Распределение данных Выравнивание по шаблону TEMPLATE REAL A(100), B(100), C(100) CDVM$TEMPLATE TABC (102) CDVM$ALIGN B( I ) WITH TABC( I ) CDVM$ALIGN A( I ) WITH TABC( I + 1 ) CDVM$ALIGN C( I ) WITH TABC( I + 2 ) CDVM$DISTRIBUTE TABC ( BLOCK )... CDVM$PARALLEL (I) ON A(I) DO I = 2, 98 A(I) = C(I-1) + B(I+1) ENDDO Для того, чтобы не было обмена между узлами необходимо разместить элементы A(I), C(I-1) и B(I+1) на одном узле. Выравнивание массивов С и В на массив А невозможно, т.к. функции выравнивания I-1 и I+1 выводят за пределы индексов измерения А. Поэтому описывается шаблон TABC. На один элемент шаблона TABC выравниваются элементы массивов A, В и С, которые должны быть размещены на одном узле.

Перераспределение данных Директивы REDISTRIBUTE и REALIGN осуществляют динамическое перераспределение массивов в программе. … CDVM$ALIGN B1( I, J ) WITH A1( I, J ) CDVM$ALIGN B2( I, J ) WITH A2( I, J ) CDVM$ DYNAMIC :: A1,A2 … CDVM$REDISTRIBUTE ( *, BLOCK ) :: A1,A2 Массивы, перераспределяемые директивами REDISTRIBUTE и REALIGN, необходимо специфицировать в директиве DYNAMIC. Если после выполнения директив REDISTRIBUTE и REALIGN перераспределяемые массивы получают новые значения, то перед этими директивами следует указать дополнительную (оптимизирующую) директиву NEW_VALUE. Эта директива отменяет пересылку значений распределенного массива.

Спецификация удаленных данных Удаленными данными будем называть данные, размещенные на одном узле и используемые на другом. A(inda) = …B(indb)… где A, B - распределенные массивы, inda, indb - индексные выражения. Ссылка B(indb) не является удаленной ссылкой, если соответствующие ей элементы массива B размещены на узле own(A(inda)). Единственной гарантией этого является выравнивание A(inda) и B(indb) в одну точку шаблона выравнивания. Если выравнивание невозможно или невыполнено, то ссылку B(indb) необходимо специфицировать как удаленную ссылку. По степени эффективности обработки удаленные ссылки разделены на два типа: SHADOW и REMOTE. Если массивы A и B выровнены и inda = indb d ( d – положительная целочисленная константа), то удаленная ссылка B(indb) принадлежит типу SHADOW. Удаленная ссылка на многомерный массив принадлежит типу SHADOW, если распределяемые измерения удовлетворяют определению типа SHADOW. Удаленные ссылки, не принадлежащие типу SHADOW, составляют множество ссылок типа REMOTE.

Удаленные ссылки типа SHADOW Синхронная спецификация независимых ссылок типа SHADOW REAL A(100), B(100) CDVM$ALIGN B( I ) WITH A( I ) CDVM$DISTRIBUTE ( BLOCK) :: A CDVM$SHADOW B( 1:2 )... CDVM$PARALLEL (I) ON A ( I ), SHADOW_RENEW ( B ) DO I = 2, 98 A(I) = (B(I-1) + B(I+1) + B(I+2) ) / 3 ENDDO... Директива SHADOW специфицирует размер теневых граней распределенного массива. Выполнение спецификации SHADOW_RENEW заключается в обновлении теневых граней значениями удаленных переменных перед выполнением цикла.

Удаленные ссылки типа SHADOW Асинхронная спецификация независимых ссылок типа SHADOW REAL A(100,100), B(100,100), C(100,100), D(100,100) CDVM$ALIGN ( I, J ) WITH C( I, J ) :: A, B, D CDVM$DISTRIBUTE ( BLOCK, BLOCK ) :: C... CDVM$SHADOW_GROUP AB ( A, B )... CDVM$SHADOW_START AB... CDVM$PARALLEL (J,I) ON C ( I, J ), SHADOW_WAIT AB DO I = 2, 99 DO J = 2, 99 C(I,J) = (A(I-1,J) + A(I+1,J) + A(I,J-1) + A(I,J+1) ) / 4 D(I,J) = (B(I-1,J) + B(I+1,J) + B(I,J-1) + B(I,J+1) ) / 4 ENDDO Описание группы Запуск обменов Ожидание значений

Distribution of array A [8][8]

Удаленные ссылки типа REMOTE Синхронная спецификация удаленных ссылок типа REMOTE. DIMENSION A(100,100), B(100,100) CDVM$DISTRIBUTE (*,BLOCK) :: A CDVM$ALIGN B( I, J ) WITH A( I, J ) … CDVM$ PARALLEL (J,I) ON A(I,J), REMOTE_ACCESS(B(:,N)) Срассылка значений B(:,N) по узлам own(A(:,J)) DO J = 1, 100 DO I = 1, 100 A(I,J) = B(I,J) + B(I,N) ENDDO REMOTE_ACCESS в параллельном цикле специфицирует удаленные данные (столбец матрицы) для всех узлов, на которые распределен массив А.

Удаленные ссылки типа REMOTE Асинхронная спецификация удаленных ссылок типа REMOTE. REAL A1(M,N1+1), A2(M1+1,N2+1) CDVM$DISTRIBUTE ( BLOCK,BLOCK) :: A1, A2 CDVM$REMOTE_GROUP RS DO ITER = 1, MIT CDVM$PREFETCH RS... *DVM$ PARALLEL (I) ON A1 ( I, N1+1 ), *DVM$* REMOTE_ACCESS ( RS: A2(I,2)) DO 10 I = 1, M1 10A1(I,N1+1) = A2(I,2) *DVM$PARALLEL (I) ON A2 ( I, 1 ), *DVM$* REMOTE_ACCESS ( RS: A1(I,N1)) DO 20 I = 1, M1 20A2(I,1) = A1(I,N1)... CDVM$RESET RS... ENDDO Упреждающая пересылка удаленных данных Накопление ссылок в переменной RS

Редукционные переменные CDVM$ PARALLEL (J, I) ON A(I, J), REDUCTION ( MAX( EPS )) C variable EPS is used for calculation of maximum value DO 21 J = 2, L-1 DO 21 I = 2, L-1 EPS = MAX ( EPS, ABS( B( I, J) - A( I, J))) A(I, J) = B(I, J) 21 CONTINUE CDVM$ PARALLEL (J, I) ON A(I, J), REDUCTION ( SUM( S )) DO 22 J = 2, L-1 DO 22 I = 2, L-1 S = S + A( I, J) 22 CONTINUE

Макроконвейерный параллелизм CDVM$ PARALLEL ( J, I) ON A( I, J), NEW (S), CDVM$* REDUCTION ( MAX( EPS )), ACROSS (A(1:1,1:1)) DO J = 2, N-1 DO I = 2, N-1 S = A( I, J ) A( I, J ) = (W / 4) * (A( I-1, J ) + A( I+1, J ) + A( I, J-1 ) + *A( I, J+1 )) + ( 1-W ) * A( I, J) EPS = MAX ( EPS, ABS( S - A( I, J ))) ENDDO

Параллелизм по гиперплоскостям ( dvm run 4 4 sor ) j i t1 t2 t3

Конвейерный параллелизм ( dvm run 3 1 sor ) p0 p1 p2 j i t1 t2 t2t2 t3 t3t3 t3t3 t4t4 t4t4 t4t4 t5t5 t5t5 t5t5 t6t6 t6t6 t6t6 t7t7 t7t7 t7t7 t8t8 t8t8 t9t9

Асинхронное копирование секций массивов INTEGER A(N,N),B(N,N),C(N,N),A1(N,N),B1(N,N) CDVM$ DISTRIBUTE ( MULT_BLOCK(NEL), MULT_BLOCK(NEL)) :: A CDVM$ ALIGN (I,J) WITH A(I,J) :: B, C, A1, B1 CDVM$ ASYNCID iflag

Асинхронное копирование секций массивов DO 9 I = 1, NBL DO 9 J = 1, NBL CDVM$ ASYNCHRONOUS iflag A((J-1)*NEL+1:(J-1)*NEL+NEL,(I-1)*NEL+1:(I-1)*NEL+NEL)= * A1((J-1)*NEL+1:(J-1)*NEL+NEL, * MOD(I,NBL)*NEL+1:MOD(I,NBL)*NEL+NEL) B((I-1)*NEL+1:(I-1)*NEL+NEL,(J-1)*NEL+1:(J-1)*NEL+NEL)= * B1( MOD(I,NBL)*NEL+1:MOD(I,NBL)*NEL+NEL, * (J-1)*NEL+1:(J-1)*NEL+NEL) CDVM$ END ASYNCHRONOUS CDVM$ ASYNCWAIT iflag 9 CONTINUE

Параллелизм задач. Параллелизм между группами процессоров Макет многоблочной задачи (multiblock) Описание количества блоков (сеток) CDVM$ TASK grid ( n ) Запрос количества процессоров, на которых выполняется задача NP = NUMBER_OF_PROCESSORS ( ) Разделение процессоров на группы G = { G 1, …, G n }

Макет многоблочной задачи (multiblock) CDVM$ DISTRIBUTE :: A1, A2, A3, A4 CDVM$ ALIGN :: B1, B2, B3, B4 CDVM$ PROCESSORS MP(NUMBER_OF_PROCESSORS()) NP = NUMBER_OF_PROCESSORS ( )

Макет многоблочной задачи (multiblock) Отображение блоков CDVM$ MAP grid ( 1 ) ONTO MP( 1 : N2) CDVM$ MAP grid ( 2 ) ONTO MP( N2+1 : N3) CDVM$ MAP grid ( 3 ) ONTO MP( N3+1 : N4) CDVM$ MAP grid ( 4 ) ONTO MP( N4+1 : NP)

Макет многоблочной задачи (multiblock) Распределение данных CDVM$ REDISTRIBUTE A1( *, BLOCK ) ONTO grid( 1 ) CDVM$ REALIGN B1 ( i, j ) WITH A1 ( i, j )...

Макет многоблочной задачи (multiblock) Распределение вычислений CDVM$ TASK_REGION grid CDVM$ ON grid ( 1 ) CALL relax ( A1, B1, epsb, m1, m2 ) CDVM$ END ON... CDVM$ END TASK_REGION