Параллельные методы решения задач линейной алгебры

вектор
Принципы распараллеливания
Анализ эффективности
Программная реализация

элементов матриц
Это параллелизм по данным
Распараллеливание = распределение частей матриц между

вычислительными узлами МВС
Способ разбиения на части и распределения данных определяет параллельный алгоритм решения задачи

строк или столбцов
Всего строк (столбцов) – М, процессоров - р
Предполагается,

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

b (n элементов), результат – вектор с (m элементов).
Общее количество

операций (для оценки Т1):
m операций умножения строк А на b, где каждая:
n операций умножения элементов и (n – 1) операция сложения произведений
Время выполнения последовательного алгоритма:
Т1 = m (2n – 1)

Порядок трудоемкости последовательного алгоритма:
О(mn)

разбивать векторы b и с?
Каждый процессор хранит строку матрицы А

+ отдельные элементы векторов – порядок числа сохраняемых значений:
О(max(m, n))

Каждый процессор хранит строку матрицы А + все элементы векторов – порядок числа сохраняемых значений:
О(max(m, n))
Дублирование не повышает порядок сложности по памяти

p < m, то выполняется объединение подзадач, соответствующих непрерывной последовательности

строк.
Распределение объединенных подзадач по процессорам произвольно

выполнения всех операций одинаково
Последовательный алгоритм:
Т1 = n (2n – 1)
Параллельный

алгоритм:
Тp = n (2n – 1)/p
Ускорение:
Sp = Т1 / Тp = p
Эффективность:
Еp = Sp/p = 1

передачи сообщения m байт
tпд = tн + m/R
tн -

время латентности, R - пропускная способность сети
Параллельный алгоритм (все узлы узнают результат):
Тp = tн (log2p) + top( n (2n – 1)/p) + ( n (n – 1)/p) m/R
Предположения:
Топология – полный граф
Последовательный обмен данными между узлами (на каждом шаге сообщения увеличиваются в 2 раза), число шагов = log2p

0;//число процессов
int ProcRank = 0;// ранг процесса
void

main(int argc, char* argv[])
{
double* pMatrix; // A
double* pVector; // b
double* pResult; // c
int Size; // n
double* pProcRows;
double* pProcResult;
int RowNum;
double t1, t2;
MPI_Init(&argc, &argv);
MPI_Comm_size(MPI_COMM_WORLD, &ProcNum);
MPI_Comm_rank(MPI_COMM_WORLD, &ProcRank);

printf ("Parallel matrix-vector multiplication program\n");
}
ProcessInitialization(pMatrix, pVector, pResult,

pProcRows, pProcResult, Size, RowNum); // функция для выделения памяти и инициализации
t1 = MPI_Wtime();
// распределение данных по процессам
DataDistribution(pMatrix, pProcRows, pVector, Size, RowNum);
ParallelResultCalculation(pProcRows, pVector, pProcResult, Size, RowNum);//Axb
ResultReplication(pProcResult, pResult, Size, RowNum);//результат – всем
t2 = MPI_Wtime();
TestDistribution(pMatrix, pVector, pProcRows, Size, RowNum, pResult, t1, t2);
ProcessTermination(pMatrix, pVector, pResult, pProcRows, pProcResult);
MPI_Finalize();
}

&pProcRows, double* &pProcResult,
int &Size, int &RowNum)
{
int

RestRows;// число строк, которые нужно распределить
int i;
if (ProcRank == 0)
{
printf("\nEnter size of matrix A (> p): ");
scanf("%d", &Size);
// можно добавить проверку и цикл do-while
}
// рассылка значения Size всем процессам
MPI_Bcast(&Size, 1, MPI_INT, 0, MPI_COMM_WORLD);

RestRows = Size;
for (i=0; i

= RestRows-RestRows/(ProcNum-i);}
// число строк на процесс
RowNum = RestRows/(ProcNum-ProcRank);
pVector = new double [Size];
pResult = new double [Size];
pProcRows = new double [RowNum*Size];//элементы строк А для процесса
pProcResult = new double [RowNum];
if (ProcRank == 0)
{
pMatrix = new double [Size*Size];
// случайное заполнение А и b
RandomDataInitialization(pMatrix, pVector, Size);
}}

j;
srand(unsigned(clock()));// инициализация датчика случайных чисел
for (i=0; i

i++)
{
pVector[i] = rand()/double(1000);
for (j=0; j pMatrix[i*Size+j] = rand()/double(1000);
}
}

int Size, int

