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

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


Вашему вниманию предлагается презентация «Параллельные методы решения задач линейной алгебры», с которой можно предварительно ознакомиться, просмотреть текст и слайды к ней, а так же, в случае, если она вам подходит - скачать файл для редактирования или печати.

Презентация содержит 25 слайдов и доступна для скачивания в формате ppt. Размер скачиваемого файла: 692.38 KB

Просмотреть и скачать

Pic.1
Параллельные методы решения задач линейной алгебры Параллельные методы умножения матрицы на вектор П
Параллельные методы решения задач линейной алгебры Параллельные методы умножения матрицы на вектор Принципы распараллеливания Анализ эффективности Программная реализация
Pic.2
Принципы распараллеливания В методах матричных вычислений повторяются одинаковые действия для разных
Принципы распараллеливания В методах матричных вычислений повторяются одинаковые действия для разных элементов матриц Это параллелизм по данным Распараллеливание = распределение частей матриц между вычислительными узлами МВС Способ разбиения на части и распределения данных определяет параллельный алгоритм решения задачи
Pic.3
Способы разбиения матриц Ленточное разбиение – каждому процессору выделяется подмножество строк или
Способы разбиения матриц Ленточное разбиение – каждому процессору выделяется подмножество строк или столбцов Всего строк (столбцов) – М, процессоров - р Предполагается, что М кратно р Блочное разбиение – каждому процессору выделяется блок элементов (прямоугольный, связный). Также возможны упрощающие предположения кратности
Pic.4
Постановка задачи Матрица А размерности m x n умножается на вектор b (n элементов), результат – вект
Постановка задачи Матрица А размерности m x n умножается на вектор b (n элементов), результат – вектор с (m элементов). Общее количество операций (для оценки Т1): m операций умножения строк А на b, где каждая: n операций умножения элементов и (n – 1) операция сложения произведений Время выполнения последовательного алгоритма: Т1 = m (2n – 1) Порядок трудоемкости последовательного алгоритма: О(mn)
Pic.5
Пример разбиения – ленточное по строкам Дополнительная задача разбиения: дублировать или разбивать в
Пример разбиения – ленточное по строкам Дополнительная задача разбиения: дублировать или разбивать векторы b и с? Каждый процессор хранит строку матрицы А + отдельные элементы векторов – порядок числа сохраняемых значений: О(max(m, n)) Каждый процессор хранит строку матрицы А + все элементы векторов – порядок числа сохраняемых значений: О(max(m, n)) Дублирование не повышает порядок сложности по памяти
Pic.6
Схема информационного взаимодействия подзадач
Схема информационного взаимодействия подзадач
Pic.7
Распределение подзадач по процессорам Количество вычислительных операций одинаково для всех подзадач
Распределение подзадач по процессорам Количество вычислительных операций одинаково для всех подзадач. Если p < m, то выполняется объединение подзадач, соответствующих непрерывной последовательности строк. Распределение объединенных подзадач по процессорам произвольно
Pic.8
Анализ эффективности параллельных вычислений Упрощенный подход: m = n Не учитывается коммуникационна
Анализ эффективности параллельных вычислений Упрощенный подход: m = n Не учитывается коммуникационная трудоемкость Время выполнения всех операций одинаково Последовательный алгоритм: Т1 = n (2n – 1) Параллельный алгоритм: Тp = n (2n – 1)/p Ускорение: Sp = Т1 / Тp = p Эффективность: Еp = Sp/p = 1
Pic.9
Анализ эффективности параллельных вычислений Учет коммуникационной трудоемкости модель Хокни - оценк
Анализ эффективности параллельных вычислений Учет коммуникационной трудоемкости модель Хокни - оценка времени передачи сообщения m байт tпд = tн + m/R tн - время латентности, R - пропускная способность сети Параллельный алгоритм (все узлы узнают результат): Тp = tн (log2p) + top( n (2n – 1)/p) + ( n (n – 1)/p) m/R Предположения: Топология – полный граф Последовательный обмен данными между узлами (на каждом шаге сообщения увеличиваются в 2 раза), число шагов = log2p
Pic.10
Программная реализация (MPI) – порядок по логике вызовов! int ProcNum = 0;//число процессов int Proc
Программная реализация (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);
Pic.11
if (ProcRank == 0) if (ProcRank == 0) { printf ("Parallel matrix-vector multiplication program\
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(); }
Pic.12
void ProcessInitialization (double* &pMatrix, double* &pVector, void ProcessInitialization (
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);
Pic.13
// осталось распределить между процессами Size строк матрицы А // осталось распределить между процес
// осталось распределить между процессами 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); }}
Pic.14
void RandomDataInitialization(double* pMatrix, double* pVector, int Size) void RandomDataInitializat
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); } }
Pic.15
void DataDistribution(double* pMatrix, double* pProcRows, double* pVector, void DataDistribution(dou
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;
Pic.16
for (int i=1; i<ProcNum; i++) for (int i=1; i<ProcNum; i++) { RestRows = RestRows - RowNum; Ro
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; }
Pic.17
Функция MPI_Scatterv int MPI_Scatterv(void* sendbuf, int *sendcounts, int *displs, MPI_Datatype send
Функция 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 - коммуникатор.
Pic.18
// будет выполняться каждым процессом // будет выполняться каждым процессом void ParallelResultCalcu
// будет выполняться каждым процессом // будет выполняться каждым процессом 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]; } }
Pic.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;
Pic.20
for (i=1; i<ProcNum; i++) for (i=1; i<ProcNum; i++) { RestRows = RestRows - pReceiveNum[i-1];
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; }
Pic.21
Функция MPI_Allgatherv int MPI_Allgatherv(void* sendbuf, int sendcount, MPI_Datatype sendtype, void*
Функция 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 у всех процессов одинаково.
Pic.22
// проверка результатов // проверка результатов void TestDistribution(double* pMatrix, double* pVect
// проверка результатов // проверка результатов 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
Pic.23
// вывод результатов с других процессов // вывод результатов с других процессов for (int i=1; i<P
// вывод результатов с других процессов // вывод результатов с других процессов 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);//ждем всех } }
Pic.24
// освобождение памяти на всех процессах // освобождение памяти на всех процессах void ProcessTermin
// освобождение памяти на всех процессах // освобождение памяти на всех процессах 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; }
Pic.25
Замечания Разделение (по функциям) действий генерации исходных данных и их рассылки процессам не под
Замечания Разделение (по функциям) действий генерации исходных данных и их рассылки процессам не подходит для больших объемов данных. Лучше сразу после генерации передавать процессам предназначенные им данные, Всегда ли вычислительные узлы одинаковы по памяти и быстродействию???


Скачать презентацию

Если вам понравился сайт и размещенные на нем материалы, пожалуйста, не забывайте поделиться этой страничкой в социальных сетях и с друзьями! Спасибо!