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

Сентябрь 3, 2022

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

Содержание

2. Принципы распараллеливания В методах матричных вычислений повторяются одинаковые действия для разных элементов матриц Это параллелизм по
3. Способы разбиения матриц Ленточное разбиение – каждому процессору выделяется подмножество строк или столбцов Всего строк (столбцов)
4. Постановка задачи Матрица А размерности m x n умножается на вектор b (n элементов), результат –
5. Пример разбиения – ленточное по строкам Дополнительная задача разбиения: дублировать или разбивать векторы b и с?
6. Схема информационного взаимодействия подзадач
7. Распределение подзадач по процессорам Количество вычислительных операций одинаково для всех подзадач. Если p Распределение объединенных подзадач
8. Анализ эффективности параллельных вычислений Упрощенный подход: m = n Не учитывается коммуникационная трудоемкость Время выполнения всех
9. Анализ эффективности параллельных вычислений Учет коммуникационной трудоемкости модель Хокни - оценка времени передачи сообщения m байт
10. Программная реализация (MPI) – порядок по логике вызовов! int ProcNum = 0;//число процессов int ProcRank =
11. if (ProcRank == 0) { printf ("Parallel matrix-vector multiplication program\n"); } ProcessInitialization(pMatrix, pVector, pResult, pProcRows, pProcResult,
12. void ProcessInitialization (double* &pMatrix, double* &pVector, double* &pResult, double* &pProcRows, double* &pProcResult, int &Size, int &RowNum)
13. // осталось распределить между процессами Size строк матрицы А RestRows = Size; for (i=0; i {
14. void RandomDataInitialization(double* pMatrix, double* pVector, int Size) { int i, j; srand(unsigned(clock()));// инициализация датчика случайных чисел
15. void DataDistribution(double* pMatrix, double* pProcRows, double* pVector, int Size, int RowNum) { int *pSendNum;//число элементов, отправляемых
16. for (int i=1; i { RestRows = RestRows - RowNum; RowNum = RestRows/(ProcNum-i);// нужно если нет
17. Функция MPI_Scatterv int MPI_Scatterv(void* sendbuf, int *sendcounts, int *displs, MPI_Datatype sendtype, void* recvbuf, int recvcount, MPI_Datatype
18. // будет выполняться каждым процессом void ParallelResultCalculation(double* pProcRows, double* pVector, double* pProcResult, int Size, int RowNum)
19. // будет выполняться каждым процессом для сбора результата void ResultReplication(double* pProcResult, double* pResult, int Size, int
20. for (i=1; i { RestRows = RestRows - pReceiveNum[i-1]; pReceiveNum[i] = RestRows/(ProcNum-i); pReceiveInd[i] = pReceiveInd[i-1]+pReceiveNum[i-1]; }
21. Функция MPI_Allgatherv int MPI_Allgatherv(void* sendbuf, int sendcount, MPI_Datatype sendtype, void* recvbuf, int recvcount,MPI_Datatype recvtype, MPI_Comm comm)
22. // проверка результатов void TestDistribution(double* pMatrix, double* pVector, double* pProcRows, int Size, int RowNum, double* pResult,
23. // вывод результатов с других процессов for (int i=1; i { if (ProcRank == i) {
24. // освобождение памяти на всех процессах void ProcessTermination (double* pMatrix, double* pVector, double* pResult, double* pProcRows,
26. Скачать презентацию

Слайд 2

Принципы распараллеливания
В методах матричных вычислений повторяются одинаковые действия для разных элементов

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

Слайд 3

Способы разбиения матриц
Ленточное разбиение – каждому процессору выделяется подмножество строк

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

Слайд 4

Постановка задачи
Матрица А размерности m x n умножается на вектор b

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

Слайд 5

Пример разбиения – ленточное по строкам
Дополнительная задача разбиения: дублировать или разбивать

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

Слайд 6

Схема информационного взаимодействия подзадач

Слайд 7

Распределение подзадач по процессорам
Количество вычислительных операций одинаково для всех подзадач.
Если p

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

Слайд 8

Анализ эффективности параллельных вычислений
Упрощенный подход:
m = n
Не учитывается коммуникационная трудоемкость
Время выполнения

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

Слайд 9

Анализ эффективности параллельных вычислений
Учет коммуникационной трудоемкости модель Хокни - оценка времени передачи

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

Слайд 10

Программная реализация (MPI) – порядок по логике вызовов!
int ProcNum = 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);

Слайд 11

$if (ProcRank == 0) { printf ("Parallel matrix-vector multiplication program\n"); }$

if (ProcRank == 0)
{
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();
}

Слайд 12

void ProcessInitialization (double* &pMatrix, double* &pVector,
double* &pResult, double* &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);

Слайд 13

// осталось распределить между процессами Size строк матрицы А
RestRows

= Size;
for (i=0; i { RestRows = 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);
}}

Слайд 14

void RandomDataInitialization(double* pMatrix, double* pVector, int Size)
{
int i, j;

srand(unsigned(clock()));// инициализация датчика случайных чисел
for (i=0; i {
pVector[i] = rand()/double(1000);
for (j=0; j pMatrix[i*Size+j] = rand()/double(1000);
}
}

Слайд 15

void DataDistribution(double* pMatrix, double* pProcRows, double* pVector,
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;

Слайд 16

for (int i=1; i{
RestRows = RestRows - 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;
}

Слайд 17

Функция MPI_Scatterv
int MPI_Scatterv(void* sendbuf, int sendcounts, int displs,
MPI_Datatype sendtype, void* recvbuf,

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

Слайд 18

// будет выполняться каждым процессом
void ParallelResultCalculation(double* pProcRows, double* pVector, double* 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];
}
}

Слайд 19

// будет выполняться каждым процессом для сбора результата
void ResultReplication(double* pProcResult, 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;

Слайд 20

for (i=1; i{
RestRows = RestRows - 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;
}

Слайд 21

Функция MPI_Allgatherv
int MPI_Allgatherv(void* sendbuf, int sendcount, MPI_Datatype sendtype, void* recvbuf, int

recvcount,MPI_Datatype recvtype, MPI_Comm comm)
sendbuf - адрес начала буфера посылки; sendcount - число посылаемых элементов;
sendtype - тип посылаемых элементов;
recvbuf - адрес начала буфера приема;
recvcount - число получаемых элементов (от каждого процесса);
recvtype - тип получаемых элементов;
comm - коммуникатор.
Получателями являются все процессы группы.
Данные, посланные процессом i из своего буфера sendbuf, помещаются в i-ю порцию буфера recvbuf каждого процесса.
После завершения операции содержимое буферов приема recvbuf у всех процессов одинаково.

Слайд 22

// проверка результатов
void TestDistribution(double* pMatrix, double* pVector, double* pProcRows,
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

Слайд 23

// вывод результатов с других процессов
for (int i=1; i{

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);//ждем всех
}
}

Слайд 24

// освобождение памяти на всех процессах
void ProcessTermination (double* pMatrix, double* pVector,

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

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

Содержание

Принципы распараллеливанияВ методах матричных вычислений повторяются одинаковые действия для разных элементов

Способы разбиения матриц Ленточное разбиение – каждому процессору выделяется подмножество строк

Постановка задачиМатрица А размерности m x n умножается на вектор b

Пример разбиения – ленточное по строкамДополнительная задача разбиения: дублировать или разбивать

Схема информационного взаимодействия подзадач

Распределение подзадач по процессорамКоличество вычислительных операций одинаково для всех подзадач.Если p

Анализ эффективности параллельных вычисленийУпрощенный подход:m = nНе учитывается коммуникационная трудоемкостьВремя выполнения

Анализ эффективности параллельных вычисленийУчет коммуникационной трудоемкости модель Хокни - оценка времени передачи

Программная реализация (MPI) – порядок по логике вызовов!int ProcNum = 0;//число

if (ProcRank == 0) { printf ("Parallel matrix-vector multiplication

void ProcessInitialization (double* &pMatrix, double* &pVector, double* &pResult, double* &pProcRows,

// осталось распределить между процессами Size строк матрицы А RestRows

void RandomDataInitialization(double* pMatrix, double* pVector, int Size) { int i, j;

void DataDistribution(double* pMatrix, double* pProcRows, double* pVector, int Size, int RowNum)

for (int i=1; i{ RestRows = RestRows - RowNum;

Функция MPI_Scattervint MPI_Scatterv(void* sendbuf, int *sendcounts, int *displs,MPI_Datatype sendtype, void* recvbuf,

// будет выполняться каждым процессомvoid ParallelResultCalculation(double* pProcRows, double* pVector, double* pProcResult,

// будет выполняться каждым процессом для сбора результатаvoid ResultReplication(double* pProcResult, double*

for (i=1; i{ RestRows = RestRows - pReceiveNum[i-1]; pReceiveNum[i]

Функция MPI_Allgathervint MPI_Allgatherv(void* sendbuf, int sendcount, MPI_Datatype sendtype, void* recvbuf, int

// проверка результатовvoid TestDistribution(double* pMatrix, double* pVector, double* pProcRows, int Size,

// вывод результатов с других процессовfor (int i=1; i{

// освобождение памяти на всех процессахvoid ProcessTermination (double* pMatrix, double* pVector,

Похожие презентации