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

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

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

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

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

Тенденции развития современных процессоров AMD Opteron серии 6100 (Magny- Cours) 6176 SE 12 2,3 ГГц, 12 МБ L3 Cache ,4 ГГц, 12 МБ L3 Cache встроенный контроллер памяти (4 канала памяти DDR3) 4 канала «точка-точка» с использованием HyperTransort 3.0 Москва, 2010 г. Параллельное программирование с OpenMP: Введение © Бахтин В.А. 6 из 40

Тенденции развития современных процессоров Москва, 2010 г. Параллельное программирование с OpenMP: Введение © Бахтин В.А. Intel Xeon серии 5600 (Nehalem) X ,33 ГГц, 12 нитей, 12 МБ L3 Cache X ,46 ГГц, 8 нитей, 12 МБ L3 Cache Intel® Turbo Boost Intel® Hyper-Threading Intel® QuickPath Intel® Intelligent Power 7 из 40

Тенденции развития современных процессоров Intel Core i7 980X (Gulftown) 3,33 ГГц 6 ядeр 12 потоков с технологией Intel Hyper-Threading 12 МБ кэш-памяти Intel Smart Cache встроенный контроллер памяти (3 канала памяти DDR МГц ) технология Intel QuickPath Interconnect Москва, 2010 г. Параллельное программирование с OpenMP: Введение © Бахтин В.А. 8 из 40

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

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

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

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

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

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

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

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

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

#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]]); указатели (ассоциация по памяти); сложный межпроцедурный анализ. Москва, 2010 г. Параллельное программирование с OpenMP: Введение © Бахтин В.А. 19 из 40

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

Автоматизированное распараллеливание 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;} } Москва, 2010 г. Параллельное программирование с OpenMP: Введение © Бахтин В.А. 21 из 40

#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

Москва, 2010 г. Параллельное программирование с OpenMP: Введение © Бахтин В.А. 24 из 40 При взаимодействии через общую память нити должны синхронизовать свое выполнение. int i=0; Thread0: i++; Thread1: i++; ВремяThread0Thread1 1load i (i = 0) 2incr i (i = 1) 3->load i (i = 0) 4incr i (i = 1) 5store i (i = 1) 6

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

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

Достоинства использования OpenMP вместо MPI для многоядерных процессоров Процессоры Intel® Xeon® серии KX HE 6 cores 41QS HE 4 cores 2200 MHz2500 MHz Процессоры Intel® Xeon® серии 7000 Процессоры AMD Opteron серии 4100 Москва, 2010 г. Параллельное программирование с OpenMP: Введение © Бахтин В.А. X cores X cores 3330 MHz3460 MHz X cores X cores 2226 MHz2666 MHz 29 из 40

Достоинства использования 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 для многоядерных процессоров Москва, 2010 г. Параллельное программирование с OpenMP: Введение © Бахтин В.А. Для получения программы, способной работать на кластере, необходимо распределить данные и вычисления между процессорами. После распределения данных требуется организовать межпроцессорные взаимодействия. В данном случае - для доступа к удаленным данным используются теневые грани, которые являются источником дублирования данных. После распределения данных требуется организовать межпроцессорные взаимодействия. В данном случае - для доступа к удаленным данным используются теневые грани, которые являются источником дублирования данных. 31 из 40

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

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

Компиляторы, поддеживающие 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 2010 C++ Москва, 2010 г. Параллельное программирование с OpenMP: Введение © Бахтин В.А. 34 из 40

Обзор основных возможностей 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 лет Москва, 2010 г. Параллельное программирование с OpenMP: Введение © Бахтин В.А. 35 из 40

Литература… Москва, 2010 г. Параллельное программирование с OpenMP: Введение © Бахтин В.А. 36 из 40

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

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

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

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

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