В информатике , параллелизм является способность различных частей или единиц программы , алгоритма или задачи , которые будут выполняться вне или в порядке частичного порядка , не влияя на конечный результат. Это позволяет выполнять параллельное выполнение параллельных модулей, что может значительно повысить общую скорость выполнения в многопроцессорных и многоядерных системах. В более технических терминах параллелизм относится к разложению программы, алгоритма или проблемы на независимые от порядка или частично упорядоченные компоненты или единицы вычисления.[1]
Ряд математических моделей были разработаны для общего параллельного вычисления , включая сети Петри , исчислений процессов , на параллельной машине с произвольным доступом модели, модели актера и Рео координации языка .
История [ править ]
Как отмечает Лесли Лэмпорт (2015): «В то время как параллельное выполнение программы рассматривалось в течение многих лет, информатика параллелизма началась с основополагающей статьи Эдсжера Дейкстры 1965 года, в которой была представлена проблема взаимного исключения ... В последующие десятилетия произошли огромные изменения. рост интереса к параллелизму - особенно в распределенных системах . Оглядываясь на истоки этой области, можно выделить фундаментальную роль, которую играет Эдсгер Дейкстра ». [2]
Проблемы [ править ]
Поскольку вычисления в параллельной системе могут взаимодействовать друг с другом во время выполнения, количество возможных путей выполнения в системе может быть чрезвычайно большим, и конечный результат может быть неопределенным . Одновременное использование общих ресурсов может быть источником неопределенности, приводящей к таким проблемам, как тупиковые ситуации и нехватка ресурсов . [3]
Дизайн параллельных систем часто влечет за собой поиск надежных методов для координации их выполнения, обмена данными, выделения памяти и планирования выполнения, чтобы минимизировать время отклика и максимизировать пропускную способность . [4]
Теория [ править ]
Теория параллелизма была активной областью исследований в теоретической информатике . Одним из первых предложений была плодотворная работа Карла Адама Петри о сетях Петри в начале 1960-х годов. За прошедшие годы было разработано множество формализмов для моделирования и рассуждений о параллелизме.
Модели [ править ]
Был разработан ряд формализмов для моделирования и понимания параллельных систем, в том числе: [5]
- Параллельная машина с произвольным доступом [6]
- Модель актер
- Вычислительные мостовые модели, такие как объемная синхронная параллельная модель (BSP)
- Сети Петри
- Расчет процесса
- Расчет коммуникационных систем (CCS)
- Модель взаимодействия последовательных процессов (CSP)
- π-исчисление
- Пространства кортежей , например, Линда
- Простое параллельное объектно-ориентированное программирование (SCOOP)
- Reo Координационный язык
Некоторые из этих моделей параллелизма в первую очередь предназначены для поддержки рассуждений и спецификации, в то время как другие могут использоваться на протяжении всего цикла разработки, включая проектирование, реализацию, проверку, тестирование и моделирование параллельных систем. Некоторые из них основаны на передаче сообщений , в то время как другие имеют разные механизмы параллелизма.
Распространение различных моделей параллелизма побудило некоторых исследователей разработать способы объединения этих различных теоретических моделей. Например, Ли и Сангиованни-Винсентелли продемонстрировали, что так называемая модель «помеченного сигнала» может использоваться для обеспечения общей структуры для определения денотационной семантики множества различных моделей параллелизма [7], в то время как Нильсен, Сассон , и Винскель продемонстрировали, что теория категорий может использоваться для обеспечения аналогичного единого понимания различных моделей. [8]
Теорема о представлении параллелизма в модели субъектов обеспечивает довольно общий способ представления параллельных систем, которые закрыты в том смысле, что они не получают сообщений извне. (Другие системы параллелизма, например, вычисления процессов могут быть смоделированы в модели акторов с использованием протокола двухфазной фиксации . [9] ) Математическое обозначение, обозначаемое замкнутой системой S , строится все более лучшими приближениями из начального поведения, называемого ⊥ S, с использованием поведение, аппроксимирующее прогрессию функции S, чтобы построить обозначение (значение) для S следующим образом: [10]
- Обозначим S ≡ ⊔ i∈ω прогрессию S i (⊥ S )
Таким образом, S можно математически охарактеризовать с точки зрения всех его возможных поведений.
Логика [ править ]
Различные типы темпоральной логики [11] могут использоваться, чтобы помочь рассуждать о параллельных системах. Некоторые из этих логик, например линейная темпоральная логика и логика дерева вычислений , позволяют делать утверждения о последовательностях состояний, через которые может проходить параллельная система. Другие, такие как логика действий вычислительного дерева , логика Хеннесси-Милнер и Лампорт временной логика действий , строить свои утверждения из последовательностей действий (изменения в состоянии). Основное применение этой логики - написание спецификаций для параллельных систем. [3]
Практика [ править ]
В этом разделе не процитировать любые источники . ( Апрель 2007 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения ) |
Параллельное программирование включает языки программирования и алгоритмы, используемые для реализации параллельных систем. Параллельное программирование обычно считается более общим, чем параллельное программирование, потому что оно может включать произвольные и динамические шаблоны взаимодействия и взаимодействия, тогда как параллельные системы обычно имеют заранее определенный и хорошо структурированный шаблон взаимодействия. Основные цели параллельного программирования включают правильность , производительность и надежность . Параллельные системы, такие как операционные системы и системы управления базами данныхобычно предназначены для работы в течение неограниченного времени, включая автоматическое восстановление после сбоя, и не прекращают работу неожиданно (см. Управление параллелизмом ). Некоторые параллельные системы реализуют форму прозрачного параллелизма, при которой параллельные вычислительные объекты могут конкурировать за один ресурс и совместно использовать его, но сложность этой конкуренции и совместного использования скрыта от программиста.
Поскольку они используют общие ресурсы, параллельные системы в целом требуют включения какого-либо арбитра где-нибудь в их реализации (часто в базовом оборудовании) для управления доступом к этим ресурсам. Использование арбитров вводит возможность неопределенности в параллельных вычислениях, что имеет большое значение для практики, включая правильность и производительность. Например, арбитраж вводит неограниченный недетерминизм, который вызывает проблемы с проверкой модели, потому что он вызывает взрыв в пространстве состояний и может даже привести к тому, что модели будут иметь бесконечное количество состояний.
Некоторые модели параллельного программирования включают сопроцессы и детерминированный параллелизм . В этих моделях, нити управления явно дают их временные срезы, либо к системе или к другому процессу.
См. Также [ править ]
- Чу пространство
- Клиент-серверные сетевые узлы
- Clojure
- Узлы кластера
- Контроль параллелизма
- Параллельные вычисления
- Параллельное объектно-ориентированное программирование
- Шаблон параллелизма
- Построение и анализ распределенных процессов (CADP)
- D (язык программирования)
- Распределенные системные узлы
- Эликсир (язык программирования)
- Erlang (язык программирования)
- Go (язык программирования)
- Гордон Паск
- Международная конференция по теории параллелизма (CONCUR)
- OpenMP
- Параллельные вычисления
- Разделенное глобальное адресное пространство
- Процессы
- Проект Птолемея
- Rust (язык программирования)
- Сноп (математика)
- Потоки
- X10 (язык программирования)
Ссылки [ править ]
- ^ Лэмпорт, Лесли (июль 1978 г.). «Время, часы и порядок событий в распределенной системе» (PDF) . Коммуникации ACM . 21 (7): 558–565. DOI : 10.1145 / 359545.359563 . Дата обращения 4 февраля 2016 .
- ^ Лэмпорт, Лесли . «Лекция Тьюринга: Компьютерные науки о параллелизме: первые годы (Коммуникации ACM, том 58, № 6, июнь 2015 г.)» . ACM . Дата обращения 22 марта 2017 .
- ^ a b Кливленд, Рэнс; Скотт Смолка (декабрь 1996 г.). «Стратегические направления в исследовании параллелизма». ACM Computing Surveys . 28 (4): 607. DOI : 10,1145 / 242223,242252 .
- ^ Кэмпбелл, Колин; Джонсон, Ральф; Миллер, Аде; Тоуб, Стивен (август 2010). Параллельное программирование с Microsoft .NET . Microsoft Press. ISBN 978-0-7356-5159-3.
- ^ Филман, Роберт; Дэниел Фридман (1984). Скоординированные вычисления - инструменты и методы для распределенного программного обеспечения . Макгроу-Хилл. ISBN 978-0-07-022439-1.
- ^ Келлер, Йорг; Кристоф Кесслер; Джеспер Трэфф (2001). Практическое программирование PRAM . Джон Уайли и сыновья.
- ^ Ли, Эдвард; Альберто Сангиованни-Винчентелли (декабрь 1998 г.). «Платформа для сравнения моделей вычислений» (PDF) . IEEE Transactions по CAD . 17 (12): 1217–1229. DOI : 10.1109 / 43.736561 .
- ^ Могенс Нильсен; Владимиро Сассоне; Глинн Винскель (1993). «Взаимоотношения между моделями параллелизма» . Школа / Симпозиум REX .
- ^ Фредерик Кнабе. Распределенный протокол для связи на основе каналов с Choice PARLE 1992.
- ^ Уильям Клингер (июнь 1981). «Основы актерской семантики». Докторская диссертация по математике. Массачусетский технологический институт. ЛВП : 1721,1 / 6935 . Цитировать журнал требует
|journal=( помощь ) - ^ Роско, Колин (2001). Модальные и временные свойства процессов . Springer. ISBN 978-0-387-98717-0.
Дальнейшее чтение [ править ]
- Линч, Нэнси А. (1996). Распределенные алгоритмы . Морган Кауфманн. ISBN 978-1-55860-348-6.
- Таненбаум, Эндрю С .; Ван Стин, Маартен (2002). Распределенные системы: принципы и парадигмы . Прентис Холл. ISBN 978-0-13-088893-8.
- Курки-Суонио, Рейно (2005). Практическая теория реактивных систем . Springer. 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-е изд.). Сомерсет: ISBN компании John Wiley & Sons Inc. 9781119131144
- Бхаттачарья, СС (2013; 2014;). Справочник по системам обработки сигналов (2-й; 2-й; 2-й 2013 г .; ред.). Нью-Йорк, Нью-Йорк: Springer.10.1007 / 978-1-4614-6859-2 ISBN 9781461468592
- Вольтер, К. (2012; 2014;). Оценка устойчивости и оценка вычислительных систем (1. Aufl.; 1; ed.). Лондон; Берлин ;: Springer. ISBN 9783642290329
Внешние ссылки [ править ]
- Параллельные системы в виртуальной библиотеке WWW
- Презентация шаблонов параллелизма на scaleconf
