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

Из Википедии, бесплатной энциклопедии
«Параллельный компьютер» перенаправляется сюда. Чтобы узнать о компании, см. Concurrent Computer Corporation .
Более практическое обсуждение см. в разделе Параллельные вычисления . Чтобы узнать о других значениях, см. Параллелизм (значения) .
«Обедающие философы » — классическая проблема, связанная с параллелизмом и общими ресурсами.

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

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

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

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

Проблемы [ править ]

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

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

Теория [ править ]

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

Модели [ править ]

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

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

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

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

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

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

Логика [ править ]

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

Практика [ править ]

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

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

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

См. также [ править ]

Ссылки [ править ]

  1. ^ Лэмпорт, Лесли (июль 1978 г.). «Время, часы и порядок событий в распределенной системе» (PDF) . Коммуникации АКМ . 21 (7): 558–565. дои : 10.1145/359545.359563 . S2CID   215822405 . Проверено 4 февраля 2016 г.
  2. ^ Параллельное и параллельное программирование на Haskell . О'Рейли Медиа. 2013. ISBN  9781449335922 .
  3. ^ Перейти обратно: а б Кливленд, Рэнс; Скотт Смолка (декабрь 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.
  10. ^ Уильям Клингер (июнь 1981 г.). «Основы семантики актеров». Докторская диссертация по математике. Массачусетский технологический институт. hdl : 1721.1/6935 . {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )
  11. ^ Роско, Колин (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

Внешние ссылки [ править ]

Retrieved from "https://en.wikipedia.org/w/index.php?title=Concurrency_(computer_science)&oldid=1226014059"