Для равномерной загрузки параллельных процессов и эффективного использования подпрограмм пакета BLAS при выполнении операций над плотными глобальными матрицами были разработаны специальные способы разбиения таких матриц на прямоугольные блоки ( MB * NB ) и распределения этих блоков по двумерной решетке параллельных процессов (о решетках см. раздел документации "Решетки процессов, контекст и подпрограммы пакета BLACS"). Простой пример конкретного разбиения плотной матрицы на блоки и распределения их по двумерной решетке процессов, называемого блочно - циклическим отображением, приводится в разделе документации "Пример блочно - циклического распределения плотной матрицы по решетке процессов".
Здесь же мы рассмотрим, каким образом блоки, отображенные на один и тот же процесс, располагаются и хранятся в локальной иамяти этого процесса. Другими словами, мы выпишем точные формулы, которые связывают элемент глобальной матрицы, определяемый глобальными индексами I и J (т.е. A ( I, J )), с координатами процесса, владеющего этим элементом, в решетке процессов ( Pr, Pc) и с расположением этого элемента матрицы в локальной памяти этого процесса.
Рассмотрим сначала, для простоты, эти связи на примере одномерного случая, т.е. размещение одномерного глобального массива длины N, разбитого на блоки длины NB, по одномерной решетке из P процессов, перенумерованных, начиная с 0 до ( P - 1). Элементы самого глобального массива нумеруются от 1 до N. Прежде всего, массив делится на смежные блоки размера NB. Когда N не делится на NB нацело, последний блок массива элементов будет содержать только mod ( N, NB ) элементов вместо NB. Блоки, на которые разбивается исходный массив, нумеруются (как и процессы), начиная с 0. Они распределяются по процессам подобно тому, как сдается колода карт участникам игры - по кругу (т.е. циклически).
Другими словами, мы предполагаем, что процесс с номером 0 получает первый блок (с номером 0), k - ый блок связывается с процессом, имеющим координату (номер) mod ( k, P ) . Блоки, связанные с одним и тем же процессом, хранятся в памяти рядом (в смежных, прилегающих частях). Отображение элемента массива с глобальным индексом I определяется следующим соотношением:
I = k * NB + x = ( m * P + p ) * NB + x ,
где I - глобальный индекс глобального массива,
m - локальная координата блока, в котором этот элемент
расположен,
р - координата процесса, владеющего этим блоком,
х - локальная координата элемента внутри того блока,
где находится элемент глобального массива с индексом I.
Легко установить соотношения между этими переменными:
p = [ ( I - 1) / NB ] mod P ,
m = [ ( I - 1) / ( P * NB ) ] ,
x = mod ( I - 1, NB ) + 1 .
Эти уравнения позволяют определить локальную информацию (т.е. локальный индекс m * NB + x), так же как и координату процесса р, соответствующую глобальному элементу, идентифицируемому его глобальным индексом I, и наоборот.
В таблице ниже показано отображение в локальную память при разбиении массива на блоки, когда P = 2, N = 16 и NB = 8.
| I | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
| p | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| m | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| x | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| m*NB + x | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
Вовсе не обязательно всегда делать распределение блоков, начиная с процесса с номером 0. Иногда, бывает полезно начать распределение данных с процесса имеющего отличную от нуля координату SRC. В этом случае соотношения становятся такими:
p = ( SRC + [ ( I - 1) / NB ] ) mod P ,
m = [ ( I - 1) / ( P * NB ) ] ,
x = mod ( I - 1, NB ) + 1 .
Ниже в таблице показано размещение блоков при P = 2, SRC = 1, NB = 3 и N = 16.
| I | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
| p | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 0 |
| m | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 2 | 2 | 2 | 2 |
| x | 1 | 2 | 3 | 1 | 2 | 3 | 1 | 2 | 3 | 1 | 2 | 3 | 1 | 2 | 3 | 1 |
| m*NB + x | 1 | 2 | 3 | 1 | 2 | 3 | 4 | 5 | 6 | 4 | 5 | 6 | 7 | 8 | 9 | 7 |
В двумерном случае предположим, что матрица разделена на MB * NB блоки и что первый блок передан процессу с координатами ( RSRC, CSRC ). Формула, приведенная выше для одномерного случая, должна использоваться повторно независимо для каждого измерения решетки процессов Pr * Pc. Например, элемент матрицы ( I, J ) находится в процессе с координатами ( Pr, Pc) внутри локального блока ( m, n ) в позиции ( x, y ), задаваемой формулами
( m, n ) = ( [ ( I - 1) / ( Pr * MB ) ], [ ( J - 1) / ( Pc * NB ) ] ) , ( Pr, Pc) = ( ( RSRC + [ ( I - 1) / MB ] ) mod Pr, ( CSRC + [ ( J - 1) / NB ] ) mod Pc ) ( x, y ) = ( mod ( I - 1, MB ) + 1, mod ( J - 1, NB ) + 1 )
Эти формулы показывают, как матрица А размера M_A * N_A отображается и хранится на решетке процессов. Она сначала разбивается на MB_A * NB_A блоки, начиная с ее верхнего левого угла. Эти блоки затем равномерно распределяются по решетке процессов циклическим образом.
Каждый процесс владеет набором блоков, которые хранятся рядом (смежно) по столбцам в двумерном массиве, расположенном в памяти "по столбцам" ("column major").
Это соглашение о локальном размещении позволяет эффективно использовать иерархию локальной памяти посредством вызова пакета BLAS для подмассивов, которые могут быть больше, чем один блок размера MB_A * NB_A.
На рисунке ниже представлено отображение матрицы 5 * 5, разделенной на блоки размером 2 * 2, на решетку процессов размером 2 * 2 (т.е. M_A = N_A = 5, Pr = Pc = 2 и MB_A = NB_A = 2). Локальные элементы каждого столбца матрицы хранятся рядом в памяти каждого процесса.
|
a11 a12 a21 a22 |
a13 a14 a23 a24 |
a15 a25 | |
|
a31 a32 a41 a42 |
a33 a34 a43 a44 |
a35 a45 | |
| a51 a52 | a53 a54 | a55 |
| 0 | 1 | ||
| 0 |
a11 a12 a21 a22 |
a15 a25 |
a13 a14 a23 a24 |
| a51 a52 | a55 | a53 a54 | |
| 1 |
a31 a32 a41 a42 |
a35 a45 |
a33 a34 a43 a44 |
Цифры 0 и 1 в левой и верхней части последней таблицы означают номера строк и столбцов решетки процессов соответственно.
Определение числа строк или столбцов плотной глобальной матрицы, которое получает конкретный процесс, является важной задачей для пользователя. ScaLAPACK предоставляет служебную подпрограмму ( tool routine ) NUMROC для выполнения этой функции. Обозначения LOCr ( ) и LOCc ( ) используются для обозначения этих локальных величин в головных комментариях текстов подпрограмм и упоминаются в разделах документации "Дескрипторы глобальных массивов" и "Пример блочно - циклического распределения плотной матрицы по решетке процессов". Значения LOCr ( ) и LOCc ( ), получаемые подпрограммой NUMROC, являются результатом точных вычислений.
Однако если требуется понять общую идею вычисления размера локального массива, то можно проделать следующее грубое вычисление верхней границы этой величины:
а) верхняя граница для LOCr ( ) оценивается по формуле
M_A + MB_A - 1
---------------------- + Pr - 1
MB_A
LOCr( ) = ------------------------------------------- * MB_A
Pr
или
LOCr( ) = [ [ M_A / MB_A] / Pr ] * MB_A
б) величина LOCc( ) оценивается по формуле
N_A + NB_A - 1
---------------------- + Pc - 1
NB_A
LOCc( ) = -------------------------------------------- * NB_A
Pc
или
LOCc( ) = [ [ N_A / NB_A ] / Pc ] * NB_A
Заметим, что эти вычисления могут привести к очень большой переоценке величины действительно требующегося пространства.