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

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

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

Примечание — В русскоязычной литературе нередко путаются термины «параллелизм» и «конкурентность»^{[источник не указан 154 дня]}. Оба^{[источник не указан 154 дня]} термина означают одновременность процессов, но первый — на физическом уровне (параллельное исполнение нескольких процессов, нацеленное только на повышение скорости исполнения за счёт использования соответствующей аппаратной поддержки), а второй — на логическом (парадигма проектирования систем, идентифицирующая процессы как независимые, что в том числе позволяет их исполнять физически параллельно, но в первую очередь нацелено на упрощение написания многопоточных программ и повышение их устойчивости).

ПроблематикаПравить

Поскольку вычисления в параллельных системах взаимодействуют друг с другом, число возможных путей выполнения может быть чрезвычайно велико, и результирующий итог может стать недетерминированным (неопределенным). Параллельное использование общих ресурсов может стать одним из источников недетерминированности, приводящей к таким проблемам, как взаимная блокировка или фатальный недостаток ресурсов.^[1]

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

ТеорияПравить

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

МоделиПравить

Сейчас разработано уже большое число формальных методов для моделирования и понимания работы параллельных систем, в том числе:^[2]

Параллельный случайный доступ к компьютеру^[3]
Модель акторов
Вычислительные связанные модели, например, модель массового синхронного параллелизма
Сети Петри
Исчисление процессов
Пространство кортежей, например, Linda
SCOOP (Simple Concurrent Object-Oriented Programming — Простое параллельное объектно-ориентированное программирование)

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

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

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

Denote_S ≡ ⊔_i∈ω progression_Sⁱ(⊥_S)

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

ЛогикаПравить

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

ПрактикаПравить

В этом разделе будет использоваться два понятия параллельности, свойственные англоязычной литературе, поскольку речь пойдёт о сравнении их друг с другом. Термин Concurrency будет переводиться «одновременность», а термин Parallelism будет переводиться «параллелизм».

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

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

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

См. такжеПравить

ПримечанияПравить

↑ ¹ ² Cleaveland, Rance; Scott Smolka. Strategic Directions in Concurrency Research (англ.) // ACM Computing Surveys (англ.) (рус. : journal. — 1996. — December (vol. 28, no. 4). — P. 607. — doi:10.1145/242223.242252.
↑ Filman, Robert; Daniel Friedman. Coordinated Computing - Tools and Techniques for Distributed Software (англ.). — McGraw-Hill Education, 1984. — ISBN 0-07-022439-0. Архивированная копия (неопр.). Дата обращения: 5 октября 2011. Архивировано из оригинала 16 мая 2007 года.
↑ Keller, Jörg; Christoph Keßler, Jesper Träff. Practical PRAM Programming (неопр.). — John Wiley and Sons, 2001.
↑ Lee, Edward; Alberto Sangiovanni-Vincentelli. A Framework for Comparing Models of Computation (англ.) // IEEE Transactions on CAD (англ.) (рус. : journal. — 1998. — December (vol. 17, no. 12). — P. 1217—1229. — doi:10.1109/43.736561.
↑ Mogens Nielsen; Vladimiro Sassone and Glynn Winskel (1993). “Relationships Between Models of Concurrency”. REX School/Symposium. Архивировано из оригинала 2009-02-26. Дата обращения 2011-10-05. Используется устаревший параметр |deadlink= (справка)
↑ Frederick Knabe. A Distributed Protocol for Channel-Based Communication with Choice PARLE 1992.
↑ William Clinger. Foundations of Actor Semantics (неопр.). — MIT, 1981. — June (т. Mathematics Doctoral Dissertation).
↑ Roscoe, Colin. Modal and Temporal Properties of Processes (англ.). — Springer, 2001. — ISBN 0-387-98717-7.

СсылкиПравить

Concurrent Systems at The WWW Virtual Library
Lynch, Nancy A. Distributed Algorithms (неопр.). — Morgan Kauffman, 1996. — ISBN 1558603484.
Tanenbaum, Andrew S.; Van Steen, Maarten. Distributed Systems: Principles and Paradigms (англ.). — Prentice Hall, 2002. — ISBN 0-13-088893-1.
Kurki-Suonio, Reino. A Practical Theory of Reactive Systems (неопр.). — Springer, 2005. — ISBN 3-540-23342-3.
Garg, Vijay K. Elements of Distributed Computing (неопр.). — Wiley-IEEE Press, 2002. — ISBN 0-471-03600-5.
Magee, Jeff;, Kramer, Jeff. Concurrency: State Models and Java Programming (англ.). — Wiley, 2006. — ISBN 0-470-09355-2.

[cleaveland1996-1] ¹ ² Cleaveland, Rance; Scott Smolka. Strategic Directions in Concurrency Research (англ.) // ACM Computing Surveys (англ.) (рус. : journal. — 1996. — December (vol. 28, no. 4). — P. 607. — doi:10.1145/242223.242252.

[2] Filman, Robert; Daniel Friedman. Coordinated Computing - Tools and Techniques for Distributed Software (англ.). — McGraw-Hill Education, 1984. — ISBN 0-07-022439-0. Архивированная копия (неопр.). Дата обращения: 5 октября 2011. Архивировано из оригинала 16 мая 2007 года.

[3] Keller, Jörg; Christoph Keßler, Jesper Träff. Practical PRAM Programming (неопр.). — John Wiley and Sons, 2001.

[4] Lee, Edward; Alberto Sangiovanni-Vincentelli. A Framework for Comparing Models of Computation (англ.) // IEEE Transactions on CAD (англ.) (рус. : journal. — 1998. — December (vol. 17, no. 12). — P. 1217—1229. — doi:10.1109/43.736561.

[5] Mogens Nielsen; Vladimiro Sassone and Glynn Winskel (1993). “Relationships Between Models of Concurrency”. REX School/Symposium. Архивировано из оригинала 2009-02-26. Дата обращения 2011-10-05. Используется устаревший параметр |deadlink= (справка)

[6] Frederick Knabe. A Distributed Protocol for Channel-Based Communication with Choice PARLE 1992.

[clinger1981-7] William Clinger. Foundations of Actor Semantics (неопр.). — MIT, 1981. — June (т. Mathematics Doctoral Dissertation).

[stirling-8] Roscoe, Colin. Modal and Temporal Properties of Processes (англ.). — Springer, 2001. — ISBN 0-387-98717-7.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]