Интернет Университет
Суперкомпьютерных технологий
Введение
Учебный курс
Параллельное программирование с
OpenMP
Бахтин В.А., кандидат физ.-мат. наук,
заведующий сектором,
Институт прикладной математики им.
М.В.Келдыша РАН
Содержание
Тенденции развития современных
процессоров
Существующие подходы для создания
параллельных программ
Основные возможности OpenMP
SMP и DSM - системы
Литература
Москва, 2015 г.
Параллельное программирование с OpenMP: Введение
© Бахтин В.А.
2 из 47
Тенденции развития современных процессоров
В течение нескольких десятилетий развитие ЭВМ сопровождалось
удвоением их быстродействия каждые 1.5-2 года. Это обеспечивалось и
повышением тактовой частоты и совершенствованием архитектуры
(параллельное и конвейерное выполнение команд).
Узким местом стала оперативная память. Знаменитый закон Мура, так
хорошо работающий для процессоров, совершенно не применим для
памяти, где скорости доступа удваиваются в лучшем случае каждые 6
лет.
Совершенствовались системы кэш-памяти, увеличивался объем,
усложнялись алгоритмы ее использования.
Для процессора Intel Itanium:
Latency to L1: 1-2 cycles
Latency to L2: 5 - 7 cycles
Latency to L3: 12 - 21 cycles
Latency to memory: 180 – 225 cycles
Важным параметром становится - GUPS (Giga Updates Per Second)
Москва, 2015 г.
Параллельное программирование с OpenMP: Введение
© Бахтин В.А.
3 из 47
Тенденции развития современных процессоров
Поток
В
П
В
П
В
П
увеличили производительность процессора в 2 раза
Поток
В
П
П
В
П
В
Поток или нить (поанглийски “thread”) –
это легковесный
процесс, имеющий с
другими потоками
общие ресурсы,
включая общую
оперативную память.
Время
В
Поток 3
Поток 2
Поток 1
В
В
В - вычисления
Москва, 2015 г.
П
В
В
П
П
В
П
В
Поток 4
В
П
В
В
П
П
В
П
В
П
П
П
Chip
MultiThreading
П
П - доступ к памяти
Параллельное программирование с OpenMP: Введение
© Бахтин В.А.
Время
4 из 47
Top 500
Москва, 2015 г.
Параллельное программирование с OpenMP: Введение
© Бахтин В.А.
5 из 47
Современные суперкомпьютерные системы
№ 4 в Top 500
Суперкомпьютер K computer, SPARC64 VIIIfx 2.0GHz, Tofu
interconnect
Пиковая производительность - 11280 TFlop/s
Число ядер в системе — 705 024
Производительность на Linpack - 10510 TFlop/s (93.17 % от пиковой)
Энергопотребление комплекса - 12659.89 кВт
Москва, 2015 г.
Параллельное программирование с OpenMP: Введение
© Бахтин В.А.
6 из 47
Современные суперкомпьютерные системы
№ 3 в Top 500
Суперкомпьютер Sequoia, IBM BlueGene/Q, Power BQC 16C 1.6GHz,
Custom interconnect
Пиковая производительность – 20152.66 TFlop/s
Число ядер в системе — 1 572 864
Производительность на Linpack – 16324.75 TFlop/s (81.08 % от
пиковой)
Энергопотребление комплекса - 7890.0 кВт
Важным параметром становится – Power Efficency (Megaflops/watt)
Как добиться максимальной производительности на Ватт => Chip
MultiProcessing, многоядерность.
Москва, 2015 г.
Параллельное программирование с OpenMP: Введение
© Бахтин В.А.
7 из 47
Тенденции развития современных процессоров
AMD Opteron серии 6300
6380 SE 16 ядер @ 2,5 ГГц, 16 МБ
L3 Cache
6348 12 ядер @ 2,8 ГГц, 16 МБ L3
Cache
6328 8 ядер @ 3,2 ГГц, 16 МБ L3
Cache
6308 4 ядра @ 3,5 ГГц, 16 МБ L3
Cache
технология AMD Turbo CORE
встроенный контроллер памяти (4
канала памяти DDR3)
4 канала «точка-точка» с
использованием HyperTransort 3.0
Москва, 2015 г.
Параллельное программирование с OpenMP: Введение
© Бахтин В.А.
8 из 47
Тенденции развития современных процессоров
Intel Xeon Processor серии E5
E5-2699 v3 (45M Cache, 2.30 GHz) 18 ядер, 36 нитей
E5-2698 v3 (40M Cache, 2.30 GHz) 16 ядер, 32 нити
E5-2697 v3 (35M Cache, 2.60 GHz) 14 ядер, 28 нитей
E5-2643 v3 (30M Cache, 3.40 GHz) 6 ядер, 12 нитей
E5-2637 v3 (15M Cache, 3.50 GHz) 4 ядра, 8 нитей
Intel® Turbo Boost
Intel® Hyper-Threading
Intel® Intelligent Power
Intel® QuickPath
Москва, 2015 г.
Параллельное программирование с OpenMP: Введение
© Бахтин В.А.
9 из 47
Тенденции развития современных процессоров
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
Москва, 2015 г.
Параллельное программирование с OpenMP: Введение
© Бахтин В.А.
10 из 47
Тенденции развития современных процессоров
Intel Itanium серии 9500
9560 8 ядер @ 2,53 ГГц, 16 нитей, 32 МБ L3 Cache
9550 4 ядра @ 2,40 ГГц, 8 нитей, 32 МБ L3 Cache
Москва, 2015 г.
Параллельное программирование с OpenMP: Введение
© Бахтин В.А.
11 из 47
Тенденции развития современных процессоров
IBM Power8
2,75 – 4,2 ГГц
12 ядер x 8 нитей
Simultaneuos
MultiThreading
64 КБ Data Cache +
32КБ instruction Cache
L2 512 КБ
L3 96 МБ
www.idh.ch/IBM_TU_2013/Power8.pdf
Москва, 2015 г.
Параллельное программирование с OpenMP: Введение
© Бахтин В.А.
12 из 47
Тенденции развития современных процессоров
Темпы уменьшения латентности памяти гораздо
ниже темпов ускорения процессоров + прогресс в
технологии изготовления кристаллов => CMT
(Chip MultiThreading)
Опережающий рост потребления энергии при
росте тактовой частоты + прогресс в технологии
изготовления кристаллов => CMP (Chip
MultiProcessing, многоядерность)
И то и другое требует более глубокого
распараллеливания для эффективного
использования аппаратуры
Москва, 2015 г.
Параллельное программирование с OpenMP: Введение
© Бахтин В.А.
13 из 47
Существующие подходы для создания
параллельных программ
Автоматическое
/ автоматизированное
распараллеливание
Библиотеки нитей
• Win32 API
• POSIX
Библиотеки
передачи сообщений
• MPI
OpenMP
Москва, 2015 г.
Параллельное программирование с OpenMP: Введение
© Бахтин В.А.
14 из 47
Вычисление числа
1
4.0
(1+x )
4.0
2
dx =
F(x) = 4.0/(1+x2)
0
Мы можем
аппроксимировать интеграл
как сумму прямоугольников:
2.0
N
F(x )x
i
i=0
0.0
Москва, 2015 г.
X
1.0
Где каждый прямоугольник
имеет ширину x и высоту
F(xi) в середине интервала
Параллельное программирование с OpenMP: Введение
© Бахтин В.А.
15 из 47
Вычисление числа . Последовательная
программа.
#include
int main ()
{
int n =100000, i;
double pi, h, sum, x;
h = 1.0 / (double) n;
sum = 0.0;
for (i = 1; i <= n; i ++)
{
x = h * ((double)i - 0.5);
sum += (4.0 / (1.0 + x*x));
}
pi = h * sum;
printf("pi is approximately %.16f”, pi);
return 0;
}
Москва, 2015 г.
Параллельное программирование с OpenMP: Введение
© Бахтин В.А.
16 из 47
Автоматическое распараллеливание
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.
pi.c(8): (col. 5) remark: LOOP WAS VECTORIZED.
В общем случае, автоматическое распараллеливание затруднено:
косвенная индексация (A[B[i]]);
указатели (ассоциация по памяти);
сложный межпроцедурный анализ.
Москва, 2015 г.
Параллельное программирование с OpenMP: Введение
© Бахтин В.А.
17 из 47
Автоматизированное распараллеливание
Intel/GAP (Guided Auto-Parallel), CAPTools/ParaWise,
BERT77, FORGE Magic/DM, ДВОР (Диалоговый
Высокоуровневый Оптимизирующий
Распараллеливатель), САПФОР (Система Автоматизации
Параллелизации ФОРтран программ)
for (i=0; i
if (A[i] > 1) {A[i] += b;}
}
icc -guide -parallel test.cpp
Москва, 2015 г.
Параллельное программирование с OpenMP: Введение
© Бахтин В.А.
18 из 47
Автоматизированное распараллеливание
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
if (A[i] > 0) {A[i] = 1 / A[i];}
if (A[i] > 1) {A[i] += b;}
}
Москва, 2015 г.
Параллельное программирование с OpenMP: Введение
© Бахтин В.А.
19 из 47
Вычисление числа с использованием
Win32 API
#include
#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
for (i=0; i
WaitForMultipleObjects(NUM_THREADS, threadHandles, TRUE,INFINITE);
printf("pi is approximately %.16f”, pi);
}
Москва, 2015 г.
Параллельное программирование с OpenMP: Введение
© Бахтин В.А.
20 из 47
Вычисление числа с использованием
Win32 API
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<= n; i=i+NUM_THREADS)
{
x = h * ((double)i - 0.5);
sum += (4.0 / (1.0 + x*x));
}
EnterCriticalSection(&hCriticalSection);
pi += h * sum;
LeaveCriticalSection(&hCriticalSection);
}
Москва, 2015 г.
Параллельное программирование с OpenMP: Введение
© Бахтин В.А.
21 из 47
Конфликт доступа к данным
При взаимодействии через общую память нити должны синхронизовать
свое выполнение.
Thread0: pi = pi + val; && Thread1: pi = pi + val;
Время
Thread 0
1
LOAD R1,pi
2
LOAD R2,val
3
ADD R1,R2
Thread 1
LOAD R3,pi
4
LOAD R4,val
5
ADD R3,R4
6
STORE R3,pi
7
STORE R1,pi
Результат зависит от порядка выполнения команд. Требуется взаимное
исключение критических интервалов.
Москва, 2015 г.
Параллельное программирование с OpenMP: Введение
© Бахтин В.А.
22 из 47
Вычисление числа с использованием
MPI
#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);
h = 1.0 / (double) n;
sum = 0.0;
Москва, 2015 г.
Параллельное программирование с OpenMP: Введение
© Бахтин В.А.
23 из 47
Вычисление числа с использованием
MPI
for (i = myid + 1; i <= n; i += numprocs)
{
x = h * ((double)i - 0.5);
sum += (4.0 / (1.0 + x*x));
}
mypi = h * sum;
MPI_Reduce(&mypi, &pi, 1, MPI_DOUBLE, MPI_SUM, 0, MPI_COMM_WORLD);
if (myid == 0) printf("pi is approximately %.16f”, pi);
MPI_Finalize();
return 0;
}
Москва, 2015 г.
Параллельное программирование с OpenMP: Введение
© Бахтин В.А.
24 из 47
Вычисление числа c использованием
OpenMP
#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 <= n; i ++)
{
x = h * ((double)i - 0.5);
sum += (4.0 / (1.0 + x*x));
}
pi = h * sum;
printf("pi is approximately %.16f”, pi);
return 0;
}
Москва, 2015 г.
Параллельное программирование с OpenMP: Введение
© Бахтин В.А.
25 из 47
Достоинства использования 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<=L-2; j++)
for(j=1; j<=L-2; j++) {eps = Max(fabs(B[i][j]-A[i][j]),eps); A[i][j] = B[i][j]; }
for(i=1; j<=L-2; j++)
for(j=1; j<=L-2; j++) B[i][j] = (A[i-1][j]+A[i+1][j]+A[i][j-1]+A[i][j+1])/4.;
printf( "it=%4i eps=%fn", it,eps);
if (eps < MAXEPS) break;
}
}
Москва, 2015 г.
Параллельное программирование с OpenMP: Введение
© Бахтин В.А.
26 из 47
Достоинства использования OpenMP вместо MPI
для многоядерных процессоров
Для получения программы,
способной работать на кластере,
необходимо распределить данные и
вычисления между процессорами.
После распределения данных
требуется организовать
межпроцессорные взаимодействия.
В данном случае - для доступа к
удаленным данным используются
“теневые” грани, которые являются
источником дублирования данных.
Москва, 2015 г.
Параллельное программирование с OpenMP: Введение
© Бахтин В.А.
27 из 47
Тесты NAS
BT
3D Навье-Стокс, метод переменных направлений
CG
Оценка наибольшего собственного значения
симметричной разреженной матрицы
EP
Генерация пар случайных чисел Гаусса
FT
IS
LU
Быстрое преобразование Фурье, 3D спектральный
метод
Параллельная сортировка
3D Навье-Стокс, метод верхней релаксации
MG
3D уравнение Пуассона, метод Multigrid
SP
3D Навье-Стокс, Beam-Warning approximate
factorization
Москва, 2015 г.
Параллельное программирование с OpenMP: Введение
© Бахтин В.А.
28 из 47
Тесты NAS
Analyzing the Effect of Different Programming Models Upon Performance
and Memory Usage on Cray XT5 Platforms
https://www.nersc.gov/assets/NERSC-Staff-Publications/2010/Cug2010Shan.pdf
Москва, 2015 г.
Параллельное программирование с OpenMP: Введение
© Бахтин В.А.
29 из 47
Тесты NAS
Analyzing the Effect of Different Programming Models Upon Performance
and Memory Usage on Cray XT5 Platforms
https://www.nersc.gov/assets/NERSC-Staff-Publications/2010/Cug2010Shan.pdf
Москва, 2015 г.
Параллельное программирование с OpenMP: Введение
© Бахтин В.А.
30 из 47
Достоинства использования OpenMP вместо MPI
для многоядерных процессоров(на 1ом узле кластера)
Возможность инкрементального распараллеливания
Упрощение программирования и эффективность на нерегулярных
вычислениях, проводимых над общими данными
Ликвидация дублирования данных в памяти, свойственного MPIпрограммам
Объем памяти пропорционален быстродействию процессора. В
последние годы увеличение производительности процессора
достигается увеличением числа ядер, при этом частота каждого
ядра не увеличивается. Наблюдается тенденция к сокращению
объема оперативной памяти, приходящейся на одно ядро.
Присущая OpenMP экономия памяти становится очень важна.
Наличие локальных и/или разделяемых ядрами КЭШей будут
учитываться при оптимизации OpenMP-программ компиляторами,
что не могут делать компиляторы с последовательных языков для
MPI-процессов.
Москва, 2015 г.
Параллельное программирование с OpenMP: Введение
© Бахтин В.А.
31 из 47
История OpenMP
1998
2002
2005
OpenMP
F/C/C++ 2.5
1997
2011
2013
OpenMP
C/C++ 2.0
OpenMP
C/C++ 1.0
OpenMP
Fortran 1.0
2008
OpenMP
F/C/C++ 3.0
OpenMP
Fortran 1.1
1999
Москва, 2015 г.
OpenMP
Fortran 2.0
Параллельное программирование с OpenMP: Введение
© Бахтин В.А.
OpenMP
F/C/C++ 3.1
OpenMP
F/C/C++ 4.0
32 из 47
OpenMP Architecture Review Board
AMD
Cray
Fujitsu
HP
IBM
Intel
NEC
Oracle Corporation
Texas Instruments
NVIDIA
Convey Computer
ST Microelectronics
Москва, 2015 г.
ANL
ASC/LLNL
cOMPunity
EPCC
LANL
NASA
Red Hat
RWTH Aachen University
Texas Advanced Computing
Center
SNL- Sandia National Lab
BSC - Barcelona
Supercomputing Center
Параллельное программирование с OpenMP: Введение
© Бахтин В.А.
33 из 47
Компиляторы, поддерживающие OpenMP
OpenMP 4.0:
GNU gcc (4.9.0)
Intel 15.0: Linux, Windows and MacOS
OpenMP 3.1:
Oracle Solaris Studio12.3: Linux and Solaris
Cray: Cray XT series Linux environment
LLVM: clang Linux and MacOS
OpenMP 3.0:
PGI 8.0: Linux and Windows
IBM 10.1: Linux and AIX
Absoft Pro FortranMP: 11.1
NAG Fortran Complier 5.3
Предыдущие версии OpenMP:
Lahey/Fujitsu Fortran 95
PathScale
Microsoft Visual Studio 2008 C++
HP
Москва, 2015 г.
Параллельное программирование с OpenMP: Введение
© Бахтин В.А.
34 из 47
Обзор основных возможностей OpenMP
C$OMP FLUSH
OpenMP:
#pragma
omp API
critical
OpenMP:
APIдля
длянаписания
написания
многонитевых
многонитевыхприложений
приложений
C$OMP THREADPRIVATE(/ABC/)
CALL OMP_SET_NUM_THREADS(10)
••Множество
директив
Множество
директивкомпилятора,
компилятора,
CALL
OMP_TEST_LOCK(LCK)
набор
наборфункции
функциибиблиотеки
библиотекисистемы
системы
поддержки,
переменные
окружения
C$OMP MASTER
поддержки,
окружения
CALL OMP_INIT_LOCK (LCK)
C$OMP
ATOMIC переменные
••Облегчает
Облегчаетсоздание
созданиемногонитиевых
многонитиевых
C$OMP SINGLE PRIVATE(X)
на
CCииC++
SETENVпрограмм
OMP_SCHEDULE
“STATIC,4”
программ
наФортране,
Фортране,
C++
•Обобщение опыта
создания
создания
C$OMP PARALLEL DO ORDERED PRIVATE•Обобщение
(A, B, C) опытаC$OMP
ORDERED
параллельных
параллельныхпрограмм
программдля
дляSMP
SMPии
DSM
за последние
DSM
систем
последние20
20лет
лет
C$OMP PARALLEL REDUCTION (+: A,
B) систем
C$OMPзаSECTIONS
C$OMP PARALLEL DO SHARED(A,B,C)
#pragma omp parallel for private(a, b)
C$OMP PARALLEL COPYIN(/blk/)
C$OMP DO LASTPRIVATE(XX)
nthrds = OMP_GET_NUM_PROCS()
Москва, 2015 г.
C$OMP BARRIER
omp_set_lock(lck)
Параллельное программирование с OpenMP: Введение
© Бахтин В.А.
35 из 47
Cимметричные мультипроцессорные системы
(SMP)
Все процессоры имеют доступ к любой точке памяти с одинаковой
скоростью.
Процессоры подключены к памяти либо с помощью общей шины,
либо с помощью crossbar-коммутатора.
Аппаратно поддерживается когерентность кэшей.
Например, серверы HP 9000 V-Class, Convex SPP-1200,…
Москва, 2015 г.
Параллельное программирование с OpenMP: Введение
© Бахтин В.А.
36 из 47
Системы с неоднородным доступом к памяти
(NUMA)
Система состоит из
однородных базовых модулей
(плат), состоящих из
небольшого числа процессоров
и блока памяти.
Модули объединены с
помощью высокоскоростного
коммутатора.
Поддерживается единое
адресное пространство.
Доступ к локальной памяти в
несколько раз быстрее, чем к
удаленной.
Москва, 2015 г.
Параллельное программирование с OpenMP: Введение
© Бахтин В.А.
37 из 47
Системы с неоднородным доступом к памяти
(NUMA)
SGI Altix UV (UltraVioloet) 2000
256 Intel® Xeon® processor E5-4600
product family 2.4GHz-3.3GHz - 2048 Cores
(4096 Threads)
64 TB памяти
NUMAlink6 (NL6; 6.7GB/s bidirectional)
http://www.sgi.com/products/servers/uv/
Москва, 2015 г.
Параллельное программирование с OpenMP: Введение
© Бахтин В.А.
38 из 47
Top 500
Москва, 2015 г.
Параллельное программирование с OpenMP: Введение
© Бахтин В.А.
39 из 47
Top 500
Москва, 2015 г.
Параллельное программирование с OpenMP: Введение
© Бахтин В.А.
40 из 47
Intel Xeon Phi (Many Integrated Core - MIC)
Москва, 2015 г.
Параллельное программирование с OpenMP: Введение
© Бахтин В.А.
41 из 47
Литературa
http://www.openmp.org
http://www.compunity.org
http://www.parallel.ru/tech/tech_dev/openmp.html
Москва, 2015 г.
Параллельное программирование с OpenMP: Введение
© Бахтин В.А.
42 из 47
Литература
Антонов А.С. Параллельное программирование с
использованием технологии OpenMP: Учебное пособие.М.: Изд-во МГУ, 2009.
http://parallel.ru/info/parallel/openmp/OpenMP.pdf
Воеводин В.В., Воеводин Вл.В. Параллельные
вычисления. - СПб.: БХВ-Петербург, 2002.
Гергель В.П. Теория и практика параллельных
вычислений. - М.: Интернет-Университет, БИНОМ.
Лаборатория знаний, 2007.
Москва, 2015 г.
Параллельное программирование с OpenMP: Введение
© Бахтин В.А.
43 из 47
Литература
Учебные курсы Интернет Университета Информационных
технологий
Гергель В.П. Теория и практика параллельных вычислений. —
http://www.intuit.ru/department/calculate/paralltp/
Левин М.П. Параллельное программирование с OpenMP
http://www.intuit.ru/department/se/openmp/
Москва, 2015 г.
Параллельное программирование с OpenMP: Введение
© Бахтин В.А.
44 из 47
Вопросы?
Вопросы?
Москва, 2015 г.
Параллельное программирование с OpenMP: Введение
© Бахтин В.А.
45 из 47
Следующая тема
OpenMP – модель параллелизма по управлению
Москва, 2015 г.
Параллельное программирование с OpenMP: Введение
© Бахтин В.А.
46 из 47
Контакты
Бахтин В.А., кандидат физ.-мат. наук, заведующий
сектором, Институт прикладной математики им.
М.В.Келдыша РАН
bakhtin@keldysh.ru
Москва, 2015 г.
Параллельное программирование с OpenMP: Введение
© Бахтин В.А.
47 из 47