Презентація на тему:
Програмування паралельних систем:

Програмування паралельних систем: кластери, багатоядерні та графічні процесори Канд. фіз.-мат. наук, доцент Єршов Сергій Володимирович Європейський Університет кафедра інформаційних систем та технологій Єршов С.В. Online лекція заняття курсів з підвищення кваліфікації © 2011 ЄУ

- * - Сучасні засоби програмування паралельних систем MPI (Message Passing Interface, інтерфейс передачі повідомлень) - стандарт програмного інтерфейсу для паралельних систем із розподіленою пам’яттю (мультикомп’ютери, кластери). Існують реалізації для мов C++, C, Fortran, Java. Open Multi-Processing (OpenMP) - стандарт програмного інтерфейсу для паралельних систем із спільною пам'яттю (багатоядерні системи). Підтримує мови C, C++, Fortran. CUDA (Compute Unified Device Architecture) – програмно-апаратна архітектура, що дозволяє здійснювати паралельні обчислення на спеціальному спрощеному діалекті мови програмування С з використанням графічних процесорів NVIDIA. Єршов С.В. Online лекція заняття курсів з підвищення кваліфікації © 2011 ЄУ

- * - Message Passing Interface (MPI) розподіляти обчислювальне навантаження, організувати інформаційну взаємодію (передачу даних) між процесорами. Вирішення всіх перерахованих питань забезпечує MPI-інтерфейс передачі даних (message passing interface) В обчислювальних системах з розподіленою пам'яттю процесори працюють незалежно один від одного. Для організації паралельних обчислень необхідно уміти: Єршов С.В. Online лекція заняття курсів з підвищення кваліфікації © 2011 ЄУ

- * - Розробка паралельних програм з використанням MPI Основи MPI Іниціализація та завершенння MPI програм структура паралельної програми, яка розроблена з використанням MPI, має наступний вигляд: #include "mpi.h" int main ( int argc, char *argv[] ) { MPI_Init ( &agrc, &argv ); MPI_Finalize(); return 0; } Єршов С.В. Online лекція заняття курсів з підвищення кваліфікації © 2011 ЄУ

- * - Область взаємодії описується спеціальною структурою - комунікатором Єршов С.В. Online лекція заняття курсів з підвищення кваліфікації © 2011 ЄУ

- * - Розробка паралельних програм з використанням MPI Основи MPI Визначення кількості та рангу процесів Як правило, виклик функцій MPI_Comm_size та MPI_Comm_rank виконується відразу після MPI_Init: #include "mpi.h" int main ( int argc, char *argv[] ) { int ProcNum, ProcRank; MPI_Init ( &agrc, &argv ); MPI_Comm_size ( MPI_COMM_WORLD, &ProcNum); MPI_Comm_rank ( MPI_COMM_WORLD, &ProcRank); MPI_Finalize(); return 0; } Єршов С.В. Online лекція заняття курсів з підвищення кваліфікації © 2011 ЄУ

- * - Розробка паралельних програм з використанням MPI Основи MPI Паралельна програма з використанням MPI #include " mpi.h " int main(int argc, char* argv[]) { int ProcNum, ProcRank, RecvRank; MPI_Status Status; MPI_Init(&argc, &argv); MPI_Comm_size(MPI_COMM_WORLD, &ProcNum); MPI_Comm_rank(MPI_COMM_WORLD, &ProcRank); if ( ProcRank == 0 ) { // Дії для процесу 0 printf ("\n Hello from process %3d", ProcRank); for ( int i=1; i < ProcNum; i++ ) { MPI_Recv(&RecvRank, 1, MPI_INT, MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &Status); printf("\n Hello from process %3d", RecvRank); } } else // Дії для всіх процесів, окрім процесу 0 MPI_Send(&ProcRank,1,MPI_INT,0,0,MPI_COMM_WORLD); // Завершення роботи MPI_Finalize(); return 0; } Єршов С.В. Online лекція заняття курсів з підвищення кваліфікації © 2011 ЄУ

- * - Форми обміну повідомленнями Двоточковий обмін (point-to-point) Односторонній обмін Єршов С.В. Online лекція заняття курсів з підвищення кваліфікації © 2011 ЄУ

- * - Блокуючий обмін повідомленнями процес 1 процес 2 БЛОКУВАННЯ БЛОКУВАННЯ “КВИТАНЦІЯ” Send(buf, 2) Recv(buf, 1) ЧАС Єршов С.В. Online лекція заняття курсів з підвищення кваліфікації © 2011 ЄУ

- * - Неблокуючий обмін повідомленнями процес 1 процес 2 Send(buf, 2) Recv(buf, 1) ЧАС Test(1)->false Test(1)->false Test(1)->false Test(1)->true Єршов С.В. Online лекція заняття курсів з підвищення кваліфікації © 2011 ЄУ

