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]

Выполнение

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

Взаимодействие и коммуникация

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

Совместная коммуникация памяти
Параллельные компоненты взаимодействуют, изменяя содержимое разделяемых областей памяти (примерами служат 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. ^ ab Pike, Rob (11.01.2012). «Параллелизм — это не параллелизм». Конференция Waza , 11 января 2012 г. Получено с http://talks.golang.org/2012/waza.slide (слайды) и http://vimeo.com/49718712 (видео).
  4. ^ "Параллелизм против параллелизма". Haskell Wiki .
  5. ^ Шнайдер, Фред Б. (1997-05-06). О параллельном программировании . Springer. ISBN 9780387949420.
  6. ^ ab Ben-Ari, Mordechai (2006). Принципы параллельного и распределенного программирования (2-е изд.). Addison-Wesley. ISBN 978-0-321-31283-9.
  7. ^ Паттерсон и Хеннесси 2013, стр. 503.
  8. ^ Лампорт, Лесли (1 сентября 1979 г.). «Как создать многопроцессорный компьютер, который правильно выполняет многопроцессорные программы». IEEE Transactions on Computers . C-28 (9): 690–691. doi :10.1109/TC.1979.1675439. S2CID  5679366.
  9. ^ "PODC Influential Paper Award: 2002", ACM Symposium on Principles of Distributed Computing , получено 24 августа 2009 г.
  10. ^ Армстронг, Джо (2003). "Создание надежных распределенных систем при наличии ошибок программного обеспечения" (PDF) . Архивировано из оригинала (PDF) 2016-04-15.
  11. ^ "Стандартный заголовок библиотеки <thread> (C++11)". en.cppreference.com . Получено 2024-10-03 .
  12. ^ "Стандартный заголовок библиотеки <coroutine> (C++20)". en.cppreference.com . Получено 2024-10-03 .
  13. ^ Марлоу, Саймон (2013) Параллельное и одновременное программирование в Haskell: методы многоядерного и многопоточного программирования ISBN 9781449335946 
  14. ^ "Параллельное и параллельное программирование в Julia — JuliaCon India 2015 — HasGeek Talkfunnel". juliacon.talkfunnel.com . Архивировано из оригинала 2016-10-18.
  15. ^ "PHP: parallel - Manual". www.php.net . Получено 2024-10-03 .
  16. ^ "Параллелизм". docs.perl6.org . Получено 24.12.2017 .
  17. ^ Документация » Стандартная библиотека Python » Параллельное выполнение
  18. ^ Блум, Бен (2012). "Typesafe Shared Mutable State" . Получено 14.11.2012 .
  19. ^ "Параллелизм". 2022 . Получено 2022-12-15 .

Источники

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

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