stringtranslate.com

Параллелизм (компьютерные науки)

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

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

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

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

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

Проблемы

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

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

Теория

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

Модели

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

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

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

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

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

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

Логики

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

Упражняться

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

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

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

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

Ссылки

  1. ^ Лампорт, Лесли (июль 1978 г.). «Время, часы и упорядочение событий в распределенной системе» (PDF) . Communications of the ACM . 21 (7): 558–565. doi :10.1145/359545.359563. S2CID  215822405 . Получено 4 февраля 2016 г. .
  2. ^ Параллельное и одновременное программирование на языке Haskell . O'Reilly Media. 2013. ISBN 9781449335922.
  3. ^ ab Cleaveland, Rance; Scott Smolka (декабрь 1996 г.). «Стратегические направления в исследовании параллелизма». ACM Computing Surveys . 28 (4): 607. doi : 10.1145/242223.242252 . S2CID  13264261.
  4. ^ Кэмпбелл, Колин; Джонсон, Ральф; Миллер, Аде; Тоуб, Стивен (август 2010 г.). Параллельное программирование с Microsoft .NET. Microsoft Press. ISBN 978-0-7356-5159-3.
  5. ^ Filman, Robert; Daniel Friedman (1984). Координированные вычисления — инструменты и методы для распределенного программного обеспечения . McGraw-Hill. ISBN 978-0-07-022439-1.
  6. ^ Келлер, Йорг; Кристоф Кесслер; Йеспер Трефф (2001). Практическое программирование PRAM . Джон Уайли и сыновья.
  7. ^ Ли, Эдвард; Альберто Санджованни-Винчентелли (декабрь 1998 г.). «Структура для сравнения моделей вычислений» (PDF) . IEEE Transactions on CAD . 17 (12): 1217–1229. doi :10.1109/43.736561.
  8. ^ Могенс Нильсен; Владимиро Сассоне; Глинн Винскел (1993). «Связи между моделями параллелизма». Школа/симпозиум REX .
  9. ^ Фредерик Кнабе. Распределенный протокол для канальной связи с выбором PARLE 1992.
  10. ^ Уильям Клингер (июнь 1981 г.). «Основы семантики акторов». Диссертация на соискание ученой степени доктора математики. Массачусетский технологический институт. hdl :1721.1/6935. {{cite journal}}: Цитировать журнал требует |journal=( помощь )
  11. ^ Роско, Колин (2001). Модальные и временные свойства процессов . Springer. ISBN 978-0-387-98717-0.

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

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