Схема размещения в локальной памяти и блочно-столбцовое разбиение ленточных матриц.

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

Размер блока выбирается исходя из числа столбцов  N глобальной матрицы  A и числа процессоров  P, используемых для решения задачи. При этом используется одномерная решетка процессов размером 1 * P. Каждый процесс должен получить один из блоков матрицы. Таким образом, размер блока  NB определяется из формулы: NB ≥ [ N / P ]. Если N делится на P нацело, все блоки, распределяемые на все процессы, имеют одинаковый размер. В противном случае последний блок, распределяемый на последний процесс, имеет размер < NB. При этом K - й столбец матрицы A попадает в память процесса с номером [ K / NB ]. Как уже говорилось, процессы нумеруются от 0 до ( P - 1). Координаты первого процесса в такой решетке есть (0, 0), а последнего - (0, P - 1). На рисунке условно показано разбиение некоторой глобальной матрицы A размера M * N на 3 блока по столбцам для распределения ее по трем процессам (координаты процессов в решетке указаны под соответствующими блоками).

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

Рассмотрим схему размещения элементов глобальной ленточной матрицы A в локальной памяти параллельных процессов на конкретных примерах.

Пусть матрица A имеет размеры 7 * 7 и ширину ленты, равную 2 :

Пусть матрица распределяется по решетке процессов 1 * 3 с размером блоков NB_A = 3.

Рассмотрим несколько случаев распределения по решетке процессов несимметричных и симметричных положительно определенных ленточных матриц.

1. Случай несимметричной ленточной матрицы, при факторизации которой используются алгоритмы без выбора ведущего элемента.

Пусть число поддиагоналей  BWL матрицы A равно 2, а число наддиагоналей BWL равно 2.

Ниже на рисунке представлено распределение такой матрицы по процессам. Символом "_*" отмечены элементы в двумерном локальном массиве, которые в дальнейших вычислениях не используются.

Из этого рисунка видно, что ведущая размерность этих локальных массивов (т.е. число строк в блоках глобальной матрицы  A, которые помещаются в каждый процессор) должна быть равна BWL + 1 + BWU (т.к. элементы изображенных массивов заносятся в локальную память по столбцам). О ведущей размерности локальных массивов см. в разделе документации "Дескрипторы глобальных массивов".

2. Случай несимметричной ленточной матрицы, при факторизации которой используются алгоритмы с выбором ведущего элемента по столбцам.

В этом случае, в отличие от случая 1, необходимо дополнительное пространство для хранения информации о производимых в процессе факторизации перестановках. А именно, в каждом локальном массиве количество элементов в начале каждого столбца должно быть увеличено на величину, равную сумме числа поддиагоналей и числа наддиагоналей, т.е. BWL + BWU.

В рассматриваемом нами примере имеем BWL = 2 и BWU = 2. Ниже на рисунке представлено распределение глобальной ленточной матрицы по процессам с выделением необходимого дополнительного пространства. Дополнительно резервируемые элементы в каждом локальном массиве обозначены буквами "F".

Из этого рисунка видно, что ведущая размерность такого локального массива должна быть равна 2 * (BWL + BWU) + 1.

3. Случай симметричной положительно определенной ленточной матрицы, у которой в памяти сохраняется только нижний треугольник (параметр UPLO в подпрограммах обработки таких матриц полагается равным "L").

Пусть ширина ленты такой матрицы BW = 2. Ниже на рисунке представлено распределение такой матрицы ( 7 * 7 ) по той же решетке процессов ( 1 * 3 ).

4. Случай симметричной положительно определенной ленточной матрицы, у которой в памяти сохраняется только верхний треугольник (параметр UPLO в подпрограммах обработки таких матриц полагается равным "U").

Ниже на рисунке представлено распределение такой матрицы по той же решетке процессов ( 1 * 3 ).

Из двух последних рисунков видно, что ведущая размерность такого локального массива равна BW + 1.

Кроме этого, при решении систем линейных уравнений предполагается, что вектор (матрица) правых частей B (размером N * NRHS) распределяется по той же решетке процессов, что и описанные выше матрицы  A, но только не блочно - столбцовым, а блочно - строчным образом. Это означает, что в блоки объединяются соседние строки матрицы B (или просто соседние элементы, если B - вектор). Ниже на рисунке условно представлено блочно - строчное разбиение матрицы (вектора) B для распределения ее по той же решетке процессов ( 1 * 3 ), что и соответствующей ленточной (или трехдиагональной) матрицы  A.

               1                     NRHS              Процессы
               _ _ _ _ _ _ _ _ _ _ _
            1 |                               |
               |                               |                  (0,0)
               |                               |
               _ _ _ _ _ _ _ _ _ _ _
               |                               |
               |                               |                  (0,1)
               |                               |
               _ _ _ _ _ _ _ _ _ _ _
               |                               |
               |                               |                  (0,2)
           N |                               |
               _ _ _ _ _ _ _ _ _ _ _

Распределение элементов вектора B по этим процессам будет следующим.

Конкретные примеры распределеня матрицы A и вектора B по процессам можно найти в разделе "Пример использования" описаний подпрограмм.