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

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

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

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

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

Введение [ править ]

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

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

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

Параллельные вычисления могут выполняться параллельно ^{[2] [5],} например, путем назначения каждого процесса отдельному процессору или ядру процессора или распределения вычислений по сети. Однако в целом языки, инструменты и методы параллельного программирования могут не подходить для параллельного программирования, и наоборот. ^{[ необходима цитата ]}

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

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

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

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

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

bool  вывести ( int  отвод ){ если  ( баланс  > =  снятие ) { баланс  - =  снятие ; вернуть  истину ; }  вернуть  ложь ;}

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

Преимущества [ править ]

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

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

Модели [ править ]

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

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

Реализация [ править ]

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

Взаимодействие и общение [ править ]

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

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

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

Обмен сообщениями

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

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

История [ править ]

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

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

Распространенность [ править ]

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

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

• Канал
• Сопрограмма
• Будущее и обещания

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

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

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

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

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

Сегодня наиболее часто используемыми языками программирования, имеющими особые конструкции для параллелизма, являются 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.
• Concurrent Clean - функциональное программирование, подобное Haskell.
• Параллельные коллекции (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 - язык параллельного и параллельного функционального программирования ^[9]
• Юм - функциональный , параллельный, для сред с ограниченным пространством и временем, где процессы автоматов описываются паттернами синхронных каналов и передачей сообщений.
• Io - параллелизм на основе акторов
• Янус - отличает разных спрашивающих и кассиров логических переменных, каналов сумок; чисто декларативный
• Java - класс потоков или интерфейс Runnable
• Юля - «Примитивы параллельного программирования: Задачи, async-wait, Каналы». ^[10]
• 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 по умолчанию включает классы для потоков, обещаний и каналов ^[11]
• Python с использованием Stackless Python
• ИНА -uses асинхронной передачи сообщений между без совместного использования объектов
• Red / System - для системного программирования на основе Rebol.
• Rust - для системного программирования, использующего передачу сообщений с семантикой перемещения, разделяемую неизменяемую память и разделяемую изменяемую память. ^[12]
• Scala - общая цель, разработанная для краткого, элегантного и типобезопасного выражения общих шаблонов программирования.
• SequenceL - функциональность общего назначения, основными целями проектирования являются простота программирования, ясность кода и удобочитаемость, автоматическое распараллеливание для повышения производительности на многоядерном оборудовании, а также отсутствие условий гонки.
• SR - для исследования
• SuperPascal -concurrent, для обучения, построенный на Concurrent Pascal и Джойса от Per Brinch Hansen
• Юникон - для исследований
• TNSDL - для развития телекоммуникационных обменов, использует асинхронную передачу сообщений.
• Язык описания оборудования VHSIC ( VHDL ) - IEEE STD-1076
• XC - подмножество языка C с расширенным параллелизмом, разработанное XMOS , основанное на взаимодействии последовательных процессов , встроенных конструкциях для программируемого ввода-вывода.

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

См. Также [ править ]

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

Заметки [ править ]

Ссылки [ править ]

Источники [ править ]

Дальнейшее чтение [ править ]

• Дейкстра, 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.

Внешние ссылки [ править ]

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