Обзор технологий параллельного программирования ФПК "Параллельные вычислительные технологии" Любая достаточно ушедшая вперед технология неотличима от чуда. А. Кларк Лекция Дейкова Татьяна Васильевна

Языки программирования Содержание 1. Критерии выбора технологии параллельного программирования 2. Классификация и обзор технологий параллельного программирования ©М.Л. Цымблер 2

Технологии параллельного программирования ©М.Л. Цымблер Языки программирования 3

Критерии выбора технологии 1. Эффективность создаваемых программ – Технологии, дающие неэффективные программы, не нужны! 2. Быстрота создания программ – Простота освоения технологии специалистами других предметных областей 3. Сохранение эффективности программ – Гарантия сохранения эффективности программ при их переносе на другую аппаратно-программную платформу ©М.Л. Цымблер 4

Языки программирования Классификация технологий Распараллеливающие компиляторы Параллельные языки программирования Параллельные расширения последовательных языков программирования Высокоуровневые коммуникационные библиотеки Параллельные библиотеки Инструментальные системы разработки параллельных программ Специализированные прикладные пакеты ©М.Л. Цымблер 5

Распараллеливающие компиляторы ©М.Л. Цымблер Языки программирования Текст программы на последовательном языке Исполняемый код последовательного компилятора Исполняемый код распараллеливающего компилятора Команда Время 6

Языки программирования Распараллеливающие компиляторы for (i=1; i<=n; i++) for (j=1; j<=n; j++) A[i+j]=A[2*n-i-j+1]*q+p for (i=1; i<=n; i++) { for (j=1; j<=n-i; j++) A[i+j]=A(2*n-i-j+1)*q+p; for (j=n-i+1; j<=n; j++) A[i+j]=A(2*n-i-j+1)*q+p; } ©М.Л. Цымблер 7 i j

Языки программирования Распараллеливающие компиляторы ? ©М.Л. Цымблер 8 for (i=1; i<=n; i++) A[i]=UserFunc(A, B[i]);

Языки программирования Классификация технологий 1. Распараллеливающие компиляторы 2. Параллельные языки программирования 3. Параллельные расширения последовательных языков программирования 4. Высокоуровневые коммуникационные библиотеки 5. Параллельные библиотеки 6. Инструментальные системы разработки параллельных программ 7. Специализи рованные прикладные пакеты ©М.Л. Цымблер 9

Параллельные языки ©М.Л. Цымблер Языки программирования Текст программы на параллельном языке Исполняемый код Время 10 ПАРАЛ_команда

Языки программирования Параллельные языки – НОРМА, ABCL, Adl, Ada, Concurrent Clean, MC#, Erlang, Linda, Modula-3, NESL, Occam, Orca, Parallaxis, Phantom, Sisal, SR, ZPL и др. ©М.Л. Цымблер 11

Язык и модель Linda Языки программирования Разработаны в 1980 гг. в Йельском университете (США). Параллельная программа – множество параллельных процессов, каждый из которых работает как последовательная программа. Процессы имеют доступ к общей памяти – пространству кортежей. Кортеж – упорядоченная последовательность значений. Процессы взаимодействуют друг с другом неявно, через пространство кортежей с помощью операций "поместить", "забрать", "скопировать" кортеж. Программа считается завершенной, если все процессы завершились или заблокированы. ("Hi", 12, 3.14) (5, TRUE, "Wow", 1) 12©М.Л. Цымблер

Функции Linda Языки программирования OUT( ) – Поместить кортеж в пространство кортежей. – Если такой кортеж уже имеется, то создается дубликат. – Вызывающий процесс не блокируется. – Примеры out("myTuple", 1); out(FALSE, 3.14, ); 13©М.Л. Цымблер

Функции Linda Языки программирования IN( ) – Получить указанный кортеж и удалить его из пространства кортежей. – Если параметру соответствует несколько кортежей, то случайным образом выбирается один из них. – Вызывающий процесс блокируется, пока соответствующий кортеж не появится в пространстве кортежей. – Примеры in("myTuple", 1); int i,j; in("myTuple",1,formal i,?j); 14©М.Л. Цымблер

Функции Linda Языки программирования READ( ) – Получить указанный кортеж из пространства кортежей (не удаляя его). – Если параметру соответствует несколько кортежей, то случайным образом выбирается один из них. – Вызывающий процесс блокируется, пока соответствующий кортеж не появится в пространстве кортежей. – Примеры int i; float j; char * s; read(?s, formal i, ?j); 15©М.Л. Цымблер

Функции Linda Языки программирования EVAL( ) – Поместить кортеж в пространство кортежей. – Если такой кортеж уже имеется, то создается дубликат. – Вызывающий процесс не блокируется. – Для вычисления поля кортежа, которое содержит обращение к какой-либо функции, порождается параллельный процесс. – Функция не ожидает завершения порожденного процесса. – Поля кортежа вычисляются в произвольном порядке. – Примеры eval("myTuple",myFunc1(a,b,c),TRUE,myFunc1(i,j,k)) ; 16©М.Л. Цымблер

