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

Нажмите для полного просмотра!

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Параллельные методы решения задач линейной алгебры. Доклад-сообщение содержит 25 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

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

Слайд 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) if (ProcRank == 0) { printf ("Parallel matrix-vector multiplication program\n"); } ProcessInitialization(pMatrix,...$

Описание слайда:

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(); }

Слайд 12

Описание слайда:

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);

Слайд 13

Описание слайда:

// осталось распределить между процессами Size строк матрицы А // осталось распределить между процессами Size строк матрицы А RestRows = Size; for (i=0; i

Слайд 14

Описание слайда:

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

Слайд 15

Описание слайда:

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;

Слайд 16

Описание слайда:

for (int i=1; i

Слайд 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

Слайд 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

Слайд 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

Слайд 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; }

Слайд 25

Описание слайда:

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