МГУ им. М.В. Ломоносова, Москва, 21 октября 2011г. КОНСОРЦИУМ УНИВЕРСИТЕТОВ РОССИИ Курс: «Технология параллельного программирования OpenMP» Лабораторная работа: « Разработка параллельных программ с использованием технологии OpenMP » Бахтин Владимир Александрович к.ф.-м.н., зав. сектором Института прикладной математики им М.В.Келдыша РАН

27 октября Москва, 2011 Технология параллельного программирования OpenMP 2 из 21 Содержание Распараллеливание итерационных методов Алгоритм Якоби Алгоритм последовательной верхней релаксации Распараллеливание циклов с зависимость по данным Балансировка нагрузки

27 октября Москва, 2011 Технология параллельного программирования OpenMP 3 из 21 Цель работы Лабораторная работа направлена на достижение следующих целей: Получить навыки распараллеливания существующих последовательных программ на языке Си. Оценить производительность параллельной программы при использовании разного количества процессоров (ядер). Для определенного количества процессоров (ядер) получить максимальную производительность, изменяя способ распределения витков циклов по процессорам (используя конструкцию SCHEDULE).

27 октября Москва, 2011 Технология параллельного программирования OpenMP 4 из 21 Система линейных уравнений Рассмотрим следующую систему линейных уравнений: A x = b где A – матрица коэффициентов, b – вектор свободных членов, x – вектор неизвестных. Для решения этой системы можно использовать следующие методы. Прямые методы. Хорошо известный метод исключения Гаусса является наиболее широко используемым алгоритмом этого класса. Явные итерационные методы. Наиболее известным алгоритмом этого класса является метод релаксации Якоби. Алгоритм выполняет следующие итерационные вычисления: Неявные итерационные методы. К этому классу относится метод последовательной верхней релаксации. Итерационное приближение вычисляется по формуле:

27 октября Москва, 2011 Технология параллельного программирования OpenMP 5 из 21 Алгоритм Якоби /* Jacobi-1 program */ #include #define Max(a,b) ((a)>(b)?(a):(b)) #define L 2000 #define ITMAX 50 int i,j,it,k; double eps; double MAXEPS = 0.5; double A[L][L], B[L][L]; int main(int an, char **as) { printf("JAC STARTED\n"); for(i=0; i

27 октября Москва, 2011 Технология параллельного программирования OpenMP 6 из 21 Алгоритм последовательной верхней релаксации /* Sor program */ #include #define Max(a,b) ((a)>(b)?(a):(b)) #define L 2000 #define ITMAX 50 int i,j,it,k; double eps; FILE *f; double A[L][L]; double tmp; int main(int an, char **as) { printf("SOR STARTED\n"); for(i=0; i

27 октября Москва, 2011 Технология параллельного программирования OpenMP 7 из 21 Распределение циклов с зависимостью по данным for(int i = 1; i < 100; i++) a[i]= a[i-1] + a[i+1] Между витками цикла с индексами i1 и i2 ( i1 i2. Если виток i1 читает старое значение, а виток i2 записывает новое значение, то между этими витками существует обратная зависимость i1

27 октября Москва, 2011 Технология параллельного программирования OpenMP 8 из 21 Распределение циклов с зависимостью по данным. Конструкция ordered Цикл с зависимостью по данным может быть распараллелен с помощью конструкции ordered: #pragma omp parallel for ordered for(int i = 1; i < 100; i++) { #pragma omp ordered { a[i]= a[i-1] + a[i+1] }

27 октября Москва, 2011 Технология параллельного программирования OpenMP 9 из 21 Распределение циклов с зависимостью по данным. Организация конвейерного выполнения цикла. for(int i = 1; i < N; 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

27 октября Москва, 2011 Технология параллельного программирования OpenMP 10 из 21 Распределение циклов с зависимостью по данным. Организация конвейерного выполнения цикла. int isync[NUMBER_OF_THREADS]; int iam, numt, limit; #pragma omp parallel private(iam,numt,limit) { iam = omp_get_thread_num (); numt = omp_get_num_threads (); limit=min(numt-1,N-2); isync[iam]=0; #pragma omp barrier for (int i=1; i0) && (iam

27 октября Москва, 2011 Технология параллельного программирования OpenMP 11 из 21 Распределение циклов с зависимостью по данным. Организация конвейерного выполнения цикла. #include int main () { #pragma omp parallel private(iam,numt) { iam = omp_get_thread_num (); numt = omp_get_num_threads (); for (int newi=1; newi

27 октября Москва, 2011 Технология параллельного программирования OpenMP 12 из 21 Балансировка нагрузки нитей. #pragma omp parallel for private(tmp) shared (a) for (int i=0; i

27 октября Москва, 2011 Технология параллельного программирования OpenMP 13 из 21 Распределение витков цикла. Клауза schedule Клауза schedule: schedule(алгоритм планирования[, число_итераций]) Где алгоритм планирования один из: schedule(static[, число_итераций]) - статическое планирование; schedule(dynamic[, число_итераций]) - динамическое планирование; schedule(guided[, число_итераций]) - управляемое планирование; schedule(runtime) - планирование в период выполнения; schedule(auto) - автоматическое планирование (OpenMP 3.0). #pragma omp parallel for schedule(static) for(int i = 1; i

27 октября Москва, 2011 Технология параллельного программирования OpenMP 14 из 21 Распределение витков цикла. Клауза schedule #pragma omp parallel for schedule(static, 10) for(int i = 1; i

27 октября Москва, 2011 Технология параллельного программирования OpenMP 15 из 21 Распределение витков цикла. Клауза schedule #pragma omp parallel for schedule(dynamic, 15) for(int i = 1; i

27 октября Москва, 2011 Технология параллельного программирования OpenMP 16 из 21 Распределение витков цикла. Клауза schedule число_выполняемых_потоком_итераций = max(число_нераспределенных_итераций/omp_get_num_threads(), число_итераций) #pragma omp parallel for schedule(guided, 10) for(int i = 1; i

27 октября Москва, 2011 Технология параллельного программирования OpenMP 17 из 21 Распределение витков цикла. Клауза schedule #pragma omp parallel for schedule(runtime) for(int i = 1; i

27 октября Москва, 2011 Технология параллельного программирования OpenMP 18 из 21 Распределение витков цикла. Клауза schedule #pragma omp parallel for schedule(auto) for(int i = 1; i

27 октября Москва, 2011 Технология параллельного программирования OpenMP 19 из 21 Балансировка нагрузки нитей. Клауза schedule #pragma omp parallel for private(tmp) shared (a) schedule (runtime) for (int i=0; i

27 октября Москва, 2011 Технология параллельного программирования OpenMP 20 из 21 Литература OpenMP Application Program Interface Version 3.0, May Антонов А.С. Параллельное программирование с использованием технологии OpenMP: Учебное пособие.-М.: Изд-во МГУ, Дж. Ортега. Введение в параллельные и векторные методы решения линейных систем. – М.: Мир, Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. – СПб.: БХВ-Петербург, 2002.