Какие хорошие (полу) асинхронные алгоритмы?

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

До сих пор я встречал только алгоритмы, которые либо

  • синхронно: они работают с локальными копиями данных, которые они изменяют, и на определенных временных интервалах обмениваются своим текущим состоянием для следующего шага (например, однократный параллельный локальный поиск) или

  • условие расы: они подразделяют структуру данных таким образом, что каждая часть может обрабатываться отдельно и безопасно с разделяемой памятью (например, параллельным Quicksort)

Знаете ли вы какой-либо понятный (полу) асинхронный алгоритм, который

  • подразделяет данные, которые должны обрабатываться несколькими процессорами индивидуально,
  • обменивает некоторые данные, сгенерированные на каждом этапе процессорами через разделяемую память (например, используя критические разделы) и, таким образом,
  • только синхронизируется свободно, но не полагается на схему сердечного ритма или другую тяжелую синхронизацию?

EDIT: Я использую терминологию из Технического отчета Синхронные и асинхронные параллельные алгоритмы для многопроцессоров от HT Kung.

EDIT2:. Чтобы уточнить терминологию, в документе различаются различные типы алгоритмов:

  • синхронизированный (например, подход с сердечным ритмом для игры в жизни).
  • асинхронный. Каждый процессор может работать в основном независимо и может передавать его другим процессорам через разделяемую память в любое время. Связь может затем повлиять на следующий шаг вычисления в других процессорах (например, найти нуль функции в монотонно сходящемся интервале через параллельный двоичный поиск)
  • полуасинхронный/синхронизированный. Синхронизация происходит, но реже, чем в синхронизированном алгоритме.

Ответы

Ответ 1

Асинхронный: существуют параллельные версии итеративных алгоритмов, таких как распространение убеждений и последовательное чрезмерное расслабление, которое, в отличие от Жизни, переносит устаревшие данные и, следовательно, не нуждается в сердцебиении. (Реальные реализации в системах, которые не являются последовательно последовательными, возможно, потребуют барьера записи.)

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

Ответ 2

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