Intel® Cilk TM Plus Введение Лекция 1. Программные инструменты параллелизма Немнюгин Сергей Андреевич

2 Содержание 1.Эволюция вычислительных технологий. 2.Последовательное и параллельное программирование. 3.Парадигмы параллельного программирования. 4.Программные инструменты параллелизма.

3 Эволюция вычислительных технологий

4 От фоннеймановской архитектуры к архитектуре многоядерной –Фоннеймановская архитектура –Как эволюционировала архитектура вычислительных систем –Эволюция программных технологий Фоннеймановская архитектура последовательная, скалярная. В «классическом» фоннеймановском компьютере параллелизм отсутствует на всех уровнях. Традиционная последовательная модель программирования, ориентированная на SISD архитектуры (по Флинну). Языки последовательного программирования.

5 Пользователю нужна производительность. Увеличение производительности позволяет: - решать новые, более сложные задачи; - решать старые задачи, но быстрее; - решать старые задачи, но с более высокой точностью. Многие расширения фоннеймановской архитектуры используют параллелизм на разном уровне

6 Вычислительные системы с распределённой памятью (кластеры, MIMD по классификации Флинна) от небольших кластеров до суперкомпьютеров, занимающих первые позиции в рейтинге Top 500 Supercomputers..

7 Многоядерные архитектуры стали доминирующими Электропитание и управление Память Кэш-память большого объёма Масштабируемая архитектура ЯдроЯдро ЯдроЯдро ЯдроЯдро Первые многоядерные процессоры появились на рынке в 2005 году. Сейчас это доминирующий тип архитектур. Вычислительная система с многоядерным процессором – параллельная вычислительная система с общей памятью, обычно SMP (Symmetric Multiprocessor System).

8 От архитектуры multicore (с небольшой многоядерностью) к архитектуре manycore (с большой многоядерностью) Архитектура Intel® Many Integrated Core (MIC) – шаг к системам с большой многоядерностью, от 32-ядерного прототипа к системам с десятками, сотнями и т.д. ядер

9 Параллельное и последовательное программирование

10 Что происходит с данными внутри программы. Информационный граф программы Алгоритм можно представить в виде диаграммы информационного графа. Информационный граф описывает последовательность выполнения операций и взаимную зависимость между различными операциями или блоками операций. Узлами информационного графа являются операции, а однонаправленными дугами каналы обмена данными. Понятие операции может трактоваться расширенно. Это может быть оператор языка, но может быть и более крупный блок программы.

11 Последовательная и параллельная модели программирования Традиционной считается последовательная модель программирования. В этом случае в любой момент времени выполняется только одна операция и только над одним элементом данных. Последовательная модель универсальна. Ее основными чертами являются применение стандартных языков программирования (для решения вычислительных задач это, обычно, Fortran и С/С++), хорошая переносимость программ и невысокая производительность. Основными особенностями параллельной модели программирования являются более высокая производительность программ, применение специальных приемов программирования и, как следствие, более высокая трудоемкость программирования, проблемы с переносимостью программ. Параллельная модель не обладает свойством универсальности.

12 Параллельная модель программирования В параллельной модели программирования появляются проблемы, непривычные для программиста, привыкшего заниматься последовательным программированием. Среди них: управление работой множества процессоров, организация межпроцессорных пересылок данных и другие. Повышенная трудоёмкость параллельного программирования связана с тем, что программист должен заботиться: об управлении работой множества процессов; об организации межпроцессных пересылок данных; о вероятности тупиковых ситуаций (взаимных блокировках); о нелокальном и динамическом характере ошибок; о возможной утрате детерминизма («гонки за данными»); о масштабируемости; о сбалансированной загрузке вычислительных узлов.

