Интернет Университет Суперкомпьютерных технологий Введение Учебный курс Параллельное программирование с OpenMP Бахтин В.А., кандидат физ.-мат. наук, заведующий сектором, Институт прикладной математики им. М.В.Келдыша РАН

Москва, 2012 г. Параллельное программирование с OpenMP: Введение © Бахтин В.А. 2 из 46 Содержание Тенденции развития современных процессоров Существующие подходы для создания параллельных программ Основные возможности OpenMP SMP и DSM - системы Литература

В течение нескольких десятилетий развитие ЭВМ сопровождалось удвоением их быстродействия каждые года. Это обеспечивалось и повышением тактовой частоты и совершенствованием архитектуры (параллельное и конвейерное выполнение команд). Узким местом стала оперативная память. Знаменитый закон Мура, так хорошо работающий для процессоров, совершенно не применим для памяти, где скорости доступа удваиваются в лучшем случае каждые 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) Тенденции развития современных процессоров Москва, 2012 г. Параллельное программирование с OpenMP: Введение © Бахтин В.А. 3 из 46

Время Тенденции развития современных процессоров В П В П В П В П В П В П Поток Время В П В П В П Поток 1 В П В П В П В П В П В П В П В П В П Поток 2 Поток 3 Поток 4 В - вычисления П - доступ к памяти Chip MultiThreading увеличили производительность процессора в 2 раза Поток или нить (по- английски thread) – это легковесный процесс, имеющий с другими потоками общие ресурсы, включая общую оперативную память. Москва, 2012 г. Параллельное программирование с OpenMP: Введение © Бахтин В.А. 4 из 46

Москва, 2012 г. Параллельное программирование с OpenMP: Введение © Бахтин В.А. 5 из 46 Top 500

Современные суперкомпьютерные системы Москва, 2012 г. Параллельное программирование с OpenMP: Введение © Бахтин В.А. 6 из 46 Суперкомпьютер K computer, SPARC64 VIIIfx 2.0GHz, Tofu interconnect Пиковая производительность TFlop/s Число ядер в системе Производительность на Linpack TFlop/s (93.17 % от пиковой) Энергопотребление комплекса кВт Важным параметром становится – Power Efficency (Megaflops/watt)

Современные суперкомпьютерные системы Москва, 2012 г. Параллельное программирование с OpenMP: Введение © Бахтин В.А. 7 из 46 Суперкомпьютер Sequoia, IBM BlueGene/Q, Power BQC 16C 1.6GHz, Custom interconnect Пиковая производительность – TFlop/s Число ядер в системе Производительность на Linpack – TFlop/s (81.08 % от пиковой) Энергопотребление комплекса кВт Важным параметром становится – Power Efficency (Megaflops/watt) Как добиться максимальной производительности на Ватт => Chip MultiProcessing, многоядерность.

Тенденции развития современных процессоров Москва, 2012 г. Параллельное программирование с OpenMP: Введение © Бахтин В.А. 8 из 46 AMD Opteron серии SE 16 2,7 ГГц, 16 МБ L3 Cache ,0 ГГц, 16 МБ L3 Cache ,3 ГГц, 16 МБ L3 Cache встроенный контроллер памяти (4 канала памяти DDR3) 4 канала «точка-точка» с использованием HyperTransort 3.0

Тенденции развития современных процессоров Москва, 2012 г. Параллельное программирование с OpenMP: Введение © Бахтин В.А. 9 из 46 Intel Xeon серии E ,9 ГГц, 16 нитей, 20 МБ L3 Cache ,5 ГГц, 8 нитей, 10 МБ L3 Cache Intel® Turbo Boost Intel® Hyper-Threading Intel® QuickPath Intel® Intelligent Power

Тенденции развития современных процессоров Москва, 2012 г. Параллельное программирование с OpenMP: Введение © Бахтин В.А. 10 из 46 Intel Core i7-3960X Extreme Edition 3,3 ГГц (3,9 ГГц) 6 ядeр 12 потоков с технологией Intel Hyper-Threading 15 МБ кэш-памяти Intel Smart Cache встроенный контроллер памяти (4 канала памяти DDR3 1066/1333/1600 МГц ) технология Intel QuickPath Interconnect

Тенденции развития современных процессоров Intel Itanium 9350 (Tukwila) 1,73 ГГц 4 ядeр 8 потоков с технологией Intel Hyper-Threading 24 МБ L3 кэш-памяти технология Intel QuickPath Interconnect технология Intel Turbo Boost Москва, 2012 г. Параллельное программирование с OpenMP: Введение © Бахтин В.А. 11 из 46

