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

Презентацию к данной лекции Вы можете скачать здесь.

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

От фоннеймановской архитектуры к архитектуре многоядерной

Фоннеймановская архитектура

Как эволюционировала архитектура вычислительных систем

Эволюция программных технологий

Фоннеймановская архитектура последовательная, скалярная. В "классическом" фоннеймановском компьютере параллелизм отсутствует на всех уровнях. Традиционная последовательная модель программирования, ориентированная на SISD архитектуры (по Флинну). Языки последовательного программирования.

Пользователю нужна производительность. Увеличение производительности позволяет:

решать новые, более сложные задачи;

решать старые задачи, но быстрее;

решать старые задачи, но с более высокой точностью.

Многие расширения фоннеймановской архитектуры используют параллелизм на разном уровне

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

Многоядерные архитектуры стали доминирующими

Первые многоядерные процессоры появились на рынке в 2005 году. Сейчас это доминирующий тип архитектур.

Вычислительная система с многоядерным процессором – параллельная вычислительная система с общей памятью, обычно SMP (Symmetric Multiprocessor System).

От архитектуры multicore (с небольшой многоядерностью) к архитектуре manycore (с большой многоядерностью)

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

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

Что происходит с данными внутри программы. Информационный граф программы

Алгоритм можно представить в виде диаграммы информационного графа.

Информационный граф описывает последовательность выполнения операций и взаимную зависимость между различными операциями или блоками операций.

Узлами информационного графа являются операции, а однонаправленными дугами каналы обмена данными.

Понятие операции может трактоваться расширенно. Это может быть оператор языка, но может быть и более крупный блок программы.

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

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

Основными особенностями параллельной модели программирования являются более высокая производительность программ, применение специальных приемов программирования и, как следствие, более высокая трудоемкость программирования, проблемы с переносимостью программ. Параллельная модель не обладает свойством универсальности.

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

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

Повышенная трудоемкость параллельного программирования связана с тем, что программист должен заботиться:

об управлении работой множества процессов;

об организации межпроцессных пересылок данных;

о вероятности тупиковых ситуаций (взаимных блокировках);

о нелокальном и динамическом характере ошибок;

о возможной утрате детерминизма ("гонки за данными");

о масштабируемости;

о сбалансированной загрузке вычислительных узлов.

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

Параллелизм данных

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

обработкой данных управляет одна программа;

пространство имен является глобальным;

параллельные операции над элементами массива выполняются одновременно на всех доступных данной программе процессорах.

От программиста требуется:

задание опций векторной или параллельной оптимизации транслятору;

задание директив параллельной компиляции;

использование специализированных языков параллельных вычислений, а также библиотек подпрограмм, специально разработанных с учетом конкретной архитектуры компьютера и оптимизированных для этой архитектуры.

Параллелизм задач

вычислительная задача разбивается на несколько относительно самостоятельных подзадач. Каждая подзадача выполняется на своем процессоре (ориентация на архитектуру MIMD);

для каждой подзадачи пишется своя собственная программа на обычном языке программирования (чаще всего это Fortran или С);

подзадачи должны обмениваться результатами своей работы, получать исходные данные. Практически такой обмен осуществляется вызовом процедур специализированной библиотеки. Программист при этом может контролировать распределение данных между различными процессорами и различными подзадачами, а также обмен данными.

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

Низкоуровневые средства

Системные вызовы операционной системы (UNIX/Linux)

IPC (InterProcess Communications)

именованные каналы;

общая память;

сообщения;

семафоры.

IPC. Сообщения. Пример

Клиент

#include <sys/types.h>
    #include <sys/ipc.h>
        #include <sys/msg.h>
            #include "mesg.h"
            main()
            {
            message  message;
            key_t	key;
            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);
            }    
                

Сервер

#include <sys/types.h>
    #include <sys/ipc.h>
        #include <sys/msg.h>
            #include "mesg.h"
            main()
            {
            Message	message;
            key_t	key;
            int	msgid, 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);
            }
                

POSIX Threads

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

Ссылка http://www.opengroup.org/onlinepubs/009695399/basedefs/pthread.h.html

POSIX Threads. Пример

#include <stdio.h>
    #include "gettimeofday.h"
    #include <pthread.h>
        
        #define gNumThreads 1
        #define N 100000000
        
        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;
        }
        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); 
        
        }
            

Windows API

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

Ссылка http://msdn.microsoft.com

Windows API. Пример

#include <windows.h>
    #include <stdio.h>
        #define N 100000000
        
        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;
        }
        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); 
        }
                

Open Multi-Processing (OpenMP)

OpenMP - стандарт программного интерфейса приложений для параллельных систем с общей памятью. Поддерживает языки C, C++, Fortran.

Первая версия появилась в 1997 (Fortran) / 1998 (C/C++) годах. Последняя версия OpenMP 3.0 (2008 год). Разработкой стандарта занимается OpenMP ARB (Architecture Board).

Ссылка http://openmp.org

OpenMP. Пример

#include <windows.h>
    #include <stdio.h>
        #define N 100000000
        
        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();   
                

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

Intel® TBB – библиотека шаблонов параллельных алгоритмов и контейнеров на языке С++

Intel® CilkTM Plus - расширение C/C++, упрощающее реализацию параллелизма для систем с общей памятью

Компиляторы – автоматическая оптимизация, автоматическое распараллеливание, векторизация.

Анализаторы производительности.

"Экспериментальные" технологии