МГУ им. М.В. Ломоносова, Москва, 2010 г. Гибридные модели параллельного программирования MPI/OpenMP и DVM/OpenMP Бахтин Владимир Александрович Ассистент. - презентация

1 МГУ им. М.В. Ломоносова, Москва, 2010 г. Гибридные модели параллельного программирования MPI/OpenMP и DVM/OpenMP Бахтин Владимир Александрович Ассистент кафедры системного программированния факультета ВМК, МГУ им. М. В. Ломоносова К.ф.-м.н., зав. сектором Института прикладной математики им М.В.Келдыша РАН

2 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 2 из 123 Содержание Современные направления развития параллельных вычислительных систем Гибридная модель MPI/OpenMP Гибридная модель DVM/OpenMP OpenMP – модель параллелизма по управлению

3 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 3 из 123 Тенденции развития современных процессоров В течение нескольких десятилетий развитие ЭВМ сопровождалось удвоением их быстродействия каждые года. Это обеспечивалось и повышением тактовой частоты и совершенствованием архитектуры (параллельное и конвейерное выполнение команд). Узким местом стала оперативная память. Знаменитый закон Мура, так хорошо работающий для процессоров, совершенно не применим для памяти, где скорости доступа удваиваются в лучшем случае каждые 6 лет. Совершенствовались системы кэш-памяти, увеличивался объем, усложнялись алгоритмы ее использования. Для процессора Intel Itanium: Latency to L1: 1-2 cycles Latency to L2: cycles Latency to L3: cycles Latency to memory: 180 – 225 cycles Важным параметром становится - GUPS (Giga Updates Per Second)

4 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 4 из 123 Время Тенденции развития современных процессоров В П В П В П В П В П В П Поток Время В П В П В П Поток 1 В П В П В П В П В П В П В П В П В П Поток 2 Поток 3 Поток 4 В - вычисления П - доступ к памяти Chip MultiThreading увеличили производительность процессора в 2 раза Поток или нить (по- английски thread) – это легковесный процесс, имеющий с другими потоками общие ресурсы, включая общую оперативную память.

5 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 5 из 123 Суперкомпьютер СКИФ МГУ «Чебышев» Пиковая производительность - 60 TFlop/s Число процессоров/ядер в системе / 5000 Производительность на Linpack TFlop/s (78.4% от пиковой) Номинальное энергопотребление компьютера кВт Энергопотребление комплекса кВт Важным параметром становится – Power Efficency (Megaflops/watt) Как добиться максимальной производительности на Ватт => Chip MultiProcessing, многоядерность. Тенденции развития современных процессоров

6 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 6 из 123 x Six-Core AMD Opteron 6 ядер встроенный контроллер памяти (2 канала памяти DDR2 800 МГц ) 3 канала «точка-точка» с использованием HyperTransort Тенденции развития современных процессоров

7 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 7 из 123 Intel Core i7 (архитектура Nehalem ) 4 ядра 8 потоков с технологией Intel Hyper-Threading 8 МБ кэш-памяти Intel Smart Cache встроенный контроллер памяти (3 канала памяти DDR3) технология Intel QuickPath Interconnect Тенденции развития современных процессоров

8 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 8 из 123 SUN UltraSPARC T2 Processor (Niagara 2) 8 ядер 64 потоков 4 контроллера памяти потребляемая мощность – Ватт встроенный котроллер 2x10 Gigabit Ethernet Тенденции развития современных процессоров

9 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 9 из 123 Темпы уменьшения латентности памяти гораздо ниже темпов ускорения процессоров + прогресс в технологии изготовления кристаллов => CMT (Chip MultiThreading) Опережающий рост потребления энергии при росте тактовой частоты + прогресс в технологии изготовления кристаллов => CMP (Chip MultiProcessing, многоядерность) И то и другое требует более глубокого распараллеливания для эффективного использования аппаратуры Тенденции развития современных процессоров

10 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 10 из 123 Содержание Современные направления развития параллельных вычислительных систем Гибридная модель MPI/OpenMP Гибридная модель DVM/OpenMP OpenMP – модель параллелизма по управлению

11 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 11 из 123 Гибридная модель MPI/OpenMP Данные Core Данные Вычисления Core … Узел 0 OpenMP Core Данные Вычисления Core … Узел N OpenMP Вычисления MPI

12 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 12 из 123 Достоинства использования в узлах OpenMP вместо MPI Возможность инкрементального распараллеливания. Упрощение программирования и эффективность на нерегулярных вычислениях, проводимых над общими данными. Ликвидация или сокращение дублирования данных в памяти, свойственного MPI-программам. Дополнительный уровень параллелизма на OpenMP реализовать проще, чем на MPI.

13 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 13 из 123 Преимущества OpenMP для многоядерных процессоров Объемы оперативной памяти и кэш памяти, приходящиеся в среднем на одно ядро, будут сокращаться – присущая OpenMP экономия памяти становится очень важна. Ядра используют общую Кэш-память, что требуется учитывать при оптимизации программы.

14 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 14 из 123 National Institute for Computational Sciences. University of Tennessee Суперкомпьютер Kraken Cray XT5-HE Opteron Six Core 2.6 GHz 3 место в TOP Пиковая производительность TFlop/s Число процессоров/ядер в системе / Производительность на Linpack TFlop/s (81% от пиковой) Updrage: замена 4-х ядерных процессоров AMD Opteron на 6-ти ядерные процессоры AMD Opteron Результат: 6-ое место в TOP500 в июне ье место в TOP500 в ноябре 2009

15 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 15 из 123 Межведомственный Суперкомпьютерный Центр Российской Академии Наук Суперкомпьютер MVS-100K 38 место в TOP Пиковая производительность TFlop/s Число процессоров/ядер в системе 2 920/ Производительность на Linpack TFlop/s (76.7% от пиковой) Updrage: замена 2-х ядерных процессоров Intel Xeon 53xx на 4-х ядерные процессоры Intel Xeon 54xx Результат: 57-ое место в TOP500 в июне ое место в TOP500 в ноябре 2008

16 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 16 из 123 Oak Ridge National Laboratory Суперкомпьютер Jaguar Cray XT5-HE Opteron Six Core 2.6 GHz 1 место в TOP Пиковая производительность TFlop/s Число ядер в системе Производительность на Linpack TFlop/s (75.4% от пиковой) Updrage: замена 4-х ядерных процессоров AMD Opteron на 6-ти ядерные процессоры AMD Opteron Результат: 2-ое место в TOP500 в июне ое место в TOP500 в ноябре 2009

