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

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

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

Параллельные вычисления — это форма модульного программирования . В его парадигме общие вычисления разбиваются на подвычисления, которые могут выполняться одновременно. Пионерами в области параллельных вычислений являются Эдсгер Дейкстра , Пер Бринч Хансен и К.АР Хоар . ^[2]

Введение

Понятие параллельных вычислений часто путают с родственным, но отличным понятием параллельных вычислений . ^[3]^[4] хотя оба могут быть описаны как «несколько процессов, выполняющихся в течение одного и того же периода времени ». тот же физический момент: например, на отдельных процессорах многопроцессорной При параллельных вычислениях выполнение происходит в один и машины, с целью ускорения вычислений — параллельные вычисления невозможны на ( одноядерном ) одном процессоре, так как только один Вычисление может происходить в любой момент (в течение любого такта). ^[а] Напротив, параллельные вычисления состоят из перекрывающихся жизней процессов , но выполнение не обязательно происходит в один и тот же момент. Целью здесь является моделирование процессов во внешнем мире, которые происходят одновременно, например, когда несколько клиентов одновременно обращаются к серверу. Структурирование программных систем, состоящих из множества одновременно взаимодействующих частей, может быть полезно для решения сложных задач, независимо от того, могут ли эти части выполняться параллельно. ^[5]^: 1

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

Параллельные вычисления могут выполняться параллельно, ^[3]^[6] например, назначив каждый процесс отдельному процессору или ядру процессора или распределив вычисления по сети.

Точное время выполнения задач в параллельной системе зависит от планирования , и задачи не всегда должны выполняться одновременно. Например, даны две задачи Т1 и Т2: ^{[ нужна ссылка ]}

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

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

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

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

bool withdraw(int withdrawal)
{
    if (balance >= withdrawal)
    {
        balance -= withdrawal;
        return true;
    } 
    return false;
}

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

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

К преимуществам параллельных вычислений относятся:

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

Модели

представленные в 1962 году, Сети Петри, были первой попыткой систематизировать правила одновременного выполнения. Теория потока данных позже была основана на них, и были созданы архитектуры потоков данных для физической реализации идей теории потоков данных. Начиная с конца 1970-х годов, исчисление процессов , такое как исчисление коммуникативных систем (CCS) и коммуникативных последовательных процессов (CSP), было разработано, чтобы позволить алгебраические рассуждения о системах, состоящих из взаимодействующих компонентов. добавило π-исчисление возможность рассуждать о динамических топологиях.

Автоматы ввода-вывода были представлены в 1987 году.

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

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

Модели согласованности

Параллельные языки программирования и многопроцессорные программы должны иметь модель согласованности (также известную как модель памяти). Модель согласованности определяет правила выполнения операций с памятью компьютера и получения результатов.

Одной из первых моделей согласованности была Лесли Лэмпорта модель последовательной согласованности . Последовательная согласованность — это свойство программы, при котором ее выполнение дает те же результаты, что и последовательная программа. В частности, программа последовательно непротиворечива, если «результаты любого выполнения такие же, как если бы операции всех процессоров выполнялись в некотором последовательном порядке, а операции каждого отдельного процессора появляются в этой последовательности в порядке, заданном его программой». ". ^[8]

Выполнение

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

Взаимодействие и общение

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

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

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

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

История

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

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

Распространенность

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

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

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

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

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

Языки, поддерживающие параллельное программирование

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

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

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

