Параллелизм (информатика)

В информатике очереди параллелизм это способность различных частей или модулей вне — или в частичном порядке программы, алгоритма или задачи выполняться , не влияя на результат. Это позволяет параллельно выполнять параллельные модули, что может значительно повысить общую скорость выполнения в многопроцессорных и многоядерных системах. Говоря более техническим языком, параллелизм означает возможность разложения программы, алгоритма или проблемы на независимые от порядка или частично упорядоченные компоненты или вычислительные единицы. ^{[ 1 ]}

Параллелизм против параллелизма

что в информатике Обратите внимание , параллелизм и параллелизм — это две разные вещи: параллельная программа использует несколько ядер ЦП , каждое из которых выполняет задачу независимо. С другой стороны, параллелизм позволяет программе выполнять несколько задач даже на одном ядре ЦП; ядро переключается между задачами (т.е. потоками ), не обязательно завершая каждую из них. Программа может иметь обе характеристики параллелизма и параллелизма, ни одну из них или их комбинацию. ^{[ 2 ]}

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

Проблемы

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

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

Теория

Теория параллелизма была активной областью исследований в теоретической информатике . Одним из первых предложений была Карла Адама Петри плодотворная работа о сетях Петри в начале 1960-х годов. За прошедшие годы было разработано множество формализмов для моделирования и рассуждений о параллелизме.

Модели

Был разработан ряд формализмов для моделирования и понимания параллельных систем, в том числе: ^{[ 5 ]}

Параллельная машина с произвольным доступом ^{[ 6 ]}
актера Модель
Вычислительные модели мостов, такие как модель объемного синхронного параллельного параллелизма (BSP).
Сети Петри
Процесс исчисления
Кортежные пространства , например, Линда
Простое параллельное объектно-ориентированное программирование (SCOOP)
Язык координации Рео
Трассировка моноидов

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

Распространение различных моделей параллелизма побудило некоторых исследователей разработать способы унификации этих различных теоретических моделей. Например, Ли и Санджованни-Винсентелли продемонстрировали, что так называемая модель «маркированного сигнала» может использоваться для обеспечения общей основы для определения денотационной семантики множества различных моделей параллелизма. ^{[ 7 ]} в то время как Нильсен, Сассоне и Винскель продемонстрировали, что теорию категорий можно использовать для обеспечения аналогичного единого понимания различных моделей. ^{[ 8 ]}

Теорема о параллельном представлении в модели актора обеспечивает довольно общий способ представления параллельных систем, которые закрыты в том смысле, что они не получают сообщений извне. (Другие системы параллелизма, например, исчисление процессов , можно смоделировать в модели актора с использованием протокола двухфазной фиксации . ^{[ 9 ]}) Математическое обозначение, обозначающее замкнутую систему S строится со все более лучшими приближениями на основе начального поведения, называемого ⊥ _S с использованием функции, аппроксимирующей поведение прогрессия _S для построения обозначения (значения) для С следующим образом: ^{[ 10 ]}

Обозначим _S ≡ ⊔ _iεω прогрессию _S^я(⊥ _S)

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

Логика

Различные типы темпоральной логики ^{[ 11 ]} может использоваться для обоснования рассуждений о параллельных системах. Некоторые из этих логик, такие как линейная временная логика и логика дерева вычислений , позволяют делать утверждения о последовательностях состояний, через которые может пройти параллельная система. Другие, такие как логика вычислительного дерева действий , логика Хеннесси-Милнера и Лэмпорта временная логика действий , строят свои утверждения на основе последовательностей действий (изменений состояния). Основное применение этой логики — написание спецификаций для параллельных систем. ^{[ 3 ]}

Упражняться

