лекции (OpenMP), страница 6

Клаузаcollapse (OpenMP 3.0)void work(int i, int j) {}void good_collapsing(int n){int i, j;#pragma omp parallel default(shared){#pragma omp for collapse (2)for (i=0; i<n; i++) {for (j=0; j < n; j++)work(i, j);}}}Клауза collapse:collapse (положительная целая константа)Москва, 2015 г.Параллельное программирование с OpenMP: Конструкциираспределения работы © Бахтин В.А.15 из 42Распределение витков многомерных циклов.

Клаузаcollapse (OpenMP 3.0)void work(int i, int j) {}void error_collapsing(int n){int i, j;#pragma omp parallel default(shared){#pragma omp for collapse (2)for (i=0; i<n; i++) {work_with_i (i);// Ошибкаfor (j=0; j < n; j++)work(i, j);}}}Клауза collapse может быть использована только для распределениявитков тесно-вложенных циклов.Москва, 2015 г.Параллельное программирование с OpenMP: Конструкциираспределения работы © Бахтин В.А.16 из 42Распределение витков многомерных циклов.

Клаузаcollapse (OpenMP 3.0)void work(int i, int j) {}void error_collapsing(int n){int i, j;#pragma omp parallel default(shared){#pragma omp for collapse (2)for (i=0; i<n; i++) {for (j=0; j < i; j++)// Ошибкаwork(i, j);}}}Клауза collapse может быть использована только для распределениявитков циклов с прямоугольным индексным пространством.Москва, 2015 г.Параллельное программирование с OpenMP: Конструкциираспределения работы © Бахтин В.А.17 из 42Распределение витков цикла. Клауза scheduleКлауза schedule:schedule(алгоритм планирования[, число_итераций])Где алгоритм планирования один из: schedule(static[, число_итераций]) - статическое планирование; schedule(dynamic[, число_итераций]) - динамическое планирование; schedule(guided[, число_итераций]) - управляемое планирование; schedule(runtime) - планирование в период выполнения; schedule(auto) - автоматическое планирование (OpenMP 3.0).#pragma omp parallel for private(tmp) shared (a) schedule (runtime)for (int i=0; i<N-2; i++)for (int j = i+1; j< N-1; j++) {tmp = a[i][j];a[i][j]=a[j][i];a[j][i]=tmp;}Москва, 2015 г.Параллельное программирование с OpenMP: Конструкциираспределения работы © Бахтин В.А.18 из 42Распределение витков цикла.

Клауза schedule#pragma omp parallel for schedule(static)for(int i = 1; i <= 100; i++)Результат выполнения программы на 4-х ядерном процессоре будетследующим: Поток 0 получает право на выполнение итераций 1-25. Поток 1 получает право на выполнение итераций 26-50. Поток 2 получает право на выполнение итераций 51-75. Поток 3 получает право на выполнение итераций 76-100.Москва, 2015 г.Параллельное программирование с OpenMP: Конструкциираспределения работы © Бахтин В.А.19 из 42Распределение витков цикла. Клауза schedule#pragma omp parallel for schedule(static, 10)for(int i = 1; i <= 100; i++)Результат выполнения программы на 4-х ядерном процессоре будетследующим: Поток 0 получает право на выполнение итераций 1-10, 41-50, 81-90. Поток 1 получает право на выполнение итераций 11-20, 51-60, 91-100. Поток 2 получает право на выполнение итераций 21-30, 61-70. Поток 3 получает право на выполнение итераций 31-40, 71-80.Москва, 2015 г.Параллельное программирование с OpenMP: Конструкциираспределения работы © Бахтин В.А.20 из 42Распределение витков цикла.

Клауза schedule#pragma omp parallel for schedule(dynamic, 15)for(int i = 0; i < 100; i++)Результат выполнения программы на 4-х ядерном процессоре можетбыть следующим:Поток 0 получает право на выполнение итераций 1-15.Поток 1 получает право на выполнение итераций 16-30.Поток 2 получает право на выполнение итераций 31-45.Поток 3 получает право на выполнение итераций 46-60.Поток 3 завершает выполнение итераций.Поток 3 получает право на выполнение итераций 61-75.Поток 2 завершает выполнение итераций.Поток 2 получает право на выполнение итераций 76-90.Поток 0 завершает выполнение итераций.Поток 0 получает право на выполнение итераций 91-100.Москва, 2015 г.Параллельное программирование с OpenMP: Конструкциираспределения работы © Бахтин В.А.21 из 42Распределение витков цикла. Клауза scheduleчисло_выполняемых_потоком_итераций =max(число_нераспределенных_итераций/omp_get_num_threads(),число_итераций)#pragma omp parallel for schedule(guided, 10)for(int i = 0; i < 100; i++)Пусть программа запущена на 4-х ядерном процессоре. Поток 0 получает право на выполнение итераций 1-25. Поток 1 получает право на выполнение итераций 26-44. Поток 2 получает право на выполнение итераций 45-59. Поток 3 получает право на выполнение итераций 60-69. Поток 3 завершает выполнение итераций. Поток 3 получает право на выполнение итераций 70-79. Поток 2 завершает выполнение итераций. Поток 2 получает право на выполнение итераций 80-89. Поток 3 завершает выполнение итераций. Поток 3 получает право на выполнение итераций 90-99. Поток 1 завершает выполнение итераций. Поток 1 получает право на выполнение 99 итерации.Москва, 2015 г.Параллельное программирование с OpenMP: Конструкциираспределения работы © Бахтин В.А.22 из 42Распределение витков цикла.

Клауза schedule#pragma omp parallel for schedule(runtime)for(int i = 0; i < 100; i++) /* способ распределения витков цикла междунитями будет задан во время выполнения программы*/При помощи переменных среды: csh:setenv OMP_SCHEDULE "dynamic,4“ ksh:export OMP_SCHEDULE="static,10“ Windows:set OMP_SCHEDULE=autoили при помощи функций системы поддержки:void omp_set_schedule(omp_sched_t kind, int modifier);Москва, 2015 г.Параллельное программирование с OpenMP: Конструкциираспределения работы © Бахтин В.А.23 из 42Распределение витков цикла.

Клауза schedule#pragma omp parallel for schedule(auto)for(int i = 0; i < 100; i++)Способ распределения витков цикла между нитями определяетсяреализацией компилятора.На этапе компиляции программы или во время ее выполненияопределяется оптимальный способ распределения.Москва, 2015 г.Параллельное программирование с OpenMP: Конструкциираспределения работы © Бахтин В.А.24 из 42Распределение витков цикла. Клауза nowaitvoid example(int n, int m, float *a, float *b, float *y, float *z){int i;#pragma omp parallel{#pragma omp for nowaitfor (i=1; i<n; i++)b[i] = (a[i] + a[i-1]) / 2.0;#pragma omp for nowaitfor (i=0; i<m; i++)y[i] = sqrt(z[i]);}}Клауза nowait отменяет барьерную синхронизацию по завершениивыполнении циклаМосква, 2015 г.Параллельное программирование с OpenMP: Конструкциираспределения работы © Бахтин В.А.25 из 42Распределение витков цикла.

Клауза nowaitvoid example(int n, float *a, float *b, float *z){int i;#pragma omp parallel{#pragma omp for schedule(static) nowaitfor (i=0; i<n; i++)c[i] = (a[i] + b[i]) / 2.0;#pragma omp for schedule(static) nowaitfor (i=0; i<n; i++)z[i] = sqrt(c[i]);}}Верно, если количество итераций у циклов совпадает и параметрыклаузы schedule совпадают (STATIC + число_итераций).Москва, 2015 г.Параллельное программирование с OpenMP: Конструкциираспределения работы © Бахтин В.А.26 из 42Распределение витков цикла.

Клауза nowaitvoid example(int n, float *a, float *b, float *z){int i;float sum = 0.0;#pragma omp parallel{#pragma omp for schedule(static) nowait reduction (+: sum)for (i=0; i<n; i++) {c[i] = (a[i] + b[i]) / 2.0;sum += c[i];}#pragma omp for schedule(static) nowaitfor (i=0; i<n; i++)z[i] = sqrt(c[i]);#pragma omp barrierprintf(“sum of array is %.16f”, sum);}}Москва, 2015 г.Параллельное программирование с OpenMP: Конструкциираспределения работы © Бахтин В.А.27 из 42Распределение циклов с зависимостью по даннымfor(int i = 1; i < 100; i++)a[i]= a[i-1] + a[i+1]Между витками цикла с индексами i1 и i2 ( i1<i2 ) существуетзависимость по данным (информационная связь) массива A, если обаэти витка осуществляют обращение к одному элементу массива посхеме запись-чтение или чтение-запись.Если виток i1 записывает значение, а виток i2 читает это значение, томежду этими витками существует потоковая зависимость или простозависимость i1 -> i2.Если виток i1 читает “старое” значение, а виток i2 записывает “новое”значение, то между этими витками существует обратная зависимостьi1<- i2.В обоих случаях виток i2 может выполняться только после витка i1.Москва, 2015 г.Параллельное программирование с OpenMP: Конструкциираспределения работы © Бахтин В.А.28 из 42Распределение циклов с зависимостью по даннымfor (int i = 0; i < n; i++) {x = (b[i] + c[i]) / 2;a[i] = a[i + 1] + x;// ANTI dependency}#pragma omp parallel shared(a, a_copy) private (x){#pragma omp forfor (int i = 0; i < n; i++) {a_copy[i] = a[i + 1];}#pragma omp forfor (int i = 0; i < n; i++) {x = (b[i] + c[i]) / 2;a[i] = a_copy[i] + x;}}Москва, 2015 г.Параллельное программирование с OpenMP: Конструкциираспределения работы © Бахтин В.А.29 из 42Распределение циклов с зависимостью по даннымfor (int i = 1; i < n; i++) {b[i] = b[i] + a[i - 1];a[i] = a[i] + c[i]; // FLOW dependency}b[1] = b[1] + a[0];#pragma omp parallel for shared(a,b,c)for (int i = 1; i < n; i++) {a[i] = a[i] + c[i];b[i + 1] = b[i + 1] + a[i];}a[n - 1] = a[n - 1] + c[n - 1];Москва, 2015 г.Параллельное программирование с OpenMP: Конструкциираспределения работы © Бахтин В.А.30 из 42Распределение циклов с зависимостью по данным.Клауза и директива orderedvoid print_iteration(int iter) {#pragma omp orderedprintf("iteration %d\n", iter);}int main( ) {int i;#pragma omp parallel{#pragma omp for orderedfor (i = 0 ; i < 5 ; i++) {print_iteration(i);another_work (i);}}}Москва, 2015 г.Результат выполнения программы:iteration 0iteration 1iteration 2iteration 3iteration 4Параллельное программирование с OpenMP: Конструкциираспределения работы © Бахтин В.А.31 из 42Распределение циклов с зависимостью по данным.Клауза orderedЦикл с зависимостью по данным может быть распараллелен спомощью клаузы ordered:#pragma omp parallel for orderedfor(int i = 1; i < 100; i++) {#pragma omp ordered{a[i]= a[i-1] + a[i+1]}}Москва, 2015 г.Параллельное программирование с OpenMP: Конструкциираспределения работы © Бахтин В.А.32 из 42Распределение циклов с зависимостью по данным.Организация конвейерного выполнения цикла.for(int i = 1; i < M; i++)for(int j = 1; j < N; j++)a[i][j] = (a[i-1][j] + a[i][j-1] + a[i+1][j] + a[i][j+1]) / 4Нить 0Москва, 2015 г.Нить 1Нить NПараллельное программирование с OpenMP: Конструкциираспределения работы © Бахтин В.А.33 из 42Распределение циклов с зависимостью по данным.Организация конвейерного выполнения цикла.for(int i = 1; i < M; i++)for(int j = 1; j < N; j++)a[i][j] = (a[i-1][j] + a[i][j-1] + a[i+1][j] + a[i][j+1]) / 4T0T1T1T2T2Нить 1Нить 2T2Нить 0Москва, 2015 г.Параллельное программирование с OpenMP: Конструкциираспределения работы © Бахтин В.А.34 из 42Распределение циклов с зависимостью по данным.Организация конвейерного выполнения цикла.int iam, numt, limit;#pragma omp for schedule(static) nowaitint *isync = (int *)for (int j=1; j<N; j++) {malloc(omp_get_max_threads()*sizeof(int));a[i][j]=(a[i-1][j] + a[i][j-1] + a[i+1][j] +#pragma omp parallel private(iam,numt,limit)a[i][j+1])/4;{}iam = omp_get_thread_num ();if (iam<limit) {numt = omp_get_num_threads ();for (;isync[iam]==1;) {limit=min(numt-1,N-2);#pragma omp flush (isync)isync[iam]=0;}#pragma omp barrierisync[iam]=1;for (int i=1; i<M; i++) {#pragma omp flush (isync)if ((iam>0) && (iam<=limit)) {}for (;isync[iam-1]==0;) {}#pragma omp flush (isync)}}isync[iam-1]=0;#pragma omp flush (isync)Параллельное программирование с OpenMP: Конструкции}35 из 42Москва, 2015 г.распределения работы © Бахтин В.А.Распределение циклов с зависимостью по данным.Организация конвейерного выполнения цикла.#include <omp.h>int main () {#pragma omp parallel private(iam,numt){iam = omp_get_thread_num ();numt = omp_get_num_threads ();for (int newi=1; newi<M + numt - 1; newi++) {int i = newi - iam;#pragma omp forfor (int j=1; j<N; j++) {if (i >= 1) && (i< M)) {a[i][j]=(a[i-1][j] + a[i][j-1] + a[i+1][j] + a[i][j+1])/4;}}}}}Москва, 2015 г.Параллельное программирование с OpenMP: Конструкциираспределения работы © Бахтин В.А.36 из 42Распределение нескольких структурных блоков междунитями (директива sections).#pragma omp sections [клауза[[,] клауза] ...]{[#pragma omp section]структурный блок[#pragma omp sectionструктурный блок ]...}где клауза одна из :private(list)firstprivate(list)lastprivate(list)reduction(operator: list)nowaitМосква, 2015 г.void XAXIS();void YAXIS();void ZAXIS();void example(){#pragma omp parallel{#pragma omp sections{#pragma omp sectionXAXIS();#pragma omp sectionYAXIS();#pragma omp sectionZAXIS();}}}Параллельное программирование с OpenMP: Конструкциираспределения работы © Бахтин В.А.37 из 42Выполнение структурного блока одной нитью(директива SINGLE).#pragma omp single [клауза[[,] клауза] ...]структурный блокгде клауза одна из :private(list)firstprivate(list)copyprivate(list)nowaitСтруктурный блок будет выполненодной из нитей.