stringtranslate.com

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

«Обедающие философы » — классическая проблема, связанная с параллелизмом и общими ресурсами.

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

Согласно Робу Пайку , параллелизм — это совокупность независимо выполняемых вычислений [2] , а параллелизм — это не параллелизм: параллелизм — это работа с множеством вещей одновременно, а параллелизм — это выполнение множества вещей одновременно. Параллелизм — это структура, параллелизм — это исполнение, параллелизм обеспечивает способ структурировать решение проблемы, которое может (но не обязательно) быть распараллеливаемым. [3]

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

История

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

Проблемы

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

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

Теория

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

Модели

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

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

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

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

Обозначим S ≡ ⊔ iεω прогрессию Si ( ⊥ S )

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

Логика

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

Упражняться

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

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

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

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

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

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

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

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