лекции (OpenMP)
Описание файла
Файл "лекции" внутри архива находится в папке "OpenMP". PDF-файл из архива "OpenMP", который расположен в категории "". Всё это находится в предмете "параллельное программирование для высокопроизводительных вычислительных систем" из 11 семестр (3 семестр магистратуры), которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст из PDF
Интернет УниверситетСуперкомпьютерных технологийВведениеУчебный курсПараллельное программирование сOpenMPБахтин В.А., кандидат физ.-мат. наук,заведующий сектором,Институт прикладной математики им.М.В.Келдыша РАНСодержаниеТенденции развития современныхпроцессоров Существующие подходы для созданияпараллельных программ Основные возможности OpenMP SMP и DSM - системы ЛитератураМосква, 2015 г.Параллельное программирование с OpenMP: Введение© Бахтин В.А.2 из 47Тенденции развития современных процессоровВ течение нескольких десятилетий развитие ЭВМ сопровождалосьудвоением их быстродействия каждые 1.5-2 года.
Это обеспечивалось иповышением тактовой частоты и совершенствованием архитектуры(параллельное и конвейерное выполнение команд).Узким местом стала оперативная память. Знаменитый закон Мура, такхорошо работающий для процессоров, совершенно не применим дляпамяти, где скорости доступа удваиваются в лучшем случае каждые 6лет.Совершенствовались системы кэш-памяти, увеличивался объем,усложнялись алгоритмы ее использования.Для процессора Intel Itanium:Latency to L1: 1-2 cyclesLatency to L2: 5 - 7 cyclesLatency to L3: 12 - 21 cyclesLatency to memory: 180 – 225 cyclesВажным параметром становится - GUPS (Giga Updates Per Second)Москва, 2015 г.Параллельное программирование с OpenMP: Введение© Бахтин В.А.3 из 47Тенденции развития современных процессоровПотокВВПВППувеличили производительность процессора в 2 разаПотокВППВПВПоток или нить (поанглийски “thread”) – этолегковесный процесс,имеющий с другимипотоками общиересурсы, включаяобщую оперативнуюпамять.ВремяПоток 3ВПоток 2Поток 1ВВВ - вычисленияМосква, 2015 г.ВПВППВПВПоток 4ВВПВППВПВПППChipMultiThreadingПП - доступ к памятиПараллельное программирование с OpenMP: Введение© Бахтин В.А.Время4 из 47Top 500Москва, 2015 г.Параллельное программирование с OpenMP: Введение© Бахтин В.А.5 из 47Современные суперкомпьютерные системы№ 4 в Top 500Суперкомпьютер K computer, SPARC64 VIIIfx 2.0GHz, Tofuinterconnect Пиковая производительность - 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)Как добиться максимальной производительности на Ватт => ChipMultiProcessing, многоядерность.Москва, 2015 г.Параллельное программирование с OpenMP: Введение© Бахтин В.А.7 из 47Тенденции развития современных процессоровAMD Opteron серии 63006380 SE 16 ядер @ 2,5 ГГц, 16 МБL3 Cache6348 12 ядер @ 2,8 ГГц, 16 МБ L3Cache6328 8 ядер @ 3,2 ГГц, 16 МБ L3Cache6308 4 ядра @ 3,5 ГГц, 16 МБ L3Cacheтехнология AMD Turbo COREвстроенный контроллер памяти (4канала памяти DDR3)4 канала «точка-точка» сиспользованием HyperTransort 3.0Москва, 2015 г.Параллельное программирование с OpenMP: Введение© Бахтин В.А.8 из 47Тенденции развития современных процессоровIntel Xeon Processor серии E5E5-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 BoostIntel® Hyper-ThreadingIntel® Intelligent PowerIntel® QuickPathМосква, 2015 г.Параллельное программирование с OpenMP: Введение© Бахтин В.А.9 из 47Тенденции развития современных процессоровIntel Core i7-3960X Extreme Edition3,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 серии 95009560 8 ядер @ 2,53 ГГц, 16 нитей, 32 МБ L3 Cache9550 4 ядра @ 2,40 ГГц, 8 нитей, 32 МБ L3 CacheМосква, 2015 г.Параллельное программирование с OpenMP: Введение© Бахтин В.А.11 из 47Тенденции развития современных процессоровIBM Power8 2,75 – 4,2 ГГц 12 ядер x 8 нитейSimultaneuosMultiThreading 64 КБ Data Cache +32КБ instruction Cache L2 512 КБ L3 96 МБwww.idh.ch/IBM_TU_2013/Power8.pdfМосква, 2015 г.Параллельное программирование с OpenMP: Введение© Бахтин В.А.12 из 47Тенденции развития современных процессоровТемпы уменьшения латентности памяти гораздониже темпов ускорения процессоров + прогресс втехнологии изготовления кристаллов => CMT (ChipMultiThreading) Опережающий рост потребления энергии приросте тактовой частоты + прогресс в технологииизготовления кристаллов => CMP (ChipMultiProcessing, многоядерность) И то и другое требует более глубокогораспараллеливания для эффективногоиспользования аппаратурыМосква, 2015 г.Параллельное программирование с OpenMP: Введение© Бахтин В.А.13 из 47Существующие подходы для созданияпараллельных программАвтоматическое / автоматизированноераспараллеливание Библиотеки нитей• Win32 API• POSIXБиблиотеки передачи сообщений• MPIOpenMPМосква, 2015 г.Параллельное программирование с OpenMP: Введение© Бахтин В.А.14 из 47Вычисление числа 14.04.0(1+x2)dx = 0Мы можемаппроксимировать интегралкак сумму прямоугольников:2.0N F(x )x ii=00.0Москва, 2015 г.1.0XГде каждый прямоугольникимеет ширину x и высотуF(xi) в середине интервалаПараллельное программирование с OpenMP: Введение© Бахтин В.А.15 из 47Вычисление числа .
Последовательнаяпрограмма.#include <stdio.h>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, UTLicc -parallel pi.cpi.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<n; i++) {if (A[i] > 0) {b=A[i]; A[i] = 1 / A[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 parallelizeddue to conditional assignment(s) into the following variable(s): b.
This loopwill be parallelized if the variable(s) become unconditionally initialized atthe top of every iteration. [VERIFY] Make sure that the value(s) of thevariable(s) read in any iteration of the loop must have been written earlierin the same iteration.test.cpp(49): remark #30525: (PAR) If the trip count of the loop at line 49 isgreater than 188, then use "#pragma loop count min(188)" to parallelizethis loop. [VERIFY] Make sure that the loop has a minimum of 188iterations.#pragma loop count min (188)for (i=0; i<n; i++) {b = A[i];if (A[i] > 0) {A[i] = 1 / A[i];}if (A[i] > 1) {A[i] += b;}}Москва, 2015 г.Параллельное программирование с OpenMP: Введение© Бахтин В.А.19 из 47Вычисление числа с использованиемWin32 API#include <stdio.h>#include <windows.h>#define NUM_THREADS 2CRITICAL_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<NUM_THREADS; i++) threadArg[i] = i+1;InitializeCriticalSection(&hCriticalSection);for (i=0; i<NUM_THREADS; i++) threadHandles[i] =CreateThread(0,0,(LPTHREAD_START_ROUTINE) Pi,&threadArg[i], 0, &threadID);WaitForMultipleObjects(NUM_THREADS, threadHandles, TRUE,INFINITE);printf("pi is approximately %.16f”, pi);}Москва, 2015 г.Параллельное программирование с OpenMP: Введение© Бахтин В.А.20 из 47Вычисление числа с использованиемWin32 APIvoid 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 01LOAD R1,pi2LOAD R2,val3ADD R1,R2Thread 1LOAD R3,pi4LOAD R4,val5ADD R3,R46STORE R3,pi7STORE R1,piРезультат зависит от порядка выполнения команд.
Требуется взаимноеисключение критических интервалов.Москва, 2015 г.Параллельное программирование с OpenMP: Введение© Бахтин В.А.22 из 47Вычисление числа с использованиемMPI#include "mpi.h"#include <stdio.h>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Вычисление числа с использованиемMPIfor (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 <stdio.h>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 20int 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=%f\n", it,eps);if (eps < MAXEPS) break;}}Москва, 2015 г.Параллельное программирование с OpenMP: Введение© Бахтин В.А.26 из 47Достоинства использования OpenMP вместо MPIдля многоядерных процессоров Для получения программы, способнойработать на кластере, необходимораспределить данные и вычислениямежду процессорами. После распределения данныхтребуется организоватьмежпроцессорные взаимодействия.В данном случае - для доступа кудаленным данным используются“теневые” грани, которые являютсяисточником дублирования данных.Москва, 2015 г.Параллельное программирование с OpenMP: Введение© Бахтин В.А.27 из 47Тесты NASBT3D Навье-Стокс, метод переменных направленийCGОценка наибольшего собственного значениясимметричной разреженной матрицыEPГенерация пар случайных чисел ГауссаFTISLUБыстрое преобразование Фурье, 3D спектральныйметодПараллельная сортировка3D Навье-Стокс, метод верхней релаксацииMG3D уравнение Пуассона, метод MultigridSP3D Навье-Стокс, Beam-Warning approximatefactorizationМосква, 2015 г.Параллельное программирование с OpenMP: Введение© Бахтин В.А.28 из 47Тесты NASAnalyzing the Effect of Different Programming Models Upon Performanceand Memory Usage on Cray XT5 Platformshttps://www.nersc.gov/assets/NERSC-Staff-Publications/2010/Cug2010Shan.pdfМосква, 2015 г.Параллельное программирование с OpenMP: Введение© Бахтин В.А.29 из 47Тесты NASAnalyzing the Effect of Different Programming Models Upon Performanceand Memory Usage on Cray XT5 Platformshttps://www.nersc.gov/assets/NERSC-Staff-Publications/2010/Cug2010Shan.pdfМосква, 2015 г.Параллельное программирование с OpenMP: Введение© Бахтин В.А.30 из 47Достоинства использования OpenMP вместо MPIдля многоядерных процессоров(на 1ом узле кластера)Возможность инкрементального распараллеливанияУпрощение программирования и эффективность на нерегулярныхвычислениях, проводимых над общими даннымиЛиквидация дублирования данных в памяти, свойственного MPIпрограммамОбъем памяти пропорционален быстродействию процессора.