Ada — общего назначения, со встроенной поддержкой передачи сообщений и параллелизма на основе мониторинга.
Алеф — параллельный, с потоками и передачей сообщений, для системного программирования в ранних версиях Plan 9 от Bell Labs.
Алиса — расширение Standard ML , добавляет поддержку параллелизма через фьючерсы.
Ateji PX — расширение для Java с параллельными примитивами, вдохновленное π-исчислением.
Axum — специфичный для предметной области, параллельный, на основе модели актера и общеязыковой среды выполнения .NET с использованием синтаксиса, подобного C.
BMDFM — двоичная модульная машина потока данных
C++ — библиотеки поддержки потоков и сопрограмм. ^[11]^[12]
Cω (C omega) — для исследований, расширяет C#, использует асинхронную связь.
C# — поддерживает параллельные вычисления с использованием блокировки, доходности, а также начиная с версии 5.0, в которой представлены ключевые слова async и await.
Clojure — современный функциональный диалект Lisp на Java . платформе
Concurrent Clean — функциональное программирование, похожее на Haskell.
Параллельные коллекции (CnC). Обеспечивает неявный параллелизм, независимый от модели памяти, путем явного определения потока данных и управления.
Параллельный Haskell — ленивый, чисто функциональный язык, выполняющий параллельные процессы в общей памяти.
Concurrent ML — параллельное расширение Standard ML.
Параллельный Паскаль — Пер Бринч Хансен
Карри
D — мультипарадигмальный язык системного программирования с явной поддержкой параллельного программирования ( модель актора )
E — использует обещания для предотвращения взаимоблокировок
ECMAScript — использует обещания для асинхронных операций.
Eiffel — через механизм SCOOP , основанный на концепции «Проектирование по контракту».
Elixir — динамический и функциональный язык метапрограммирования, работающий на виртуальной машине Erlang.
Erlang — использует синхронную или асинхронную передачу сообщений без общей памяти.
FAUST — функция реального времени, для обработки сигналов компилятор обеспечивает автоматическое распараллеливание через OpenMP или специальный перехватывающий работу. планировщик,
Фортран — coarrays и do concurrent являются частью стандарта Fortran 2008.
Go — для системного программирования с моделью параллельного программирования на основе CSP.
Haskell — параллельный и параллельный язык функционального программирования. ^[13]
Хьюма - функциональный, параллельный, для сред с ограниченным пространством и временем, где автоматные процессы описываются шаблонами синхронных каналов и передачей сообщений.
Io — параллелизм на основе актеров
Янус — имеет отдельные спрашивающие и говорящие логические переменные, каналы сумок; носит чисто декларативный характер
Java — класс потока или интерфейс Runnable.
Джулия — «Примитивы параллельного программирования: задачи, асинхронное ожидание, каналы». ^[14]
JavaScript — через веб-воркеры , в среде браузера, обещания и обратные вызовы .
JoCaml — на основе параллельных и распределенных каналов, расширение OCaml , реализует исчисление соединений процессов.
Присоединиться к Java — параллельно, на основе Java языка
Джоуль — на основе потока данных, общение посредством передачи сообщений.
Джойс — параллельное обучение, построенное на Concurrent Pascal с функциями CSP Пера Бринча Хансена.
LabVIEW — графический, поток данных, функции — это узлы графа, данные — это проводники между узлами; включает объектно-ориентированный язык
Лимбо — родственник Алефа , для системного программирования в Inferno (операционная система)
Локомотивный BASIC — вариант BASIC Amstrad содержит команды EVERY и AFTER для параллельных подпрограмм.
MultiLisp — вариант схемы расширен для поддержки параллелизма.
Модуль-2 — для системного программирования, автор Н. Вирт, как преемник Паскаля с встроенной поддержкой сопрограмм.
Modula-3 — современный член семейства Algol с обширной поддержкой потоков, мьютексов и условных переменных.
Newsqueak — для исследований, где каналы являются первоклассной ценностью; предшественник Алефа
occam — сильно зависит от взаимодействия последовательных процессов (CSP).
- occam-π — современный вариант occam Милнера . , включающий в себя идеи π-исчисления
Орк - сильно конкурентный, недетерминированный, основанный на алгебре Клини.
Оз-Моцарт — мультипарадигма, поддерживает параллелизм с общим состоянием и передачей сообщений, а также фьючерсы.
ParaSail — объектно-ориентированный, параллельный, без указателей, условий гонки.
Pict Милнера . — по сути, исполняемая реализация π-исчисления
Raku по умолчанию включает классы для потоков, промисов и каналов. ^[15]
Python — использует параллелизм на основе потоков и параллелизм на основе процессов. ^[16]
Reia — использует асинхронную передачу сообщений между объектами без общего доступа.
Red/System — для системного программирования на базе Rebol.
Rust — для системного программирования, использующего передачу сообщений с семантикой перемещения, разделяемую неизменяемую память и разделяемую изменяемую память. ^[17]
Scala — общего назначения, предназначенный для выражения общих шаблонов программирования кратким, элегантным и типобезопасным способом.
SequenceL — функционал общего назначения, основными целями проектирования являются простота программирования, ясность и читаемость кода, автоматическое распараллеливание для обеспечения производительности на многоядерном оборудовании и доказуемое отсутствие условий гонки .
СР — для исследований
SuperPascal — параллельный, для обучения, созданный на основе Concurrent Pascal и Joyce Пера Бринча Хансена.
Swift — встроенная поддержка структурированного написания асинхронного и параллельного кода. ^[18]
Юникон — для исследований
TNSDL — для развития телекоммуникационного обмена использует асинхронную передачу сообщений.
Язык описания оборудования VHSIC ( VHDL ) — IEEE STD-1076.
XC — подмножество языка C с расширенным параллелизмом, разработанное XMOS , основанное на взаимодействии последовательных процессов , встроенных конструкциях для программируемого ввода-вывода.

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