13 Параллельная модель программирования В параллельной модели программирования появляются проблемы, непривычные для программиста, привыкшего заниматься последовательным программированием. Среди них: управление работой множества процессоров, организация межпроцессорных пересылок данных и другие. Повышенная трудоёмкость параллельного программирования связана с тем, что программист должен заботиться: об управлении работой множества процессов; об организации межпроцессных пересылок данных; о вероятности тупиковых ситуаций (взаимных блокировках); о нелокальном и динамическом характере ошибок; о возможной утрате детерминизма («гонки за данными»); о масштабируемости; о сбалансированной загрузке вычислительных узлов.

14 Парадигмы параллельного программирования

15 Парадигмы параллельного программирования Параллелизм данных -одна операция применяется сразу к нескольким элементам массива данных. Различные фрагменты такого массива обрабатываются на векторном процессоре или на разных процессорах параллельной машины; -обработкой данных управляет одна программа; -пространство имен является глобальным; -параллельные операции над элементами массива выполняются одновременно на всех доступных данной программе процессорах. От программиста требуется: задание опций векторной или параллельной оптимизации транслятору; задание директив параллельной компиляции; использование специализированных языков параллельных вычислений, а также библиотек подпрограмм, специально разработанных с учетом конкретной архитектуры компьютера и оптимизированных для этой архитектуры.

16 Парадигмы параллельного программирования Параллелизм задач -вычислительная задача разбивается на несколько относительно самостоятельных подзадач. Каждая подзадача выполняется на своем процессоре (ориентация на архитектуру MIMD); -для каждой подзадачи пишется своя собственная программа на обычном языке программирования (чаще всего это Fortran или С); -подзадачи должны обмениваться результатами своей работы, получать исходные данные. Практически такой обмен осуществляется вызовом процедур специализированной библиотеки. Программист при этом может контролировать распределение данных между различными процессорами и различными подзадачами, а также обмен данными.

17 Программные инструменты параллелизма

Системные вызовы операционной системы (UNIX/Linux) IPC (InterProcess Communications) именованные каналы; общая память; сообщения; семафоры. Низкоуровневые средства

Клиент #include #include "mesg.h" main() { message message; key_tkey; int msgid, length, n; if ((key = ftok("server", 'A')) < 0){ printf("Невозможно получить ключ\n"); exit(1); } message.mtype=1L; if ((msgid = msgget(key, PERM | IPC_CREAT)) < 0){ printf("Невозможно создать очередь\n"); exit(1); } n = msgrcv(msgid, &message, sizeof(message), message.mtype, 0); if (n > 0) { if (write(1, message.buff, n) != n) { printf("Ошибка вывода\n"); exit(1); } } else { printf("Ошибка чтения сообщения\n"); exit(1); } exit(0); } IPC. Сообщения. Пример

Сервер #include #include "mesg.h" main() { Messagemessage; key_tkey; intmsgid, length; message.mtype = 1L; if ((key = ftok("server", 'A')) < 0){ printf("Невозможно получить ключ\n"); exit(1); } if ((msgid = msgget(key, 0)) < 0){ printf("Невозможно получить доступ к очереди\n"); exit(1); } if ((length = sprintf(message.buff, "Здравствуй, Мир!\n")) < 0){ printf("Ошибка копирования в буфер\n"); exit(1); } if (msgsnd(msgid, (void *) &message, length, 0) !=0){ printf("Ошибка записи сообщения в очередь\n"); exit(1); } if (msgctl(msgid, IPC_RMID, 0) < 0){ printf("Ошибка удаления очереди\n"); exit(1); } exit(0); } IPC. Сообщения. Пример

POSIX Threads - стандарт POSIX реализации потоков (нитей) выполнения, определяющий API для создания и управления ими. Ссылка POSIX Threads

#include #include "gettimeofday.h" #include #define gNumThreads 1 #define N double a[N + 1], b[N + 1], sum; int i, j; double start, stop; const int gNumSteps = N; double gVectorSum = 0; void *threadFunction(void *arg) { int i; int myNum = *((int *)arg); double partialSum = 0; // local to each thread for ( i = myNum; i < gNumSteps; i += gNumThreads ) // use every gNumThreads-th step { partialSum += a[i] * b[i]; //compute partial sums at each thread } gVectorSum += partialSum; // add partial to global final answer return 0; } POSIX Threads. Пример

