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

Форма вычислений, при которой несколько вычислений выполняются в перекрывающиеся периоды времени

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

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

Параллельные вычисления - это форма модульного программирования. В его парадигме общее вычисление факторизуется на подвычисления, которые могут выполняться одновременно. Пионерами в области параллельных вычислений являются Эдсгер Дейкстра, Пер Бринч Хансен и C.A.R. Хоар.

• 1 Введение
  • 1.1 Координация доступа к общим ресурсам
  • 1.2 Преимущества
• 2 Модели
• 3 Реализация
  • 3.1 Взаимодействие и коммуникация
• 4 История
• 5 Распространенность
• 6 Языки, поддерживающие параллельное программирование
• 7 См. Также
• 8 Примечания
• 9 Ссылки
• 10 Источники
• 11 Дополнительная литература
• 12 Внешние ссылки

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

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

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

Точное время, когда задачи в параллельной системе выполняются, зависит от планирование, и задачи не всегда должны выполняться одновременно. Например, учитывая две задачи, T1 и T2:

• T1 может быть выполнен и завершен до T2 или наоборот (последовательный и последовательный)
• T1 и T2 могут выполняться поочередно (последовательно и одновременно)
• T1 и T2 могут выполняться одновременно в один и тот же момент времени (параллельно и одновременно)

Слово «последовательный» используется как антоним для «одновременного» и «параллельного»; когда они явно различаются, параллельные / последовательные и параллельные / последовательные используются как противоположные пары. Расписание, в котором задачи выполняются по одной (последовательно, без параллелизма), без чередования (последовательно, без параллелизма: ни одна задача не начинается до завершения предыдущей задачи), называется последовательным расписанием. Набор задач, которые можно планировать последовательно, является сериализуемым, что упрощает контроль параллелизма.

Координация доступа к общим ресурсам

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

1 bool снятия (int снятия) 2 {3 if (баланс>= снятие) 4 {5 баланс - = снятие ; 6 вернуть истину; 7} 8 return false; 9}

Предположим, что balance = 500, и два параллельных потока выполняют вызовы remove (300)и takew (350). Если строка 3 в обеих операциях выполняется до строки 5, обе операции обнаружат, что баланс>= снятиеоценивается как истина, и выполнение перейдет к вычитанию суммы снятия. Однако, поскольку оба процесса производят снятие средств, общая снятая сумма будет больше, чем исходный баланс. Такого рода проблемы с общими ресурсами выигрывают от использования управления параллелизмом или неблокирующих алгоритмов.

Преимущества

Преимущества параллельных вычислений включают:

• Повышенная пропускная способность программы - параллельное выполнение параллельная программа позволяет количеству задач, выполненных за заданное время, увеличиваться пропорционально количеству процессоров в соответствии с законом Густафсона
• Высокая скорость реагирования на ввод / вывод - программы с интенсивным вводом / выводом в основном ждут ввода или вывода операции для завершения. Параллельное программирование позволяет использовать время, которое было бы потрачено на ожидание, которое будет использовано для другой задачи.
• Более подходящая структура программы - некоторые проблемы и проблемные области хорошо подходят для представления в виде параллельных задач или процессов.

Модели для понимания и анализа параллельных вычислительных систем включают:

• Модель актора
  • Модель возможностей объекта для безопасности
• Автомат ввода / вывода
• Программная транзакционная память (STM)
• Сети Петри
• Процессные вычисления такие как
  • Окружающие вычисления
  • Вычисления взаимодействующих систем (CCS)
  • Последовательные процессы, взаимодействующие между собой (CSP)
  • Присоединиться -calculus
  • π-исчисление

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

Взаимодействие и коммуникация

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

Обмен данными с общей памятью

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

Связью с передачей сообщений

Параллельные компоненты взаимодействуют посредством обмена сообщениями (например, MPI, Go, Scala, Erlang и occam ). Обмен сообщениями может выполняться асинхронно или может использоваться синхронный стиль «рандеву», в котором отправитель блокируется, пока сообщение не будет принято. Асинхронная передача сообщений может быть надежной или ненадежной (иногда ее называют «отправь и помолись»). Обсуждать параллелизм передачи сообщений, как правило, гораздо проще, чем параллелизм с общей памятью, и он обычно считается более надежной формой параллельного программирования. Доступен широкий спектр математических теорий для понимания и анализа систем передачи сообщений, включая модель актора и различные вычисления процесса. Передача сообщений может быть эффективно реализована с помощью симметричной многопроцессорной обработки, с общей памятью или без нее согласованность кеша.

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

