Я ищу некоторые параллельные алгоритмы данных в структурах данных, таких как списки или графики, которые не используют синхронизацию, но используют критические разделы для обеспечения согласованности состояний.
До сих пор я встречал только алгоритмы, которые либо
-
синхронно: они работают с локальными копиями данных, которые они изменяют, и на определенных временных интервалах обмениваются своим текущим состоянием для следующего шага (например, однократный параллельный локальный поиск) или
-
условие расы: они подразделяют структуру данных таким образом, что каждая часть может обрабатываться отдельно и безопасно с разделяемой памятью (например, параллельным Quicksort)
Знаете ли вы какой-либо понятный (полу) асинхронный алгоритм, который
- подразделяет данные, которые должны обрабатываться несколькими процессорами индивидуально,
- обменивает некоторые данные, сгенерированные на каждом этапе процессорами через разделяемую память (например, используя критические разделы) и, таким образом,
- только синхронизируется свободно, но не полагается на схему сердечного ритма или другую тяжелую синхронизацию?
EDIT: Я использую терминологию из Технического отчета Синхронные и асинхронные параллельные алгоритмы для многопроцессоров от HT Kung.
EDIT2:. Чтобы уточнить терминологию, в документе различаются различные типы алгоритмов:
- синхронизированный (например, подход с сердечным ритмом для игры в жизни).
- асинхронный. Каждый процессор может работать в основном независимо и может передавать его другим процессорам через разделяемую память в любое время. Связь может затем повлиять на следующий шаг вычисления в других процессорах (например, найти нуль функции в монотонно сходящемся интервале через параллельный двоичный поиск)
- полуасинхронный/синхронизированный. Синхронизация происходит, но реже, чем в синхронизированном алгоритме.
