Параллельные вычисления

Не следует путать с Распределённые вычисления.

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

Существуют различные способы реализации параллельных вычислений. Например, каждый вычислительный процесс может быть реализован в виде процесса операционной системы, либо же вычислительные процессы могут представлять собой набор потоков выполнения внутри одного процесса ОС. Параллельные программы могут физически исполняться либо последовательно на единственном процессоре — перемежая по очереди шаги выполнения каждого вычислительного процесса, либо параллельно — выделяя каждому вычислительному процессу один или несколько процессоров (находящихся рядом или распределённых в компьютерную сеть).

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

Способы синхронизации параллельного взаимодействия

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

• Взаимодействие через разделяемую память: на каждом процессоре мультипроцессорной системы запускается поток исполнения, который принадлежит одному процессу. Потоки обмениваются данными через общий для данного процесса участок памяти. Количество потоков соответствует количеству процессоров. Потоки создаются либо средствами языка (например, в Java или C#, C++ (начиная с C++11), C (начиная с C11)), либо с помощью библиотек явно (например, в С/C++ с помощью PThreads), либо декларативно (например, с помощью библиотеки OpenMP), или автоматически встроенными средствами компилятора (например, High Performance Fortran). Данный вид параллельного программирования обычно требует какой-то формы захвата управления (мьютексы, семафоры, мониторы) для координации потоков между собой.
• Взаимодействие с помощью передачи сообщений: на каждом процессоре многопроцессорной системы запускается однопоточный процесс, который обменивается данными с другими процессами, работающими на других процессорах, с помощью сообщений. Процессы создаются явно, путём вызова соответствующей функции операционной системы, а обмен сообщениями — с помощью библиотеки (например, реализация протокола MPI), или с помощью средств языка (например, High Performance Fortran, Erlang или occam). Обмен сообщениями может происходить асинхронно, либо с использованием метода «рандеву», при котором отправитель блокирован до тех пор, пока его сообщение не будет доставлено. Асинхронная передача сообщений может быть надёжной (с гарантией доставки) либо ненадёжной.

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

У параллелизма с распределенной памятью и с передачей сообщений разные характеристики производительности. Обычно (но не всегда), накладные расходы памяти на процесс и времени на переключение задач у систем с передачей сообщений ниже, однако передача самих сообщений более накладна, чем вызовы процедур. Эти различия часто перекрываются другими факторами, влияющими на производительность.

• Гибридный способ: на многопроцессорных системах с распределённой памятью (DM-MIMD), где каждый узел системы представляет собой мультипроцессор с общей памятью (SM-MIMD), можно использовать гибридный метод программирования. На каждом узле системы запускается многопоточный процесс, который распределяет потоки между процессорами данного узла. Обмен данными между потоками на узле осуществляется через общую память, а обмен данными между узлами — через передачу сообщений. В этом случае количество процессов определяется количеством узлов, а количество потоков — количеством процессоров на каждом узле. Гибридный способ программирования более сложен (требуется особым образом переписывать параллельную программу), но наиболее эффективен в использовании аппаратных ресурсов каждого узла многопроцессорной системы.

Разумеется в такой системе можно также использовать и исключительно метод передачи сообщений, то есть запустить на каждом процессоре каждого узла отдельный процесс. В этом случае количество процессов (и потоков) будет равно количеству процессоров на всех узлах. Этот способ проще (в параллельной программе надо только увеличить количество процессов), но является менее эффективным, так как процессоры одного и того же узла будут обмениваться друг с другом сообщениями, словно они находятся на разных машинах.

Типичные задачи, допускающие параллельные вычисления

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

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

• OpenMP — стандарт интерфейса приложений для параллельных систем с общей памятью.
• POSIX Threads — стандарт реализации потоков (нитей) выполнения.
• Windows API — многопоточные приложения для C++.
• PVM (Parallel Virtual Machine) позволяет объединить разнородный (но связанный сетью) набор компьютеров в общий вычислительный ресурс.
• MPI (Message Passing Interface) — стандарт систем передачи сообщений между параллельно исполняемыми процессами.

См. также

• Распределённые вычисления
• Многопоточность
• Многозадачность
• Параллельные вычислительные системы
• Классификация параллельных вычислительных систем
• Закон Амдала
• Вычислительный конвейер
• Симметричная мультипроцессорность
• Грид
• GPGPU
• NUMA
• Кластер
• MIPS
• LINPACK
• NAS Parallel Benchmarks

Литература

• Словарь по кибернетике / Под редакцией академика В. С. Михалевича. — 2-е. — Киев: Главная редакция Украинской Советской Энциклопедии имени М. П. Бажана, 1989. — 751 с. — (С48). — 50 000 экз. — ISBN 5-88500-008-5.
• RS/6000 SP: Practical MPI Programming. — IBM RedBook, 1999. — 238 с. Архивная копия от 19 января 2008 на Wayback Machine (англ.)
• Воеводин В. В., Воеводин Вл. В. Параллельные вычисления. — СПб.: БХВ-Петербург, 2002. — 608 с. — ISBN 5-94157-160-7.
• Оленев Н. Н. Основы параллельного программирования в системе MPI. — М.: ВЦ РАН, 2005. — 80 с. — ISBN 5201098320.

Ссылки

• DataGrid Project (англ.)
• Open Grid Forum (англ.)