- Параллелизм (компьютерные науки)
-
В компьютерных науках параллели́зм — это свойство систем, при которой несколько вычислений выполняются одновременно, и при этом, возможно, взаимодействуют друг с другом. Вычисления могут выполняться на нескольких ядрах одного чипа с вытеснящим разделением времени потоков вычислений на одном процессоре, либо выполняться на физически отдельных процессорах. Для выполнения параллельных вычислений разработаны ряд математических моделей, в том числе сети Петри, исчисление процессов, модели параллельных случайных доступов к вычислениям и модели акторов.
Следует отметить, что в англоязычной литературе для описания понятия параллелизма в компьютерных науках используются два термина: Concurrency (одновременность) и Parallelism (параллелизм). Между ними имеется некоторое различие, о чём будет сказано ниже. В русскоязычной литературе для обеих этих терминов используется только один перевод: параллелизм, что создаёт определённые терминологические трудности.
Содержание
Проблематика
Поскольку вычисления в параллельных системах взаимодействуют друг с другом, число возможных путей выполнения может быть чрезвычайно велико, и результирующий итог может стать недетерминированным. Параллельное использование общих ресурсов может стать одним из источников недетерминированности, приводящей к таким проблемам, как взаимная блокировка или фатальный недостаток ресурсов.[1]
Построение параллельных систем требует поиска надёжных методов координации выполняемых процессов, обмена данными, распределения памяти и планирования для минимизации времени отклика и увеличения пропускной способности.
Теория
Теория параллельных вычислений является активной областью исследований теоретической информатики. Одним из первых предложений в этом направлении была плодотворная работа Карла Адама Петри по сетям Петри в начале 1960-х. В последующие годы был разработан широкий спектр формализмов для моделирования и описания параллельных систем.
Модели
Сейчас разработано уже большое число формальных методов для моделирования и понимания работы параллельных систем, в том числе:[2]
- Параллельный случайный доступ к компьютеру[3]
- Модель акторов
- Вычислительные связанные модели, например, модель массового синхронного параллелизма
- Сети Петри
- Исчисление процессов
- Пространство кортежей, например, Linda
- SCOOP (Simple Concurrent Object-Oriented Programming — Простое параллельное объектно-ориентированное программирование)
Некоторые из этих моделей параллелизма предназначены в первую очередь для логических умозаключений и описания спецификаций, тогда как другие могут быть использованы на протяжении всего цикла разработки, включая проектирование, внедрение, доказательство истинности результатов, тестирование и моделирование параллельных систем.
Распространение различных моделей параллелизма побудило некоторых исследователей разработать способы объединения этих теоретических моделей. Например, Ли и Санджованни-Винсентелли показали, что так называемую модель «меченых сигналов» можно использовать для создания общей основы для описания денотационной семантики различных моделей параллелизма,[4] а Нильсен, Сассун и Винскль показали, что теория категорий может быть использована для обеспечения единого понимания различных моделей.[5]
Теорема представления параллелизма из модели актора обеспечивает достаточно общий способ описания параллельных систем, замкнутых в том смысле, что они не получают сообщений извне. Другие методы описания параллелизма, как, например, исчисление процессов, могут быть описаны через модель актора, используя двухфазный протокол фиксации.[6] Математические обозначения, используемые для описания замкнутой системы S, обеспечивают в большей степени хорошее приближение, если они строятся на основе начального поведения, обозначаемого ⊥S, с использованием аппроксимирующей функции поведения progressionS.[7] Тогда обозначения для S строятся следующим образом:
-
- DenoteS ≡ ⊔i∈ω progressionSi(⊥S)
Таким образом, S может быть математически выражена посредством всех его возможных поведений.
Логика
Чтобы обеспечить логические рассуждения о параллельных систем, можно использовать различные виды темпоральных логик[8]. Некоторые из них, как, например, линейная темпоральная логика или логика вычислительного дерева, позволяют делать утверждения о последовательности состояний, через которые параллельная система может пройти. Другие же, такие как логика действий вычислительного дерева, логика Хеннесси-Милнера или темпоральная логика действий Лэмпорта, строят свои утверждения от последовательности действий (изменения состояний). Основное применение этих логик состоит в записи спецификаций для параллельных систем.[1]
Практика
В этом разделе будет использоваться два понятия параллельности, свойственные англоязычной литературе, поскольку речь пойдёт о сравнении их друг с другом. Термин Concurrency будет переводиться «одновременность», а термин Parallelism будет переводиться «параллелизм».
Одновременное программирование включает в себя языки программирования и алгоритмы, используемые для реализации одновременных систем. Одновременное программирование обычно считается более общим понятием, чем параллельное программирование, поскольку оно может включать произвольные динамические модели общения и взаимодействия, тогда как параллельные системы чаще всего реализуют заранее определённые и хорошо структурированные модели связей. Основными целями одновременного программирования являются корректность, эффективность, устойчивость. Одновременные системы, такие как операционные системы и системы управления базами данных предназначены прежде всего для работы в неопределённых условиях, в том числе с учётом автоматического восстановления после сбоя, они не должны неожиданно прекращать работу. Некоторые одновременные системы осуществляют работу в виде прозрачной одновременности, при которой одновременные вычислительные сущности могут конкурировать за использование одного и того же ресурса, но суть этой конкуренции скрыта для программиста.
Поскольку одновременные системы используют общие ресурсы, они обычно требуют наличие какого-либо арбитра, встроенного в их реализацию (часто в базовое оборудование) для управления доступом к этим ресурсам. Использование арбитров создаёт вероятность неопределённости в одновременных вычислениях, которая имеет большое значение для практики, в том числе для обеспечения корректности и эффективности. Например, арбитраж не исключает неограниченный индетерминизм, который связан с проблемой проверки моделей, являющейся причиной взрывного характера пространства состояний и может даже стать причиной образования модели с бесконечным числом состояний.
Некоторые одновременные модели программирования включают создание сопроцессов и детерминированной одновременности. В этих моделях потоки выполнения по управлению процессами явно отдают свое кванты времени либо системе, либо другому процессу.
См. также
- Технология «клиент-сервер»
- Кластеры
- Параллельные вычисления
- Распределённые вычисления
- OpenMP
- Разделённое глобальное адресное пространство
- Процессы
- Пучок (математика)
- Поток выполнения
- X10 (язык программирования)
Примечания
- ↑ 1 2 Cleaveland, Rance; Scott Smolka (December, 1996). «Strategic Directions in Concurrency Research». ACM Computing Surveys 28 (4): 607. DOI:10.1145/242223.242252.
- ↑ Filman Robert Coordinated Computing - Tools and Techniques for Distributed Software. — McGraw-Hill, 1984. — ISBN 0-07-022439-0
- ↑ Keller Jörg Practical PRAM Programming. — John Wiley and Sons, 2001.
- ↑ Lee, Edward; Alberto Sangiovanni-Vincentelli (December, 1998). «A Framework for Comparing Models of Computation». IEEE Transactions on CAD 17 (12): 1217–1229. DOI:10.1109/43.736561.
- ↑ Mogens Nielsen; Vladimiro Sassone and Glynn Winskel (1993). "Relationships Between Models of Concurrency". REX School/Symposium.
- ↑ Frederick Knabe. A Distributed Protocol for Channel-Based Communication with Choice PARLE 1992.
- ↑ William Clinger (June 1981). «Foundations of Actor Semantics» (MIT).
- ↑ 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. 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
Параллельные вычисления Общие положения Облачные вычисления · Высокопроизводительные вычисления · Кластерные вычисления · Распределённые вычисления · Грид-вычисления · Гибридные вычисления Уровни паралеллизма Биты · Инструкции · Данные · Задачи Поток выполнения Суперпоточность · Гиперпоточность Теория Закон Амдала · Закон Густавсона — Барсиса · Эффективность затрат · Метрика Карпа-Флэтта · Замедление · Коэффициент ускорения Элементы Процесс · Поток · Файбер · ПМПД · Instruction window Взаимодействие Многопроцессорность · Многопоточность · Когерентность памяти · Когерентность кэша · Недействительность кэша · Барьер · Синхронизация · Контрольная точка Программирование Модели (Скрытый паралеллизм · Явный паралеллизм · Параллелизм) · Таксономия Флинна (SISD • SIMD • MISD • MIMD (SPMD)) · Поток · Неблокирующая синхронизация Компьютерная техника Мультипроцессорность (Симметричная · Асимметричная) · Память (NUMA · COMA · Распределённая · Разделяемая · Распределённая разделяемая) · Одновременная многопоточность
MPP · Суперскалярность · Векторный процессор · Суперкомпьютер · BeowulfAPI Ateji PX · POSIX Threads · OpenMP · OpenHMPP · PVM · MPI · UPC · Intel Threading Building Blocks · Boost · Global Arrays · Charm++ · Cilk · Co-array Fortran · OpenCL · CUDA · Stream · Dryad · DryadLINQ Проблемы Затруднительное распараллеливание · Проблемы Великого Вызова · Блокировка ПО · Масштабируемость · Состояние гонки · Взаимная блокировка · Активный тупик · Детерминированный алгоритм · Параллельное замедление Категории:- Информатика
- Параллельные вычисления
Wikimedia Foundation. 2010.