Параллельные вычисления были разработаны на основе более ранних работ по железным дорогам и телеграфии в XIX и начале XX века, и некоторые термины, например семафоры, относятся к этому периоду.. Они возникли для решения вопроса о том, как управлять несколькими поездами в одной и той же железнодорожной системе (избегать столкновений и максимизировать эффективность) и как обрабатывать несколько передач по заданному набору проводов (повышение эффективности), например, через с разделением по времени мультиплексирование (1870-е).

Академическое исследование параллельных алгоритмов началось в 1960-х годах, когда Дейкстра (1965) был признан первой статьей в этой области, выявившей и решившей взаимное исключение.

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

На уровне языка программирования:

• Канал
• Coroutine
• Futures and Promises

На уровне операционной системы:

• Многозадачность компьютера, включая оба кооператива многозадачность и вытесняющая многозадачность
  • с разделением времени, которые заменили последовательную пакетную обработку заданий на одновременное использование системы
• Процесс
• Поток

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

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

Сегодня наиболее часто используемыми языками программирования, имеющими особые конструкции для параллелизма, являются Java и C #. Оба этих языка в основном используют модель параллелизма с общей памятью с блокировкой, обеспечиваемой мониторами (хотя модели передачи сообщений могут быть реализованы и были реализованы поверх базовой модели с общей памятью). Из языков, использующих модель параллелизма с передачей сообщений, Erlang, вероятно, является наиболее широко используемым в настоящее время в промышленности.

Многие языки параллельного программирования были разработаны больше как языки исследований (например, Pict ), а не как языки для производственного использования. Однако такие языки, как Erlang, Limbo и occam, за последние 20 лет в разное время применялись в промышленности. Языки, на которых параллелизм играет важную роль, включают:

• Ada - общего назначения, с встроенной поддержкой передачи сообщений и параллелизма на основе монитора.
• Alef - параллельный, с потоками и передачей сообщений, для системного программирования. в ранних версиях Plan 9 от Bell Labs
• Алиса - расширение до Standard ML, добавляет поддержку параллелизма через фьючерсы
• Ateji PX - расширение до Java с параллельными примитивами, вдохновленными π-исчислением
• Axum - специфичным для домена, параллельным, на основе модели акторов и.NET Common Language Runtime с использованием синтаксиса C-подобного
• BMDFM —Binary Modular DataFlow Machine
• C ++ —std :: thread
• Cω (C omega) —для исследований, расширяет C #, использует асинхронную связь
• C# —поддерживает параллельные вычисления с использованием блокировки, yield, также с тех пор, как версия 5.0 введены ключевые слова async и await
• Clojure - современный, функциональный диалект Lisp на платформе Java
• Concurrent Clean - функциональный пр программирование, подобное Haskell
• Concurrent Collections (CnC) - обеспечивает неявный параллелизм независимо от модели памяти путем явного определения потока данных и управления
• Concurrent Haskell - ленивый, чистый функциональный язык, работающий параллельные процессы в общей памяти
• Concurrent ML - параллельное расширение Standard ML
• Concurrent Pascal - от Пер Бринч Хансен
• Карри
• D —мультипарадигма язык системного программирования с явной поддержкой параллельного программирования (модель актора )
• E - использует обещания для предотвращения взаимоблокировок
• ECMAScript - использует обещания для асинхронных операций
• Eiffel - с помощью механизма SCOOP, основанного на концепциях проектирования по контракту
• Elixir - языка динамического и функционального метапрограммирования, работающего на виртуальной машине Erlang.
• Erlang - использует асинхронную передачу сообщений без общего доступа
• FAUST - функционал реального времени, для обработки сигналов компилятор обеспечивает автоматическое распараллеливание Работа через OpenMP или специальный планировщик work-stealing
• Fortran - coarrays и параллельная обработка являются частью стандарта Fortran 2008
• Go - для системного программирования, с моделью параллельного программирования, основанной на CSP
• Haskell - языке параллельного и параллельного функционального программирования
• Hume - функциональном, параллельном, для сред с ограниченным пространством и временем, где автоматы процессы описываются шаблонами синхронных каналов и передачей сообщений
• Io - параллелизм на основе факторов
• Янус - отличает различных запрашивающих и кассиров логических переменных, каналов пакетов; является чисто декларативным
• Java - класс потока или Runnable interface
• Julia - «примитивы параллельного программирования: задачи, асинхронное ожидание, каналы».
• JavaScript - через веб-воркеры, в среде браузера, promises и обратные вызовы.
• JoCaml - на основе параллельных и распределенных каналов, расширение OCaml, реализует объединенное исчисление процессов
• Присоединение Java - одновременный, на основе Java язык
• Джоуль - на основе потока данных, общение осуществляется посредством передачи сообщений
• Джойс - параллельное обучение, построенное на Concurrent Pascal с функциями из CSP от Пера Бринча Хансена
• LabVIEW - графическое изображение, поток данных, функции узлы в графе, данные - провода между узлами; включает объектно-ориентированный язык
• Limbo - аналог Alef, для системного программирования в Inferno (операционная система)
• MultiLisp - Scheme вариант, расширенный для поддержки параллелизма
• Modula-2 - для системного программирования, Н. Вирт как преемник Паскаля с встроенной поддержкой сопрограмм
• Modula-3 - современный член семейства Algol с обширным поддержка потоков, мьютексов, условных переменных
• Newsqueak - для исследования, с каналами как первоклассными значениями; предшественник Alef
• occam - находился под сильным влиянием последовательных процессов передачи (CSP)
  • occam-π - современный вариант occam, который включает в себя идеи из π-исчисления
