Параллельные вычисления - это форма вычислений, при которой несколько вычислений выполняются одновременно - в перекрывающиеся периоды времени - вместо того, чтобы последовательно - при этом одно завершается до начала следующего.
Это свойство системы - будь то программа , компьютер или сеть - где есть отдельная точка выполнения или «поток управления» для каждого процесса. Одновременно система является одним где вычисление может заранее , не дожидаясь все другие вычисления , чтобы закончить. [1]
Параллельные вычисления - это форма модульного программирования . В своих парадигмах общее вычисление учтено в subcomputations , которые могут выполняться одновременно. Пионерами в области параллельных вычислений являются Эдсгер Дейкстра , Пер Бринч Хансен и Кар Хоар .
СОДЕРЖАНИЕ
1 Введение
1.1 Координация доступа к общим ресурсам
1.2 Преимущества
2 модели
2.1 Модели согласованности
3 Реализация
3.1 Взаимодействие и общение
4 История
5 Распространенность
6 языков, поддерживающих параллельное программирование
7 См. Также
8 Примечания
9 ссылки
10 Источники
11 Дальнейшее чтение
12 Внешние ссылки
Вступление
См. Также: Параллельные вычисления
В этом разделе есть несколько проблем. Пожалуйста, помогите улучшить его или обсудите эти вопросы на странице обсуждения . ( Узнайте, как и когда удалить эти сообщения-шаблоны )
Этот раздел требует дополнительных ссылок для проверки . Пожалуйста, помогите улучшить эту статью , добавив цитаты из надежных источников . Материал, не полученный от источника, может быть оспорен и удален. ( Декабрь 2016 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )
Этот раздел, возможно, содержит оригинальные исследования . Пожалуйста, улучшите его , проверив сделанные утверждения и добавив встроенные цитаты . Заявления, содержащие только оригинальные исследования, следует удалить. ( Декабрь 2016 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )
( Узнайте, как и когда удалить этот шаблон сообщения )
Концепция параллельного вычисления часто путать с родственными , но отчетливой концепции параллельных вычислений , [2] [3] , хотя оба могут быть описаны как «несколько процессов , исполняющих в течение того же периода времени ». В параллельных вычислений, выполнение происходит в той же физической момент: например, на отдельных процессорах одного многопроцессорной машины, с целью ускорения вычисли--параллельных вычислений невозможно на ( один основной ) один процессор, так как только один вычисление может происходить в любой момент (в течение любого одного такта). [a] Напротив, параллельные вычисления состоят из времени жизни процесса.перекрываются, но выполнение не обязательно должно происходить в один и тот же момент. Цель здесь - моделировать процессы во внешнем мире, которые происходят одновременно, например, несколько клиентов одновременно обращаются к серверу. Структурирование программных систем, состоящих из нескольких одновременно взаимодействующих частей, может быть полезно для решения проблемы сложности, независимо от того, могут ли эти части выполняться параллельно. [4] : 1
Например, параллельные процессы могут выполняться на одном ядре путем чередования этапов выполнения каждого процесса через срезы с разделением времени : одновременно выполняется только один процесс, и если он не завершается в течение своего временного среза, он приостанавливается , другой процесс начинается или возобновляется, а затем возобновляется первоначальный процесс. Таким образом, несколько процессов частично выполняются в один момент, но в этот момент выполняется только один процесс. [ необходима цитата ]
Параллельные вычисления могут выполняться параллельно [2] [5], например, путем назначения каждого процесса отдельному процессору или ядру процессора или распределения вычислений по сети. Однако в целом языки, инструменты и методы параллельного программирования могут не подходить для параллельного программирования, и наоборот. [ необходима цитата ]
Точное время выполнения задач в параллельной системе зависит от расписания , и задачи не всегда должны выполняться одновременно. Например, даны две задачи, T1 и T2: [ необходима ссылка ]
T1 может быть выполнен и завершен до T2 или наоборот (последовательный и последовательный)
Т1 и Т2 могут выполняться поочередно (последовательно и одновременно)
T1 и T2 могут выполняться одновременно в один и тот же момент времени (параллельно и одновременно)
Слово «последовательный» используется как антоним как «параллельный», так и «параллельный»; когда они явно различаются, параллельные / последовательные и параллельные / последовательные используются как противоположные пары. [6] Расписание, в котором задачи выполняются по одной (последовательно, без параллелизма), без чередования (последовательно, без параллелизма: ни одна задача не начинается, пока не завершится предыдущая задача), называется последовательным расписанием . Набор задач, которые можно планировать последовательно, можно сериализовать , что упрощает управление параллелизмом . [ необходима цитата ]
Координация доступа к общим ресурсам
Основная проблема при разработке параллельных программ - это управление параллелизмом : обеспечение правильной последовательности взаимодействий или обмена данными между различными вычислительными исполнениями и координация доступа к ресурсам, которые совместно используются исполнениями. [5] Потенциальные проблемы включают состояния гонки , взаимоблокировки и нехватку ресурсов . Например, рассмотрим следующий алгоритм для снятия средств с текущего счета, представленного общим ресурсом balance:
Предположим balance = 500, и два параллельных потока выполняют вызовы withdraw(300)и withdraw(350). Если строка 3 в обеих операциях выполняется перед строкой 5, обе операции обнаруживают, что balance >= withdrawalоценка равна true, и выполнение переходит к вычитанию суммы снятия. Однако, поскольку оба процесса производят снятие средств, общая снятая сумма в конечном итоге будет больше, чем исходный баланс. Подобные проблемы с общими ресурсами выигрывают от использования контроля параллелизма или неблокирующих алгоритмов .
Преимущества
В этом разделе не процитировать любые источники . Пожалуйста, помогите улучшить этот раздел , добавив цитаты из надежных источников . Материал, не полученный от источника, может быть оспорен и удален . ( Декабрь 2006 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )
Преимущества параллельных вычислений:
Повышенная производительность программы - параллельное выполнение параллельной программы позволяет количеству задач, выполненных за заданное время, увеличиваться пропорционально количеству процессоров в соответствии с законом Густафсона.
Высокая скорость реагирования на ввод / вывод - программы с интенсивным вводом / выводом обычно ждут завершения операций ввода или вывода. Параллельное программирование позволяет использовать время, которое было бы потрачено на ожидание, для другой задачи. [ необходима цитата ]
Более подходящая структура программы - некоторые проблемы и проблемные области хорошо подходят для представления в виде параллельных задач или процессов. [ необходима цитата ]
Модели
Представленные в 1962 году сети Петри были первой попыткой кодифицировать правила одновременного выполнения. Позже на их основе была основана теория потоков данных, и были созданы архитектуры потоков данных, чтобы физически реализовать идеи теории потоков данных. Начиная с конца 1970-х годов, были разработаны процессы исчисления, такие как исчисление коммуникационных систем (CCS) и коммуникационные последовательные процессы (CSP), чтобы позволить алгебраические рассуждения о системах, составленных из взаимодействующих компонентов. Π-исчисление добавлена возможность для рассуждений о динамических топологиях.
Автоматы ввода / вывода были представлены в 1987 году.
Логика, такая как TLA + Лампорта , и математические модели, такие как трассировки и диаграммы событий акторов , также были разработаны для описания поведения параллельных систем.
Программная транзакционная память заимствует из теории баз данных концепцию атомарных транзакций и применяет их к доступам к памяти.
Модели согласованности
Основная статья: Модель согласованности
Языки параллельного программирования и многопроцессорные программы должны иметь модель согласованности (также известную как модель памяти). Модель согласованности определяет правила того, как происходят операции с памятью компьютера и как создаются результаты.
Одна из первых моделей непротиворечивости была Лэмпорт «s последовательная непротиворечивость модели. Последовательная согласованность - это свойство программы, при котором ее выполнение дает те же результаты, что и последовательная программа. В частности, программа является последовательной, если «результаты любого выполнения такие же, как если бы операции всех процессоров выполнялись в некотором последовательном порядке, и операции каждого отдельного процессора появляются в этой последовательности в порядке, указанном его программой. ". [7]
См. Также: Расслабленное последовательное
Реализация
Этот раздел нуждается в расширении . Вы можете помочь, добавив к нему . ( Февраль 2014 г. )
Для реализации параллельных программ может использоваться ряд различных методов, таких как реализация каждого вычислительного выполнения как процесса операционной системы или реализация вычислительных процессов как набора потоков в рамках одного процесса операционной системы.
Взаимодействие и общение
В некоторых параллельных вычислительных системах взаимодействие между параллельными компонентами скрыто от программиста (например, с помощью фьючерсов ), в то время как в других оно должно обрабатываться явно. Явное общение можно разделить на два класса:
Общение с общей памятью
Параллельные компоненты взаимодействуют, изменяя содержимое ячеек совместно используемой памяти (на примере Java и C # ). Этот стиль параллельного программирования обычно требует использования некоторой формы блокировки (например, мьютексов , семафоров или мониторов ) для координации между потоками. Программа, которая правильно реализует любой из них, называется потокобезопасной .
Обмен сообщениями
Параллельные компоненты обмениваются сообщениями (например, MPI , Go , Scala , Erlang и occam ). Обмен сообщениями может выполняться асинхронно или может использовать синхронный стиль «рандеву», в котором отправитель блокируется до тех пор, пока сообщение не будет получено. Асинхронная передача сообщений может быть надежной или ненадежной (иногда ее называют «отправь и помолись»). Обсуждать параллелизм передачи сообщений гораздо проще, чем параллелизм с разделяемой памятью, и он обычно считается более надежной формой параллельного программирования. [ необходима цитата ]Доступен широкий спектр математических теорий для понимания и анализа систем передачи сообщений, включая модель актора и различные вычисления процессов . Передача сообщений может быть эффективно реализована с помощью симметричной многопроцессорной обработки , с согласованностью кеш- памяти совместно используемой памяти или без нее .
Общая память и параллелизм при передаче сообщений имеют разные характеристики производительности. Обычно (хотя и не всегда) накладные расходы на память для каждого процесса и на переключение задач ниже в системе передачи сообщений, но накладные расходы на передачу сообщений больше, чем при вызове процедуры. Эти различия часто перекрываются другими факторами производительности.
История
Параллельные вычисления возникли в результате более ранних работ по железным дорогам и телеграфии , начиная с 19-го и начала 20-го века, и некоторые термины, такие как семафоры, относятся к этому периоду. Они возникли для решения вопроса о том, как управлять несколькими поездами в одной и той же железнодорожной системе (избегать столкновений и максимизировать эффективность) и как обрабатывать несколько передач по заданному набору проводов (повышение эффективности), например, с помощью мультиплексирования с временным разделением (1870-е годы). ).
Академическое исследование параллельных алгоритмов началось в 1960-х годах, когда Дейкстра (1965) был признан первой статьей в этой области, выявившей и устраняющей взаимное исключение . [8]
Распространенность
Параллелизм широко распространен в вычислениях, начиная с низкоуровневого оборудования на одном кристалле и кончая всемирными сетями. Примеры приведены ниже.
На уровне языка программирования:
Канал
Сопрограмма
Будущее и обещания
На уровне операционной системы:
Многозадачность компьютера , включая как совместную многозадачность, так и вытесняющую многозадачность
Разделение времени , заменившее последовательную пакетную обработку заданий на одновременное использование системы.
Процесс
Нить
На сетевом уровне сетевые системы обычно параллельны по своей природе, поскольку состоят из отдельных устройств.
Языки параллельного программирования - это языки программирования, которые используют языковые конструкции для параллелизма . Эти конструкции могут включать многопоточность , поддержку распределенных вычислений , передачу сообщений , общие ресурсы (включая разделяемую память ) или фьючерсы и обещания . Такие языки иногда называют языками, ориентированными на параллелизм, или языками программирования, ориентированными на параллелизм (COPL). [9]
Сегодня наиболее часто используемыми языками программирования, имеющими особые конструкции для параллелизма, являются Java и C # . Оба этих языка в основном используют модель параллелизма с общей памятью с блокировкой, обеспечиваемой мониторами (хотя модели передачи сообщений могут быть реализованы и были реализованы поверх базовой модели с общей памятью). Из языков, использующих модель параллелизма с передачей сообщений, Erlang , вероятно, в настоящее время является наиболее широко используемым в отрасли. [ необходима цитата ]
Многие языки параллельного программирования были разработаны больше как языки для исследований (например, Pict ), а не как языки для производственного использования. Однако такие языки, как Erlang , Limbo и occam , за последние 20 лет в разное время использовались в промышленности. Неполный список языков, которые используют или предоставляют средства параллельного программирования:
Ada - общая цель, с встроенной поддержкой передачи сообщений и параллелизма на основе мониторинга.
Alef - параллельный, с потоками и передачей сообщений, для системного программирования в ранних версиях Plan 9 от Bell Labs.
Алиса - расширение Standard ML , добавляет поддержку параллелизма через фьючерсы.
Атэдзи PX -продолжение на Java с параллельными примитивами вдохновленного от пи-исчисления
Axum - специфичный для домена, параллельный, на основе модели акторов и .NET Common Language Runtime с использованием синтаксиса, подобного C
BMDFM - двоичная модульная машина потока данных
C ++ —std :: thread
Cω (C omega) - для исследований, расширяет C #, использует асинхронную связь.
C # - поддерживает параллельные вычисления с использованием lock, yield, также начиная с версии 5.0, введены ключевые слова async и await.
Clojure - современный функциональный диалект Лиспа на платформе Java.
Параллельные коллекции (CnC) - обеспечивает неявный параллелизм, независимый от модели памяти, путем явного определения потока данных и управления.
Concurrent Haskell - ленивый, чистый функциональный язык, работающий с параллельными процессами в общей памяти.
Concurrent ML - одновременное расширение Standard ML
Параллельный Паскаль - Пер Бринч Хансен
Карри
D - многопарадигмальный системный язык программирования с явной поддержкой параллельного программирования ( модель акторов )
E - использует обещания для предотвращения тупиковых ситуаций.
ECMAScript - использует обещания для асинхронных операций.
Eiffel - через механизм SCOOP , основанный на концепциях дизайна по контракту.
Elixir - язык динамического и функционального метапрограммирования, работающий на виртуальной машине Erlang.
Erlang - использует асинхронную передачу сообщений без общего доступа
ФАУСТ -Real время функциональное, для обработки сигналов, компилятор обеспечивает автоматическое распараллеливание с помощью OpenMP или конкретной работы кражи планировщика
Fortran - coarrays и do concurrent являются частью стандарта Fortran 2008
Go - для системного программирования с моделью параллельного программирования, основанной на CSP.
Haskell - язык параллельного и параллельного функционального программирования [10]
Юм - функциональный , параллельный, для сред с ограниченным пространством и временем, где процессы автоматов описываются паттернами синхронных каналов и передачей сообщений.
Io - параллелизм на основе акторов
Янус - отличает разных спрашивающих и кассиров логических переменных, каналов сумок; чисто декларативный
JavaScript - через веб- воркеров , в среде браузера, обещания и обратные вызовы .
JoCaml - на основе параллельных и распределенных каналов, расширение OCaml , реализует объединение процессов.
Присоединяйтесь к Java - одновременно, на основе языка Java
Джоуль - на основе потока данных, общается путем передачи сообщений
Джойс -concurrent, обучение, построенное на Concurrent Pascal с функциями от ПСА по Per Brinch Hansen
LabVIEW - графическое изображение, поток данных, функции - это узлы в графе, данные - это провода между узлами; включает объектно-ориентированный язык
Limbo - родственник Alef , для системного программирования в Inferno (операционная система)
MultiLisp - вариант схемы расширен для поддержки параллелизма
Modula-2 - для системного программирования, Н. Вирт как преемник Паскаля с встроенной поддержкой сопрограмм.
Modula-3 - современный член семейства Algol с обширной поддержкой потоков, мьютексов, условных переменных.
Newsqueak - для исследований, когда каналы являются первоклассной ценностью; предшественник Алефа
occam - сильно зависит от взаимодействия последовательных процессов (CSP)
occam-π - современный вариант occam , который включает идеи из π-исчисления Милнера.
Орк - сильно конкурирующий, недетерминированный, основанный на алгебре Клини
Оз-Моцарт - мультипарадигма, поддерживает параллелизм с общим состоянием и передачей сообщений, а также фьючерсы.
ParaSail - объектно-ориентированный, параллельный, свободный от указателей, условия гонки
Pict - по сути, исполняемая реализация π-исчисления Милнера
Raku по умолчанию включает классы для потоков, обещаний и каналов [12]
Python - использует параллелизм на основе потоков и параллелизм на основе процессов [13]
ИНА -uses асинхронной передачи сообщений между без совместного использования объектов
Red / System - для системного программирования на основе Rebol.
Rust - для системного программирования, использующего передачу сообщений с семантикой перемещения, разделяемую неизменяемую память и разделяемую изменяемую память. [14]
Scala - общая цель, разработанная для краткого, элегантного и типобезопасного выражения общих шаблонов программирования.
SequenceL - функциональность общего назначения, основными целями проектирования являются простота программирования, ясность кода и удобочитаемость, автоматическое распараллеливание для повышения производительности на многоядерном оборудовании, а также отсутствие условий гонки.
SR - для исследования
SuperPascal -concurrent, для обучения, построенный на Concurrent Pascal и Джойса от Per Brinch Hansen
Юникон - для исследований
TNSDL - для развития телекоммуникационных обменов, использует асинхронную передачу сообщений.
Язык описания оборудования VHSIC ( VHDL ) - IEEE STD-1076
XC - подмножество языка C с расширенным параллелизмом, разработанное XMOS , основанное на взаимодействии последовательных процессов , встроенных конструкциях для программируемого ввода-вывода.
Многие другие языки предоставляют поддержку параллелизма в виде библиотек на уровнях, примерно сопоставимых с приведенным выше списком.
Смотрите также
Асинхронный ввод / вывод
Пространство Чу
Программирование на основе потоков
Java ConcurrentMap
Список важных публикаций по параллельным, параллельным и распределенным вычислениям
Проект Птолемея
Состояние гонки § Вычисления
Сноп (математика)
Обработка транзакции
Примечания
^ Это не учитывает параллелизм, внутренний по отношению к ядру процессора, такой как конвейерная обработка или векторизация инструкций. Одноядерная, однопроцессорная машина может быть способна к некоторому параллелизму, например, с сопроцессором , но только процессор - нет.
использованная литература
^ Понятия операционной системы 9-е издание, Абрахам Зильбершатц. «Глава 4: Потоки»
^ a b Пайк, Роб (11.01.2012). «Параллелизм - это не параллелизм». Конференция Waza , 11 января 2012 г. Получено с http://talks.golang.org/2012/waza.slide (слайды) и http://vimeo.com/49718712 (видео).
^ «Параллелизм против параллелизма» . Haskell Wiki .
^ Шнайдер, Фред Б. (1997-05-06). О параллельном программировании . Springer. ISBN 9780387949420.
^ а б Бен-Ари, Мордехай (2006). Принципы параллельного и распределенного программирования (2-е изд.). Эддисон-Уэсли. ISBN 978-0-321-31283-9.
Перейти ↑ Patterson & Hennessy 2013 , p. 503.
^ Лэмпорт, Лесли (1 сентября 1979). «Как сделать многопроцессорный компьютер, который правильно выполняет многопроцессорные программы». Транзакции IEEE на компьютерах . С-28 (9): 690–691. DOI : 10.1109 / TC.1979.1675439 . S2CID 5679366 .
^ «PODC Influential Paper Award: 2002» , Симпозиум ACM по принципам распределенных вычислений , получено 24 августа 2009 г.
^ Армстронг, Джо (2003). «Создание надежных распределенных систем при наличии программных ошибок» (PDF) .
^ Марлоу, Саймон (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 .
Источники
Паттерсон, Дэвид А .; Хеннесси, Джон Л. (2013). Компьютерная организация и дизайн: аппаратно-программный интерфейс . Серия Морган Кауфманн в компьютерной архитектуре и дизайне (5 - е изд.). Морган Кауфманн. ISBN 978-0-12407886-4.
дальнейшее чтение
Дейкстра, EW (1965). «Решение проблемы управления параллельным программированием». Коммуникации ACM . 8 (9): 569. DOI : 10,1145 / 365559,365617 . S2CID 19357737 .
Херлихи, Морис (2008) [2008]. Искусство многопроцессорного программирования . Морган Кауфманн. ISBN 978-0123705914.
Дауни, Аллен Б. (2005) [2005]. Маленькая книга семафоров (PDF) . Пресс для зеленого чая. ISBN 978-1-4414-1868-5. Архивировано из оригинального (PDF) 04 марта 2016 года . Проверено 21 ноября 2009 .
Филман, Роберт Э .; Дэниел П. Фридман (1984). Скоординированные вычисления: инструменты и методы для распределенного программного обеспечения . Нью-Йорк: Макгроу-Хилл. п. 370 . ISBN 978-0-07-022439-1.
Леппяярви, Йоуни (2008). Прагматичный исторически ориентированный обзор универсальности примитивов синхронизации (PDF) . Университет Оулу.
Таубенфельд, Гади (2006). Алгоритмы синхронизации и параллельное программирование . Пирсон / Прентис Холл. п. 433. ISBN. 978-0-13-197259-9.
внешние ссылки
СМИ, связанные с параллельным программированием на Викискладе?
Виртуальная библиотека параллельных систем
vтеПараллельные вычисления
Общий
Параллелизм
Контроль параллелизма
Расчет процесса
CSP
CCS
ACP
LOTOS
π-исчисление
Окружающее исчисление
API-исчисление
PEPA
Соединение-исчисление
Классические проблемы
Проблема ABA
Проблема курильщиков сигарет
Тупик
Проблема обедающих философов
Проблема производителя и потребителя
Состояние гонки
Проблема читателей – писателей
Проблема сна парикмахера
Категория: Параллельные вычисления
Категории :
Параллельные вычисления
Технологии операционной системы
Эдсгер В. Дейкстра
Голландские изобретения
Скрытые категории:
Статьи с кратким описанием
Краткое описание соответствует Викиданным
Статьи, требующие дополнительных ссылок, от февраля 2014 г.
Все статьи, требующие дополнительных ссылок
Статьи, требующие дополнительных ссылок, за декабрь 2016 г.
Статьи, которые могут содержать оригинальные исследования за декабрь 2016 г.
Все статьи, которые могут содержать оригинальные исследования
Статьи с множеством проблем с обслуживанием
Все статьи с утверждениями без источника
Статьи с неподтвержденными источниками за декабрь 2016 г.
Статьи, требующие дополнительных ссылок, от декабря 2006 г.
Статьи будут расширены с февраля 2014 г.
Все статьи будут расширены
Статьи с использованием небольших окон сообщений
Статьи с неподтвержденными источниками за май 2013 г.
Статьи с неподтвержденными источниками за август 2010 г.
Ссылка на категорию Commons находится в Викиданных