- * - Розробка паралельних програм з використанням MPI Знайомство з колективними операціями передачі даних Передача даних від одного процесу всім процесам програми Функція MPI_Bcast здійснює розсилку даних з буфера buf, що містить count елементів типу type з процесу, який має номер root, всім процесам, що входять в комунікатор comm Єршов С.В. Online лекція заняття курсів з підвищення кваліфікації © 2011 ЄУ

- * - Розробка паралельних програм з використанням MPI Знайомство з колективними операціями передачі даних Передача даних від всіх процесів одному процесу Процедура збору і подальшого підсумовування даних - приклад часто виконуваної колективної операції передачі даних від всіх процесів одному процесу, у якій над збираними значеннями здійснюється обробка даних. Єршов С.В. Online лекція заняття курсів з підвищення кваліфікації © 2011 ЄУ

- * - Приклад: Обчислення числа Значення числа може бути отримано за допомогою інтеграла Для чисельного інтегрування застосуємо метод прямокутників Єршов С.В. Online лекція заняття курсів з підвищення кваліфікації © 2011 ЄУ

- * - Розподілимо обчислення між p процесорами (циклічна схема) Отримувані на окремих процесорах часткові суми мають бути підсумовані Приклад: Обчислення числа - Процесор 0 - Процесор 1 - Процесор 2 Єршов С.В. Online лекція заняття курсів з підвищення кваліфікації © 2011 ЄУ

- * - #include "mpi.h" #include double f(double a) { return (4.0 / (1.0 + a*a)); } int main(int argc, char *argv) { int ProcRank, ProcNum, done = 0, n = 0, i; double PI25DT = 3.141592653589793238462643; double mypi, pi, h, sum, x, t1, t2; MPI_Init(&argc,&argv); MPI_Comm_size(MPI_COMM_WORLD,&ProcNum); MPI_Comm_rank(MPI_COMM_WORLD,&ProcRank); while (!done ) { // основний цикл обчислень if ( ProcRank == 0) { printf("Enter the number of intervals: "); scanf("%d",&n); t1 = MPI_Wtime(); } Приклад: Обчислення числа Єршов С.В. Online лекція заняття курсів з підвищення кваліфікації © 2011 ЄУ