17 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 17 из 123 Oak Ridge National Laboratory Jaguar Scheduling Policy MIN Cores MAX Cores MAXIMUM WALL-TIME (HOURS)

18 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 18 из 123 Алгоритм Якоби. Последовательная версия /* Jacobi program */ #include #define L 1000 #define ITMAX 100 int i,j,it; double A[L][L]; double B[L][L]; int main(int an, char **as) { printf("JAC STARTED\n"); for(i=0;i

19 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 19 из 123 Алгоритм Якоби. Последовательная версия /****** iteration loop *************************/ for(it=1; it

20 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 20 из 123 Алгоритм Якоби. MPI-версия

21 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 21 из 123 Алгоритм Якоби. MPI-версия /* Jacobi-1d program */ #include #include "mpi.h" #define m_printf if (myrank==0)printf #define L 1000 #define ITMAX 100 int i,j,it,k; int ll,shift; double (* A)[L]; double (* B)[L];

22 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 22 из 123 Алгоритм Якоби. MPI-версия int main(int argc, char **argv) { MPI_Request req[4]; int myrank, ranksize; int startrow,lastrow,nrow; MPI_Status status[4]; double t1, t2, time; MPI_Init (&argc, &argv); /* initialize MPI system */ MPI_Comm_rank(MPI_COMM_WORLD, &myrank);/*my place in MPI system*/ MPI_Comm_size (MPI_COMM_WORLD, &ranksize); /* size of MPI system */ MPI_Barrier(MPI_COMM_WORLD); /* rows of matrix I have to process */ startrow = (myrank *L) / ranksize; lastrow = (((myrank + 1) * L) / ranksize)-1; nrow = lastrow - startrow + 1; m_printf("JAC1 STARTED\n");

23 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 23 из 123 Алгоритм Якоби. MPI-версия /* dynamically allocate data structures */ A = malloc ((nrow+2) * L * sizeof(double)); B = malloc ((nrow) * L * sizeof(double)); for(i=1; i

24 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 24 из 123 Алгоритм Якоби. MPI-версия /****** iteration loop *************************/ t1=MPI_Wtime(); for(it=1; it

25 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 25 из 123 Алгоритм Якоби. MPI-версия if(myrank!=0) MPI_Irecv(&A[0][0],L,MPI_DOUBLE, myrank-1, 1235,MPI_Irecv MPI_COMM_WORLD, &req[0]); if(myrank!=ranksize-1) MPI_Isend(&A[nrow][0],L,MPI_DOUBLE, myrank+1, 1235,MPI_Isend MPI_COMM_WORLD,&req[2]); if(myrank!=ranksize-1) MPI_Irecv(&A[nrow+1][0],L,MPI_DOUBLE, myrank+1, 1236, MPI_COMM_WORLD, &req[3]); if(myrank!=0) MPI_Isend(&A[1][0],L,MPI_DOUBLE, myrank-1, 1236, MPI_COMM_WORLD,&req[1]); ll=4; shift=0; if (myrank==0) {ll=2;shift=2;} if (myrank==ranksize-1) {ll=2;} MPI_Waitall(ll,&req[shift],&status[0]);

26 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 26 из 123 Алгоритм Якоби. MPI-версия for(i=1; i

27 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 27 из 123 Алгоритм Якоби. MPI-версия

28 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 28 из 123 Алгоритм Якоби. MPI-версия /*Jacobi-2d program */ #include #include "mpi.h" #define m_printf if (myrank==0)printf #define L 1000 #define LC 2 #define ITMAX 100 int i,j,it,k; double (* A)[L/LC+2]; double (* B)[L/LC];

29 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 29 из 123 Алгоритм Якоби. MPI-версия int main(int argc, char **argv) { MPI_Request req[8]; int myrank, ranksize; int srow,lrow,nrow,scol,lcol,ncol; MPI_Status status[8]; double t1; int isper[] = {0,0}; int dim[2]; int coords[2]; MPI_Comm newcomm; MPI_Datatype vectype; int pleft,pright, pdown,pup; MPI_Init (&argc, &argv); /* initialize MPI system */ MPI_Comm_size (MPI_COMM_WORLD, &ranksize); /* size of MPI system */ MPI_Comm_rank (MPI_COMM_WORLD, &myrank); /* my place in MPI system */

30 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 30 из 123 Алгоритм Якоби. MPI-версия dim[0]=ranksize/LC; dim[1]=LC; if ((L%dim[0])||(L%dim[1])) { m_printf("ERROR: array[%d*%d] is not distributed on %d*%d processors\n",L,L,dim[0],dim[1]); MPI_Finalize(); exit(1); } MPI_Cart_create(MPI_COMM_WORLD,2,dim,isper,1,&newcomm); MPI_Cart_shift(newcomm,0,1,&pup,&pdown); MPI_Cart_shift(newcomm,1,1,&pleft,&pright); MPI_Comm_rank (newcomm, &myrank); /* my place in MPI system */ MPI_Cart_coords(newcomm,myrank,2,coords);

31 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 31 из 123 Алгоритм Якоби. MPI-версия /* rows of matrix I have to process */ srow = (coords[0] * L) / dim[0]; lrow = (((coords[0] + 1) * L) / dim[0])-1; nrow = lrow - srow + 1; /* columns of matrix I have to process */ scol = (coords[1] * L) / dim[1]; lcol = (((coords[1] + 1) * L) / dim[1])-1; ncol = lcol - scol + 1; MPI_Type_vector(nrow,1,ncol+2,MPI_DOUBLE,&vectype); MPI_Type_commit(&vectype); m_printf("JAC2 STARTED on %d*%d processors with %d*%d array, it=%d\n",dim[0],dim[1],L,L,ITMAX); /* dynamically allocate data structures */ A = malloc ((nrow+2) * (ncol+2) * sizeof(double)); B = malloc (nrow * ncol * sizeof(double));

32 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 32 из 123 Алгоритм Якоби. MPI-версия for(i=0; i

33 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 33 из 123 Алгоритм Якоби. MPI-версия MPI_Irecv(&A[0][1],ncol,MPI_DOUBLE, pup, 1235, MPI_COMM_WORLD, &req[0]); MPI_Isend(&A[nrow][1],ncol,MPI_DOUBLE, pdown, 1235, MPI_COMM_WORLD,&req[1]); MPI_Irecv(&A[nrow+1][1],ncol,MPI_DOUBLE, pdown, 1236, MPI_COMM_WORLD, &req[2]); MPI_Isend(&A[1][1],ncol,MPI_DOUBLE, pup, 1236, MPI_COMM_WORLD,&req[3]); MPI_Irecv(&A[1][0],1,vectype, pleft, 1237, MPI_COMM_WORLD, &req[4]); MPI_Isend(&A[1][ncol],1,vectype, pright, 1237, MPI_COMM_WORLD,&req[5]); MPI_Irecv(&A[1][ncol+1],1,vectype, pright, 1238, MPI_COMM_WORLD, &req[6]); MPI_Isend(&A[1][1],1,vectype, pleft, 1238, MPI_COMM_WORLD,&req[7]); MPI_Waitall(8,req,status);

34 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 34 из 123 Алгоритм Якоби. MPI-версия for(i=1; i

35 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 35 из 123 Алгоритм Якоби. MPI-версия for(i=1; i

36 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 36 из 123 Алгоритм Якоби. MPI/OpenMP-версия /* Jacobi-1d program */ #include #include "mpi.h" #define m_printf if (myrank==0)printf #define L 1000 #define ITMAX 100 int i,j,it,k; int ll,shift; double (* A)[L]; double (* B)[L];

37 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 37 из 123 Алгоритм Якоби. MPI/OpenMP-версия int main(int argc, char **argv) { MPI_Request req[4]; int myrank, ranksize; int startrow,lastrow,nrow; MPI_Status status[4]; double t1, t2, time; MPI_Init (&argc, &argv); /* initialize MPI system */ MPI_Comm_rank(MPI_COMM_WORLD,&myrank); /*my place in MPI system */ MPI_Comm_size (MPI_COMM_WORLD, &ranksize); /* size of MPI system */ MPI_Barrier(MPI_COMM_WORLD); /* rows of matrix I have to process */ startrow = (myrank * N) / ranksize; lastrow = (((myrank + 1) * N) / ranksize)-1; nrow = lastrow - startrow + 1; m_printf("JAC1 STARTED\n");

38 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 38 из 123 Алгоритм Якоби. MPI/OpenMP-версия /* dynamically allocate data structures */ A = malloc ((nrow+2) * N * sizeof(double)); B = malloc ((nrow) * N * sizeof(double)); for(i=1; i

39 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 39 из 123 Алгоритм Якоби. MPI/OpenMP-версия /****** iteration loop *************************/ t1=MPI_Wtime(); for(it=1; it

40 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 40 из 123 Алгоритм Якоби. MPI/OpenMP-версия if(myrank!=0) MPI_Irecv(&A[0][0],L,MPI_DOUBLE, myrank-1, 1235, MPI_COMM_WORLD, &req[0]); if(myrank!=ranksize-1) MPI_Isend(&A[nrow][0],L,MPI_DOUBLE, myrank+1, 1235, MPI_COMM_WORLD,&req[2]); if(myrank!=ranksize-1) MPI_Irecv(&A[nrow+1][0],L,MPI_DOUBLE, myrank+1, 1236, MPI_COMM_WORLD, &req[3]); if(myrank!=0) MPI_Isend(&A[1][0],L,MPI_DOUBLE, myrank-1, 1236, MPI_COMM_WORLD,&req[1]); ll=4; shift=0; if (myrank==0) {ll=2;shift=2;} if (myrank==ranksize-1) {ll=2;} MPI_Waitall(ll,&req[shift],&status[0]);

41 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 41 из 123 Алгоритм Якоби. MPI/OpenMP-версия for(i=1; i

42 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 42 из 123 Алгоритм Якоби. Оптимизированная MPI/OpenMP-версия /****** iteration loop *************************/ t1=MPI_Wtime(); #pragma omp parallel default(none) private(it,i,j) shared (A,B,myrank, nrow,ranksize,ll,shift,req,status) for(it=1; it

43 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 43 из 123 Алгоритм Якоби. Оптимизированная MPI/OpenMP-версия #pragma omp barrier #pragma omp single { if(myrank!=0) MPI_Irecv(&A[0][0],L,MPI_DOUBLE, myrank-1, 1235, MPI_COMM_WORLD, &req[0]); if(myrank!=ranksize-1) MPI_Isend(&A[nrow][0],L,MPI_DOUBLE, myrank+1, 1235, MPI_COMM_WORLD,&req[2]); if(myrank!=ranksize-1) MPI_Irecv(&A[nrow+1][0],L,MPI_DOUBLE, myrank+1, 1236, MPI_COMM_WORLD, &req[3]); if(myrank!=0) MPI_Isend(&A[1][0],L,MPI_DOUBLE, myrank-1, 1236, MPI_COMM_WORLD,&req[1]); ll=4; shift=0; if (myrank==0) {ll=2;shift=2;} if (myrank==ranksize-1) {ll=2;} MPI_Waitall(ll,&req[shift],&status[0]); }

44 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 44 из 123 Алгоритм Якоби. Оптимизированная MPI/OpenMP-версия for(i=1; i

45 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 45 из 123 Тесты NASA MultiZone BT (Block Tridiagonal Solver)3D Навье-Стокс, метод переменных направлений LU (Lower-Upper Solver) 3D Навье-Стокс, метод верхней релаксации SP(Scalar PentadiagonalSolver)3D Навье-Стокс, Beam- Warning approximate factorization

46 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 46 из 123 Тесты NASA MultiZone

47 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 47 из 123 Тест SP-MZ (класс A) на IBM eServer pSeries 690 Regatta

48 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 48 из 123 Тест LU-MZ (класс A) на IBM eServer pSeries 690 Regatta

49 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 49 из 123 Тест BT-MZ (класс A) на IBM eServer pSeries 690 Regatta зоны от 13 x 13 x 16 и до 58 x 58 x 16

50 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 50 из 123 Расчет дозвукового обтекания летательного аппарата Задача 810 областей средняя загрузка Max загрузка 75 процессоров процессоров процессоров процессоров процессоров

51 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 51 из 123 Ликвидация или сокращение дублирования данных в памяти узла. Дополнительный уровень параллелизма на OpenMP реализовать проще, чем на MPI (например, когда в программе есть два уровня параллелизма – параллелизм между подзадачами и параллелизм внутри подзадачи). Улучшение балансировки на многоблочных задачах при меньшей трудоемкости реализации еще одного уровня параллелизма. Преимущества гибридной модели MPI/OpenMP

52 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 52 из 123 Содержание Современные направления развития параллельных вычислительных систем Гибридная модель MPI/OpenMP Гибридная модель DVM/OpenMP OpenMP – модель параллелизма по управлению

53 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 53 из 123 Гибридная модель DVM/OpenMP Данные Core Данные Вычисления Core … Узел 0 OpenMP Core Данные Вычисления Core … Узел N OpenMP DVM

54 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 54 из 123 DVM/OpenMP – гибридная модель программирования высокого уровня В модели DVM/OpenMP можно описать следующие уровни параллелизма программы: Параллелизм распределенных задач, позволяющий отобразить параллельно выполняющиеся задачи на непересекающиеся многомерные секции узлов. Параллелизм распределенных многомерных циклов, витки которых распределяются между узлами многомерной секции. Параллелизм конструкций разделения работы OpenMP (циклы и секции). Эти конструкции могут быть в произвольном порядке вложены друг в друга.

55 В.Бахтин Гибридные модели MPI/OpenMP и DVM/OpenMP 55 из 123 PROGRAM JAC_SERIAL PARAMETER (L=8, ITMAX=20) REAL A(L,L), B(L,L) PRINT *, '********** TEST_JACOBI **********' DO IT = 1, ITMAX DO J = 2, L-1 DO I = 2, L-1 A(I, J) = B(I, J) ENDDO DO J = 2, L-1 DO I = 2, L-1 B(I, J) = (A(I-1, J) + A(I, J-1) + A(I+1, J) + + A(I, J+1)) / 4 ENDDO END Алгоритм Якоби. Последовательная версия

56 PROGRAM JAC_DVM PARAMETER (L=8, ITMAX=20) REAL A(L,L), B(L,L) CDVM$ DISTRIBUTE ( BLOCK, BLOCK) :: A CDVM$ ALIGN B(I,J) WITH A(I,J) PRINT *, '********** TEST_JACOBI **********' DO IT = 1, ITMAX CDVM$ PARALLEL (J,I) ON A(I, J) DO J = 2, L-1 DO I = 2, L-1 A(I, J) = B(I, J) ENDDO CDVM$ PARALLEL (J,I) ON B(I, J), SHADOW_RENEW (A) DO J = 2, L-1 DO I = 2, L-1 B(I, J) = (A(I-1, J) + A(I, J-1) + A(I+1, J) + + A(I, J+1)) / 4 ENDDO END

57 В.Бахтин Гибридные модели MPI/OpenMP и DVM/OpenMP 57 из 123

58 PROGRAM JAC_OpenMP_DVM PARAMETER (L=8, ITMAX=20) REAL A(L,L), B(L,L) CDVM$ DISTRIBUTE ( BLOCK, BLOCK) :: A CDVM$ ALIGN B(I,J) WITH A(I,J) PRINT *, '********** TEST_JACOBI **********' C$OMP PARALLEL SHARED(A,B) DO IT = 1, ITMAX CDVM$ PARALLEL (J,I) ON A(I, J) DO J = 2, L-1 C$OMP DO DO I = 2, L-1 A(I, J) = B(I, J) ENDDO C$OMP ENDDO NOWAIT ENDDO C$OMP BARRIER CDVM$ PARALLEL (J,I) ON B(I, J), SHADOW_RENEW (A) DO J = 2, L-1 C$OMP DO DO I = 2, L-1 B(I, J) = (A(I-1, J) + A(I, J-1) + A(I+1, J) + A(I, J+1)) / 4 ENDDO C$OMP ENDDO NOWAIT ENDDO C$OMP END PARALLEL END

59 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 59 из 123 Fortran DVM/OpenMP программа Fortran DVM/OpenMP компилятор Fortran DVM компилятор Fortran + обращения к LibDVM (MPI) Fortran OpenMP + обращения к LibDVM (MPI) Штатный Fortran компилятор Компиляция DVM/OpenMP-программ

60 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 60 из 123 Тесты NASA MultiZone BT (Block Tridiagonal Solver)3D Навье-Стокс, метод переменных направлений LU (Lower-Upper Solver) 3D Навье-Стокс, метод верхней релаксации SP(Scalar PentadiagonalSolver)3D Навье-Стокс, Beam- Warning approximate factorization

61 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 61 из 123 Тест SP-MZ (класс A) на IBM eServer pSeries 690 Regatta DVMMPI

62 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 62 из 123 Тест LU-MZ (класс A) на IBM eServer pSeries 690 Regatta DVMMPI

63 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 63 из 123 Тест BT-MZ (класс A) на IBM eServer pSeries 690 Regatta зоны от 13 x 13 x 16 и до 58 x 58 x 16 DVMMPI

64 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 64 из 123 Расчет солнечной конвекции При запуске DVM- программы на 225 процессорах используются 4 ядра (по памяти). DVM/OpenMP- программа позволяет использовать все ресурсы на узле. 1000x1000x проц (57 узлов) проц x 2 нити (57 узлов) проц x 8 нитей (57 узлов) МВС-100K (МСЦ РАН) В задаче используется около 50 массивов размерности NX=1000, NY=1000, NZ=168; порядка 60-ти циклов, в 12-ти из которых, есть регулярная зависимость по данным.

65 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 65 из 123 Преимущества DVM/OpenMP Близость моделей OpenMP и DVM, что упрощает их совместное использование. Получение гибких программ, способных настраиваться на неоднородность узлов SMP-кластера. Возможность использования параллельной программы как последовательной, как OpenMP-программы, как DVM- программы, и как DVM/OpenMP -программы.

66 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 66 из 123 Содержание Современные направления развития параллельных вычислительных систем Гибридная модель MPI/OpenMP Гибридная модель DVM/OpenMP OpenMP – модель параллелизма по управлению

67 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 67 из 123 История OpenMP OpenMP Fortran 1.1 OpenMP C/C OpenMP Fortran 2.0 OpenMP Fortran 2.0 OpenMP C/C OpenMP C/C OpenMP Fortran OpenMP F/C/C OpenMP F/C/C OpenMP F/C/C OpenMP F/C/C

68 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 68 из 123 OpenMP Architecture Review Board AMD Cray Fujitsu HP IBM Intel NEC The Portland Group, Inc. SGI Sun Microsoft ASC/LLNL cOMPunity EPCC NASA RWTH Aachen University

69 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 69 из 123 Компиляторы, поддеживающие OpenMP OpenMP 3.0: Intel 11.0: Linux, Windows and MacOS Sun Studio Express 11/08: Linux and Solaris PGI 8.0: Linux and Windows IBM 10.1: Linux and AIX GNU gcc (4.4.0) Предыдущие версии OpenMP: Absoft Pro FortranMP Lahey/Fujitsu Fortran 95 PathScale HP Microsoft Visual Studio 2008 C++

70 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 70 из 123 Обзор основных возможностей OpenMP omp_set_lock(lck) #pragma omp parallel for private(a, b) #pragma omp critical C$OMP PARALLEL DO SHARED(A,B,C) C$OMP PARALLEL REDUCTION (+: A, B) CALL OMP_INIT_LOCK (LCK) CALL OMP_TEST_LOCK(LCK) SETENV OMP_SCHEDULE STATIC,4 CALL CALL OMP_SET_NUM_THREADS(10) C$OMP DO LASTPRIVATE(XX) C$OMP ORDERED C$OMP SINGLE PRIVATE(X) C$OMP SECTIONS C$OMP MASTER C$OMP ATOMIC C$OMP FLUSH C$OMP PARALLEL DO ORDERED PRIVATE (A, B, C) C$OMP THREADPRIVATE(/ABC/) C$OMP PARALLEL COPYIN(/blk/) nthrds = OMP_GET_NUM_PROCS() C$OMP BARRIER

71 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 71 из 123 Директивы и клаузы Спецификации параллелизма в OpenMP представляют собой директивы вида: #pragma omp название-директивы[ клауза[ [,]клауза]...] Например: #pragma omp parallel default (none) shared (i,j) Исполняемые директивы: barrier taskwait flush Описательная директива: threadprivate

72 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 72 из 123 Структурный блок Действие остальных директив распространяется на структурный блок: #pragma omp название-директивы[ клауза[ [,]клауза]...] { структурный блок } Структурный блок: блок кода с одной точкой входа и одной точкой выхода. #pragma omp parallel { … mainloop: res[id] = f (id); if (res[id] != 0) goto mainloop; … exit (0); } Структурный блок #pragma omp parallel { … mainloop: res[id] = f (id); … } if (res[id] != 0) goto mainloop; Не структурный блок

73 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 73 из 123 Выполнение OpenMP-программы Fork-Join параллелизм: Главная (master) нить порождает группу (team) нитей по мере небходимости. Параллелизм добавляется инкрементально. Параллельные области

74 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 74 из 123 Параллельная область (директива PARALLEL) #pragma omp parallel [ клауза[ [, ] клауза]...] структурный блок где клауза одна из : default(shared | none) private(list) firstprivate(list) shared(list) reduction(operator: list) if(scalar-expression) num_threads(integer-expression) copyin(list)

75 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 75 из Модель памяти в OpenMP Нить 001 Нить 001 Нить

76 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 76 из Нить Нить 1 static int i = 0; … = i + 1; i = i + 1; i = 0 i = 1 … = i + 2; // ? #pragma omp flush (i) i = 1 Модель памяти в OpenMP

77 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 77 из 123 Консистентность памяти в OpenMP Корректная последовательность работы нитей с переменной: Нить0 записывает значение переменной - write(var) Нить0 выполняет операцию синхронизации – flush (var) Нить1 выполняет операцию синхронизации – flush (var) Нить1 читает значение переменной – read (var) Директива flush: #pragma omp flush [(list)] - для Си !$omp flush [(list)] - для Фортран

78 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 78 из 123 Консистентность памяти в OpenMP 1.Если пересечение множеств переменных, указанных в операциях flush, выполняемых различными нитями не пустое, то результат выполнения операций flush будет таким, как если бы эти операции выполнялись в некоторой последовательности (единой для всех нитей). 2.Если пересечение множеств переменных, указанных в операциях flush, выполняемых одной нитью не пустое, то результат выполнения операций flush, будет таким, как если бы эти операции выполнялись в порядке, определяемом программой. 3.Если пересечение множеств переменных, указанных в операциях flush, пустое, то операции flush могут выполняться независимо (в любом порядке).

79 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 79 из 123 Классы переменных В модели программирования с разделяемой памятью: Большинство переменных по умолчанию считаются SHARED Глобальные переменные совместно используются всеми нитями (shared) : Фортран: COMMON блоки, SAVE переменные, MODULE переменные Си: file scope, static Динамически выделяемая память (ALLOCATE, malloc, new) Но не все переменные являются разделяемыми... Стековые переменные в подпрограммах (функциях), вызываемых из параллельного региона, являются PRIVATE. Переменные, объявленные внутри блока операторов параллельного региона, являются приватными. Счетчики циклов, витки которых распределяются между нитями при помощи конструкций for и parallel for.

80 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 80 из 123 double Array1[100]; int main() { int Array2[100]; #pragma omp parallel work(Array2); printf(%d\n, Array2[0]); } extern double Array1[10]; void work(int *Array) { double TempArray[10]; static int count;... } TempArray Array1, Array2, count Модель памяти в OpenMP

81 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 81 из 123 Можно изменить класс переменной при помощи конструкций: SHARED (список переменных) PRIVATE (список переменных) FIRSTPRIVATE (список переменных) LASTPRIVATE (список переменных) THREADPRIVATE (список переменных) DEFAULT (PRIVATE | SHARED | NONE) Классы переменных

82 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 82 из 123 Конструкция PRIVATE Конструкция «private(var)» создает локальную копию переменной «var» в каждой из нитей. Значение переменной не инициализировано Приватная копия не связана с оригинальной переменной В OpenMP 2.5 значение переменной «var» не определено после завершения параллельной конструкции void wrong() { int tmp = 0; #pragma omp for private(tmp) for (int j = 0; j < 1000; ++j) tmp += j; printf(%d\n, tmp); } tmp не инициализирована tmp: 0 в 3.0, не определено в 2.5

83 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 83 из 123 Конструкция FIRSTPRIVATE «Firstprivate» является специальным случаем «private». Инициализирует каждую приватную копию соответствующим значением из главной (master) нити. void wrong() { int tmp = 0; #pragma omp for firstprivate(tmp) for (int j = 0; j < 1000; ++j) tmp += j; printf(%d\n, tmp); } tmp инициализирована 0 tmp: 0 в 3.0, не определено в 2.5

84 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 84 из 123 Конструкция LASTPRIVATE Lastprivate передает значение приватной переменной, посчитанной на последней итерации в глобальную переменную. void almost_right () { int tmp = 0; #pragma omp for firstprivate(tmp) lastprivate (tmp) for (int j = 0; j < 1000; ++j) tmp += j; printf(%d\n, tmp); } tmp инициализирована 0 переменная tmp получит значение, посчитанное на последней итерации (j=999)

85 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 85 из 123 Директива THREADPRIVATE Отличается от применения конструкции PRIVATE: PRIVATE скрывает глобальные переменные THREADPRIVATE – переменные сохраняют глобальную область видимости внутри каждой нити #pragma omp threadprivate (Var) Var = 1 Var = 2 … = Var Если количество нитей не изменилось, то каждая нить получит значение, посчитанное в предыдущей параллельной области.

86 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 86 из 123 Конструкция DEFAULT Меняет класс переменной по умолчанию: DEFAULT (SHARED) – действует по умолчанию DEFAULT (PRIVATE) – есть только в Fortran DEFAULT (NONE) – требует определить класс для каждой переменной itotal = 100 #pragma omp parallel private(np,each) { np = omp_get_num_threads() each = itotal/np ……… } itotal = 100 #pragma omp parallel default(none) private(np,each) shared (itotal) { np = omp_get_num_threads() each = itotal/np ……… }

87 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 87 из 123 Параллельная область (директива PARALLEL) #pragma omp parallel [ клауза[ [, ] клауза]...] структурный блок где клауза одна из : default(shared | none) private(list) firstprivate(list) shared(list) reduction(operator: list) if(scalar-expression) num_threads(integer-expression) copyin(list)

88 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 88 из 123 Вычисление числа 4.0 (1+x 2 ) dx = 0 1 F(x i ) x i = 0 N Мы можем аппроксимировать интеграл как сумму прямоугольников: Где каждый прямоугольник имеет ширину x и высоту F(x i ) в середине интервала F(x) = 4.0/(1+x 2 ) X 0.0

89 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 89 из 123 #include int main () { int n =100000, i; double pi, h, sum, x; h = 1.0 / (double) n; sum = 0.0; for (i = 1; i

90 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 90 из 123 #include #define NUM_THREADS 32 int main () { int n =100000, i; double pi, h, sum[NUM_THREADS], x; h = 1.0 / (double) n; #pragma omp parallel default (none) private (i,x) shared (n,h,sum) { int id = omp_get_thread_num(); int numt = omp_get_num_threads(); for (i = id + 1, sum[id] = 0.0; i

91 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 91 из 123 #include int main () { int n =100000, i; double pi, h, sum, x; h = 1.0 / (double) n; sum = 0.0; #pragma omp parallel default (none) private (i,x) shared (n,h) reduction(+:sum) { int id = omp_get_thread_num(); int numt = omp_get_num_threads(); for (i = id + 1; i

92 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 92 из 123 Клауза reduction reduction(operator:list) Внутри паралельной области для каждой переменной из списка list создается копия этой переменной. Эта переменная инициализируется в соответствии с оператором operator (например, 0 для «+»). Для каждой нити компилятор заменяет в параллельной области обращения к редукционной переменной на обращения к созданной копии. По завершении выполнения параллельной области осуществляется объединение полученных результатов. ОператорНачальное значение +0 *1 -0 &~0 |0 ^0 &&1 ||0

93 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 93 из 123 Клауза num_threads num_threads(integer-expression) integer-expression задает максимально возможное число нитей, которые будут созданы для выполнения структурного блока #include int main() { int n = 0; printf("Enter the number of intervals: (0 quits) "); scanf("%d",&n); omp_set_dynamic(1); #pragma omp parallel num_threads(10) { int id = omp_get_thread_num (); func (n, id); } return 0; }

94 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 94 из 123 Клауза copyin copyin(list) Значение каждой threadprivate-переменной из списка list, устанавливается равным значению этой переменной в master-нити #include float* work; int size; float tol; #pragma omp threadprivate(work,size,tol) void build() { int i; work = (float*)malloc( sizeof(float)*size ); for( i = 0; i < size; ++i ) work[i] = tol; } int main() { read_from_file (&tol, &size); #pragma omp parallel copyin(tol,size) build(); }

95 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 95 из 123 Конструкции распределения работы Распределение витков циклов (директива for) Выполнение структурного блока одной нитью (директива single)

96 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 96 из 123 Вычисление числа 4.0 (1+x 2 ) dx = 0 1 F(x i ) x i = 0 N Мы можем аппроксимировать интеграл как сумму прямоугольников: Где каждый прямоугольник имеет ширину x и высоту F(x i ) в середине интервала F(x) = 4.0/(1+x 2 ) X 0.0

97 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 97 из 123 #include int main () { int n =100000, i; double pi, h, sum, x; h = 1.0 / (double) n; sum = 0.0; for (i = 1; i

98 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 98 из 123 int main () { int n =100, i; double pi, h, sum, x; h = 1.0 / (double) n; sum = 0.0; #pragma omp parallel default (none) private (i,x) shared (n,h) reduction(+:sum) { int iam = omp_get_thread_num(); int numt = omp_get_num_threads(); int start = iam * n / numt + 1; int end = (iam + 1) * n / numt; for (i = start; i

99 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 99 из 123 #include int main () { int n =100, i; double pi, h, sum, x; h = 1.0 / (double) n; sum = 0.0; #pragma omp parallel default (none) private (i,x) shared (n,h) reduction(+:sum) { #pragma omp for schedule (static) for (i = 1; i

100 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 100 из 123 Распределение витков цикла #pragma omp for [клауза[[,]клауза]... ] for (init-expr; test-expr; incr-expr) структурный блок где клауза одна из : private(list) firstprivate(list) lastprivate(list) reduction(operator: list) schedule(kind[, chunk_size]) collapse(n) ordered nowait

101 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 101 из 123 Распределение витков цикла. Клауза schedule #pragma omp parallel for schedule(static, 10) for(int i = 1; i

102 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 102 из 123 Распределение витков цикла. Клауза schedule #pragma omp parallel for schedule(dynamic, 15) for(int i = 1; i

103 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 103 из 123 Распределение витков цикла. Клауза schedule число_выполняемых_потоком_итераций = max(число_нераспределенных_итераций/omp_get_num_threads(), число_итераций) #pragma omp parallel for schedule(guided, 10) for(int i = 1; i

104 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 104 из 123 Распределение витков цикла. Клауза schedule #pragma omp parallel for schedule(runtime) for(int i = 1; i

105 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 105 из 123 Распределение витков цикла. Клауза schedule #pragma omp parallel for schedule(auto) for(int i = 1; i

106 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 106 из 123 Распределение витков цикла. Клауза nowait void example(int n, float *a, float *b, float *с, float *z) { int i; float sum = 0.0; #pragma omp parallel { #pragma omp for schedule(static) nowait reduction (+: sum) for (i=0; i

107 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 107 из 123 Выполнение структурного блока одной нитью (директива single). #pragma omp single [клауза[[,] клауза]...] структурный блок где клауза одна из : private(list) firstprivate(list) copyprivate(list) nowait Структурный блок будет выполнен одной из нитей. Все остальные нити будут дожидаться результатов выполнения блока, если не указана клауза NOWAIT. #include float x, y; #pragma omp threadprivate(x, y) void init(float a, float b ) { #pragma omp single copyprivate(a,b,x,y) scanf("%f %f %f %f", &a, &b, &x, &y); } int main () { #pragma omp parallel { float x1,y1; init (x1,y1); parallel_work (); }

108 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 108 из 123 Конструкции для синхронизации нитей Директива master Директива critical Директива barrier Директива flush

109 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 109 из 123 #pragma omp master структурный блок /*Структурный блок будет выполнен MASTER-нитью группы. По завершении выполнения структурного блока барьерная синхронизация нитей не выполняется*/ #include void init(float *a, float *b ) { #pragma omp master scanf("%f %f", a, b); #pragma omp barrier } int main () { float x,y; #pragma omp parallel { init (&x,&y); parallel_work (x,y); } Директива master

110 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 110 из 123 При взаимодействии через общую память нити должны синхронизовать свое выполнение. int i=0; #pragma omp parallel { i++; } Взаимное исключение критических интервалов Результат зависит от порядка выполнения команд. Требуется взаимное исключение критических интервалов. ВремяThread0Thread1 1load i (i = 0) 2incr i (i = 1) 3->->load i (i = 0) 4incr i (i = 1) 5store i (i = 1) 6

111 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 111 из 123 Решение проблемы взаимного исключения должно удовлетворять требованиям: в любой момент времени только одна нить может находиться внутри критического интервала; если ни одна нить не находится в критическом интервале, то любая нить, желающая войти в критический интервал, должна получить разрешение без какой либо задержки; ни одна нить не должна бесконечно долго ждать разрешения на вход в критический интервал (если ни одна нить не будет находиться внутри критического интервала бесконечно). Взаимное исключение критических интервалов

112 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 112 из 123 Вычисление числа 4.0 (1+x 2 ) dx = 0 1 F(x i ) x i = 0 N Мы можем аппроксимировать интеграл как сумму прямоугольников: Где каждый прямоугольник имеет ширину x и высоту F(x i ) в середине интервала F(x) = 4.0/(1+x 2 ) X 0.0

113 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 113 из 123 int main () { int n =100000, i; double pi, h, sum, x; h = 1.0 / (double) n; sum = 0.0; for (i = 1; i

114 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 114 из 123 #include int main () { int n =100000, i; double pi, h, sum, x; h = 1.0 / (double) n; sum = 0.0; #pragma omp parallel default (none) private (i,x) shared (n,h,sum) { double local_sum = 0.0; #pragma omp for for (i = 1; i

115 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 115 из 123 Точка в программе, достижимая всеми нитями группы, в которой выполнение программы приостанавливается до тех пор пока все нити группы не достигнут данной точки. #pragma omp barrier По умолчанию барьерная синхронизация нитей выполняется: по завершению конструкции parallel; при выходе из конструкций распределения работ (for, single, sections), если не указана клауза nowait. int size; #pragma omp parallel { #pragma omp master { scanf("%d",&size); } #pragma omp barrier process(size); } Директива barrier

116 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 116 из 123 #pragma omp flush [(список переменных)] По умолчанию все переменные приводятся в консистентное состояние (#pragma omp flush): При барьерной синхронизации При входе и выходе из конструкций parallel, critical и ordered. При выходе из конструкций распределения работ (for, single, sections, workshare), если не указана клауза nowait. При вызове omp_set_lock и omp_unset_lock. При вызове omp_test_lock, omp_set_nest_lock, omp_unset_nest_lock и omp_test_nest_lock, если изменилось состояние семафора. При входе и выходе из конструкции atomic выполняется #pragma omp flush(x), где x – переменная, изменяемая в конструкции atomic. Директива flush

117 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 117 из 123 Система поддержки выполнения OpenMP- программ. Внутренние переменные, управляющие выполнением OpenMP-программы (ICV-Internal Control Variables). Задание/опрос значений ICV-переменных. Функции работы со временем.

118 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 118 из 123 Для параллельных областей: nthreads-var thread-limit-var dyn-var nest-var max-active-levels-var Для циклов: run-sched-var def-sched-var Для всей программы: stacksize-var wait-policy-var Internal Control Variables.

119 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 119 из 123 Internal Control Variables. nthreads-var Определяет максимально возможное количество нитей в создаваемой параллельной области. Начальное значение: зависит от реализации. Значение переменной можно изменить: C shell: setenv OMP_NUM_THREADS 16 Korn shell: export OMP_NUM_THREADS=16 Windows: set OMP_NUM_THREADS=16 void omp_set_num_threads(int num_threads); Узнать значение переменной можно: int omp_get_max_threads(void);

120 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 120 из 123 Internal Control Variables. run-sched-var Задает способ распределения витков цикла между нитями, если указана клауза schedule(runtime). Начальное значение: зависит от реализации. Существует одна копия этой переменной для каждой нити. Значение переменной можно изменить: C shell: setenv OMP_SCHEDULE "guided,4" Korn shell: export OMP_SCHEDULE "dynamic,5" Windows: set OMP_SCHEDULE=static void omp_set_schedule(omp_sched_t kind, int modifier); Узнать значение переменной можно: void omp_get_schedule(omp_sched_t * kind, int * modifier ); typedef enum omp_sched_t { omp_sched_static = 1, omp_sched_dynamic = 2, omp_sched_guided = 3, omp_sched_auto = 4 } omp_sched_t;

121 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 121 из 123 int omp_get_num_threads(void); -возвращает количество нитей в текущей параллельной области #include void work(int i); void test() { int np; np = omp_get_num_threads(); /* np == 1*/ #pragma omp parallel private (np) { np = omp_get_num_threads(); #pragma omp for schedule(static) for (int i=0; i < np; i++) work(i); } Система поддержки выполнения OpenMP- программ.

122 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 122 из 123 int omp_get_thread_num(void); -возвращает номер нити в группе [0: omp_get_num_threads()-1] #include void work(int i); void test() { int iam; iam = omp_get_thread_num(); /* iam == 0*/ #pragma omp parallel private (iam) { iam = omp_get_thread_num(); work(iam); } Система поддержки выполнения OpenMP- программ.

123 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 123 из 123 int omp_get_num_procs(void); -возвращает количество процессоров, на которых программа выполняется #include void work(int i); void test() { int nproc; nproc = omp_get_num_ procs(); #pragma omp parallel num_threads(nproc) { int iam = omp_get_thread_num(); work(iam); } Система поддержки выполнения OpenMP- программ.

124 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 124 из 123 double omp_get_wtime(void); возвращает для нити астрономическое время в секундах, прошедшее с некоторого момента в прошлом. Если некоторый участок окружить вызовами данной функции, то разность возвращаемых значений покажет время работы данного участка. Гарантируется, что момент времени, используемый в качестве точки отсчета, не будет изменен за время выполнения программы. double start; double end; start = omp_get_wtime(); /*... work to be timed...*/ end = omp_get_wtime(); printf("Work took %f seconds\n", end - start); double omp_get_wtick(void); - возвращает разрешение таймера в секундах (количество секунд между последовательными импульсами таймера). Система поддержки выполнения OpenMP-программ. Функции работы со временем

125 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 125 из 123 Материалы по курсу Презентация доступна: ftp://ftp.keldysh.ru/K_student/MSU2010/MSU2010_MPI_OpenMP.pdf

126 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 126 из 123 Литература OpenMP Application Program Interface Version 3.0, May MPI: A Message-Passing Interface Standard Version 2.2, September Антонов А.С. Параллельное программирование с использованием технологии OpenMP: Учебное пособие.-М.: Изд-во МГУ, Антонов А.С. Параллельное программирование с использованием технологии MPI: Учебное пособие.-М.: Изд-во МГУ, Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. – СПб.: БХВ-Петербург, Э. Таненбаум, М. ван Стеен. Распределенные системы. Принципы и парадигмы. – СПб. Питер, 2003

127 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 127 из 123 Автор Бахтин Владимир Александрович, кандидат физико-математических наук, заведующий сектором Института прикладной математики им. М.В. Келдыша РАН,

128 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 128 из 123 Инициализация и завершение MPI программ Первой вызываемой функцией MPI должна быть функция: int MPI_Init ( int *agrc, char ***argv ) Для инициализации среды выполнения MPI-программы. Параметрами функции являются количество аргументов в командной строке и текст самой командной строки. Последней вызываемой функцией MPI обязательно должна являться функция: int MPI_Finalize (void) Обратно

129 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 129 из 123 Определение количества и ранга процессов Определение количества процессов в выполняемой параллельной программе осуществляется при помощи функции: int MPI_Comm_size ( MPI_Comm comm, int *size ). Для определения ранга процесса используется функция: int MPI_Comm_rank ( MPI_Comm comm, int *rank ). Обратно

130 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 130 из 123 Неблокирующие обмены данными между процессорами Для передачи сообщения процесс-отправитель должен выполнить функцию: int MPI_Isend(void *buf, int count, MPI_Datatype type, int dest, int tag, MPI_Comm comm, MPI_Request *request), где buf - адрес буфера памяти, в котором располагаются данные отправляемого сообщения, count - количество элементов данных в сообщении, type - тип элементов данных пересылаемого сообщения, dest - ранг процесса, которому отправляется сообщение, tag - значение-тег, используемое для идентификации сообщений, comm - коммуникатор, в рамках которого выполняется передача данных. Для приема сообщения процесс-получатель должен выполнить функцию: int MPI_Irecv(void *buf, int count, MPI_Datatype type, int source, int tag, MPI_Comm comm, MPI_Status *status, MPI_Request *request), где buf, count, type - буфер памяти для приема сообщения, назначение каждого отдельного параметра соответствует описанию в MPI_Send, source - ранг процесса, от которого должен быть выполнен прием сообщения, tag - тег сообщения, которое должно быть принято для процесса, comm - коммуникатор, в рамках которого выполняется передача данных, status - указатель на структуру данных с информацией о результате выполнения операции приема данных. Обратно

131 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 131 из 123 MPI_Waitall Ожидание завершения всех операций обмена осуществляется при помощи функции: int MPI_Waitall( int count, MPI_Request array_of_requests[], MPI_Status array_of_statuses[]) Обратно

132 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 132 из 123 MPI_Cart_create Создание декартовой топологии (решетки) в MPI: int MPI_Cart_create(MPI_Comm oldcomm, int ndims, int *dims, int *periods, int reorder, MPI_Comm *cartcomm), где: oldcomm - исходный коммуникатор, ndims - размерность декартовой решетки, dims - массив длины ndims, задает количество процессов в каждом измерении решетки, periods - массив длины ndims, определяет, является ли решетка периодической вдоль каждого измерения, reorder - параметр допустимости изменения нумерации процессов, cartcomm - создаваемый коммуникатор с декартовой топологией процессов. Обратно

133 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 133 из 123 MPI_Cart_shift Функция: int MPI_Card_shift(MPI_Comm comm, int dir, int disp, int *source, int *dst) для получения номеров посылающего(source) и принимающего (dst) процессов в декартовой топологии коммуникатора (comm) для осуществления сдвига вдоль измерения dir на величину disp. Обратно

134 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 134 из 123 MPI_Card_coords Определение декартовых координат процесса по его рангу: int MPI_Card_coords(MPI_Comm comm,int rank,int ndims,int *coords), где: comm - коммуникатор с топологией решетки, rank - ранг процесса, для которого определяются декартовы координаты, ndims - размерность решетки, coords - возвращаемые функцией декартовы координаты процесса. Обратно

135 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 135 из 123 MPI_Type_vector Для снижения сложности в MPI предусмотрено несколько различных способов конструирования производных типов: Непрерывный способ позволяет определить непрерывный набор элементов существующего типа как новый производный тип, Векторный способ обеспечивает создание нового производного типа как набора элементов существующего типа, между элементами которого существуют регулярные промежутки по памяти. При этом, размер промежутков задается в числе элементов исходного типа, Индексный способ отличается от векторного метода тем, что промежутки между элементами исходного типа могут иметь нерегулярный характер, Структурный способ обеспечивает самое общее описание производного типа через явное указание карты создаваемого типа данных. int MPI_Type_vector(int count, int blocklen, int stride, MPI_Data_type oldtype, MPI_Datatype *newtype), где count - количество блоков, blocklen - размер каждого блока, stride - количество элементов, расположенных между двумя соседними блоками oldtype - исходный тип данных, newtype - новый определяемый тип данных. Обратно

136 9 марта Москва, 2010 Гибридные модели MPI/OpenMP и DVM/OpenMP 136 из 123 MPI_Type_commit Перед использованием производный тип должен быть объявлен при помощи функции: int MPI_Type_commit (MPI_Datatype *type ) При завершении использования производный тип должен быть аннулирован при помощи функции: int MPI_Type_free (MPI_Datatype *type ). Обратно