Параллельное программирование включает в себя языки программирования и алгоритмы, используемые для реализации параллельных систем. Параллельное программирование обычно рассматривается ^{[ кем? ]} быть более общим, чем параллельное программирование , поскольку оно может включать произвольные и динамические шаблоны связи и взаимодействия, тогда как параллельные системы обычно ^{[ по мнению кого? ]} иметь заранее определенную и хорошо структурированную схему общения. Базовые цели параллельного программирования включают корректность , производительность и надежность . Параллельные системы, такие как операционные системы и системы управления базами данных, обычно разрабатываются ^{[ кем? ]} работать неопределенно долго, включая автоматическое восстановление после сбоя, и не завершаться неожиданно (см. Управление параллелизмом ). Некоторый ^{[ нужен пример ]} параллельные системы реализуют форму прозрачного параллелизма, в котором параллельные вычислительные объекты могут конкурировать за один ресурс и совместно использовать его, но сложности этой конкуренции и совместного использования скрыты от программиста.

Поскольку они используют общие ресурсы, параллельные системы в целом ^{[ по мнению кого? ]} требуют включения некоторых ^{[ нужен пример ]} своего рода арбитр где-то в их реализации (часто в базовом оборудовании), контролирующий доступ к этим ресурсам. Использование арбитров приводит к возможности неопределенности в параллельных вычислениях , что имеет серьезные последствия для практики, включая правильность и производительность. Например, арбитраж вводит неограниченный недетерминизм , который вызывает проблемы с проверкой модели , поскольку он вызывает взрыв в пространстве состояний и может даже привести к тому, что модели будут иметь бесконечное количество состояний.

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

См. также

Ссылки

^ Лэмпорт, Лесли (июль 1978 г.). «Время, часы и порядок событий в распределенной системе» (PDF) . Коммуникации АКМ . 21 (7): 558–565. дои : 10.1145/359545.359563 . S2CID 215822405 . Проверено 4 февраля 2016 г.
^ Параллельное и параллельное программирование на Haskell . О'Рейли Медиа. 2013. ISBN 9781449335922 .
^ Jump up to: ^а ^б Кливленд, Рэнс; Скотт Смолка (декабрь 1996 г.). «Стратегические направления в исследованиях параллелизма» . Обзоры вычислительной техники ACM . 28 (4): 607. дои : 10.1145/242223.242252 . S2CID 13264261 .
^ Кэмпбелл, Колин; Джонсон, Ральф; Миллер, Ад; Тауб, Стивен (август 2010 г.). Параллельное программирование с помощью Microsoft .NET . Майкрософт Пресс. ISBN 978-0-7356-5159-3 .
^ Филман, Роберт; Дэниел Фридман (1984). Координированные вычисления — инструменты и методы для распределенного программного обеспечения . МакГроу-Хилл. ISBN 978-0-07-022439-1 .
^ Келлер, Йорг; Кристоф Кесслер; Йеспер Трефф (2001). Практическое программирование PRAM . Джон Уайли и сыновья.
^ Ли, Эдвард; Альберто Санджованни-Винсентелли (декабрь 1998 г.). «Схема сравнения моделей вычислений» (PDF) . Транзакции IEEE в САПР . 17 (12): 1217–1229. дои : 10.1109/43.736561 .
^ Могенс Нильсен; Владимиро Сассоне; Глинн Винскель (1993). «Отношения между моделями параллелизма» . Школа/Симпозиум REX .
^ Фредерик Кнабе. Распределенный протокол для канальной связи с возможностью выбора PARLE 1992.
^ Уильям Клингер (июнь 1981 г.). «Основы семантики актеров». Докторская диссертация по математике. Массачусетский технологический институт. hdl : 1721.1/6935 . {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )
^ Роско, Колин (2001). Модальные и временные свойства процессов . Спрингер. ISBN 978-0-387-98717-0 .

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

