Модели параллельных вычислений: PRAM, память, SIMD/MIMD, BSP

Урок даёт карту моделей, в которых рассуждают о параллельных алгоритмах.

Модель вычислений — упрощённое описание машины, которое позволяет анализировать алгоритм, не отвлекаясь на детали конкретного железа.

PRAM — идеальная теоретическая машина

PRAM (Parallel Random Access Machine) — это абстракция: бесконечно много процессоров, у всех мгновенный доступ к общей памяти, синхронные шаги. Она нереалистична (память не бывает мгновенной для всех сразу), но удобна для теории: на ней удобно доказывать, что задачу в принципе можно решить за O(log n) параллельных шагов. PRAM различается по правилам конфликтов записи/чтения в одну ячейку: EREW (исключительное чтение и запись), CREW (общее чтение, исключительная запись), CRCW (общее и то и другое). Чем либеральнее модель, тем легче алгоритм, но тем дальше она от реальности.

Разделяемая против распределённой памяти

Это главное практическое деление. При разделяемой памяти (shared memory) все ядра видят одну общую оперативную память — так устроен многоядерный процессор в вашем ноутбуке. Обмен данными бесплатен (просто читаешь общую переменную), но нужна синхронизация, чтобы не было гонок. При распределённой памяти (distributed memory) каждый узел кластера имеет свою память, и чтобы поделиться данными, узлы шлют друг другу сообщения по сети. Обмен дорогой, зато система масштабируется до тысяч машин.

SIMD и MIMD

Классификация по тому, что делают процессоры. SIMD (Single Instruction, Multiple Data) — одна инструкция применяется ко множеству данных одновременно: так работают векторные регистры CPU и ядра GPU. Идеально для «одинаковой операции над массивом». MIMD (Multiple Instruction, Multiple Data) — каждый процессор выполняет свою программу над своими данными: так работают ядра обычного CPU и узлы кластера. SIMD проще и быстрее на однородной работе, MIMD гибче.

BSP — мост между теорией и практикой

Модель BSP (Bulk Synchronous Parallel) описывает вычисление как последовательность суперштагов. В каждом суперштаге процессоры сначала считают локально, потом обмениваются сообщениями, потом синхронизируются на барьере — и только затем начинается следующий суперштаг. BSP реалистично учитывает стоимость коммуникации и синхронизации, поэтому её используют для оценки алгоритмов на кластерах и в системах вроде Pregel/Giraph для графов.

Суперштаг BSP:
  [локальные вычисления]  ->  [обмен сообщениями]  ->  [барьер]
  затем следующий суперштаг...

Как работает под капотом

Реальное железо — это смесь моделей. Кластер из многоядерных машин с GPU сочетает распределённую память (между узлами), разделяемую (между ядрами узла) и SIMD (внутри GPU). Грамотный инженер выбирает модель под задачу: для счёта на одном сервере думает в терминах разделяемой памяти, для кластера — в терминах сообщений и BSP, для GPU — в терминах SIMD.

Зачем вообще нужны абстрактные модели, если есть конкретное железо? Затем, что они позволяют рассуждать об алгоритме до того, как он написан, и переносить выводы между машинами. Доказав на PRAM, что задача решается за O(log n) параллельных шагов, мы знаем её принципиальный предел — даже если реальная машина этого предела не достигнет. Зная, что алгоритм требует частого обмена данными, мы заранее понимаем: на разделяемой памяти он пойдёт, а на распределённой задохнётся в коммуникации. Модель — это карта: она не повторяет местность в деталях, но показывает, куда идти и где будут горы.

Частые ошибки

• Брать PRAM-алгоритм и ждать, что он буквально так же быстр на реальной машине: PRAM игнорирует стоимость памяти и коммуникации.
• Применять SIMD-мышление к задаче с ветвлениями: если потоки идут разными путями, SIMD теряет эффективность.
• Игнорировать стоимость сообщений в распределённой памяти — она часто доминирует над счётом.

Итоги

• PRAM — идеализированная теоретическая модель для оценки «потенциала» параллелизма.
• Разделяемая vs распределённая память — главное практическое деление, определяющее стоимость обмена.
• SIMD — одна операция над многими данными (GPU/векторы); MIMD — разные программы (ядра CPU, кластер).
• BSP реалистично моделирует суперштаги с коммуникацией и барьерами.