Примеры программ на языке Linda Языки программирования Получение номера собственного процесса и общего количества процессов – out("Next", 1); – in("Next", ?myNumber); out("Next", myNumber+1); – read("Next", ?numProcesses); 17©М.Л. Цымблер

Примеры программ на языке Linda Языки программирования Барьерная синхронизация процессов – out("I want barrier", numProcesses); – in("I want barrier", ?Barrier); Barrier--; if (Barrier!=0) { out("I want barrier", Barrier); read("Barrier"); } else out("Barrier"); 18©М.Л. Цымблер

Примеры программ на языке Linda Языки программирования Параллельные процессы, работающие по схеме "мастер- рабочие" – int i, workers; void main(int argc, char * argv[]) { workers=atoi(argv[1]); for (i=0; i<workers; i++) eval("Рабочий", Worker(i)); for (i=0; i<workers; i++) in("Завершение работы"); } – void Worker(int i) { /* Работа */ out("Завершение работы"); } 19©М.Л. Цымблер

Языки программирования Классификация технологий Распараллеливающие компиляторы Параллельные языки программирования Параллельные расширения последовательных языков программирования Высокоуровневые коммуникационные библиотеки Параллельные библиотеки Инструментальные системы разработки параллельных программ Специализированные прикладные пакеты ©М.Л. Цымблер 20

Языки программирования Параллельные расширения Дополнение последовательного языка программирования параллельными операторами или директивами компилятора – Параллельные расширения и диалекты языка Fortran Fortran-DVM, Cray MPP Fortran, F--, Fortran 90/95, Fortran D95, Fortran M, Fx, HPF, Opus, Vienna Fortran и др. – Параллельные расширения и диалекты языков C/C++ C-DVM, A++/P++, CC++, Charm/Charm++, Cilk, HPC, HPC++, C/OpenMP Maisie, Mentat, mpC, MPC++, Parsec, pC++, sC++, uC++ и др. ©М.Л. Цымблер 21

Язык High Performance FORTRAN Языки программирования HPF – расширение языка FORTRAN, которые дают компилятору информацию для оптимизации выполнения программы на многопроцессорном (многоядерном) компьютере. 1. Примеры директив – !HPF$ PROCESSORS (n) Определение количества процессоров, которые могут использоваться программой. – !HPF$ DISTRIBUTE (BLOCK) ONTO procs :: переменные Блочное распределение данных массива список переменных по процессорам (распределение равными блоками). – ALIGN переменные 1(i) WITH переменные 2(i+1) Установка связи между распределением двух массивов. Для всех значений переменной i элемент массива список переменных 1(i) должен быть размещен в памяти того же процессора, что и элемент массива список переменных 2(i). – FORALL (i=1:1000) переменные 1(i)=переменныхе(i) Определение набора операторов, которые могут выполняться параллельно. 22©М.Л. Цымблер