Линч, Нэнси А. (1996). Распределенные алгоритмы . Морган Кауфманн. ISBN 978-1-55860-348-6 .
Таненбаум, Эндрю С.; Ван Стин, Мартен (2002). Распределенные системы: принципы и парадигмы . Прентис Холл. ISBN 978-0-13-088893-8 .
Курки-Суонио, Рейно (2005). Практическая теория реактивных систем . Спрингер. ISBN 978-3-540-23342-8 .
Гарг, Виджай К. (2002). Элементы распределенных вычислений . Wiley-IEEE Press. ISBN 978-0-471-03600-5 .
Маги, Джефф; Крамер, Джефф (2006). Параллелизм: модели состояний и программирование на Java . Уайли. ISBN 978-0-470-09355-9 .
Дистефано С. и Брунео Д. (2015). Количественные оценки распределенных систем: Методологии и методы (1-е изд.). Сомерсет: John Wiley & Sons Inc. ISBN 9781119131144
Бхаттачарья, СС (2013;2014;). Справочник по системам обработки сигналов (Второй;2;2-й 2013; изд.). Нью-Йорк, штат Нью-Йорк: Springer.10.1007/978-1-4614-6859-2. ISBN 9781461468592
Уолтер, К. (2012;2014;). Оценка устойчивости и оценка вычислительных систем (1. Ауфл.;1; изд.). Лондон;Берлин;: Springer. ISBN 9783642290329

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

[1] Лэмпорт, Лесли (июль 1978 г.). «Время, часы и порядок событий в распределенной системе» (PDF) . Коммуникации АКМ . 21 (7): 558–565. дои : 10.1145/359545.359563 . S2CID 215822405 . Проверено 4 февраля 2016 г.

[2] Параллельное и параллельное программирование на Haskell . О'Рейли Медиа. 2013. ISBN 9781449335922 .

[cleaveland1996-3] Jump up to: ^а ^б Кливленд, Рэнс; Скотт Смолка (декабрь 1996 г.). «Стратегические направления в исследованиях параллелизма» . Обзоры вычислительной техники ACM . 28 (4): 607. дои : 10.1145/242223.242252 . S2CID 13264261 .

[4] Кэмпбелл, Колин; Джонсон, Ральф; Миллер, Ад; Тауб, Стивен (август 2010 г.). Параллельное программирование с помощью Microsoft .NET . Майкрософт Пресс. ISBN 978-0-7356-5159-3 .

[5] Филман, Роберт; Дэниел Фридман (1984). Координированные вычисления — инструменты и методы для распределенного программного обеспечения . МакГроу-Хилл. ISBN 978-0-07-022439-1 .

[6] Келлер, Йорг; Кристоф Кесслер; Йеспер Трефф (2001). Практическое программирование PRAM . Джон Уайли и сыновья.

[7] Ли, Эдвард; Альберто Санджованни-Винсентелли (декабрь 1998 г.). «Схема сравнения моделей вычислений» (PDF) . Транзакции IEEE в САПР . 17 (12): 1217–1229. дои : 10.1109/43.736561 .

[8] Могенс Нильсен; Владимиро Сассоне; Глинн Винскель (1993). «Отношения между моделями параллелизма» . Школа/Симпозиум REX .

[9] Фредерик Кнабе. Распределенный протокол для канальной связи с возможностью выбора PARLE 1992.

[clinger1981-10] Уильям Клингер (июнь 1981 г.). «Основы семантики актеров». Докторская диссертация по математике. Массачусетский технологический институт. hdl : 1721.1/6935 . {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )

[stirling-11] Роско, Колин (2001). Модальные и временные свойства процессов . Спрингер. ISBN 978-0-387-98717-0 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

v т и Параллельные вычисления
Общий	Параллелизм Управление параллелизмом Параллельные структуры данных Параллельные хэш-таблицы Одновременные пользователи Неопределенность Линеаризуемость
Процесс исчисления	CSP CCS АШП ЛОТОС π-исчисление Окружающее исчисление API-исчисление БУМАГА Джойн-исчисление
Классические задачи	проблема ABA Проблема курильщиков сигарет Тупик Проблема обедающих философов Проблема производителя и потребителя Состояние гонки Проблема читателей и писателей Проблема со спящим парикмахером
Категория: Параллельные вычисления