Модели параллелизма и памяти
Модели параллелизма и памяти определяют, как структурируются параллельные программы и как их взаимодействующие потоки наблюдают за общей памятью, что является основой для корректного параллельного программного обеспечения.
Definition
Модели параллелизма описывают, как компонуются и взаимодействуют независимо выполняющиеся вычисления, в то время как модель памяти определяет, какие значения могут наблюдаться при чтении, когда параллельные потоки обращаются к общей памяти, определяя контракт между программистом, языком и оборудованием.
Scope
Эта область охватывает язык и теорию параллелизма: процессные исчисления и модели параллелизма для коммуникации и синхронизации, модели согласованности памяти, которые определяют допустимые порядки операций с памятью, механизмы синхронизации и отсутствие состояний гонки данных, а также системы типов для параллелизма, такие как сессионные типы. Она рассматривает, как языки придают смысл программам, которые выполняются одновременно и совместно используют состояние.
Sub-topics
Core questions
- Как можно моделировать и анализировать параллельные взаимодействующие процессы?
- Какие порядки операций с памятью может наблюдать программа?
- Как гарантируется или специфицируется отсутствие состояний гонки данных?
- Как типы могут дисциплинировать коммуникацию и предотвращать ошибки параллелизма?
Key theories
- Процессные исчисления
- CSP Хоара и CCS и пи-исчисление Милнера предоставляют алгебраические теории параллельных, взаимодействующих процессов с операторами для композиции и синхронизации и понятиями поведенческой эквивалентности, такими как бисимуляция.
- Последовательная согласованность
- Лэмпорт определил последовательную согласованность как требование, чтобы выполнение на многопроцессорной системе выглядело как некоторое чередование операций каждого процессора в порядке программы, что является базовым уровнем, с которым сравниваются более слабые модели памяти.
- Модели согласованности памяти
- Эдв и Гарачорлу систематизируют спектр моделей согласованности общей памяти, объясняя, как ослабленные порядки позволяют повысить производительность, усложняя при этом рассуждения о параллельных программах.
Clinical relevance
Модели памяти теперь являются частью основных спецификаций языков (например, в C++ и Java), потому что многоядерное оборудование сделало наблюдаемыми ослабленные порядки; их правильное применение имеет важное значение для корректного, переносимого параллельного программного обеспечения. Процессные исчисления и сессионные типы лежат в основе разработки языков и протоколов передачи сообщений.
History
Теория параллелизма выросла из сетей Петри и работ Хоара (CSP) и Милнера (CCS) 1970-х годов, позднее пи-исчисления для мобильных процессов. Лэмпорт определил последовательную согласованность в 1979 году; по мере распространения ослабленного оборудования модели памяти были формализованы для таких языков, как Java и C++ в 2000-х годах, и семантика слабой памяти стала активной областью исследований.
Debates
- Строгая против ослабленной согласованности памяти
- Разработчики обменивают интуитивную простоту строгих моделей, таких как последовательная согласованность, на производительность ослабленных моделей, которые допускают переупорядочивание, что усложняет рассуждения и требует тщательной семантики на уровне языка.
Key figures
- C. A. R. Hoare
- Robin Milner
- Leslie Lamport
- Sarita Adve
Related topics
Seminal works
- hoare1978
- milner1989
- lamport1979
- adve1996
Frequently asked questions
- Что такое модель памяти?
- Модель памяти — это формальный контракт, который определяет, какие значения может возвращать операция чтения, когда несколько потоков обращаются к общей памяти, определяя, какие переупорядочивания могут выполнять компилятор и оборудование и на что может полагаться программист.
- Что такое последовательная согласованность?
- Последовательная согласованность требует, чтобы параллельное выполнение вело себя как некоторое единичное чередование операций потоков, которое соблюдает порядок программы каждого потока, что делает ее наиболее интуитивной (но часто ослабленной) моделью памяти.