лекции (1185991), страница 9

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

Текст из файла (страница 9)

прогр. длявысокопроизводительных систем",24.11.201546Алгоритм КеннонаЛекции спецкурс "Пар. прогр. длявысокопроизводительных систем",24.11.201547Схема алгоритма Кеннонаfor all (i=0 to s-1)// начальное распределение блоков матрицы AЦиклический сдвиг влево строки i матрицы A на jтак, чтобы на место A(i,j) была записана подматрица A(i,(i+j) mod s)endfor for all (i=0 to s-1) // начальное распределение блоков матрицы BЦиклический сдвиг вверх столбца j матрицы B на jтак, чтобы на место B(i,j) была записана подматрица B((i+j) mod s,j)endfor for k=0 to s-1for all (i=0 to s-1, j=0 to s-1)C(i,j) = C(i,j) + A(i,j)*B(i,j)Лекции спецкурс "Пар. прогр.

длявысокопроизводительных систем",24.11.201548Схема алгоритма КеннонаЦиклический сдвиг влево каждой строки матрицы A на 1так,чтобы на место A(i,j) была записана подматрица A(i,(j+1) mod s)Циклический сдвиг вверх каждого столбца матрицы B на 1так, чтобы на место B(i,j) была записана подматрица B((i+1)mod s,j)end forend forЛекции спецкурс "Пар. прогр. длявысокопроизводительных систем",24.11.201549Алгоритм Кеннона: основной циклdims[0] = dims[1] = sqrt(P);periods[0] = periods[1] = 1;MPI_Cart_Create(comm,2,dims,periods,1,&comm_2d);MPI_Comm_rank(comm_2d, &my2drank);MPI_Cart_coords(comm_2d, my2drank, 2, mycoords);MPI_Cart_shift(comm_2d, 0, -1, &rightrank, &leftrank);MPI_Cart_shift(comm_2d, 1, -1, &downrank, &uprank);nlocal = n/dims[0];Лекции спецкурс "Пар. прогр.

длявысокопроизводительных систем",24.11.201550Алгоритм Кеннона: основной цикл/* Initial Matrix Alignment */MPI_Cart_shift(comm_2d, 0, -mycoords[0], &shiftsource,&shiftdest);MPI_Sendrecv_replace(a, nlocal*nlocal, MPI_DOUBLE,shiftdest, 1, shiftsource, 1, comm_2d, &status);MPI_Cart_shift(comm_2d, 1, -mycoords[1], &shiftsource,&shiftdest);MPI_Sendrecv_replace(b, nlocal*nlocal, MPI_DOUBLE,shiftdest, 1, shiftsource, 1, comm_2d, &status);Лекции спецкурс "Пар. прогр. длявысокопроизводительных систем",24.11.201551Алгоритм Кеннона: основной цикл/* Main Computation Loop */for(i=0; i<dims[0]; i++){MatrixMultiply(nlocal,a,b,c); /* c=c+a*b*//* Shift matrix a left by one */MPI_Sendrecv_replace(a, nlocal*nlocal, MPI_DOUBLE,leftrank, 1, rightrank, 1, comm_2d, &status);/* Shift matrix b up by one */MPI_Sendrecv_replace(b, nlocal*nlocal, MPI_DOUBLE,uprank, 1, downrank, 1, comm_2d, &status);}Лекции спецкурс "Пар.

прогр. длявысокопроизводительных систем",24.11.201552Алгоритм Кеннона: основной цикл/* Restore original distribution of a and b */MPI_Cart_shift(comm_2d, 0, +mycoords[0], &shiftsource,&shiftdest);MPI_Sendrecv_replace(a, nlocal*nlocal, MPI_DOUBLE,shiftdest, 1, shiftsource, 1, comm_2d, &status);MPI_Cart_shift(comm_2d, 1, +mycoords[1], &shiftsource,&shiftdest);MPI_Sendrecv_replace(b, nlocal*nlocal, MPI_DOUBLE,shiftdest, 1, shiftsource, 1, comm_2d, &status);Лекции спецкурс "Пар.

