Parallel Computation Examples

Учебный репозиторий с примерами параллельного программирования: CUDA, MPI, OpenMP, OpenCL и Hadoop-стек (MapReduce, Cassandra, Hive). Более 80 исходных файлов, каждый из которых — самостоятельный, компилируемый пример с комментариями на русском языке.

Примеры упорядочены по возрастанию сложности и покрывают путь от первого «Hello World» на GPU до tensor cores, multi-GPU, CUDA Graphs и warp-level scan.

Репозиторий используется в курсе «Параллельные вычисления» в ФПМИ МФТИ.

---

Быстрый старт

# MPI + OpenMP (по умолчанию)
mkdir build && cd build && cmake .. && make

# Включить CUDA и OpenCL
cmake .. -DBUILD_CUDA_EXAMPLES=ON -DBUILD_OPENCL_EXAMPLES=ON && make

# Запуск MPI
mpiexec -np 4 ./MPI/00-hello-world/bin/MpiHelloWorld

# Запуск CUDA / OpenCL
./CUDA/01-intro/01-hello-world-single-cuda-thread/main

Зависимости

Технология	Ubuntu	macOS
MPI	sudo apt install openmpi-bin libopenmpi-dev	brew install open-mpi
OpenMP	Входит в GCC	brew install libomp
CUDA	CUDA Toolkit	—
OpenCL	sudo apt install opencl-headers ocl-icd-opencl-dev	Входит в систему

На кластере: module add mpi/openmpi4-x86_64

---

Структура проекта

CUDA (20 тем, 80+ файлов)

Введение и архитектура

#	Директория	Описание
00	00-how-to-run-task-on-cluster	Инструкция по запуску задач на кластере (SLURM)
01	01-intro	Hello World, сложение массивов, memcpy, умножение матриц
02	02-device-specs-benchmarks	Характеристики устройства, замер времени, bandwidth, ILP, occupancy

Модель памяти

#	Директория	Описание
03	03-memory-model	10 подтем: coalesced/uncoalesced access, shared memory и bank conflicts, pinned memory, кеширование, pitching, constant memory, transpose (naive → tiled → padded), stencil с halo cells, zero-copy (mapped) memory, сводный бенчмарк bandwidth (pageable / pinned / WC / unified / prefetch)
03.5	03.5-matrix-multiplication-example	Наивное умножение матриц на CUDA

Reduction, Scan, Atomics, Warp-примитивы

#	Директория	Описание
04	04-reduction	8 реализаций: наивная → shared memory → bank-conflict-free → warp-reduce (volatile + __shfl_down_sync)
04.5	04.5-atomics	atomicAdd, наивная и приватизированная гистограмма
04.7	04.7-warp-primitives	__shfl_sync, __shfl_down_sync (warp reduce), __ballot_sync / __any_sync
05	05-scan	7 реализаций prefix sum: CPU baseline → naive (data race) → double-buffer → recursive multi-block → two-layer → bank-conflict-free Blelloch → warp-level scan через __shfl_up_sync

Библиотеки CUDA Toolkit

#	Директория	Описание
06	06-cublas	cuBLAS: vector add, AXPY, cosine distance, matrix sums
13	13-curand	cuRAND: Monte Carlo для числа π (host API + device API)
17	17-cufft	cuFFT: 1D complex FFT (forward → inverse roundtrip)
18	18-cusparse	cuSPARSE: SpMV на CSR-матрице (generic API)

Продвинутые возможности

#	Директория	Описание
07	07-pycuda	PyCUDA: программирование GPU из Python
08	08-streams-events	Потоки, события, 3 способа замера времени, перекрытие copy/compute
09	09-unified-memory	Unified memory: cudaMallocManaged и cudaMemPrefetchAsync
10	10-cooperative-groups	Cooperative groups: warp/block-группы, tiled_partition
11	11-cuda-graphs	CUDA Graphs: stream capture и explicit graph API
12	12-thrust	Thrust: device_vector, transform_reduce, sort
14	14-multi-gpu	Multi-GPU: независимые устройства и peer access (>= 2 GPU)
15	15-tensor-cores	Tensor Cores / WMMA (FP16 x FP16 -> FP32), требует sm_70+
16	16-dynamic-parallelism	Dynamic parallelism: запуск ядер из ядра (-rdc=true)
19	19-profiling-tools	Профилирование: NVTX-аннотации для Nsight Systems / Nsight Compute / nvprof, скрипт запуска

Домашние задания

#	Файл	Описание
1	01-random-calculation.md	Случайные вычисления
2	02-matrix-multiplication.md	Tiled matrix multiplication (shared memory)
3	03-quick-sort.md	Quick sort с parallel scan

---

MPI (14 примеров)

#	Директория	Описание
00	00-hello-world	Hello World с MPI
01	01-send_recv	Блокирующие MPI_Send / MPI_Recv
02	02-ping-pong	Обмен сообщениями «Пинг-понг»
03	03-probe-message-status	MPI_Probe и получение статуса сообщений
04	04-isend-irecv	Неблокирующие MPI_Isend / MPI_Irecv
05	05-bcast	MPI_Bcast и ручные реализации (линейная, биномиальное дерево)
06	06-scatter-gather	MPI_Scatter / MPI_Gather и аналоги на Send/Recv
07	07-reduce-allreduce	MPI_Reduce / MPI_Allreduce и ручная редукция
08	08-alltoall	MPI_Alltoall и реализация через MPI_Sendrecv
09	09-collective-benchmark	Сводный бенчмарк коллективных операций (CSV)
10	10-comm-split	MPI_Comm_split (чётные vs нечётные)
11	11-comm-dup	MPI_Comm_dup: изоляция тегов для библиотек
12	12-comm-group	Группы рангов: MPI_Group_incl, MPI_Comm_create_group
13	13-comm-cart	Декартова 2D-топология: MPI_Cart_create, MPI_Cart_shift