Параллельное расширение C/OpenMP Языки программирования 23©М.Л. Цымблер Последовательный язык CПараллельное расширение C/OpenMP int Fact(int N) { int i, F; F = 1; for (i = 1; i<=N; i++) F *= i; return F; } int N; void main (void) { printf("Введите число: '); scanf(&N); printf("%d! = %d", N, Fact(N)); } int Fact(int N) { int i, F; F = 1; #pragma omp parallel for reduction(*:F) for (i = 1; i<=N; i++) F *= i; return F; } int N; void main (void) { printf("Введите число: '); scanf(&N); printf("%d! = %d", N, Fact(N)); }

Параллельное расширение C/OpenMP Языки программирования 24©М.Л. Цымблер Параллельное расширение C/OpenMP int Fact(int N) { int i, F; F = 1; #pragma omp parallel for reduction(*:F) for (i = 1; i<=N; i++) F *= i; return F; } int N; void main (void) { printf("Введите число: '); scanf(&N); printf("%d! = %d", N, Fact(N)); } F 1 i=1 i=2 F 3 i=5 i=6 F 2 i=3 i=4 F F 1 *F 2 *F 3

Языки программирования Классификация технологий Распараллеливающие компиляторы Параллельные языки программирования Параллельные расширения последовательных языков программирования Высокоуровневые коммуникационные библиотеки Параллельные библиотеки Инструментальные системы разработки параллельных программ Специализированные прикладные пакеты ©М.Л. Цымблер 25

Языки программирования Интерфейсы параллельного программирования Программирование на стандартных и широко распространенных языках программирования с использованием высокоуровневых коммуникационных библиотек и интерфейсов (API) для организации межпроцессного взаимодействия. Коммуникационные библиотеки и интерфейсы – ACE, ARCH, BIP, BLACS, BSPlib, CVM, Counterpoint, FM, Gala, GA, HPVM, ICC, JIAJIA, KELP, LPARX, MPI, MPL, OOMPI, OpenMP, POSIX Threads, P4, Para++, Phosphorus, PVM, Quarks, ROMIO, ShMem, SVMlib, TOOPS, Windows Threads ©М.Л. Цымблер 26

MPI-программа ©М.Л. Цымблер Языки программирования #include "mpi.h" // Подключение библиотеки int main (int argc, char *argv[]) { // Здесь код без использования MPI функций MPI_Init(&argc, &argv); // Инициализация выполнения // Здесь код, реализующий обмены MPI_Finalize(); // Завершение // Здесь код без использования MPI функций return 0; } 27

Пример MPI-программы ©М.Л. Цымблер Языки программирования #include "mpi.h" #include int main(int argc, char *argv[]) { int numtasks, rank, dest, src, rc, tag=777; char inmsg, outmsg='x'; MPI_Status Stat; MPI_Init(&argc,&argv); MPI_Comm_size(MPI_COMM_WORLD, &numtasks); MPI_Comm_rank(MPI_COMM_WORLD, &rank); if (rank == 0) { dest = 1; src = 1; rc = MPI_Send(&outmsg, 1, MPI_CHAR, dest, tag, MPI_COMM_WORLD); rc = MPI_Recv(&inmsg, 1, MPI_CHAR, src, tag, MPI_COMM_WORLD, &Stat); } else if (rank == 1) { dest = 0; src = 0; rc = MPI_Recv(&inmsg, 1, MPI_CHAR, src, tag, MPI_COMM_WORLD, &Stat); rc = MPI_Send(&outmsg, 1, MPI_CHAR, dest, tag, MPI_COMM_WORLD); } MPI_Finalize(); }

Пример программы с POSIX Threads ©М.Л. Цымблер Языки программирования #include #define NUM_THREADS 4 void *hello (void *arg) { printf(Hello Thread\n); } main() { pthread_t tid[NUM_THREADS]; for (int i=0; i<NUM_THREADS; i++) pthread_create(&tid[i], NULL, hello, NULL); for (int i=0; i<NUM_THREADS; i++) pthread_join(tid[i], NULL); } 29

Языки программирования Классификация технологий Распараллеливающие компиляторы Параллельные языки программирования Параллельные расширения последовательных языков программирования Высокоуровневые коммуникационные библиотеки Параллельные библиотеки Инструментальные системы разработки параллельных программ Специализированные прикладные пакеты ©М.Л. Цымблер 30

Языки программирования Специализированные параллельные библиотеки Библиотеки заранее распараллеленных процедур для решения различных научно- технических задач (линейная алгебра, сеточные методы, методы Монте-Карло, генетические алгоритмы, рендеринг изображений, …) – ATLAS, Aztec, BlockSolve95, Distributed Parallelization at CWP, DOUG, GALOPPS, JOSTLE, NAMD, P-Sparslib, PIM, ParMETIS, PARPACK, PBLAS, PETSc, PGAPack, PLAPACK, ScaLAPACK, SPRNG и др. ©М.Л. Цымблер 31

Параллельная библиотека Intel MKL ©М.Л. Цымблер Языки программирования for (i=0; i<N; i++) { for (j=0; j<N; j++) { for (k=0; k<N; k++) C[i][j]+=A[i][k]*B[k][j]; } for (i=0; i<N; i++ ) { for (j=0; j<N; j++ ) C[i][j]=cblas_ddot(N, &A[i], incx, &B[0][j], incy); } 32

Языки программирования Классификация технологий Распараллеливающие компиляторы Параллельные языки программирования Параллельные расширения последовательных языков программирования Высокоуровневые коммуникационные библиотеки Параллельные библиотеки Инструментальные системы разработки параллельных программ Специализированные прикладные пакеты ©М.Л. Цымблер 33

Языки программирования Инструментальные системы разработки Интегрированные среды прототипирования, разработки и отладки параллельных программ – CODE, Converse, DEEP, EDPEPPS, GRADE, HeNCE, Reactor, TRAPPER и др. Средства распознавания параллелизма в алгоритмах, средства автоматического и полуавтоматического распараллеливания последовательных программ – BERT 77, FORGE, KAP, PIPS, VAST, V-Ray и др. ©М.Л. Цымблер 34

Языки программирования Инструментальная система CODE Параллельная программа = граф – вершины – последовательные участки – дуги – пересылки данных. Последовательные участки могут быть написаны на любом языке, для пересылок используется MPI. ©М.Л. Цымблер 35

Языки программирования Пакет V-Ray V-Ray – комплекс инструментальных средств, направленных на автоматизацию создания и оптимизацию параллельных Fortran-программ для современных суперкомпьютерных систем. Разработка НИВЦ МГУ. Основные возможности: – Макроанализ – граф вызовов (порядок вызова процедур проекта), граф вложенности циклов в процедурах, граф использования общей памяти и др. – Микроанализ – иерархический граф управления, определение параллельных циклов, и др. ©М.Л. Цымблер 36

Языки программирования V-Ray: граф использования общей памяти ©М.Л. Цымблер 37

Языки программирования Классификация технологий Распараллеливающие компиляторы Параллельные языки программирования Параллельные расширения последовательных языков программирования Высокоуровневые коммуникационные библиотеки Параллельные библиотеки Инструментальные системы разработки параллельных программ Специализированные прикладные пакеты ©М.Л. Цымблер 38

Языки программирования Специализированные прикладные пакеты Специализированные прикладные пакеты, работающие на параллельных вычислительных платформах – Задачи инженерного анализа, прочности, теплофизики, деформации, упругости, пластичности, электромагнетизма ANSYS, MSC.NASTRAN, ABAQUS, LS-DYNA – Задачи аэро- и гидродинамики, механики жидкостей и газов, горения и детонации CFX, FLUENT, STAR-CD, FLOWVISION, FLOW-3D, GDT – Задачи акустического анализа LMS Virtual Lab. Acoustic, COMET/Acoustics ©М.Л. Цымблер 39

Языки программирования Пакеты ANSYS и CFX: расчет напряжения трубы Создание геометрии модели (ANSYS) Создание сетки (ANSYS) Настройка тепловых напряжений (ANSYS) Расчет тепловых нагрузок (CFX)Расчет напряжения от температуры (ANSYS) ©М.Л. Цымблер 40

Параллельное программирование в стандарте OpenMP ФПК "Параллельные вычислительные технологии" Общая сумма разума на планете есть величина постоянная, несмотря на постоянный прирост населения. А. Блох

Параллельные вычисления 42 Лекция Дейкова Татьяна Васильевна 2012 Параллельное программирование с использованием OpenMP

Москва, 2009 г. 43 из 26 Технология Intel Cluster OpenMP В 2006 году в Intel® компиляторах версии 9.1 появилась поддержка Cluster OpenMP. Технология Cluster OpenMP поддерживает выполнение OpenMP программ на нескольких вычислительных узлах, объединенных сетью. Базируется на программной реализации DSM (Thread Marks software by Rice University). Для компилятора Intel® C++: icc -cluster-openmp options source-file icc -cluster-openmp-profile options source-file Для компилятора Intel® Fortran: ifort -cluster-openmp options source-file ifort -cluster-openmp-profile options source-file kmp_cluster.ini --hostlist=home,remote --process_threads=2 Параллельное программирование с OpenMP: Использование OpenMP на кластере © Бахтин В.А.

Москва, 2009 г. 44 из 26 Преимущества Intel Cluster OpenMP Упрощает распределение последовательного или OpenMP кода по узлам. Позволяет использовать одну и ту же программу для последовательных, многоядерных и кластерных систем. Требует совсем незначительного изменения кода программы, что упрощает отладку. Позволяет слегка измененной OpenMP-программе выполняться на большем числе процессоров без вложений в аппаратную составляющую SMP. Представляет собой альтернативу MPI, которая может быть быстрее освоена и применена. Параллельное программирование с OpenMP: Использование OpenMP на кластере © Бахтин В.А.

Москва, 2009 г. 45 из 26 Преимущества Intel Cluster OpenMP Переносимость и гибкость упрощает и снижает стоимость разработки приложений. Тип вычислительной системы Аппаратная составляющая расходов Программная составляющая расходов Большие SMP системы с общей памятью и OpenMP Кластерные системы с распределенной памятью и MPI Кластерные системы с распределенной памятью и Cluster OpenMP Параллельное программирование с OpenMP: Использование OpenMP на кластере © Бахтин В.А.

001 Модель памяти в OpenMP Москва, 2009 г. 46 из 26 Нить 001 Нить 001 Нить Параллельное программирование с OpenMP: Использование OpenMP на кластере © Бахтин В.А.

Консистентность памяти в OpenMP Москва, 2009 г. 48 из 26 Корректная последовательность работы нитей с переменной: Нить 0 записывает значение переменной - write(var) Нить 0 выполняет операцию синхронизации – flush (var) Нить 1 выполняет операцию синхронизации – flush (var) Нить 1 читает значение переменной – read (var) 1: A = : flush(A) Параллельное программирование с OpenMP: Использование OpenMP на кластере © Бахтин В.А.

Директива SHARABLE Москва, 2009 г. 49 из 26 #pragma intel omp sharable ( variable [, variable …] ) – для Си и Си++ !dir$ omp sharable ( variable [, variable …] ) - для Фортрана определяют переменные, которые должны быть помещены в Distributed Virtual Shared Memory В компиляторе существуют опции, которые позволяют изменить класс переменных, не изменяя текст программы: [-no]-clomp-sharable-argexprs [-no]-clomp-sharable-commons [-no]-clomp-sharable-localsaves [-no]-clomp-sharable-modvars Параллельное программирование с OpenMP: Использование OpenMP на кластере © Бахтин В.А.

Москва, 2009 г. 50 из 26 Использование Intel Cluster OpenMP malloc (…) -> kmp_sharable_malloc (…) #include foo * fp = new foo (10); foo * fp = new kmp_sharable foo (10); std::vector * vp = new std::vector ; std::vector > * vp = new kmp_sharable std::vector >; Параллельное программирование с OpenMP: Использование OpenMP на кластере © Бахтин В.А.

Работа с SHARABLE- переменными Москва, 2009 г. 51 из 26 Параллельное программирование с OpenMP: Использование OpenMP на кластере © Бахтин В.А.

Москва, 2009 г. 52 из 26 Использование Intel Cluster OpenMP Целесообразно: если программа дает хорошее ускорение при использовании технологии OpenMP: Speedup = Time(1thread)/Time (n threads) = ~n еcли программа требует малой синхронизации данные в программе хорошо локализованы Наиболее целесообразно для задач (RMS - recognition, mining, and synthesis): Обработка больших массивов данных Рендеринг в графике Поиск Распознавание образов Выделение последовательностей в генетике Параллельное программирование с OpenMP: Использование OpenMP на кластере © Бахтин В.А.

Москва, 2009 г. 53 из 26 Использование Intel Cluster OpenMP 1. a particle-simulation code 2. a magneto-hydro-dynamics code 3. a computational fluid dynamics code 4. a structure-simulation code 5. a graph-processing code 6. a linear solver code 7. an x-ray crystallography code Параллельное программирование с OpenMP: Использование OpenMP на кластере © Бахтин В.А.

Москва, 2009 г. 54 из 26 Гибридная модель параллельного программирования MPI/OpenMP Данны е Core Данные Вычисления Core … Узел 0 OpenMP Core Данные Вычисления Core … Узел N OpenMP Вычисления MPI Параллельное программирование с OpenMP: Использование OpenMP на кластере © Бахтин В.А.

Содержание ФПК "Параллельные вычислительные технологии" Модель программирования в общей памяти Модель "пульсирующего" параллелизма FORK-JOIN Стандарт OpenMP Основные понятия и функции OpenMP © М.Л. Цымблер 55

Программирование в общей памяти © М.Л. Цымблер ФПК "Параллельные вычислительные технологии" 56 Параллельное приложение состоит из нескольких нитей, выполняющихся одновременно. Нити разделяют общую память. Обмены между нитями осуществляются посредством чтения/записи данных в общей памяти. Нити выполняются на различных ядрах одного процессора. … Нить 0Нить 1Нить N-1 Данные

Модель FORK-JOIN © М.Л. Цымблер ФПК "Параллельные вычислительные технологии" 57 Программа – полновесный процесс. Процесс может запускать легковесные процессы (нити), выполняющиеся в фоновом режиме. – Процесс приложения – главная нить. – Нить может запускать другие нити в рамках процесса. Каждая нить имеет собственный сегмент стека. – Все нити процесса разделяют сегмент данных процесса. Сегмент данных Главная нить (процесс) main() … нить Сег. стека Сегмент стека нить Сег. стека Нить … FORK JOIN Главная нить

Стандарт OpenMP © М.Л. Цымблер ФПК "Параллельные вычислительные технологии" 58 OpenMP (Open Multi-Processing) – стандарт, реализующий модели программирования в общей памяти и Fork-Join. Стандарт содержит набор директив компилятора и спецификаций подпрограмм на языках C, С++ и FORTRAN. Стандарт реализуется разработчиками компиляторов для различных аппаратно- программных платформ (кластеры, персональные компьютеры, …, Windows, Unix/Linux, …). Разработчик стандарта – OpenMP Architecture Review Board (

OpenMP-программа © М.Л. Цымблер ФПК "Параллельные вычислительные технологии" 59 Главная нить (программа) порождает семейство дочерних нитей (сколько необходимо). Порождение и завершение осуществляется с помощью директив компилятора. Главная нить Нити Параллельные регионы Последовательные регионы

Простая OpenMP-программа © М.Л. Цымблер ФПК "Параллельные вычислительные технологии" 60 void main() { printf("Hello!\n"); } void main() { #pragma omp parallel { printf("Hello!\n"); } } Результат Результат (для 2-х нитей) Hello!Hello! Последовательный код Параллельный код

Простая OpenMP-программа © М.Л. Цымблер ФПК "Параллельные вычислительные технологии" 61

Преимущества OpenMP © М.Л. Цымблер ФПК "Параллельные вычислительные технологии" 62 Поэтапное (инкрементное) распараллеливание – Можно распараллеливать последовательные программы поэтапно, не меняя их структуру. Единственность кода – Нет необходимости поддерживать последовательный и параллельный вариант программы, поскольку директивы игнорируются обычными компиляторами. Эффективность кода – Учет и использование возможностей систем с общей памятью. Мобильность кода – Поддержка языков C/C++, Fortran и ОС Windows, Unix/Linux.

Директивы OpenMP © М.Л. Цымблер ФПК "Параллельные вычислительные технологии" 63 Директивы OpenMP – директивы C/C++ компилятора #pragma. – параметр компиляции /openmp. Синтаксис директив OpenMP – #pragma omp имя_директивы[параметры] Примеры: – #pragma omp parallel – #pragma omp for private(i, j) reduction(+: sum)

Функции библиотеки OpenMP © М.Л. Цымблер ФПК "Параллельные вычислительные технологии" 64 Назначение функций библиотеки: – контроль и просмотр параметров OpenMP- программы omp_get_thread_num() возвращает номер текущей нити – явная синхронизация нитей на базе "замков" omp_set_lock() устанавливает "замок" Подключение библиотеки – #include "omp.h"

Переменные окружения OpenMP © М.Л. Цымблер ФПК "Параллельные вычислительные технологии" 65 Переменные окружения контролируют поведение приложения. – OMP_NUM_THREADS – количество нитей в параллельном регионе – OMP_DYNAMIC – разрешение или запрет динамического изменения количества нитей. – OMP_NESTED – разрешение или запрет вложенных параллельных регионов. – OMP_SCHEDULE – способ распределения итераций в цикле. Функции назначения параметров изменяют значения соответствующих переменных окружения. Макрос _OPENMP для условной компиляции отдельных участков исходного кода, характерных для параллельной версии программы.

Область видимости переменных © М.Л. Цымблер ФПК "Параллельные вычислительные технологии" 66 Общая переменная (shared) – глобальная по отношению к нити переменная; доступна для модификации всем нитям. Частная переменная (private) – локальная переменная нити; доступна для модификации только одной (создавшей ее) нити только на время выполнения этой нити. Видимость переменных по умолчанию: – переменные, определенные вне параллельной области – общие; – переменные, определенные внутри параллельной области – частные. Явное указание области видимости – параметры директив: – #pragma omp parallel shared(buf) – #pragma omp for private(i, j)

Частные и общие переменные © М.Л. Цымблер ФПК "Параллельные вычислительные технологии" 67 void main() { int a, b, c; … #pragma omp parallel shared(с) private(a) { int d, e; … } void main() { int a, b, c; … #pragma omp parallel { int d, e; … } Частные переменные Общие переменные

Частные и общие переменные © М.Л. Цымблер ФПК "Параллельные вычислительные технологии" 68 void main() { int rank; #pragma omp parallel { rank = omp_get_thread_num(); } printf("%d\n", rank); } void main() { int rank; #pragma omp parallel { rank = omp_get_thread_num(); printf("%d\n", rank); } Одно случайное число из диапазона 0..OMP_NUM_THREADS-1 OMP_NUM_THREADS случайных чисел (возможно, повторяющихся) из диапазона 0..OMP_NUM_THREADS-1

Частные и общие переменные © М.Л. Цымблер ФПК "Параллельные вычислительные технологии" 69 void main() { int rank; #pragma omp parallel shared (rank) { rank = omp_get_thread_num(); printf("%d\n", rank); } void main() { int rank; #pragma omp parallel private (rank) { rank = omp_get_thread_num(); printf("%d\n", rank); } OMP_NUM_THREADS случайных чисел (возможно, повторяющихся) из диапазона 0..OMP_NUM_THREADS-1 OMP_NUM_THREADS чисел из диапазона 0..OMP_NUM_THREADS-1 (без повторений, в случайном порядке)

Распределение вычислений © М.Л. Цымблер ФПК "Параллельные вычислительные технологии" 70 Директивы распределения вычислений между нитями в параллельной области – sections – функциональное распараллеливание раздельных фрагментов кода – single и master – директивы для указания выполнения кода только одной нитью – for – распараллеливание циклов Начало выполнения директив по умолчанию не синхронизируется. Завершение директив по умолчанию является синхронным.

Директива sections © М.Л. Цымблер ФПК "Параллельные вычислительные технологии" 71 Явное определение блоков кода, которые могут исполняться параллельно. – каждый фрагмент выполняется однократно – разные фрагменты выполняются разными нитями – завершение директивы синхронизируется. #pragma omp parallel sections { #pragma omp section Job1(); #pragma omp section Job2(); #pragma omp section Job3(); }

Директива single © М.Л. Цымблер ФПК "Параллельные вычислительные технологии" 72 Определяет код, который выполняется только одной (первой пришедшей в данную точку) нитью. – Остальные нити пропускают соответствующий код и ожидают окончания его выполнения. – Если ожидание других нитей необязательно, может быть добавлен параметр nowait. #pragma omp parallel { #pragma omp single printf("Start Work #1.\n"); Work1(); #pragma omp single printf("Stop Work #1.\n"); #pragma omp single nowait printf("Stop Work #1 and start Work #2.\n"); Work2(); }

Директива master © М.Л. Цымблер ФПК "Параллельные вычислительные технологии" 73 Определяет код, который выполняется только одной главной нитью. Остальные нити пропускают соответствующий код, не ожидая окончания его выполнения. #pragma omp parallel { #pragma omp master printf("Beginning Work1.\n"); Work1(); #pragma omp master printf("Finishing Work1.\n"); #pragma omp master printf("Finished Work1 and beginning Work2.\n"); Work2(); }

Распараллеливание циклов © М.Л. Цымблер ФПК "Параллельные вычислительные технологии" 74 Счетчик цикла по умолчанию является частной переменной. По умолчанию вычисления распределяются равномерно между нитями. #pragma omp parallel { #pragma omp for for (i=0; i<N; i++) { res[i] = big_calc(); } #pragma omp parallel for for (i=0; i<N; i++) { res[i] = big_calc(); } i=0 i=1 i=2 i=3 i=8 i=9 i=10 i=11 i=4 i=5 i=6 i=7

Распараллеливание циклов © М.Л. Цымблер ФПК "Параллельные вычислительные технологии" 75 Можно явно определять частные данные цикла. } void work(float c[], int N) { float x, y; int i; #pragma omp parallel for private(x, y) for(i=0; i<N; i++) { x = a[i]; y = b[i]; c[i] = x + y; }

Распараллеливание циклов © М.Л. Цымблер ФПК "Параллельные вычислительные технологии" 76 Бесконтрольное изменение нитями общих данных приводит к логическим ошибкам. } float scalar_product(float a[], float b[], int N) { float sum = 0.0; #pragma omp parallel for shared(sum) for(i=0; i<N; i++) { sum = sum + a[i] * b[i]; } return sum; }

Критическая секция в циклах © М.Л. Цымблер ФПК "Параллельные вычислительные технологии" 77 В любой момент времени код критической секции может быть выполнен только одной нитью. } float scalar_product(float a[], float b[], int N) { float sum = 0.0; #pragma omp parallel for shared(sum) for(i=0; i<N; i++) { #pragma omp critical sum = sum + a[i] * b[i]; } return sum; }

Редукция операций в циклах © М.Л. Цымблер ФПК "Параллельные вычислительные технологии" 78 Редукция подразумевает определение для каждой нити частной переменной для вычисления "частичного" результата и автоматическое выполнение операции "слияния" частичных результатов. Опера ция Нач. знач-е +0 *1 -0 ^0 &~0 |0 &&1 ||0 float scalar_product(float a[], float b[], int N) { float sum = 0.0; #pragma omp parallel for reduction(+:sum) for(i=0; i<N; i++) { sum = sum + a[i] * b[i]; } return sum; }

Редукция операций в циклах © М.Л. Цымблер ФПК "Параллельные вычислительные технологии" 79 #include long long num_steps = ; double step; int main(int argc, char* argv[]) { clock_t start, stop; double x, pi, sum=0.0; int i; step = 1./(double)num_steps; start = clock(); #pragma omp parallel for private(x) reduction(+:sum) for (i=0; i<num_steps; i++) { x = (i + 0.5)*step; sum = sum + 4.0/(1.+ x*x); } pi = sum*step; stop = clock(); printf("PI=%15.12f\n", pi); printf("Time=%f sec.\n",((double)(stop - start)/1000.0)); return 0; } - Нить 0 - Нить 1 - Нить 2

Директива for © М.Л. Цымблер ФПК "Параллельные вычислительные технологии" 80 Формат директивы – #pragma omp parallel for [clause...] for (…) Виды параметра clause – private(список_переменных) – firstprivate(список_переменных) – lastprivate(список_переменных) – reduction(оператор: переменная) – ordered – nowait – schedule(вид_распределения[, размер])

Параметр firstprivate © М.Л. Цымблер ФПК "Параллельные вычислительные технологии" 81 Определяет частные переменные цикла for, которые в начале цикла принимают значения последовательной части программы. myrank = omp_get_thread_num(); #pragma omp parallel for firstprivate(addendum) for (i=0; i<N-1; i++) { a[i] = b[i] + b[i+1] + myrank; myrank = myrank + N % (i+1); }

Параметр lastprivate © М.Л. Цымблер ФПК "Параллельные вычислительные технологии" 82 Определяет частные переменные, которые по окончании цикла for принимают такие значения, как если бы цикл выполнялся последовательно. #pragma omp parallel for lastprivate(i) for (i=0; i<N-1; i++) { a[i] = b[i] + b[i+1]; } // здесь i=N

Параметр ordered © М.Л. Цымблер ФПК "Параллельные вычислительные технологии" 83 Определяет код в теле цикла for, выполняемый в точности в том порядке, в каком он выполнялся бы при последовательном исполнении цикла. #pragma omp for ordered schedule(dynamic) for (i=start; i<stop; i+=step) Process(i); void Process(int k) { #pragma omp ordered printf(" %d", k); }

Параметр nowait © М.Л. Цымблер ФПК "Параллельные вычислительные технологии" 84 Позволяет избежать неявного барьера при завершении директивы for. #pragma omp parallel { #pragma omp for nowait for (i=1; i<n; i++) b[i] = (a[i] + a[i-1]) / 2.0; #pragma omp for nowait for (i=0; i<m; i++) y[i] = sqrt(z[i]); }

Распределение итераций цикла © М.Л. Цымблер ФПК "Параллельные вычислительные технологии" 85 Распределение итераций в директиве for регулируется параметром schedule (вид_распределения [, размер]) – static – итерации делятся на блоки по размер итераций и статически разделяются между потоками; если параметр размер не определен, итерации делятся между потоками равномерно и непрерывно – dynamic – распределение итерационных блоков осуществляется динамически (по умолчанию размер=1 ) – guided – размер итерационного блока уменьшается экспоненциально при каждом распределении; размер определяет минимальный размер блока (по умолчанию размер=1 ) – runtime – правило распределения определяется переменной OMP_SCHEDULE (при использовании runtime параметр размер задаваться не должен)

Пример © М.Л. Цымблер ФПК "Параллельные вычислительные технологии" 86 // Объем работы в итерациях предсказуем и примерно одинаков #pragma omp parallel for schedule(static) for(i=0; i<n; i++) { invariant_amount_of_work(i); } // Объем работы в итерациях может существенно различаться // или непредсказуем #pragma omp parallel for schedule(dynamic) for(i=0; i<n; i++) { unpredictable_amount_of_work(i); }

Пример © М.Л. Цымблер ФПК "Параллельные вычислительные технологии" 87 // Нити подходят к точке распределения итераций // в разное время, объем работы в итерациях // предсказуем и примерно одинаков #pragma omp parallel { #pragma omp sections nowait {... } #pragma omp for schedule(guided) for(i=0; i<n; i++) { invariant_amount_of_work(i); }

Синхронизация вычислений © М.Л. Цымблер ФПК "Параллельные вычислительные технологии" 88 Директивы явной синхронизации – critical – barrier – atomic Директива неявной синхронизации – #pragma omp parallel

Директива critical © М.Л. Цымблер ФПК "Параллельные вычислительные технологии" 89 Определяет критическую секцию – участок кода, выполняемый одновременно не более чем одной нитью. #pragma omp parallel shared(x, y) private(x_next, y_next) { #pragma omp critical (Xaxis_critical_section) x_next = Queue_Remove(x); Process(x_next); #pragma omp critical (Yaxis_critical_section) y_next = Queue_Remove(y); Process(y_next); }

Директива atomic © М.Л. Цымблер ФПК "Параллельные вычислительные технологии" 90 Определяет критическую секцию для одного оператора вида – x++ и ++x – x-- и --x – x+=выражение, x-=выражение и др. extern float a[], *p = a, b; // Предохранение от гонок данных // при обновлении несколькими нитями #pragma omp atomic a[index[i]] += b; // Предохранение от гонок данных // при обновлении несколькими нитями #pragma omp atomic p[i] -= 1.0f;

Директива barrier © М.Л. Цымблер ФПК "Параллельные вычислительные технологии" 91 Определяет барьер – точку в программе, которую должна достигнуть каждая нить, чтобы все нити продолжили вычисления. // Директива должна быть частью структурного блока if (x!=0) { #pragma omp barrier... } #pragma omp parallel shared (A, TmpRes, FinalRes) { DoSomeWork(A, TmpRes); printf("Processed A into TmpRes\n"); #pragma omp barrier DoSomeWork(TmpRes, FinalRes); printf("Processed B into C\n"); }

Директива barrier © М.Л. Цымблер ФПК "Параллельные вычислительные технологии" 92 int main() { sub1(2); sub2(2); sub3(2); } void sub1(int n) { int i; #pragma omp parallel private(i) shared(n) { #pragma omp for for (i=0; i<n; i++) sub2(i); } void sub2(int k) { #pragma omp parallel shared(k) sub3(k); } void sub3(int n) { work(n); #pragma omp barrier work(n); }

Директивы и параметры © М.Л. Цымблер ФПК "Параллельные вычислительные технологии" 93 if private shared default firstprivate lastprivate reduction copyin schedule ordered nowait

Время работы © М.Л. Цымблер ФПК "Параллельные вычислительные технологии" 94 double start; double end; start = omp_get_wtime(); // Работа end = omp_get_wtime(); printf(Work took %f sec. time.\n, end-start);

Количество нитей © М.Л. Цымблер ФПК "Параллельные вычислительные технологии" 95 // Неверно np = omp_get_num_threads(); // Здесь еще не выполнен FORK #pragma omp parallel for schedule(static) for (i=0; i<np; i++) work(i); // Верно #pragma omp parallel private(i) { i = omp_get_thread_num(); work(i); }