Тенденции развития современных процессоров IBM Power7 3,5 - 4,0 ГГц 8 ядер x 4 нити Simultaneuos MultiThreading L1 64КБ L2 256 КБ L3 32 МБ встроенный контроллер памяти Москва, 2012 г. Параллельное программирование с OpenMP: Введение © Бахтин В.А. 12 из 46

Тенденции развития современных процессоров Темпы уменьшения латентности памяти гораздо ниже темпов ускорения процессоров + прогресс в технологии изготовления кристаллов => CMT (Chip MultiThreading) Опережающий рост потребления энергии при росте тактовой частоты + прогресс в технологии изготовления кристаллов => CMP (Chip MultiProcessing, многоядерность) И то и другое требует более глубокого распараллеливания для эффективного использования аппаратуры Москва, 2012 г. Параллельное программирование с OpenMP: Введение © Бахтин В.А. 13 из 46

Существующие подходы для создания параллельных программ Автоматическое / автоматизированное распараллеливание Библиотеки нитей Win32 API POSIX Библиотеки передачи сообщений MPI OpenMP Москва, 2012 г. Параллельное программирование с OpenMP: Введение © Бахтин В.А. 14 из 46

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 Москва, 2012 г. Параллельное программирование с OpenMP: Введение © Бахтин В.А. 15 из 46 Вычисление числа

#include int main () { int n =100000, i; double pi, h, sum, x; h = 1.0 / (double) n; sum = 0.0; for (i = 1; i

Автоматическое распараллеливание Polaris, CAPO, WPP, SUIF, VAST/Parallel, OSCAR, Intel/OpenMP, UTL icc -parallel pi.c pi.c(8): (col. 5) remark: LOOP WAS AUTO-PARALLELIZED. pi.c(8): (col. 5) remark: LOOP WAS VECTORIZED. В общем случае, автоматическое распараллеливание затруднено: косвенная индексация (A[B[i]]); указатели (ассоциация по памяти); сложный межпроцедурный анализ. Москва, 2012 г. Параллельное программирование с OpenMP: Введение © Бахтин В.А. 17 из 46

Автоматизированное распараллеливание Intel/GAP (Guided Auto-Parallel), CAPTools/ParaWise, BERT77, FORGE Magic/DM, ДВОР (Диалоговый Высокоуровневый Оптимизирующий Распараллеливатель), САПФОР (Система Автоматизации Параллелизации ФОРтран программ) for (i=0; i 0) {b=A[i]; A[i] = 1 / A[i]; } if (A[i] > 1) {A[i] += b;} } icc -guide -parallel test.cpp Москва, 2012 г. Параллельное программирование с OpenMP: Введение © Бахтин В.А. 18 из 46

Автоматизированное распараллеливание test.cpp(49): remark #30521: (PAR) Loop at line 49 cannot be parallelized due to conditional assignment(s) into the following variable(s): b. This loop will be parallelized if the variable(s) become unconditionally initialized at the top of every iteration. [VERIFY] Make sure that the value(s) of the variable(s) read in any iteration of the loop must have been written earlier in the same iteration. test.cpp(49): remark #30525: (PAR) If the trip count of the loop at line 49 is greater than 188, then use "#pragma loop count min(188)" to parallelize this loop. [VERIFY] Make sure that the loop has a minimum of 188 iterations. #pragma loop count min (188) for (i=0; i 0) {A[i] = 1 / A[i];} if (A[i] > 1) {A[i] += b;} } Москва, 2012 г. Параллельное программирование с OpenMP: Введение © Бахтин В.А. 19 из 46

#include #define NUM_THREADS 2 CRITICAL_SECTION hCriticalSection; double pi = 0.0; int n =100000; void main () { int i, threadArg[NUM_THREADS]; DWORD threadID; HANDLE threadHandles[NUM_THREADS]; for(i=0; i