прогр. длявысокопроизводительных систем",24.11.201553Алгоритм ФоксаЛекции спецкурс "Пар. прогр. длявысокопроизводительных систем",24.11.201554Алгоритм ФоксаЛекции спецкурс "Пар. прогр. длявысокопроизводительных систем",24.11.201555Алгоритм ФоксаШаг 1. Широковещательная рассылка диагонального элемента каждойстроки матрицы A по всем процессорам своей строки.Каждый процессор (i,j) выполняетC(i,j) = A(i,i)*B(i,j)Столбец матрицы B циклически сдвигается вверх по своемустолбцу, замещая элемент B(i,j).Шаг 2.

Широковещательная рассылка элемента матрицы A,находящегося справа от диагонального, по всем процессорамсвоей строки.Каждый процессор (i,j) выполняетC(i,j) = C(i,i)+A(i+1,i)*B(i+1,j)Столбец матрицы B циклически сдвигается вверх по своемустолбцуШаг k. Широковещательная рассылка очередного (i+k) mod sэлемента строки матрицы A по всем процессорам своей строки.Каждый процессор (i,j) выполняет:C(i,j) = C(i,j) + A(i,(i+k) mod s)*B((i+k) mod s,j)Столбец матрицы B циклически сдвигается вверх по своемустолбцу, замещая собой текущий элемент B(i,j)Лекции спецкурс "Пар. прогр. длявысокопроизводительных систем",24.11.201556Алгоритм Фокса (1)typedef struct {int p; /* Общее число процессов */MPI_Comm comm; /* Коммуникатор для сетки */MPI_Comm row_comm; /* Коммуникатор строки */MPI_Comm col_comm; /* Коммуникатор столбца */int q; /* Порядок сетки */int my_row; /* Номер строки */int my_col; /* Номер столбца */int my_rank; /* Ранг процесса в коммуникаторе сетки */} GRID-INFO-TYPE;Лекции спецкурс "Пар.

прогр. длявысокопроизводительных систем",24.11.201557Алгоритм Фокса (2)void Setvup_grid(GRID_INFO_TYPE* grid) {intintintintintold_rank;dimensions[2];periods[2];coordinates[2];varying-coords[2];/* Настройка глобальной информации о сетке */MPI_Comm_size(MPI_COMM_WORLD, &(grid->p));MPI_Comm_rank(MPI_COMM_WORLD, &old_rank);grid->q = (int) sqrt((double) grid->p);dimensions[0] = dimensions[1] = grid->q;periods[0] = periods[1] = 1;MPI_Cart_create(MPI_COMM_WORLD, 2, dimensions, periods, 1,&(grid->comm));Лекции спецкурс "Пар. прогр. длявысокопроизводительных систем",24.11.201558Алгоритм Фокса (3)MPI_Comm_rank(grid->comm, &(grid->my_rank));MPI_Cart_coords(grid->comm, grid->my_rank, 2, coordinates);grid->my_row = coordinates[0];grid->my_col = coordinates[1];/* Настройка коммуникаторов для строк и столбцов */varying_coords[0] = 0; varying_coords[1] = 1;MPI_Cart_sub(grid->comm, varying_coords, &(grid->row_comm));varying_coords[0] = 1; varying_coords[1] = 0;MPI_Cart_sub(grid->comm, varying_coords, &(grid->col_comm));} /* Setup_grid */Лекции спецкурс "Пар.

прогр. длявысокопроизводительных систем",24.11.201559Алгоритм Фокса (4)void Fox(int n, GRID_INFO_TYPE* grid, LOCAL_MATRIX_TYPE*local_A,LOCAL_MATRIX_TYPE* local_B, LOCAL_MATRIX_TYPE*local_C){LOCAL_MATRIX_TYPE* temp_A;int step;int bcast_root;int n_bar; /* порядок подматрицы = n/q */int source;int dest;int tag = 43;MPI_Status status;n_bar = n/grid->q;Set_to_zero(local_C);Лекции спецкурс "Пар. прогр.

