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

Для более теоретического обсуждения см. Параллелизм (информатика).
Парадигмы программирования

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

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

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

Вступление

Смотрите также: Параллельные вычисления

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

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

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

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

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

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

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

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

1 bool снять со счета(int снятие)2 {3     если (баланс >= снятие)4     {5         баланс -= снятие;6         возвращаться истинный;7     } 8     возвращаться ложный;9 }

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

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

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

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

Модели

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

Выполнение

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

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

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

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

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

История

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

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

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

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

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

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

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

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

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

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

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

  • Ада - общего назначения с встроенной поддержкой передачи сообщений и параллелизма на основе мониторинга
  • Алеф - одновременный, с потоками и передачей сообщений, для системного программирования в ранних версиях План 9 от Bell Labs
  • Алиса - расширение на Стандартный ML, добавляет поддержку параллелизма через фьючерсы
  • Ateji PX - расширение на Ява с параллельными примитивами, вдохновленными π-исчисление
  • Аксум - зависящий от домена, параллельный, на основе модели субъектов и .NET Common Language Runtime с использованием синтаксиса, подобного C
  • BMDFM —Бинарная модульная машина потока данных
  • C ++ —Std :: thread
  • Cω (C omega) - для исследований, расширяет C #, использует асинхронную связь.
  • C # —Поддерживает параллельные вычисления с использованием lock, yield, а также начиная с версии 5.0, введены ключевые слова async и await
  • Clojure -современное, функциональный диалект Лисп на Ява Платформа
  • Параллельная очистка - функциональное программирование, подобное Haskell
  • Параллельные коллекции (CnC) - обеспечивает неявный параллелизм независимо от модели памяти путем явного определения потока данных и управления.
  • Параллельный Haskell - ленивый, чистый функциональный язык, управляющий параллельными процессами в общей памяти
  • Параллельный ML - одновременное продление Стандартный ML
  • Параллельный Паскаль -к Пер Бринч Хансен
  • Карри
  • D —мультипарадигма язык системного программирования с явной поддержкой параллельного программирования (актерская модель )
  • E —Использует обещания для предотвращения тупиковых ситуаций
  • ECMAScript —Использует обещания для асинхронных операций
  • Эйфель - через его SCOOP механизм, основанный на концепции «Дизайн по контракту»
  • Эликсир - язык динамического и функционального метапрограммирования, работающий на виртуальной машине Erlang.
  • Erlang - использует асинхронную передачу сообщений без общего доступа
  • ФАУСТ - функционал реального времени, для обработки сигналов компилятор обеспечивает автоматическое распараллеливание через OpenMP или конкретный воровство планировщик
  • Фортран —грубые и делать одновременно являются частью стандарта Fortran 2008
  • Идти —Для системного программирования, с моделью параллельного программирования, основанной на CSP
  • Haskell - язык параллельного и параллельного функционального программирования[9]
  • Юм - функциональный, параллельный, для сред с ограниченным пространством и временем, где процессы автоматов описываются шаблонами синхронных каналов и передачей сообщений
  • Ио - акторный параллелизм
  • Янус - отличительные особенности спрашивающие и кассира к логическим переменным, каналам пакетов; чисто декларативный
  • Ява - класс потока или интерфейс Runnable
  • Юля - «Примитивы параллельного программирования: задачи, асинхронное ожидание, каналы».[10]
  • JavaScript -через веб-работники, в среде браузера, обещания, и обратные вызовы.
  • JoCaml - на основе параллельных и распределенных каналов, расширение OCaml, реализует соединительное исчисление процессов
  • Присоединяйтесь к Java - одновременно, на основе Ява язык
  • Джоуль - на основе потока данных, общается путем передачи сообщений
  • Джойс - одновременное обучение, построенное на Параллельный Паскаль с особенностями от CSP к Пер Бринч Хансен
  • LabVIEW - графические, поток данных, функции - это узлы в графе, данные - это связи между узлами; включает объектно-ориентированный язык
  • Лимбо - родственник Алеф, для системного программирования в Inferno (операционная система)
  • MultiLisp —Схема вариант расширен для поддержки параллелизма
  • Модула-2 —Для системного программирования, Н. Вирт как преемник Паскаля с встроенной поддержкой сопрограмм
  • Модула-3 - современный член семейства Algol с обширной поддержкой потоков, мьютексов, условных переменных.
  • Newsqueak - для исследований с первоклассной ценностью каналов; предшественник Алеф
  • Оккам - под сильным влиянием связь последовательных процессов (CSP)
  • Орк - сильно совпадающие, недетерминированные, основанные на Клини алгебра
  • Оз-Моцарт - мультипарадигма, поддерживает параллелизм с общим состоянием и передачей сообщений, а также фьючерсы
  • ParaSail - объектно-ориентированный, параллельный, свободный от указателей, условия гонки
  • Pict - по сути, исполняемая реализация Милнера π-исчисление
  • Раку по умолчанию включает классы для потоков, обещаний и каналов[11]
  • Python с помощью Безстековый Python
  • Рея - использует асинхронную передачу сообщений между объектами без общего доступа
  • Красный / Система - для системного программирования на основе Ребол
  • Ржавчина - для системного программирования с использованием передачи сообщений с семантикой перемещения, совместно используемой неизменяемой памяти и совместно используемой изменяемой памяти.[12]
  • Scala - общего назначения, предназначенного для краткого, элегантного и безопасного для типов выражения общих шаблонов программирования.
  • SequenceL - функциональность общего назначения, основными целями проектирования являются простота программирования, ясность кода, удобочитаемость и автоматическое распараллеливание для обеспечения производительности на многоядерном оборудовании и, возможно, без условия гонки
  • SR —Для исследования
  • СуперПаскаль - одновременное обучение, основанное на Параллельный Паскаль и Джойс к Пер Бринч Хансен
  • Юникон —Для исследования
  • TNSDL —Для развития телекоммуникационных обменов использует асинхронную передачу сообщений
  • Язык описания оборудования VHSIC (VHDL ) —IEEE STD-1076
  • XC - подмножество языка C с расширенным параллелизмом, разработанное XMOS, на основе связь последовательных процессов, встроенные конструкции для программируемого ввода / вывода

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

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

