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

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

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

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

Вступление

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

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

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

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

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

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

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

Основная проблема при разработке параллельных программ - это управление параллелизмом : обеспечение правильной последовательности взаимодействий или обмена данными между различными вычислительными исполнениями и координация доступа к ресурсам, которые совместно используются исполнениями. Возможные проблемы включают состояния гонки , взаимоблокировки и нехватку ресурсов . Например, рассмотрим следующий алгоритм для снятия средств с текущего счета, представленного общим ресурсом 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 + Лампорта , и математические модели, такие как трассировки и диаграммы событий акторов , также были разработаны для описания поведения параллельных систем.

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

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

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

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

Реализация

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

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

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

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

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

История

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

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

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

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

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

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

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

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

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

Сегодня наиболее часто используемыми языками программирования, имеющими особые конструкции для параллелизма, являются 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 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 - язык параллельного и параллельного функционального программирования.
  • Юм - функциональный , параллельный, для сред с ограниченным пространством и временем, где процессы автоматов описываются паттернами синхронных каналов и передачей сообщений.
  • Io - параллелизм на основе акторов
  • Янус - отличает разных спрашивающих и кассиров логических переменных, каналов сумок; чисто декларативный
  • Java - класс потоков или интерфейс Runnable
  • Юля - «Примитивы параллельного программирования: Задачи, async-wait, Каналы».
  • JavaScript - через веб- воркеров , в среде браузера, обещания и обратные вызовы .
  • JoCaml - на основе параллельных и распределенных каналов, расширение OCaml , реализует объединение процессов.
  • Присоединяйтесь к Java - одновременно, на основе языка Java
  • Джоуль - на основе потока данных, общается путем передачи сообщений
  • Джойс -concurrent, обучение, построенное на Concurrent Pascal с функциями от ПСА по Per Brinch Hansen
  • LabVIEW - графическое изображение, поток данных, функции - это узлы в графе, данные - это провода между узлами; включает объектно-ориентированный язык
  • Limbo - родственник Alef , для системного программирования в Inferno (операционная система)
  • MultiLisp - вариант схемы расширен для поддержки параллелизма
  • Modula-2 - для системного программирования, Н. Вирт как преемник Паскаля с встроенной поддержкой сопрограмм.
  • Modula-3 - современный член семейства Algol с обширной поддержкой потоков, мьютексов, условных переменных.
  • Newsqueak - для исследований, когда каналы являются первоклассной ценностью; предшественник Алефа
  • occam - сильно зависит от взаимодействия последовательных процессов (CSP)
  • Орк - сильно конкурирующий, недетерминированный, основанный на алгебре Клини
  • Оз-Моцарт - мультипарадигма, поддерживает параллелизм с общим состоянием и передачей сообщений, а также фьючерсы.
  • ParaSail - объектно-ориентированный, параллельный, свободный от указателей, условия гонки
  • Pict - по сути, исполняемая реализация π-исчисления Милнера
  • Raku по умолчанию включает классы для потоков, обещаний и каналов.
  • Python - использует параллелизм на основе потоков и параллелизм на основе процессов
  • ИНА -uses асинхронной передачи сообщений между без совместного использования объектов
  • Red / System - для системного программирования на основе Rebol.
  • Rust - для системного программирования, использующего передачу сообщений с семантикой перемещения, разделяемую неизменяемую память и разделяемую изменяемую память.
  • Scala - общая цель, разработанная для краткого, элегантного и безопасного для типов выражения общих шаблонов программирования.
  • SequenceL - функциональность общего назначения, основными целями проектирования являются простота программирования, ясность кода и удобочитаемость, автоматическое распараллеливание для повышения производительности на многоядерном оборудовании, а также отсутствие условий гонки.
  • SR - для исследования
  • SuperPascal -concurrent, для обучения, построенный на Concurrent Pascal и Джойса от Per Brinch Hansen
  • Юникон - для исследований
  • TNSDL - для развития телекоммуникационных обменов, использует асинхронную передачу сообщений.
  • Язык описания оборудования VHSIC ( VHDL ) - IEEE STD-1076
  • XC - подмножество языка C с расширенным параллелизмом, разработанное XMOS , основанное на взаимодействии последовательных процессов , встроенных конструкциях для программируемого ввода-вывода.

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

Смотрите также

Примечания

использованная литература

Источники

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

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

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