См. также

Примечания

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

Ссылки

^ Концепции операционной системы, 9-е издание, Авраам Зильбершац. «Глава 4: Потоки»
^ Хансен, Пер Бринч, изд. (2002). Происхождение параллельного программирования . дои : 10.1007/978-1-4757-3472-0 . ISBN 978-1-4419-2986-0 . S2CID 44909506 .
^ Jump up to: ^а ^б Пайк, Роб (11 января 2012 г.). «Конкуренция — это не параллелизм». Конференция Waza , 11 января 2012 г. Получено с http://talks.golang.org/2012/waza.slide (слайды) и http://vimeo.com/49718712 (видео).
^ «Параллелизм против параллелизма» . Хаскелл Вики .
^ Шнайдер, Фред Б. (6 мая 1997 г.). О параллельном программировании . Спрингер. ISBN 9780387949420 .
^ Jump up to: ^а ^б Бен-Ари, Мордехай (2006). Принципы параллельного и распределенного программирования (2-е изд.). Аддисон-Уэсли. ISBN 978-0-321-31283-9 .
^ Паттерсон и Хеннесси, 2013 , с. 503.
^ Лэмпорт, Лесли (1 сентября 1979 г.). «Как создать многопроцессорный компьютер, который правильно выполняет многопроцессные программы». Транзакции IEEE на компьютерах . С-28 (9): 690–691. дои : 10.1109/TC.1979.1675439 . S2CID 5679366 .
^ «Награда PODC Influential Paper: 2002» , Симпозиум ACM по принципам распределенных вычислений , получено 24 августа 2009 г.
^ Армстронг, Джо (2003). «Создание надежных распределенных систем при наличии ошибок в программном обеспечении» (PDF) .
^ https://en.cppreference.com/w/cpp/header/thread
^ https://en.cppreference.com/w/cpp/header/coroutine
^ Марлоу, Саймон (2013) Параллельное и параллельное программирование в Haskell: методы многоядерного и многопоточного программирования ISBN 9781449335946
^ https://juliacon.talkfunnel.com/2015/21-concurrent-and-parallel-programming-in-julia Параллельное и параллельное программирование в Julia
^ «Параллельность» . docs.perl6.org . Проверено 24 декабря 2017 г.
^ Документация » Стандартная библиотека Python » Параллельное выполнение
^ Блюм, Бен (2012). «Типебезопасное общее изменяемое состояние» . Проверено 14 ноября 2012 г.
^ «Параллельность» . 2022 . Проверено 15 декабря 2022 г.

Источники

Паттерсон, Дэвид А.; Хеннесси, Джон Л. (2013). Организация и проектирование компьютера: аппаратно-программный интерфейс . Серия Моргана Кауфмана по компьютерной архитектуре и дизайну (5-е изд.). Морган Кауфманн. ISBN 978-0-12407886-4 .

Дальнейшее чтение