void Pi (void *arg) { int i, start; double h, sum, x; h = 1.0 / (double) n; sum = 0.0; start = *(int *) arg; for (i=start; i

Москва, 2012 г. Параллельное программирование с OpenMP: Введение © Бахтин В.А. 22 из 46 Конфликт доступа к данным При взаимодействии через общую память нити должны синхронизовать свое выполнение. Thread0: pi = pi + val; && Thread1: pi = pi + val; ВремяThread 0 Thread 1 1LOAD R1,pi 2LOAD R2,val 3ADD R1,R2LOAD R3,pi 4LOAD R4,val 5ADD R3,R4 6STORE R3,pi 7STORE R1,pi Результат зависит от порядка выполнения команд. Требуется взаимное исключение критических интервалов.

#include "mpi.h" #include int main (int argc, char *argv[]) { int n =100000, myid, numprocs, i; double mypi, pi, h, sum, x; MPI_Init(&argc,&argv); MPI_Comm_size(MPI_COMM_WORLD,&numprocs); MPI_Comm_rank(MPI_COMM_WORLD,&myid); MPI_Bcast(&n, 1, MPI_INT, 0, MPI_COMM_WORLD); h = 1.0 / (double) n; sum = 0.0; Вычисление числа с использованием MPI Москва, 2012 г. Параллельное программирование с OpenMP: Введение © Бахтин В.А. 23 из 46

for (i = myid + 1; i

#include int main () { int n =100000, i; double pi, h, sum, x; h = 1.0 / (double) n; sum = 0.0; #pragma omp parallel for reduction(+:sum) private(x) for (i = 1; i

Достоинства использования OpenMP вместо MPI для многоядерных процессоров Возможность инкрементального распараллеливания Упрощение программирования и эффективность на нерегулярных вычислениях, проводимых над общими данными Ликвидация дублирования данных в памяти, свойственного MPI- программам Объем памяти пропорционален быстродействию процессора. В последние годы увеличение производительности процессора достигается увеличением числа ядер, при этом частота каждого ядра не увеличивается. Наблюдается тенденция к сокращению объема оперативной памяти, приходящейся на одно ядро. Присущая OpenMP экономия памяти становится очень важна. Наличие локальных и/или разделяемых ядрами КЭШей будут учитываться при оптимизации OpenMP-программ компиляторами, что не могут делать компиляторы с последовательных языков для MPI-процессов. Москва, 2012 г. Параллельное программирование с OpenMP: Введение © Бахтин В.А. 26 из 46

Тесты NAS Москва, 2012 г. Параллельное программирование с OpenMP: Введение © Бахтин В.А. 27 из 46 BT3D Навье-Стокс, метод переменных направлений CGОценка наибольшего собственного значения симметричной разреженной матрицы EPГенерация пар случайных чисел Гаусса FTБыстрое преобразование Фурье, 3D спектральный метод ISПараллельная сортировка LU3D Навье-Стокс, метод верхней релаксации MG3D уравнение Пуассона, метод Multigrid SP3D Навье-Стокс, Beam-Warning approximate factorization

Тесты NAS Москва, 2012 г. Параллельное программирование с OpenMP: Введение © Бахтин В.А. 28 из 46 Analyzing the Effect of Different Programming Models Upon Performance and Memory Usage on Cray XT5 Platforms

Тесты NAS Москва, 2012 г. Параллельное программирование с OpenMP: Введение © Бахтин В.А. 29 из 46 Analyzing the Effect of Different Programming Models Upon Performance and Memory Usage on Cray XT5 Platforms

Достоинства использования OpenMP вместо MPI для многоядерных процессоров #define Max(a,b) ((a)>(b)?(a):(b)) #define L 8 #define ITMAX 20 int i,j,it,k; double eps, MAXEPS = 0.5; double A[L][L], B[L][L]; int main(int an, char **as) { for (it=1; it < ITMAX; it++) { eps= 0.; for(i=1; j

Достоинства использования OpenMP вместо MPI для многоядерных процессоров Москва, 2012 г. Параллельное программирование с OpenMP: Введение © Бахтин В.А. Для получения программы, способной работать на кластере, необходимо распределить данные и вычисления между процессорами. После распределения данных требуется организовать межпроцессорные взаимодействия. В данном случае - для доступа к удаленным данным используются теневые грани, которые являются источником дублирования данных. 31 из 46

История OpenMP Москва, 2012 г. Параллельное программирование с OpenMP: Введение © Бахтин В.А. 32 из 46 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 OpenMP F/C/C OpenMP F/C/C

OpenMP Architecture Review Board Москва, 2012 г. Параллельное программирование с OpenMP: Введение © Бахтин В.А. 33 из 46 AMD Cray Fujitsu HP IBM Intel NEC The Portland Group, Inc. Oracle Corporation Microsoft Texas Instrument CAPS-Enterprise NVIDIA Convey Computer ANL ASC/LLNL cOMPunity EPCC LANL NASA RWTH Aachen University Texas Advanced Computing Center

Компиляторы, поддерживающие OpenMP Москва, 2012 г. Параллельное программирование с OpenMP: Введение © Бахтин В.А. 34 из 46 OpenMP 3.1: Intel 12.0: Linux, Windows and MacOS Oracle Solaris Studio12.3: Linux and Solaris GNU gcc (4.7.0) OpenMP 3.0: PGI 8.0: Linux and Windows IBM 10.1: Linux and AIX Cray: Cray XT series Linux environment Absoft Pro FortranMP: 11.1 NAG Fortran Complier 5.3 Предыдущие версии OpenMP: Lahey/Fujitsu Fortran 95 PathScale HP Microsoft Visual Studio 2008 C++

Обзор основных возможностей 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 OpenMP: API для написания многонитевых приложений Множество директив компилятора, набор функции библиотеки системы поддержки, переменные окружения Облегчает создание многонитиевых программ на Фортране, C и C++ Обобщение опыта создания параллельных программ для SMP и DSM систем за последние 20 лет OpenMP: API для написания многонитевых приложений Множество директив компилятора, набор функции библиотеки системы поддержки, переменные окружения Облегчает создание многонитиевых программ на Фортране, C и C++ Обобщение опыта создания параллельных программ для SMP и DSM систем за последние 20 лет Москва, 2012 г. Параллельное программирование с OpenMP: Введение © Бахтин В.А. 35 из 46

Все процессоры имеют доступ к любой точке памяти с одинаковой скоростью. Процессоры подключены к памяти либо с помощью общей шины, либо с помощью crossbar-коммутатора. Аппаратно поддерживается когерентность кэшей. Москва, 2012 г. Параллельное программирование с OpenMP: Введение © Бахтин В.А. Cимметричные мультипроцессорные системы (SMP) 36 из 46

Fujitsu SPARC Enterprise M9000 SPARC64 VII 2,88 / 2,52 GHz 64 процессоров, 256 ядер, 512 нитей (Simultaneous Multi Threading) 4TB памяти OS Solaris 10 Москва, 2012 г. Параллельное программирование с OpenMP: Введение © Бахтин В.А. Cимметричные мультипроцессорные системы (SMP) 37 из 46

Системы с неоднородным доступом к памяти (NUMA) Система состоит из однородных базовых модулей (плат), состоящих из небольшого числа процессоров и блока памяти. Модули объединены с помощью высокоскоростного коммутатора. Поддерживается единое адресное пространство. Доступ к локальной памяти в несколько раз быстрее, чем к удаленной. Москва, 2012 г. Параллельное программирование с OpenMP: Введение © Бахтин В.А. 38 из 46

Системы с неоднородным доступом к памяти (NUMA) SGI Altix UV (UltraVioloet) Intel® Xeon® quad-, six- or eight-core 7500 series (2048 cores) 16 TB памяти Interconnect Speed 15 ГБ/с, 1мкс Москва, 2012 г. Параллельное программирование с OpenMP: Введение © Бахтин В.А. 39 из 46

Intel Many Integrated Core (MIC) !dir$ offload target(mic) !$omp parallel do do i=1,10 A(i) = B(i) * C(i) enddo !$omp end parallel Москва, 2012 г. Параллельное программирование с OpenMP: Введение © Бахтин В.А. 40 из 46

Литературa Москва, 2012 г. Параллельное программирование с OpenMP: Введение © Бахтин В.А. 41 из 46

Литература Антонов А.С. Параллельное программирование с использованием технологии OpenMP: Учебное пособие.- М.: Изд-во МГУ, Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. - СПб.: БХВ-Петербург, Гергель В.П. Теория и практика параллельных вычислений. - М.: Интернет-Университет, БИНОМ. Лаборатория знаний, Москва, 2012 г. Параллельное программирование с OpenMP: Введение © Бахтин В.А. 42 из 46

Литература Учебные курсы Интернет Университета Информационных технологий Гергель В.П. Теория и практика параллельных вычислений. Левин М.П. Параллельное программирование с OpenMP Дополнительные учебные курсы: Богданов А.В. и др. Архитектуры и топологии многопроцессорных вычислительных систем. Барский А.Б. Архитектура параллельных вычислительных систем. Барский А.Б. Параллельное программирование. Москва, 2012 г. Параллельное программирование с OpenMP: Введение © Бахтин В.А. 43 из 46

Вопросы? Москва, 2012 г. Параллельное программирование с OpenMP: Введение © Бахтин В.А. 44 из 46

OpenMP – модель параллелизма по управлению Следующая тема Москва, 2012 г. Параллельное программирование с OpenMP: Введение © Бахтин В.А. 45 из 46

Бахтин В.А., кандидат физ.-мат. наук, заведующий сектором, Институт прикладной математики им. М.В.Келдыша РАН Контакты Москва, 2012 г. Параллельное программирование с OpenMP: Введение © Бахтин В.А. 46 из 46