int main() { pthread_t tid[gNumThreads]; int tNum[gNumThreads], i, j; // initialize vector for (j = 0; j < N; j++) { a[j] = 1.031; b[j] = 1.057; } printf("Computed value of vector sum: "); start = wcgettimeofday(); for (i = 0; i < gNumThreads; i++) { tNum[i] = i; pthread_create(&tid[i], NULL, threadFunction, &tNum[i]); } for (i = 0; i < gNumThreads; i++) pthread_join(tid[i], NULL); stop = wcgettimeofday(); printf("sum = %f\n", gVectorSum); printf("time = %g\n", stop - start); }

В Microsoft Windows имеется возможность разработки многопоточных приложений на C++ с помощью «стандартных» системных средств – прикладного программного интерфейса операционной системы. Ссылка Windows API

#include #define N double a[N + 1], b[N + 1], sum; int i, j; double start, stop; const int gNumSteps = N; const int gNumThreads = 1; double gVectorSum = 0; CRITICAL_SECTION gCS; DWORD WINAPI threadFunction(LPVOID pArg) { int i; int myNum = *((int *)pArg); double partialSum = 0; // local to each thread for ( i = myNum*(gNumSteps / gNumThreads); i < (myNum+1)*(gNumSteps / gNumThreads); i++ ) // use every gNumThreads-th step { partialSum += a[i] * b[i]; //compute partial sums at each thread } EnterCriticalSection(&gCS); gVectorSum += partialSum; // add partial to global final answer LeaveCriticalSection(&gCS); return 0; } Windows API. Пример

int main() { HANDLE threadHandles[gNumThreads]; int tNum[gNumThreads], i, j; for (j = 0; j < N; j++) { a[j] = 1.031; b[j] = 1.057; } printf("Computed value of dot product: "); start = wcgettimeofday(); InitializeCriticalSection(&gCS); for ( i = 0; i < gNumThreads; ++i ) { tNum[i] = i; threadHandles[i] = CreateThread( NULL, // Security attributes 0, // Stack size threadFunction, // Thread function (LPVOID)&tNum[i], // Data for thread func() 0, // Thread start mode NULL); // Returned thread ID } WaitForMultipleObjects(gNumThreads, threadHandles, TRUE, INFINITE); DeleteCriticalSection(&gCS); stop = wcgettimeofday(); printf("sum = %f\n", gVectorSum); printf("time = %g\n", stop - start); }

OpenMP - стандарт программного интерфейса приложений для параллельных систем с общей памятью. Поддерживает языки C, C++, Fortran. Первая версия появилась в 1997 (Fortran) / 1998 (C/C++) годах. Последняя версия OpenMP 3.0 (2008 год). Разработкой стандарта занимается OpenMP ARB (Architecture Board). Официальный сайт OpenMP Open Multi-Processing (OpenMP)

#include #define N double a[N + 1], b[N + 1]; int i; double start, stop; double gDotProduct = 0; int main() { // initialize vectors for (i = 0; i < N; i++) { a[i] = 1.034; b[i] = 1.057; } printf("Computed value of vector sum: "); start = omp_get_wtime(); OpenMP. Пример

29 Программные инструменты Intel разработки параллельных приложений для вычислительных систем с общей памятью

30 Intel® Cilk TM Plus - расширение C/C++, упрощающее реализацию параллелизма для систем с общей памятью Intel® TBB – библиотека шаблонов параллельных алгоритмов и контейнеров на языке С++

31 Компиляторы – автоматическая оптимизация, автоматическое распараллеливание, векторизация. Анализаторы производительности. «Экспериментальные» технологии

32