stringtranslate.com

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

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

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

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

Введение

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

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

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

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

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

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

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

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

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

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

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

Модели

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

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

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

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

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

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

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

Выполнение

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

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

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

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

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

История

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

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

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

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

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

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

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

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

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

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

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

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

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

Примечания

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

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

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

Источники

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

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