Кратко и по существу — для каждой модели: что это, какие примитивы/ограничения, влияние на алгоритм и на аппаратную реализацию.
1) Shared memory (совместная память)
- Что: несколько потоков/процессоров имеют общий адресный пространство и читают/пишут общие данные.
- Примитивы: атомарные операции, мьютексы, барьеры, память с последовательностью видимости (memory model).
- Алгоритмические последствия: требуется синхронизация для согласованного доступа; выгодны алгоритмы с мелко‑ или среднезернистой параллельностью и высокой локальностью данных; важно уменьшать ложное совместное использование cache (false sharing).
- Аппаратно: многопроцессорные кэширующие системы (SMP, NUMA), coherence-протоколы, аппаратные атомарные инструкции. Производительность ограничена пропускной способностью шин/интерконнекта и латентностью памяти; на NUMA важна привязка данных к процессору.
2) Message passing (обмен сообщениями)
- Что: процессы имеют свою локальную память; взаимодействуют обменом сообщений (send/recv).
- Примитивы: точечные/коллективные операции (MPI), асинхронные/буферизованные передачи.
- Алгоритмические последствия: явное управление распределением данных и коммуникацией; лучше для распределённых систем и слабосвязанных задач; алгоритмы нацелены на минимизацию объёма и числа сообщений, агрегацию, перекрытие коммуникации с вычислением.
- Аппаратно: кластеры, распределённые системы, сети (InfiniBand, Ethernet); критичны пропускная способность и латентность сети. Масштабируется легче, чем shared‑memory на больших count узлов, но требует явного проектирования обмена данными.
3) SIMD (Single Instruction, Multiple Data)
- Что: единая команда применяется одновременно ко множеству однотипных элементов (векторные инструкции, широкие регистры, GPU warp/wavefront).
- Примитивы: векторные операции, маскирования (select), согласованные ветвления затруднены.
- Алгоритмические последствия: подходит для регулярных, однообразных, сильно векторизуемых задач (линейная алгебра, обработка массивов, фильтрация). Нужно выравнивание данных, минимизация ветвлений и разветвлённой логики.
- Аппаратно: SIMD‑юниты в CPU (AVX), GPU SIMT — большие массивы ALU, память с высокой пропускной способностью; эффективность зависит от выравнивания, коалесценции обращений и степени занятости векторов.
4) Data parallelism (параллелизм данных)
- Что: операция (или набор однотипных операций) применяется параллельно к разбиению данных; тесно связан с SIMD, но охватывает и распределённые/массивные системы (map/reduce).
- Примитивы: map, reduce, bulk synchronous parallel, параллельные алгоритмы над массивами/матрицами.
- Алгоритмические последствия: акцент на декомпозиции данных (sharding), минимизации зависимостей между кусками; удобен для масштабирования и выражения однотипных вычислений.
- Аппаратно: реализуется как SIMD на уровне процессора, как data‑parallel на GPU, или как распределённые фреймворки (Spark, MapReduce) на кластерах; требует высокой пропускной способности памяти и эффективной агрегации результатов.
Общее влияние выбора модели
- Коммуникация vs синхронизация: shared memory упрощает обмен (общая память) но требует механизмов синхронизации и страдает от когерентности; message passing делает коммуникацию явной и контролируемой, что даёт предсказуемость на кластерах.
- Гранулярность: мелкозернистые задачи лучше в shared memory/SIMD; крупнозернистые — в message passing/data parallel.
- Локальность данных: ключевой фактор производительности — уменьшить удалённые доступы/сообщения; выбор модели определяет способы достижения локальности (affinity, partitioning).
- Масштабируемость: SIMD/data‑parallel хорошо масштабируются по числу элементов внутри узла; message passing лучше масштабируется на многие узлы; shared memory ограничено аппаратной памятью и coherence.
- Модели влияют на сложность реализации алгоритма: message passing требует явного распределения, shared memory — корректной синхронизации, SIMD — рефакторинга для векторизации.
- Теоретическое ограничение: ускорение ограничено последовательной частью (Аmdahl): $$S(N)=\frac{1}{(1-p)+\frac{p}{N}}$$ где $p$ — параллельная доля, $N$ — число единиц. Выбор модели влияет на достижимую $p$ и эффективное $N$.
Практическое правило выбора
- Многопоточный доступ к общей памяти и быстрый обмен — shared memory (OpenMP, pthreads) на одном узле.
- Распределённые большие данные — message passing или высокоуровневые data‑parallel фреймворки (MPI, Spark).
- Регулярные численные вычисления — SIMD/GPU (AVX, CUDA/OpenCL).
- Data‑parallel абстракции удобны для преобразования и масштабирования задач без ручного управления потоками.
Вывод: модель диктует структуру алгоритма (распределение работы, синхронизацию, коммуникацию), требования к локальности и когерентности данных, а также аппаратные средства (кэш‑когерентность, сеть, векторные блоки, пропускная способность памяти).