Примечания

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

Рекомендации

  1. ^ Понятия операционной системы 9-е издание, Авраам Зильбершатц. «Глава 4: Потоки»
  2. ^ а б Пайк, Роб (2012-01-11). «Параллелизм - это не параллелизм». Ваза конференция, 11 января 2012 г. Получено из http://talks.golang.org/2012/waza.slide (слайды) и http://vimeo.com/49718712 (видео).
  3. ^ «Параллелизм против параллелизма». Haskell Вики.
  4. ^ Шнайдер, Фред Б. (1997-05-06). О параллельном программировании. Springer. ISBN  9780387949420.
  5. ^ а б Бен-Ари, Мордехай (2006). Принципы параллельного и распределенного программирования (2-е изд.). Эддисон-Уэсли. ISBN  978-0-321-31283-9.
  6. ^ Паттерсон и Хеннесси 2013, п. 503.
  7. ^ «Премия PODC Influential Paper Award: 2002», Симпозиум ACM по принципам распределенных вычислений, получено 2009-08-24
  8. ^ Армстронг, Джо (2003). «Создание надежных распределенных систем при наличии программных ошибок» (PDF).
  9. ^ Марлоу, Саймон (2013) Параллельное и параллельное программирование в Haskell: методы многоядерного и многопоточного программирования ISBN  9781449335946
  10. ^ https://juliacon.talkfunnel.com/2015/21-concurrent-and-parallel-programming-in-julia Параллельное и параллельное программирование в Julia
  11. ^ «Параллелизм». docs.perl6.org. Получено 2017-12-24.
  12. ^ Блюм, Бен (2012). «Типобезопасное совместное мутабельное состояние». Получено 2012-11-14.

Источники

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

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

внешняя ссылка