длявысокопроизводительных систем",24.11.201560Алгоритм Фокса (5)/* Вычисление адресов для циклического сдвига B */source = (grid->my_row + 1) % grid->q;dest = (grid->my_row + grid->q-1) % grid->q;/* Выделение памяти для рассылки блоков A */temp_A = Local_matrix_allocate(n_bar);for (step = 0; step < grid->q; step++) {bcast_root = (grid->my_row + step) % grid->q;if (bcast_root == grid->my_col) {MPI_Bcast(local_A, 1, DERIVED_LOCAL_MATRIX, bcast_root,grid->row_comm);Local_matrix_multiply(local_A, local_B, local_C);Лекции спецкурс "Пар.

прогр. длявысокопроизводительных систем",24.11.201561Алгоритм Фокса (6)} else {MPI_Bcast(temp_A, 1, DERIVED_LOCAL_MATRIX, bcast_root,grid->row_comm);Local_matrix_multiply(temp_A, local_B, local_C);}MPI_Send(local_B, 1, DERIVED_LOCAL_MATRIX, dest, tag,grid->col_comm);MPI_Recv(local_B, 1, DERIVED_LOCAL_MATRIX, source, tag,grid->col_comm, &status);} /*for*/}/*Fox*/Лекции спецкурс "Пар. прогр. длявысокопроизводительных систем",24.11.201562Задание .Реализовать блочные параллельныеалгоритмы матричного умноженияФокса и Кеннона Провести исследованиеэффективности разработанныхалгоритмов.Лекции спецкурс "Пар. прогр. длявысокопроизводительных систем",24.11.201563Параллельное программирование длявысокопроизводительных вычислительных систем.сентябрь – декабрь 2015 г.Лекторы: доцент Н.Н.Попова,асс.В.А.БахтинЛекция1 декабря 2015 г.Спецкурс "Параллельноепрогораммирование", MPI,лекция 7, лекторН.Н.ПоповаТемаУточнение постановки задания«Параллельные алгоритмы матричногоумножения»Итоговое задание :«Исследование решения задачи Дирихле»Спецкурс "Параллельноепрогораммирование", MPI,лекция 7, лекторН.Н.ПоповаЗадание 3.На основе представленных в лекциях алгоритмовФокса, Кеннона разработать параллельныйалгоритм матричного умножения C=AxBПровести исследование эффективностиразработанных алгоритмов.Исследовать влияние мэппинга процессов на времявыполнения параллельных программ.

Провестианализ временных затрат (вычисления, обменданными).Спецкурс "Параллельноепрогораммирование", MPI,лекция 7, лекторН.Н.ПоповаРежимы использования ядер Blue Gene/P3 режимаSMP: 1 MPI процесс из 4 SMP нитей,2 Гб памяти- mode smpСпецкурс "Параллельноепрогораммирование", MPI,лекция 7, лекторН.Н.ПоповаРежимы использования ядер3 режимаDUAL: 2 MPI процесса по 2 SMP нити,1 Гб памяти на MPI процесс- mode dualСпецкурс "Параллельноепрогораммирование", MPI,лекция 7, лекторН.Н.ПоповаРежимы использования ядер3 режимаVNM: 4 MPI процесса- mode vnСпецкурс "Параллельноепрогораммирование", MPI,лекция 7, лекторН.Н.ПоповаПроцессорные партицииПодмножества вычислительных узлов, выделяемыхзадачеКаждой задаче выделяется своя партицияЗагрузка задачи на исполнение производитсянезависимо от других задачРазмер партиции определяется кратным 32(на текущий момент на системе ВМК - кратным 128 )Для партиций размером кратным 512поддерживается топология тораСпецкурс "Параллельноепрогораммирование", MPI,лекция 7, лекторН.Н.ПоповаНазначение процессов на процессоры(mapping) Blue Gene/PРаспределение процессовпо процессорам по умолчанию:XYZT, где <XYZ> - координатыпроцесса в торе,T – номер ядра внутри процесса.Сначала увеличивается X –координата, затем Y и Zкоординаты, после этогоT- номер ядраСпецкурс "Параллельноепрогораммирование", MPI,лекция 7, лекторН.Н.ПоповаMapping2 способа назначения процессов на процессоры: с помощью аргумента командной строки командыmpirun–mapfile TXYZ (задаем порядок TXYZ или другиеперестановки X,Y,Z,T: TYXZ, TZXY и т.д.)Спецкурс "Параллельноепрогораммирование", MPI,лекция 7, лекторН.Н.ПоповаMappingуказание map- файла в mpisubmit.bg–e BG_MAPPING = map.txtгде map.txt – имя файла.Синтаксис файла распределения – четыре целых числа в каждойстроке задают координаты для каждого MPI-процесса (перваястрока задает координаты для процесса с номером 0, втораястрока – для процесса с номером 1 и т.д.).00010011Спецкурс "Параллельноепрогораммирование", MPI,лекция 7, лекторН.Н.ПоповаНазначение процессов напроцессоры.

