Документ взят из кэша поисковой машины. Адрес оригинального документа : http://num-anal.srcc.msu.ru/par_prog/org/examp9.htm
Дата изменения: Mon Oct 28 17:15:50 2013
Дата индексирования: Thu Feb 27 20:51:09 2014
Кодировка: Windows-1251
Параллельные программы. Пример блочно-циклического распределения плотной матрицы по решетке процессов.

Пример блочно-циклического распределения плотной матрицы по решетке процессов.

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

В соответствии с принятой схемой, сначала плотная матрица  A размера M * N разделяется на блоки размера MB * NB начиная с левого верхнего угла этой матрицы. Эти блоки затем равномерно распределяются по каждому измерению решетки процессов. Точные математические соотношения, соответствующие такой схеме распределения, приводятся в разделе документации "Схема размещения в локальной памяти и блочно - циклическое отображение плотных матриц".

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

Ниже на рисунке показано разделение матрицы  A размером  9 * 9 на блоки размером  2 * 2.

a11  a12
a21  a22
a13  a14
a23  a24
a15  a16
a25  a26
a17  a18
a27  a28
a19
a29
a31  a32
a41  a42
a33  a34
a43  a44
a35  a36
a45  a46
a37  a38
a47  a48
a39
a49
a51  a52
a61  a62
a53  a54
a63  a64
a55  a56
a65  a66
a57  a58
a67  a68
a59
a69
a71  a72
a81  a82
a73  a74
a83  a84
a75  a76
a85  a86
a77  a78
a87  a88
a79
a89
a91  a92 a93  a94 a95  a96 a97  a98 a99

Далее показано отображение полученных блоков на решетку процессов размером  2 * 3 (двумерное блочно - циклическое распределение данных).

Чтобы понять, как распределятся изображенные выше блоки по процессам решетки, сначала напишем на каждой из клеток (блоков) рисунка координаты процессов, куда они должны быть распределены в соответствии с установленным блочно - циклическим распределением, описанным в разделе документации "Схема размещения в локальной памяти и блочно - циклическое отображение плотных матриц".

(0,0) (0,1) (0,2) (0,0) (0,1)
(1,0) (1,1) (1,2) (1,0) (1,1)
(0,0) (0,1) (0,2) (0,0) (0,1)
(1,0) (1,1) (1,2) (1,0) (1,1)
(0,0) (0,1) (0,2) (0,0) (0,1)

Пусть первый блок распределяется в процесс (0, 0). Тогда все блоки, расположенные с ним в той же строке будут распределяться в ту же строку решетки процессов, т.е. первая координата в этих клетках будет равна 0.

Вторая же координата (столбца решетки) будет циклически изменяться: 0, 1, 2, 0, 1, т.к. столбцов в решетке только 3 (с координатами 0, 1, 2).

Все блоки, расположенные с первым в том же самом столбце, будут распределяться в тот же самый столбец решетки процессов. Т.е. вторая координата в этих клетках будет равна 0. Первая же координата (строки решетки) будет циклически изменяться: 0, 1, 0, 1, 0, т.к. число строк в решетке только 2 (с координатами 0,1).

Другими словами, каждая координата независимо от другой (в строках - слева направо, а в столбцах - сверху вниз), циклически изменяется.

Если теперь мы соединим вместе (пристыкуем) все клетки (блоки), имеющие одинаковые координаты процесса, то получим массив элементов, который и должен расположиться в локальной памяти процесса с такими координатами.

Сборка клеток (блоков) с одинаковыми координатами делается так:

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

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

Ниже представлено расположение элементов исходной матрицы во всех процессах решетки после завершения процесса блочно - циклического распределения. Вверху указаны номера столбцов решетки процессов, слева - номера строк решетки процессов.

0 1 2
0 a11  a12
a21  a22
a17  a18
a27  a28
a13  a14
a23  a24
a19
a29
a15  a16
a25  a26
a51  a52
a61  a62
a57  a58
a67  a68
a53  a54
a63  a64
a59
a69
a55  a56
a65  a66
a91  a92 a97  a98 a93  a94 a99 a95  a96
1 a31  a32
a41  a42
a37  a38
a47  a48
a33  a34
a43  a44
a39
a49
a35  a36
a45  a46
a71  a72
a81  a82
a77  a78
a87  a88
a73  a74
a83  a84
a79
a89
a75  a76
a85  a86

Ниже в таблице указаны характеристики локальных массивов для каждого из процессов решетки.

     Координаты
     процесса             LLD_A       LOCr ( M_A )       LOCc ( N_A )
    _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
         (0,0)                      5                     5                             4
         (0,1)                      5                     5                             3
         (0,2)                      5                     5                             2
 
         (1,0)                      4                     4                             4
         (1,1)                      4                     4                             3
         (1,2)                      4                     4                             2

Число строк LOCr и число столбцов LOCc матрицы  A, которыми владеет (обладает) конкретный процесс, могут отличаться у разных процессов в решетке (процессов). Подобно этому, для каждого процесса в решетке процессов существует ведущая локальная размерность LLD. Ее величина может быть различной для разных процессов в решетке процессов. Например, как мы можем видеть на рисунке выше, локальный массив, хранящийся (расположенный) в строке решетки процессов с номером 0, должен иметь ведущую локальную размерность LLD не меньше 5, а хранящийся в строке с номером 1 - не меньше 4. Подробнее о ведущей локальной размерности LLD см. в разделе документации "Дескрипторы глобальных массивов".