Параллелизм (компьютерные науки)
Способность выполнять задачу не последовательно

Параллелизм относится к способности системы выполнять несколько задач посредством одновременного выполнения или разделения времени (контекстного переключения), совместного использования ресурсов и управления взаимодействиями. Параллелизм улучшает отзывчивость, пропускную способность и масштабируемость в современных вычислениях, включая: [1] [2] [3] [4] [5]

Параллелизм — это более широкая концепция, которая охватывает несколько связанных идей, в том числе: [1] [2] [3] [4] [5]

  • Параллелизм (одновременное выполнение на нескольких процессорных устройствах). Параллелизм выполняет задачи независимо на нескольких ядрах ЦП, в то время как параллелизм управляет несколькими задачами на одном или нескольких ядрах, переключаясь между потоками или разделяя их по времени без завершения каждого из них. Программы могут демонстрировать только параллелизм, только параллелизм, и параллелизм, и параллелизм, ни то, ни другое. [6]
    Параллелизм против параллелизма
  • Многопоточность и многопроцессорность (общие системные ресурсы)
  • Синхронизация (координация доступа к общим ресурсам)
  • Координация (управление взаимодействием между параллельными задачами)
  • Управление параллелизмом (обеспечение согласованности и целостности данных)
  • Межпроцессное взаимодействие (IPC, упрощение обмена информацией)

Проблемы

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

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

Теория

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

Модели

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

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

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

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

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

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

Логики

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

Упражняться

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

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

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

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

Ссылки

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

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

  • Линч, Нэнси А. (1996). Распределенные алгоритмы . Морган Кауфманн. ISBN 978-1-55860-348-6.
  • Таненбаум, Эндрю С.; Ван Стин, Маартен (2002). Распределенные системы: принципы и парадигмы . Prentice Hall. ISBN 978-0-13-088893-8.
  • Курки-Суонио, Рейно (2005). Практическая теория реактивных систем . Springer. ISBN 978-3-540-23342-8.
  • Гарг, Виджай К. (2002). Элементы распределенных вычислений . Wiley-IEEE Press. ISBN 978-0-471-03600-5.
  • Magee, Jeff; Kramer, Jeff (2006). Параллелизм: модели состояний и программирование на Java . Wiley. ISBN 978-0-470-09355-9.
  • Distefano, S., & Bruneo, D. (2015). Количественные оценки распределенных систем: Методологии и методы (1-е изд.). Somerset: John Wiley & Sons Inc. ISBN 9781119131144 
  • Bhattacharyya, SS (2013;2014;). Справочник по системам обработки сигналов (Второе;2;2-е 2013; изд.). Нью-Йорк, Нью-Йорк: Springer.10.1007/978-1-4614-6859-2 ISBN 9781461468592 
  • Вольтер, К. (2012;2014;). Оценка устойчивости и оценка вычислительных систем (1. Aufl.;1; ред.). Лондон;Берлин;: Springer. ISBN 9783642290329 
  • Дневник алгебры процессов — блог профессора Луки Ачето о теории параллелизма
  • Параллельные системы в Виртуальной библиотеке WWW
  • Презентация шаблонов параллелизма на scaleconf
Retrieved from "https://en.wikipedia.org/w/index.php?title=Concurrency_(computer_science)&oldid=1266066899"