---

OpenMP (7 примеров)

#	Директория	Описание
00	00-hello-world	Hello World с #pragma omp parallel
01	01-parallel-for	Параллельные циклы
02	02-sections	Секции
03	03-master	Директива master
04	04-parralel-sum	Параллельное суммирование
05	05-matrix-multiplication	Умножение матриц
06	06-critical-sections	Критические секции

---

OpenCL (20 примеров)

Развернуть полный список

#	Директория	Описание
00	00-platform-device-info	Перечисление платформ и устройств
01	01-intro	Vector add
02	02-local-memory	__local память, транспоз матрицы naive vs local
03	03-reduction	Дерево редукции с barrier(CLK_LOCAL_MEM_FENCE)
04	04-matrix-multiplication	Наивное умножение матриц
05	05-profiling-events	Профилирование: cl_event, 4 стадии event'а, bandwidth
06	06-image-objects	Image objects: image2d_t, sampler_t, Box Blur
07	07-multi-queue	Несколько очередей: перекрытие copy/compute
08	08-coalesced-access	Coalesced vs strided доступ, замер bandwidth
09	09-constant-memory	__constant память: broadcast-оптимизация
10	10-pinned-memory	Pinned (mapped) память vs pageable
11	11-stencil	1D-стенсил с halo cells в __local памяти
12	12-atomics	Атомарные операции, наивная и приватизированная гистограмма
13	13-scan	Prefix sum: Хиллис-Стил (inclusive) и Блеллох (exclusive, work-efficient)
14	14-kernel-from-file	Загрузка ядра из внешнего .cl файла
15	15-build-options	Опции компиляции: -cl-fast-relaxed-math, -cl-mad-enable
16	16-offline-compilation	Кеширование скомпилированного бинарника
17	17-sub-groups	Sub-groups (аналог warp): sub_group_reduce_add() (OpenCL 2.0+)
18	18-svm	Shared Virtual Memory (аналог Unified Memory, OpenCL 2.0+)
19	19-multi-device	Разделение работы между CPU и GPU
20	20-pyopencl	PyOpenCL: Python-обёртка

---

Hadoop-стек

Директория	Описание
MapReduce/01-one-stage	Одностадийный MapReduce (WordCount)
MapReduce/02-two-stages	Двухстадийный MapReduce (Top-слова)
Cassandra	Apache Cassandra (Docker Compose)
Hive	Apache Hive (Maven)

---

Сборка

Проект использует CMake со зонтичной сборкой. MPI и OpenMP включены по умолчанию, CUDA и OpenCL — по флагам:

mkdir build && cd build

# Только MPI + OpenMP
cmake .. && make

# Всё, включая CUDA и OpenCL
cmake .. -DBUILD_CUDA_EXAMPLES=ON -DBUILD_OPENCL_EXAMPLES=ON && make

# Переопределить CUDA-архитектуры (по умолчанию: Pascal—Ada Lovelace)
cmake .. -DBUILD_CUDA_EXAMPLES=ON -DCMAKE_CUDA_ARCHITECTURES="80;86;89"

Каждый пример можно собрать и отдельно:

cd MPI/00-hello-world && cmake . && make
cd CUDA/04-reduction/05-warp-reduce && nvcc main.cu -o main

---

Запуск

MPI

mpiexec -np 4 ./bin/MpiHelloWorld       # локально
sbatch bin/start_sbatch.sh              # на кластере (SLURM)

CUDA / OpenCL

./main                                  # локально
sbatch run.sh                           # на кластере с GPU

Профилирование CUDA

# Nsight Systems (timeline + NVTX-аннотации)
nsys profile --trace=cuda,nvtx -o report ./main

# Nsight Compute (метрики ядер)
ncu --set full ./main

# nvprof (legacy, CUDA <= 11)
nvprof --print-gpu-trace ./main

---

Использование SLURM-кластера

Команда	Описание
sinfo	Информация по нодам кластера
sinfo -N -l	Информация по каждой ноде
squeue	Очередь задач
srun <command>	Запуск команды на ноде
sbatch <script>	Запуск скрипта (начинается с #!/bin/bash)

Пример: MPI/00-hello-world/bin/start_sbatch.sh. После sbatch появится Submitted batch job <job_id>, результат — в slurm-<job_id>.out.

---

Полезные ссылки

Документация и инструменты

• NVIDIA CUDA Toolkit Documentation
• nvprof / Visual Profiler
• Nsight Systems / Nsight Compute
• OpenMPI 4.0 Manual
• MPI Tutorial

Курсы и лекции

• GPU Programming — Caltech CS179
• Лекции Евгения Перепёлкина (YouTube)
• Лекции Павла Ахтямова в Лектории ФПМИ МФТИ (YouTube)

Книги

• Дж. Сандерс, Э. Кэррот. Технология CUDA в примерах и задачах, 2013
• Боресков А. В., Харламов А. А. Основы работы с технологией CUDA
• GPU Gems 3 — особенно глава 39 (Parallel Prefix Sum)

Статьи

• Parallel Prefix Sum (Scan) with CUDA — Mark Harris, NVIDIA
• Лекция по Scan — Ben-Gurion University
• Хабр: Краткая история GPU
• Хабр: Работа с памятью в GPU

---

Лицензия

Учебный репозиторий для курса «Параллельные вычисления» ФПМИ МФТИ.