map-файл.Очень важно, чтобы этот файлзадавалкорректноераспределение, с однозначнымсоответствием между номеромпроцесса и координатами <X, Y,Z, T>.0-й процесс1-й процессXYZTФрагмент файла,задающегоmapping,сгенерированныйслучайнымобразом.Спецкурс "Параллельноепрогораммирование", MPI,лекция 7, лекторН.Н.Попова33122060131322221171203112430123137202502133326221023211…..Основной шаблон протокола работыпользователяКомпиляция MPI-программы (C,C++ BGP, front-end)%mpixlc –O3 –qarch=450 –qtune=450example.c -o c_ex%mpixlcxx –O3 –qarch=450 –qtune=450example.cpp -o cpp_exКомпиляция гибридной MPI-OpenMP программы:%mpixlc_r -qsmp=omp –O3 –qarch=450–qtune=450 hw.c -o hwВыполнение MPI-программы% mpisubmit.bg –n 128 –w 00:15:00 –eBG_MAPPING=TZXYZ -m smp example – arg1 arg2%mpisubmit.bg –helpСпецкурс "Параллельноепрогораммирование", MPI,лекция 7, лекторН.Н.ПоповаОсновной шаблон протокола работыпользователяПостановка MPI-программы в очередь задач с лимитом выполнения 15 минутна 32 узлах в режиме VN c параметром командной строки :%mpisubmit.bg -w 00:15:00 -m vn -n 32prog – 0.1 200Постановка MPI+OpenMP программы prog в очередь задач с лимитомвыполнения 15 минут на 128 узлах в режиме SMP c 4 нитями на каждомузле, с заданием файла мэпинга map.txt и c параметром командной строкиparameter:%mpisubmit.bg -w 00:15:00 -m smp -n 128-e \”OMP_NUM_THREADS=4 BG_MAPPING=map.txt \”prog -- parameterОсновной шаблон протокола работыпользователяПроверка состояния очереди задач:%llqУдаление задачи из очереди:%llcancel <task_id>Текущее состояние очереди%llmapСпецкурс "Параллельноепрогораммирование", MPI,лекция 7, лекторН.Н.ПоповаPMPIPMPI позволяет заменять вызовы MPIфункций во время линкования (не требуетсяперекомпиляция)Спецкурс "Параллельноепрогораммирование", MPI,лекция 7, лекторН.Н.ПоповаИтоговое задание .Исследование эффективности решениязадачи Дирихле для уравнения Лапласа.Задача Дирихле для уравнения Лапласа (1).  2u  2u  2u 2  2  2  0, ( x, y, z )  D,yz xu ( x, y, z )  g ( x, y, z ), ( x, y, z )  D 0 ,(1)где u(x, y, z) - функция, удовлетворяющая в области D уравнениюЛапласа и принимающая на границе D0 области D значения g(x, y, z).М.В.Абакумов, А.В.Гулин Лекции по численным методамматематической физики.

Характеристики

Список файлов лекций