RowNum)
{
int *pSendNum;//число элементов, отправляемых процессу
int *pSendInd;//индекс первого отправляемого процессу элемента
int RestRows=Size;
// рассылка вектора b всем процессам
MPI_Bcast(pVector, Size, MPI_DOUBLE, 0, MPI_COMM_WORLD);
//подготовка к распределению строк матрицы А по процессам
pSendInd = new int [ProcNum];//номера по процессам
pSendNum = new int [ProcNum];// количества по процессам
RowNum = Size/ProcNum;// повторно определение числа строк
// определение отсылаемых строк для каждого процесса
pSendNum[0] = RowNum*Size;
pSendInd[0] = 0;

- RowNum;
RowNum = RestRows/(ProcNum-i);// нужно если нет кратности

pSendNum[i] = RowNum*Size; //число элементов
pSendInd[i] = pSendInd[i-1]+pSendNum[i-1];//номер через смещение
}
// функция для отправления процессам разного числа элементов
MPI_Scatterv(pMatrix , pSendNum, pSendInd, MPI_DOUBLE, pProcRows,
pSendNum[ProcRank], MPI_DOUBLE, 0, MPI_COMM_WORLD);
// освобождение памяти
delete [] pSendNum;
delete [] pSendInd;
}

recvbuf, int recvcount, MPI_Datatype recvtype, int root, MPI_Comm comm)
sendbuf -

адрес начала буфера посылки (используется только в процессе-отправителе root);
sendcounts - целочисленный массив (размер равен числу процессов в группе), содержащий число элементов, посылаемых каждому процессу;
displs - целочисленный массив (размер равен числу процессов в группе), i-ое значение определяет смещение относительно начала sendbuf для данных, посылаемых процессу i;
sendtype - тип посылаемых элементов;
recvbuf - адрес начала буфера приема;
recvcount - число получаемых элементов;
recvtype - тип получаемых элементов;
root - номер процесса-отправителя;
comm - коммуникатор.

pProcResult, int Size, int RowNum)
{
int i, j;

for (i=0; i {
pProcResult[i] = 0;
for (j=0; j pProcResult[i] += pProcRows[i*Size+j]*pVector[j];
}
}

double* pResult, int Size, int RowNum)
{
int i;

int *pReceiveNum; //число получаемых элементов
int *pReceiveInd; //индекс элемента в векторе-результате
int RestRows=Size;//число нераспределенных элементов
// временные массивы
pReceiveNum = new int [ProcNum];//количества по процессам
pReceiveInd = new int [ProcNum];// номера по процессам
// определение частей (блоков элементов) вектора-результата
pReceiveInd[0] = 0;
pReceiveNum[0] = Size/ProcNum;

pReceiveNum[i-1];
pReceiveNum[i] = RestRows/(ProcNum-i);
pReceiveInd[i] = pReceiveInd[i-1]+pReceiveNum[i-1];
}
//

функция для сбора данных(для результата) на всех процессах группы
MPI_Allgatherv(pProcResult, pReceiveNum[ProcRank], MPI_DOUBLE, pResult, pReceiveNum, pReceiveInd, MPI_DOUBLE, MPI_COMM_WORLD);
// освобождение памяти
delete [] pReceiveNum;
delete [] pReceiveInd;
}

int recvcount,MPI_Datatype recvtype, MPI_Comm comm)
sendbuf - адрес начала буфера

посылки; sendcount - число посылаемых элементов;
sendtype - тип посылаемых элементов;
recvbuf - адрес начала буфера приема;
recvcount - число получаемых элементов (от каждого процесса);
recvtype - тип получаемых элементов;
comm - коммуникатор.

Получателями являются все процессы группы.
Данные, посланные процессом i из своего буфера sendbuf, помещаются в i-ю порцию буфера recvbuf каждого процесса.
После завершения операции содержимое буферов приема recvbuf у всех процессов одинаково.

int Size, int RowNum, double* pResult, double t1, double t2)

{
if (ProcRank == 0)
{
printf("\nInitial Matrix: \n");
PrintMatrix(pMatrix, Size, Size);//самостоятельно
printf("\nInitial Vector: \n");
PrintVector(pVector, Size);//самостоятельно
printf("\n\nResult Vector: \n");
PrintVector(pResult, Size);
PrintTime(t1,t2);//самостоятельно
}
MPI_Barrier(MPI_COMM_WORLD);// все ждут процесс 0

{
if (ProcRank == i)
{
printf("\nProcRank

= %d \n", ProcRank);
printf(" Matrix Stripe:\n");
PrintMatrix(pProcRows, RowNum, Size);//самостоятельно
printf(" Vector: \n");
PrintVector(pVector, Size);//самостоятельно
}
MPI_Barrier(MPI_COMM_WORLD);//ждем всех
}
}

pVector, double* pResult, double* pProcRows, double* pProcResult)
{
if (ProcRank

== 0)
delete [] pMatrix;// матрица А только на процессе 0
//на всех процессах
delete [] pVector;
delete [] pResult;
delete [] pProcRows;
delete [] pProcResult;
}

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

передавать процессам предназначенные им данные,
Всегда ли вычислительные узлы одинаковы по памяти и быстродействию???