Параллельные вычисления — способ организации компьютерных вычислений, при котором программы разрабатываются как набор взаимодействующих вычислительных процессов, работающих одновременно.
Существуют различные способы реализации параллельных вычислений: каждый вычислительный процесс может быть реализован в виде процесса операционной системы, либо же вычислительные процессы могут представлять собой набор потоков выполнения внутри одного процесса. Поток (или правильнее поток выполнения) – наименьшая единица обработки, исполнение которой может быть назначено ядром операционной системы. Несколько потоков выполнения могут существовать в рамках одного и того же процесса и совместно использовать ресурсы, такие как память, тогда как процессы не разделяют этих ресурсов. Параллельные программы могут физически исполняться либо последовательно на единственном процессоре — перемежая по очереди шаги выполнения каждого вычислительного процесса, либо параллельно — выделяя каждому вычислительному процессу один или несколько процессоров (находящихся рядом или распределённых в компьютерную сеть).
Основная сложность при проектировании параллельных программ — обеспечить правильную последовательность взаимодействий между различными вычислительными процессами, а также разделение таких ресурсов, как оперативная память или периферийные устройства.
В некоторых параллельных системах программирования передача данных между компонентами скрыта от программиста, тогда как в других она должна указываться явно. Явные взаимодействия могут быть разделены на два типа:
1. Взаимодействие через разделяемую память (например, в Java или C#). Данный вид параллельного программирования обычно требует какой-то формы захвата управления для координации потоков между собой.
2. Взаимодействие с помощью передачи сообщений. Обмен сообщениями может происходить асинхронно, либо с использованием метода «рандеву», при котором отправитель блокирован до тех пор, пока его сообщение не будет доставлено. Асинхронная передача сообщений может быть надёжной (с гарантией доставки) либо ненадёжной. Параллельные системы, основанные на обмене сообщениями, зачастую более просты для понимания, чем системы с разделяемой памятью, и обычно рассматриваются как более совершенный метод параллельного программирования. Обмен сообщениями может быть эффективно реализован на симметричных мультипроцессорах как с разделяемой когерентной памятью, так и без неё.
Существует довольно много разных технологий параллельного программирования. Причем эти технологии отличаются не столько языками программирования, сколько архитектурными подходами к построению параллельных систем. Например, какие-то технологии предполагают построение параллельных решений на основе нескольких компьютеров (как одного, так и разных типов), другие же предполагают именно работу на одной машине с несколькими процессорными ядрами. В настоящее время основными программные инструменты создания параллельных программ являются:
1. OpenMP используется в параллельных системах с общей памятью (например, современные компьютеры с многоядерными процессорами);
2. MPI (Message Passing Interface) является стандартом систем передачи сообщений между параллельно исполняемыми процессами, используется при разработке программ для суперкомпьютеров;
3. POSIX Threads является стандартом реализации потоков выполнения;
4. Операционная система Windows имеет встроенную поддержку многопоточных приложений для C++ на уровне API;
5. PVM (Parallel Virtual Machine) позволяет объединять разнородные связанные сетью компьютеры в общий вычислительный ресурс.
Системы на базе нескольких компьютеров относят к классу систем для распределенных вычислений. Подобные решения используются довольно давно. Наиболее яркий пример технологии распределенных вычислений — MPI (Message Passing Interface — интерфейс передачи сообщений). MPI является наиболее распространённым стандартом интерфейса обмена данными в параллельном программировании, существуют его реализации для огромнейшего числа компьютерных платформ. MPI предоставляет программисту единый механизм взаимодействия ветвей внутри параллельного приложения независимо от машинной архитектуры (однопроцессорные/многопроцессорные с общей/раздельной памятью), взаимного расположения ветвей (на одном процессоре или на разных).
Так как MPI предназначен в первую очередь для систем с раздельной памятью, то использование его для организации параллельного процесса в системе с общей памятью является крайне сложным нецелесообразным. Тем не менее, ничего не мешает делать MPI-решения для одной машины.
А вот системы параллельного программирования для работы на одной машине, начали развиваться относительно недавно. Конечно, это не принципиально новые идеи, но именно с приходом многоядерных систем на рынок персональных компьютеров, мобильных устройств, такие технологии как OpenMP получили значительное развитие.
Очень важно, чтобы технология параллельного программирования поддерживала возможность делать программу параллельной постепенно. Разумеется идеальную параллельную программу следует сразу писать параллельной, возможно на каком-нибудь функциональном языке, где вопрос распараллеливания вообще не стоит. Но на практике приходится, постепенно распараллеливать написанную последовательную с целью повышения быстродействия. В этом случае технология OpenMP будет очень удачным выбором. Она позволяет, выбрав в приложении наиболее нуждающиеся в параллелизации места, в первую очередь сделать параллельными именно их. Процесс разработки параллельной версии можно прерывать, выпускать промежуточные версии программы, возвращаться к нему по мере необходимости. Именно поэтому в частности технология OpenMP стала довольно популярной.
OpenMP (Open Multi-Processing) — это набор директив компилятора, библиотечных процедур и переменных окружения, которые предназначены для программирования многопоточных приложений на многопроцессорных системах с общей памятью.
Разработку спецификации OpenMP ведут несколько крупных производителей вычислительной техники и программного обеспечения, чья работа регулируется некоммерческой организацией, называемой OpenMP Architecture Review Board (ARB).
Первая версия появилась в 1997 году, предназначалась для языка Fortran. Для С/С++ версия разработана в 1998 году. В 2008 году вышла версия OpenMP 3.0. Интерфейс OpenMP стал одной из наиболее популярных технологий параллельного программирования. OpenMP успешно используется как при программировании суперкомпьютерных систем с большим количеством процессоров, так и в настольных пользовательских системах или, например, в Xbox 360.
OpenMP реализует параллельные вычисления с помощью многопоточности, в которой «главный» (master) поток создает набор подчиненных (slave) потоков и задача распределяется между ними. Предполагается, что потоки выполняются параллельно на машине с несколькими процессорами (количество процессоров не обязательно должно быть больше или равно количеству потоков).
Задачи, выполняемые потоками параллельно, также как и данные, требуемые для выполнения этих задач, описываются с помощью специальных директив препроцессора соответствующего языка — прагм. Например, участок кода на языке Fortran, который должен исполняться несколькими потоками, каждый из которых имеет свою копию переменной N, предваряется следующей директивой:!$OMP PARALLEL PRIVATE(N)
Количество создаваемых потоков может регулироваться как самой программой при помощи вызова библиотечных процедур, так и извне, при помощи переменных окружения.
Ключевыми элементами OpenMP являются
1. конструкции для создания потоков (директива parallel);
2. конструкции распределения работы между потоками (директивы DO/for и section);
3. конструкции для управления работой с данными (выражения shared и private для определения класса памяти переменных);
4. конструкции для синхронизации потоков (директивы critical, atomic и barrier);
5. процедуры библиотеки поддержки времени выполнения (например, omp_get_thread_num);
6. переменные окружения (например, OMP_NUM_THREADS).
В OpenMP используется модель параллельного выполнения «ветвление-слияние». Программа OpenMP начинается как единственный поток выполнения, называемый начальным потоком. Когда поток встречает параллельную конструкцию, он создает новую группу потоков, состоящую из себя и некоторого числа дополнительных потоков, и становится главным в новой группе. Все члены новой группы (включая главный) выполняют код внутри параллельной конструкции. В конце параллельной конструкции имеется неявный барьер. После параллельной конструкции выполнение пользовательского кода продолжает только главный поток. В параллельный регион могут быть вложены другие параллельные регионы, в которых каждый поток первоначального региона становится основным для своей группы потоков. Вложенные регионы могут в свою очередь включать регионы более глубокого уровня вложенности.
Число потоков в группе, выполняющихся параллельно, можно контролировать несколькими способами. Один из них — использование переменной окружения OMP_NUM_THREADS. Другой способ — вызов процедуры omp_set_num_threads(). Еще один способ — использование выражения num_threads в сочетании с директивой parallel.
В этой программе два массива (a и b) складываются параллельно десятью потоками.
#include <stdio.h>
#include <omp.h>
#define N 100
int main(int argc, char *argv[])
{
float a[N], b[N], c[N];
int i;
omp_set_dynamic(0); // запретить библиотеке openmp менять число потоков во время исполнения
omp_set_num_threads(10); // установить число потоков в 10
// инициализируем массивы
for (I = 0; I < N; i++)
{
a[i] = I * 1.0;
b[i] = i * 2.0;
}
// вычисляем сумму массивов
#pragma omp parallel shared(a, b, c) private(i)
{
#pragma omp for
for (I = 0; I < N; i++)
c[i] = a[i] + b[i];
}
printf (“%f\n”, c[10]);
return 0;
}
Эту программу можно скомпилировать, используя gcc-4.4 и более новые с флагом –fopenmp. Очевидно, если убрать подключение заголовочного файла omp.h, а также вызовы функции настроки OpenMP, программу возможно скомпилировать на любом компиляторе С как обычную последовательную программу.
OpenMP поддерживается многими современными компиляторами:
1. Компиляторы Sun Studio поддерживают официальную спецификацию — OpenMP 2.5 — с улучшенной производительностью под ОС Solaris; поддержка Linux запланирована на следующий релиз.
2. Visual C++ 2005 и выше поддерживает OpenMP в редакциях Professional и Team System.
3. GCC 4.2 поддерживает OpenMP, а некоторые дистрибутивы (такие как Fedora Core 5 gcc) включили поддержку в свои версии GCC 4.1.
4. Intel C++ Compiler, включая версию Intel Cluster OpenMP для программирования в системах с распределённой памятью.
Message Passing Interface (MPI, интерфейс передачи сообщений) — программный интерфейс (API) для передачи информации, который позволяет обмениваться сообщениями между процессами, выполняющими одну задачу. Разработан Уильямом Гроуппом, Эвином Ласком (англ.) и другими.
MPI является наиболее распространённым стандартом интерфейса обмена данными в параллельном программировании, существуют его реализации для большого числа компьютерных платформ. Используется при разработке программ для кластеров и суперкомпьютеров. Основным средством коммуникации между процессами в MPI является передача сообщений друг другу. Стандартизацией MPI занимается MPI Forum. В стандарте MPI описан интерфейс передачи сообщений, который должен поддерживаться как на платформе, так и в приложениях пользователя. В настоящее время существует большое количество бесплатных и коммерческих реализаций MPI. Существуют реализации для языков Фортран 77/90, Си и Си++.
В первую очередь MPI ориентирован на системы с распределенной памятью, то есть когда затраты на передачу данных велики, в то время как OpenMP ориентирован на системы с общей памятью (многоядерные с общим ЭШем). Обе технологии могут использоваться совместно, дабы оптимально использовать в кластере многоядерные системы.
Первая версия MPI разрабатывалась в 1993—1994 году, и MPI 1 вышла в 1994.
Большинство современных реализаций MPI поддерживают версию 1.1. Стандарт MPI версии 2.0 поддерживается большинством современных реализаций, однако некоторые функции могут быть реализованы не до конца.
В MPI 1.1 (опубликован 12 июня 1995 года, первая реализация появилась в 2002 году) поддерживаются следующие функции:
передача и получение сообщений между отдельными процессами;
коллективные взаимодействия процессов;
взаимодействия в группах процессов;
реализация топологий процессов;
В MPI 2.0 (опубликован 18 июля 1997 года) дополнительно поддерживаются следующие функции:
динамическое порождение процессов и управление процессами;
односторонние коммуникации (Get/Put);
параллельный ввод и вывод;
расширенные коллективные операции (процессы могут выполнять коллективные операции не только внутри одного коммуникатора, но и в рамках нескольких коммуникаторов).
Версия MPI 2.1 вышла в начале сентября 2008 года.
Базовым механизмом связи между MPI процессами является передача и приём сообщений. Сообщение несёт в себе передаваемые данные и информацию, позволяющую принимающей стороне осуществлять их выборочный приём:
1. отправитель — ранг (номер в группе) отправителя сообщения;
2. получатель — ранг получателя;
3. признак — может использоваться для разделения различных видов сообщений;
4. коммуникатор — код группы процессов.
Операции приёма и передачи могут быть блокирующимися и не блокирующимися. Для не блокирующихся операций определены функции проверки готовности и ожидания выполнения операции.
Другим способом связи является удалённый доступ к памяти (RMA), позволяющий читать и изменять область памяти удалённого процесса. Локальный процесс может переносить область памяти удалённого процесса (внутри указанного процессами окна) в свою память и обратно, а также комбинировать данные, передаваемые в удалённый процесс с имеющимися в его памяти данными (например, путём суммирования). Все операции удалённого доступа к памяти не блокирующиеся, однако, до и после их выполнения необходимо вызывать блокирующиеся функции синхронизации.
Ниже приведён пример программы вычисления числа π на языке C с использованием MPI:
// Подключение необходимых заголовков
#include <stdio.h>
#include <math.h>
// Подключение заголовочного файла MPI
#include «mpi.h»
// Функция для промежуточных вычислений
double f(double a)
{
return (4.0 / (1.0+ a*a));
}
// Главная функция программы
int main(int argc, char **argv)
{
// Объявление переменных
int done = 0, n, myid, numprocs, I;
double PI25DT = 3.141592653589793238462643;
double mypi, pi, h, sum, x;
double startwtime = 0.0, endwtime;
int namelen;
char processor_name[MPI_MAX_PROCESSOR_NAME];
// Инициализация подсистемы MPI
MPI_Init(&argc, &argv);
// Получить размер коммуникатора MPI_COMM_WORLD
// (общее число процессов в рамках задачи)
MPI_Comm_size(MPI_COMM_WORLD,&numprocs);
// Получить номер текущего процесса в рамках
// коммуникатора MPI_COMM_WORLD
MPI_Comm_rank(MPI_COMM_WORLD,&myid);
MPI_Get_processor_name(processor_name,&namelen);
// Вывод номера потока в общем пуле
fprintf(stdout, “Process %d of %d is on %s\n”, myid,numprocs,processor_name);
fflush(stdout);
while(!done)
{
// количество интервалов
if(myid==0)
{
fprintf(stdout, “Enter the number of intervals: (0 quits) “);
fflush(stdout);
if(scanf(“%d”,&n)!= 1)
{
fprintf(stdout, “No number entered; quitting\n”);
n = 0;
}
startwtime = MPI_Wtime();
}
// Рассылка количества интервалов всем процессам (в том числе и себе)
MPI_Bcast(&n, 1, MPI_INT, 0, MPI_COMM_WORLD);
if(n==0)
done = 1;
else
{
h = 1.0 / (double) n;
sum = 0.0;
// Обсчитывание точки, закрепленной за процессом
for(I = myid + 1; (I <= n); I += numprocs)
{
x = h * ((double)I – 0.5);
sum += f(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, Error is %.16f\n”, pi, fabs(pi – PI25DT));
endwtime = MPI_Wtime();
printf(“wall clock time = %f\n”, endwtime-startwtime);
fflush(stdout);
}
}
}
// Освобождение подсистемы MPI
MPI_Finalize();
return 0;
}
Наиболее распространенными реализациями MPI на сегодняшний день являются:
MPICH — самая распространённая бесплатная реализация, работает на UNIX-системах и Windows NT
LAM/MPI — ещё одна бесплатная реализация MPI. Поддерживает гетерогенные конфигурации, LAM (https://www.lam-mpi.org) поддерживает гетерогенные конфигурации, пакет Globus и удовлетворяет IMPI (Interoperable MPI).
Поддерживаются различные коммуникационные системы (в том числе Myrinet).
WMPI — реализация MPI для Windows
MPI/PRO for Windows NT — коммерческая реализация для Windows NT
Intel MPI — коммерческая реализация для Windows / Linux
Microsoft MPI входит в состав Compute Cluster Pack SDK. Основан на MPICH2, но включает дополнительные средства управления заданиями. Поддерживается спецификация MPI-2.
HP-MPI — коммерческая реализация от HP
SGI MPT — платная библиотека MPI от SGI
Mvapich — бесплатная реализация MPI для Infiniband
Open MPI — бесплатная реализация MPI, наследник LAM/MPI
Oracle HPC ClusterTools — бесплатная реализация для Solaris SPARC/x86 и Linux на основе Open MPI
MPJ — MPI for Java
POSIX Threads — стандарт POSIX реализации потоков выполнения, определяющий API для создания и управления ими.
Библиотеки, реализующие этот стандарт (и функции этого стандарта), обычно называются Pthreads (функции имеют приставку «pthread_»). Хотя наиболее известны варианты для Unix-подобных операционных систем, таких как Linux или Solaris, но существует и реализация для Microsoft Windows (Pthreads-w32)
Pthreads определяет набор типов и функций на языке программирования Си. Заголовочный файл — pthread.h.
Типы данных:
1. pthread_t – дескриптор потока;
2. pthread_attr_t – перечень атрибутов потока.
Функции управления потоками:
1. pthread_create() – создание потока;
2. pthread_exit() – завершение потока (должна вызываться функцией потока при завершении);
3. pthread_cancel() – отмена потока;
4. pthread_join() – заблокировать выполнение потока до прекращения другого потока, указанного в вызове функции;
5. pthread_detach() – освободить ресурсы занимаемые потоком (если поток выполняется, то освобождение ресурсов произойдёт после его завершения);
6. pthread_attr_init() – инициализировать структуру атрибутов потока;
7. pthread_attr_setdetachstate() – указать системе, что после завершения потока она может автоматически освободить ресурсы, занимаемые потоком;
8. pthread_attr_destroy() – освободить память от структуры атрибутов потока (уничтожить дескриптор).
Функции синхронизации потоков:
2. pthread_mutex_init(), pthread_mutex_destroy(), pthread_mutex_lock(), pthread_mutex_trylock(), pthread_mutex_unlock();
3. pthread_cond_init(), pthread_cond_signal(), pthread_cond_wait().
Пример использования потоков на языке C:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <pthread.h>
static void wait_thread(void)
{
time_t start_time = time(NULL);
while (time(NULL) == start_time)
{
/* do nothing except chew CPU slices for up to one second. */
}
}
static void *thread_func(void *vptr_args)
{
int I;
for (I = 0; I < 20; i++)
{
fputs(“ b\n”, stderr);
wait_thread();
}
return NULL;
}
int main(void)
{
int I;
pthread_t thread;
if (pthread_create(&thread, NULL, thread_func, NULL)!= 0)
{
return EXIT_FAILURE;
}
for (I = 0; I < 20; i++)
{
puts(“a”);
wait_thread();
}
if (pthread_join(thread, NULL)!= 0)
{
return EXIT_FAILURE;
}
return EXIT_SUCCESS;
}
Представленная программа используют два потока, печатающих в консоль сообщения, один, печатающий 'a', второй — 'b'. Вывод сообщений смешивается в результате переключения выполнения между потоками или одновременном выполнении на мультипроцессорных системах.
Программа на C создает один новый поток для печати 'b', а основной поток печатает 'a'. Основной поток (после печати 'aaaaa….') ждёт завершения дочернего потока.
Контрольные вопросы
- Что такое параллельная программа?
- В чем отличие между процессом и потоком выполнения?
- Может ли программа создать 5 потоков при работе на четырехядерном процессоре?
- Каковы особенности параллельных программ с разделяемой памятью?
- Какие существуют программные средства для разработки параллельных программ?
- Почему большое распространение при создании программ для ПК получил именно OpenMP, а не, например, MPI?