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

Содержание слайда: Параллельные методы решения задач линейной алгебры Параллельные методы умножения матрицы на вектор Принципы распараллеливания Анализ эффективности Программная реализация

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

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

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

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

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

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

Содержание слайда: Анализ эффективности параллельных вычислений Упрощенный подход: m = n Не учитывается коммуникационная трудоемкость Время выполнения всех операций одинаково Последовательный алгоритм: Т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

Содержание слайда: Программная реализация (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);

Содержание слайда: if (ProcRank == 0) 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(); }

Содержание слайда: void ProcessInitialization (double* &pMatrix, double* &pVector, 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);

Содержание слайда: // осталось распределить между процессами Size строк матрицы А // осталось распределить между процессами Size строк матрицы А RestRows = Size; for (i=0; i<ProcRank; 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); }}

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

Содержание слайда: void DataDistribution(double* pMatrix, double* pProcRows, double* pVector, 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;

Содержание слайда: for (int i=1; i<ProcNum; i++) for (int i=1; i<ProcNum; 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; }

Содержание слайда: Функция 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 - коммуникатор.

Содержание слайда: // будет выполняться каждым процессом // будет выполняться каждым процессом void ParallelResultCalculation(double* pProcRows, double* pVector, double* pProcResult, int Size, int RowNum) { int i, j; for (i=0; i<RowNum; i++) { pProcResult[i] = 0; for (j=0; j<Size; j++) pProcResult[i] += pProcRows[i*Size+j]*pVector[j]; } }

Содержание слайда: // будет выполняться каждым процессом для сбора результата // будет выполняться каждым процессом для сбора результата 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;

Содержание слайда: for (i=1; i<ProcNum; i++) for (i=1; i<ProcNum; 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; }

Содержание слайда: Функция 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 у всех процессов одинаково.

Содержание слайда: // проверка результатов // проверка результатов 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

Содержание слайда: // вывод результатов с других процессов // вывод результатов с других процессов for (int i=1; i<ProcNum; 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);//ждем всех } }

Содержание слайда: // освобождение памяти на всех процессах // освобождение памяти на всех процессах 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; }

Содержание слайда: Замечания Разделение (по функциям) действий генерации исходных данных и их рассылки процессам не подходит для больших объемов данных. Лучше сразу после генерации передавать процессам предназначенные им данные, Всегда ли вычислительные узлы одинаковы по памяти и быстродействию???