• Orc - сильно параллельного, недетерминированного, основанного на алгебре Клини
• Оз-Моцарта - мультипарадигмы, поддерживает разделяемое состояние и сообщение -пропуск параллелизма и фьючерсы
• ParaSail - объектно-ориентированный, параллельный, свободный от указателей, условия гонки
• Pict - по сути, исполняемая реализация π-исчисления Милнера
• Raku по умолчанию включает классы для потоков, обещаний и каналов
• Python с использованием Stackless Python
• Reia - использует асинхронную передачу сообщений между объектами без общего доступа
• Red / System - для системного программирования на основе Rebol
• Rust - для системного программирования с использованием передачи сообщений с семантикой перемещения, совместно используемой неизменяемой памяти и совместно используемой изменяемой памяти.
• Scala - общего назначения, предназначенный для выражать общие шаблоны программирования в краткой, элегантной и типобезопасной форме
• SequenceL - функциональность общего назначения, основные задачи проектирования - простота программирования, ясность кода и автоматическое распараллеливание для повышения производительности на многоядерном оборудовании, а также доказуемо свободным от состояний гонки
• SR - для исследований
• SuperPascal - одновременных, для обучения, построенных на Concurrent Pascal и Joyce от Per Бринч Хансен
• Unicon - для исследований
• TNSDL - для разработки телекоммуникационных обменов, использует асинхронную передачу сообщений
• Язык описания оборудования VHSIC (VHDL ) —IEEE STD-1076
• XC - подмножество языка C с расширенным параллелизмом, разработанное XMOS, основанное на взаимодействующих последовательных процессах, встроенных конструкциях для программируемого ввода-вывода

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

• Асинхронный ввод-вывод
• Пространство Чу
• Программирование на основе потоков
• Java ConcurrentMap
• Список важных публикаций по параллельным, параллельным и распределенным вычислениям
• Проект Птолемея
• Состояние гонки § Вычисления
• Сноп (математика)
• Обработка транзакций

• Дейкстра, EW (1965). «Решение проблемы управления параллельным программированием». Связь ACM. 8(9): 569. doi : 10.1145 / 365559.365617. CS1 maint: ref = harv (link )
• Херлихи, Морис (2008) [2008]. Искусство многопроцессорного программирования. Морган Кауфманн. ISBN 978-0123705914.
• Дауни, Аллен Б. (2005) [2005]. Маленькая книга семафоров (PDF). Green Tea Press. ISBN 978-1-4414-1868-5. Архивировано с оригинала (PDF) от 4 марта 2016 г. Проверено 21 ноября 2009 г.
• Филман, Роберт Э.; Дэниел П. Фридман (1984). Скоординированные вычисления: инструменты и методы для распределенного программного обеспечения. Нью-Йорк: McGraw-Hill. Стр. 370. ISBN 978-0-07-022439-1.
• Леппяярви, Йоуни (2008). A прагматичный, исторически ориентированный обзор универсальности примитивов синхронизации (PDF). University of Oulu.
• Taubenfeld, Gadi (2006). Synchronization Algorithms and Concurrent Programming. Pearson / Prentice Hall. стр. 433. ISBN 978-0-13-197259-9.

• Носители, относящиеся к параллельному программированию на Wikimedia Commons
• Виртуальная библиотека параллельных систем