Параллелизм (информатика) - Concurrency (computer science)

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

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

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

История

В качестве Лесли Лэмпорт (2015) отмечает: «В то время как параллельная программа выполнение рассматривалось в течение многих лет, информатика параллелизма началась с Эдсгер Дейкстра основополагающая статья 1965 года, в которой взаимное исключение проблема. ... В последующие десятилетия наблюдался огромный рост интереса к параллелизму, особенно в распределенные системы. Оглядываясь назад на истоки этой области, можно выделить фундаментальную роль, которую сыграл Эдсгер Дейкстра ».[2]

вопросы

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

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

Теория

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

Модели

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

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

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

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

ОбозначитьS ≡ ⊔i∈ω прогрессSя(⊥S)

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

Логика

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

Упражняться

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

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

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

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

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

  1. ^ Лэмпорт, Лесли (июль 1978 г.). «Время, часы и порядок событий в распределенной системе» (PDF). Коммуникации ACM. 21 (7): 558–565. Дои:10.1145/359545.359563. Получено 4 февраля 2016.
  2. ^ Лэмпорт, Лесли. «Лекция Тьюринга: Компьютерные науки о параллелизме: первые годы (Сообщения ACM, том 58, № 6, июнь 2015 г.)». ACM. Получено 22 марта 2017.
  3. ^ а б Кливленд, Рэнс; Скотт Смолка (декабрь 1996 г.). «Стратегические направления в исследовании параллелизма». Опросы ACM Computing. 28 (4): 607. Дои:10.1145/242223.242252.
  4. ^ Кэмпбелл, Колин; Джонсон, Ральф; Миллер, Аде; Тоуб, Стивен (август 2010). Параллельное программирование с Microsoft .NET. Microsoft Press. ISBN  978-0-7356-5159-3.
  5. ^ Фильман, Роберт; Дэниел Фридман (1984). Скоординированные вычисления - инструменты и методы для распределенного программного обеспечения. Макгроу-Хилл. ISBN  978-0-07-022439-1.
  6. ^ Келлер, Йорг; Кристоф Кесслер; Джеспер Трэфф (2001). Практическое программирование PRAM. Джон Уайли и сыновья.
  7. ^ Ли, Эдвард; Альберто Сангиованни-Винчентелли (декабрь 1998 г.). «Платформа для сравнения моделей вычислений» (PDF). IEEE Transactions по CAD. 17 (12): 1217–1229. Дои:10.1109/43.736561.
  8. ^ Могенс Нильсен; Владимиро Сассоне; Глинн Винскель (1993). «Взаимосвязи между моделями параллелизма». Школа / Симпозиум REX.
  9. ^ Фредерик Кнабе. Распределенный протокол для связи на основе каналов с Choice PARLE 1992.
  10. ^ Уильям Клингер (Июнь 1981 г.). «Основы актерской семантики». Докторская диссертация по математике. Массачусетский технологический институт. HDL:1721.1/6935. Цитировать журнал требует | журнал = (помощь)
  11. ^ Роско, Колин (2001). Модальные и временные свойства процессов.. Springer. ISBN  978-0-387-98717-0.

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

  • Линч, Нэнси А. (1996). Распределенные алгоритмы. Морган Кауфманн. ISBN  978-1-55860-348-6.
  • Таненбаум, Эндрю С .; Ван Стин, Маартен (2002). Распределенные системы: принципы и парадигмы. Прентис Холл. ISBN  978-0-13-088893-8.
  • Курки-Суонио, Рейно (2005). Практическая теория реактивных систем. Springer. 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. Aufl.; 1; ed.). Лондон; Берлин ;: Springer. ISBN  9783642290329

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