Дейкстра, EW (1965). «Решение задачи управления параллельным программированием» . Коммуникации АКМ . 8 (9): 569. дои : 10.1145/365559.365617 . S2CID 19357737 .
Херлихи, Морис (2008) [2008]. Искусство многопроцессорного программирования . Морган Кауфманн. ISBN 978-0123705914 .
Дауни, Аллен Б. (2005) [2005]. Маленькая книга семафоров (PDF) . Пресс для зеленого чая. ISBN 978-1-4414-1868-5 . Архивировано из оригинала (PDF) 4 марта 2016 г. Проверено 21 ноября 2009 г.
Фильман, Роберт Э.; Дэниел П. Фридман (1984). Координированные вычисления: инструменты и методы для распределенного программного обеспечения . Нью-Йорк: МакГроу-Хилл. п. 370 . ISBN 978-0-07-022439-1 .
Леппяярви, Йоуни (2008). Прагматичный, исторически ориентированный обзор универсальности примитивов синхронизации (PDF) . Университет Оулу.
Таубенфельд, Гади (2006). Алгоритмы синхронизации и параллельное программирование . Пирсон / Прентис Холл. п. 433. ИСБН 978-0-13-197259-9 .

Внешние ссылки

СМИ, связанные с параллельным программированием, на Викискладе?
Виртуальная библиотека параллельных систем

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

[1] Концепции операционной системы, 9-е издание, Авраам Зильбершац. «Глава 4: Потоки»

[2] Хансен, Пер Бринч, изд. (2002). Происхождение параллельного программирования . дои : 10.1007/978-1-4757-3472-0 . ISBN 978-1-4419-2986-0 . S2CID 44909506 .

[waza-3] Jump up to: ^а ^б Пайк, Роб (11 января 2012 г.). «Конкуренция — это не параллелизм». Конференция Waza , 11 января 2012 г. Получено с http://talks.golang.org/2012/waza.slide (слайды) и http://vimeo.com/49718712 (видео).

[4] «Параллелизм против параллелизма» . Хаскелл Вики .

[6] Шнайдер, Фред Б. (6 мая 1997 г.). О параллельном программировании . Спрингер. ISBN 9780387949420 .

[benari2006-7] Jump up to: ^а ^б Бен-Ари, Мордехай (2006). Принципы параллельного и распределенного программирования (2-е изд.). Аддисон-Уэсли. ISBN 978-0-321-31283-9 .

[FOOTNOTEPattersonHennessy2013503-8] Паттерсон и Хеннесси, 2013 , с. 503.

[9] Лэмпорт, Лесли (1 сентября 1979 г.). «Как создать многопроцессорный компьютер, который правильно выполняет многопроцессные программы». Транзакции IEEE на компьютерах . С-28 (9): 690–691. дои : 10.1109/TC.1979.1675439 . S2CID 5679366 .

[10] «Награда PODC Influential Paper: 2002» , Симпозиум ACM по принципам распределенных вычислений , получено 24 августа 2009 г.

[armstrong2003-11] Армстронг, Джо (2003). «Создание надежных распределенных систем при наличии ошибок в программном обеспечении» (PDF) .

[12] ttps://en.cppreference.com/w/cpp/header/thread

[13] ttps://en.cppreference.com/w/cpp/header/coroutine

[14] Марлоу, Саймон (2013) Параллельное и параллельное программирование в Haskell: методы многоядерного и многопоточного программирования ISBN 9781449335946

[15] ttps://juliacon.talkfunnel.com/2015/21-concurrent-and-parallel-programming-in-julia Параллельное и параллельное программирование в Julia

[16] «Параллельность» . docs.perl6.org . Проверено 24 декабря 2017 г.

[17] Документация » Стандартная библиотека Python » Параллельное выполнение

[bblum2012-18] Блюм, Бен (2012). «Типебезопасное общее изменяемое состояние» . Проверено 14 ноября 2012 г.

[19] «Параллельность» . 2022 . Проверено 15 декабря 2022 г.

[1]

[2]

[3]

[4]

[а]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

v т и Параллельные вычисления
General	Concurrency Concurrency control Concurrent data structures Concurrent hash tables Concurrent users Indeterminacy Linearizability
Process calculi	CSP CCS ACP LOTOS π-calculus Ambient calculus API-Calculus PEPA Join-calculus
Classic problems	ABA problem Cigarette smokers problem Deadlock Dining philosophers problem Producer–consumer problem Race condition Readers–writers problem Sleeping barber problem
Category: Concurrent computing

v т и Типы языков программирования
Level	Machine Assembly Compiled Interpreted Low-level High-level Very high-level Esoteric
Generation	First Second Third Fourth Fifth