- * - Приклад: Обчислення числа MPI_Bcast(&n, 1, MPI_INT, 0, MPI_COMM_WORLD); if (n > 0) { // обчислення локальних сум h = 1.0 / (double) n; sum = 0.0; for (i = ProcRank + 1; i

- * - Час Тенденції розвитку сучасних процесорів О П О П О П О П О П О П Потік Потік Час О П О П О П Потік 1 О П О П О П О П О П О П О П О П О П Потік 2 Потік 3 Потік 4 В - обчислення П - доступ до пам’яті Chip MultiThreading збільшили продуктивність процесора в 2 рази Потік (“thread”) – це легковагий процес, що має з іншими потоками спільні ресурси, в тому числі спільну оперативну пам'ять. Єршов С.В. Online лекція заняття курсів з підвищення кваліфікації © 2011 ЄУ

- * - Intel Xeon серії 5600 (Nehalem) X5680 6 ядер @ 3,33 ГГц, 12 потоків, 12 МБ L3 Cache X5677 4 ядра @ 3,46 ГГц, 8 потоків, 12 МБ L3 Cache Intel® Turbo Boost Intel® Hyper-Threading Intel® QuickPath Intel® Intelligent Power Тенденції розвитку сучасних процесорів Єршов С.В. Online лекція заняття курсів з підвищення кваліфікації © 2011 ЄУ

- * - Переваги використання OpenMP замість MPI для багатоядерних процесорів Можливість інкрементального розпаралелювання Спрощення програмування і ефективність на нерегулярних обчисленнях, що проводяться над спільними даними Ліквідація дублювання даних в пам'яті, що властиве MPI-програмам Останніми роками спостерігається тенденція до скорочення обсягу оперативної пам'яті, що виділяється на одне ядро. Властива OpenMP економія пам’яті стає дуже важливою. Наявність локальних КЕШів (і/або таких, що розділяються ядрами) враховуватиметься при оптимізації OpenMP-програм компіляторами, що не можуть робити компілятори послідовних мов для MPI-процесів. Єршов С.В. Online лекція заняття курсів з підвищення кваліфікації © 2011 ЄУ

- * - Виконання OpenMP-програми Fork-Join паралелізм: Головний (master) потік породжує групу (team) потоків за мірою необхідності. Паралелізм додається інкрементально. Паралельні області Єршов С.В. Online лекція заняття курсів з підвищення кваліфікації © 2011 ЄУ

- * - 001 Модель пам’яті в OpenMP Потік 001 Потік 001 Потік Єршов С.В. Online лекція заняття курсів з підвищення кваліфікації © 2011 ЄУ

- * - 001 Модель пам’яті в OpenMP Потік 0 001 Потік 1 static int i = 0; … = i + 1; i = i + 1; i = 0 i = 1 … = i + 2; // ? #pragma omp flush (i) #pragma omp flush (i) i = 1 i = 1 Єршов С.В. Online лекція заняття курсів з підвищення кваліфікації © 2011 ЄУ

- * - Класи перемінних double Array1[100]; int main() { int Array2[100]; #pragma omp parallel { int iam = omp_get_thread_num(); work(Array2, iam); printf(“%d\n”, Array2[0]); } } extern double Array1[100]; void work(int *Array, int iam) { double TempArray[100]; static int count; ... } TempArray,iam TempArray,iam TempArray, iam Array1, Array2, count Array1, Array2, count Єршов С.В. Online лекція заняття курсів з підвищення кваліфікації © 2011 ЄУ

- * - #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

- * - Використання директиви task typedef struct node node; struct node { int data; node * next; }; void increment_list_items(node * head) { #pragma omp parallel { #pragma omp single { node * p = head; while (p) { #pragma omp task process(p); p = p->next; } } } } Єршов С.В. Online лекція заняття курсів з підвищення кваліфікації © 2011 ЄУ

- * - Програмна модель CUDA Масштабованість на десятки ядер, сотні паралельних потоків Дозволяє сфокусуватися на розробці паралельних алгоритмів – А не внутрішніх засобах мови програмування Підтримує гетерогенні обчислення –CPU для послідовного коду, GPU – для паралельного Єршов С.В. Online лекція заняття курсів з підвищення кваліфікації © 2011 ЄУ

- * - Масивно-паралельні системи на основі архітектури CUDA Мультипроцесор Tesla 10 Єршов С.В. Online лекція заняття курсів з підвищення кваліфікації © 2011 ЄУ

- * - Масивно-паралельні системи на основі архітектури CUDA Interconnection Network ROP L2 ROP L2 ROP L2 ROP L2 ROP L2 ROP L2 ROP L2 ROP L2 DRAM DRAM DRAM DRAM DRAM DRAM DRAM DRAM CPU Bridge Host Memory Архітектура Tesla 10 Єршов С.В. Online лекція заняття курсів з підвищення кваліфікації © 2011 ЄУ

- * - Програмна модель CUDA GPU (device) - це обчислювальний пристрій, який: Є співпроцесором до CPU (host) Має власну пам'ять (DRAM) Виконує одночасно дуже багато ниток Паралельна частина коду виконується як велика кількість потоків Потоки групуються в блоки фіксованого розміру Блоки об'єднуються в сітку блоків Ядро виконується на сітці з блоків Кожний потік і блок мають свій ідентифікатор Єршов С.В. Online лекція заняття курсів з підвищення кваліфікації © 2011 ЄУ

- * - Програмна модель CUDA Десятки тисяч потоків for (int ix = 0; ix < nx; ix++) { pData[ix] = f(ix); } for (int ix = 0; ix < nx; ix++) for (int iy = 0; iy < ny; iy++) { pData[ix + iy * nx] = f(ix) * g(iy); } for (int ix = 0; ix < nx; ix++) for (int iy = 0; iy < ny; iy++) for (int iz = 0; iz < nz; iz++) { pData[ix + (iy + iz * ny) * nx] = f(ix) * g(iy) * h(iz); } Єршов С.В. Online лекція заняття курсів з підвищення кваліфікації © 2011 ЄУ

- * - Програмна модель CUDA Потоки в CUDA об’єднуються в блоки: Можлива 1D, 2D, 3D топологія блоку Загальна кількість потоків в блоці є обмежена У сучасному HW це 512 потоків Єршов С.В. Online лекція заняття курсів з підвищення кваліфікації © 2011 ЄУ

- * - Програмна модель CUDA Потоки в одному блоці можуть розділяти ресурси зі своїми сусідами float g_Data[gN]; for (int ix = 0; ix < nx; ix++) { pData[ix] = f(ix, g_Data[ix / n]); } Єршов С.В. Online лекція заняття курсів з підвищення кваліфікації © 2011 ЄУ

- * - Програмна модель CUDA Блоки потоків об’єднуються в сітку (grid) потоків Можлива 1D, 2D топологія сітки блоків потоків Єршов С.В. Online лекція заняття курсів з підвищення кваліфікації © 2011 ЄУ

- * - Синтаксис CUDA CUDA – це розширення мови C [+] специфікатори для функцій та перемінних [+] нові вбудовані типи [+] вбудовані перемінні (усередині ядра) [+] директива для запуску ядра з C коду Як скомпілювати CUDA код [+] nvcc компілятор [+] .cu розширення файлу Єршов С.В. Online лекція заняття курсів з підвищення кваліфікації © 2011 ЄУ

- * - Синтаксис CUDA Порівняємо код для CPU з кодом CUDA kernel: __global__ void incKernel ( float * pData ) { int idx = blockIdx.x * blockDim.x + threadIdx.x; pData [idx] = pData [idx] + 1.0f; } float * pData; for (int ix = 0; ix < nx; ix++) { pData[ix] = pData[ix] + 1.0f; } nx = 2048 У блоці 256 потоків кількість блоків = 2048 / 256 = 8 [ 0 .. 7 ] [ == 256] [ 0 .. 255 ] Єршов С.В. Online лекція заняття курсів з підвищення кваліфікації © 2011 ЄУ

- * - Синтаксис CUDA. Директиви запуску ядра Як запустити ядро із загальною кількістю потоків, що дорівнює nx? incKernel ( pData ); dim3 threads(256, 1, 1); dim3 blocks(nx / 256, 1); float * pData; > кутові дужки, усередині яких задаються параметри запуску ядра: Кількість блоків в сітці Кількість потоків у блоці … Неявно припускаємо, що nx кратне 256 Єршов С.В. Online лекція заняття курсів з підвищення кваліфікації © 2011 ЄУ

- * - Типи пам’яті в CUDA Тип пам’яті Доступ Рівень виділення Швидкість роботи Регістри R/W Per-thread Висока (on-chip) Локальна R/W Per-thread Низька (DRAM) Shared R/W Per-block Висока (on-chip) Глобальна R/W Per-grid Низька (DRAM) Constant R/O Per-grid Висока (L1 cache) Texture R/O Per-grid Висока (L1 cache) Єршов С.В. Online лекція заняття курсів з підвищення кваліфікації © 2011 ЄУ

- * - Множення матриць в CUDA #define BLOCK_SIZE 16 __global__ void matMult (float* a, float* b, int n, float* c) { int bx = blockIdx.x; int by = blockIdx.y; int tx = threadIdx.x; int ty = threadIdx.y; float sum = 0.0f; int ia = n * BLOCK_SIZE * by + n * ty; int ib = BLOCK_SIZE * bx + tx; int ic = n * BLOCK_SIZE * by + BLOCK_SIZE * bx; for ( int k = 0; k < n; k++ ) sum += a [ia + k] * b [ib + k*n]; c [ic + n * ty + tx] = sum; } Єршов С.В. Online лекція заняття курсів з підвищення кваліфікації © 2011 ЄУ

- * - Множення матриць в CUDA int numBytes = N * N * sizeof ( float ); float * adev, * bdev, * cdev ; dim3 threads ( BLOCK_SIZE, BLOCK_SIZE ); dim3 blocks ( N / threads.x, N / threads.y); cudaMalloc ( (void**)&adev, numBytes ); // allocate DRAM cudaMalloc ( (void**)&bdev, numBytes ); // allocate DRAM cudaMalloc ( (void**)&cdev, numBytes ); // allocate DRAM // copy from CPU to DRAM cudaMemcpy ( adev, a, numBytes, cudaMemcpyHostToDevice ); cudaMemcpy ( bdev, b, numBytes, cudaMemcpyHostToDevice ); matMult ( adev, bdev, N, cdev ); cudaThreadSynchronize(); cudaMemcpy ( c, cdev, numBytes, cudaMemcpyDeviceToHost ); // free GPU memory cudaFree ( adev ); cudaFree ( bdev ); cudaFree ( cdev ); Єршов С.В. Online лекція заняття курсів з підвищення кваліфікації © 2011 ЄУ

- * - Актуальні засоби програмування паралельних систем MPI (Message Passing Interface, інтерфейс передачі повідомлень) - стандарт програмного інтерфейсу для паралельних систем із розподіленою пам’яттю (мультикомп’ютери, кластери). Open Multi-Processing (OpenMP) - стандарт програмного інтерфейсу для паралельних систем із спільною пам'яттю (багатоядерні системи). CUDA (Compute Unified Device Architecture) – програмно-апаратна архітектура, що дозволяє здійснювати паралельні обчислення з використанням графічних процесорів NVIDIA. Єршов С.В. Online лекція заняття курсів з підвищення кваліфікації © 2011 ЄУ

- * - Запитання? Єршов С.В. Online лекція заняття курсів з підвищення кваліфікації © 2011 ЄУ