Классификация параллельных архитектур

ОБЯЗАТЕЛЬНОДЛЯ НОВИЧКОВ

Разработчику Архитектору Инженеру

Классификация архитектур - Flynn и модели памяти

Перед тем как распараллеливать программу, полезно понять какое железо у вас под рукой. Один и тот же код на GPU и на двухъядерном CPU ведёт себя по-разному. Классификации помогают ответить на вопрос: сколько независимых потоков инструкций может выполняться одновременно и насколько они синхронны.

В этой статье — классическая таксономия Флинна, конвейер и векторные машины, а также связь с тем, что вы уже видели в главе про процессор.

Две оси простыми словами

Ось	Вопрос	Пример «один»	Пример «много»
Поток управления	Сколько разных программ/веток выполняется?	Одно ядро, один while	8 ядер, 8 потоков OpenMP
Поток данных	Сколько элементов данных обрабатывает одна команда?	c = a + b — одна пара чисел	SIMD: c[i] = a[i] + b[i] для 8 i сразу

Поток управления — «кто командует»: один счётчик команд или несколько независимых. Поток данных — «сколько чисел за раз трогает одна инструкция».

---

Таксономия Флинна (1966)

Майкл Флинн предложил делить системы по двум осям:

• S — одна (Single) или M — много (Multiple) потоков управления (program counter — «куда идёт следующая команда»).
• S — одна или M — много потоков данных (сколько операндов обрабатывает одна инструкция за такт).

Получаются четыре класса:

Класс	Расшифровка	Смысл	Примеры
SISD	Single Instruction, Single Data	Классический последовательный CPU (без параллелизма на уровне потоков)	Старые одноядерные процессоры
SIMD	Single Instruction, Multiple Data	Одна команда — много данных	AVX/SSE, GPU warp/wavefront
MISD	Multiple Instruction, Single Data	Несколько команд над одним потоком данных	Редко; отказоустойчивые системы
MIMD	Multiple Instruction, Multiple Data	Независимые потоки с разным кодом и данными	Многоядерный CPU, кластер MPI

SISD

Историческая база: одна инструкция за такт (или конвейер, но логически один поток). Современные ядра сами по себе уже не чистый SISD — но один поток программы на одном ядре ведёт себя как SISD с ускорением от конвейера и SIMD внутри.

SIMD — векторный параллелизм

SIMD (Single Instruction, Multiple Data) — одна команда процессора применяется ко многим элементам данных сразу. Удобная аналогия: один учитель говорит «все, сложите столбик A и столбик B» — и 32 ученика делают одно и то же действие над своими числами.

ADD  V1, V2, V3    ; V3[i] = V1[i] + V2[i] для всех i в векторном регистре

На x86 расширения SSE, AVX, AVX-512 — это SIMD: регистр шириной 128–512 бит хранит пачку float, и одна инструкция add складывает их попарно.

На x86 это SSE, AVX, AVX-512 (подробнее). На GPU — warp из 32 потоков, выполняющих одну инструкцию над разными элементами массива.

Когда SIMD идеален: плотные массивы, одинаковая операция на каждый элемент, мало ветвлений.

Когда плох: разреженные данные, сложные if внутри цикла, нерегулярная память.

MIMD — главная модель общего программирования

Каждый процессор (или ядро, или узел) может выполнять свою ветку кода со своими данными:

• Потоки OpenMP на 8 ядрах — MIMD.
• 1000 процессов MPI на кластере — MIMD.
• Микросервисы на разных серверах — тоже MIMD на уровне системы (хотя это уже другой уровень абстракции).

MIMD — самый гибкий класс и основа мультипроцессоров и кластеров.

MISD — скорее учебный случай

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

---

Конвейерная обработка (pipeline)

Конвейер — способ повысить пропускную способность: операция разбивается на стадии, и несколько операций одновременно находятся на разных стадиях.

Классический пример — конвейер команд CPU:

Такт 1:  [Fetch A][     ][     ][     ]
Такт 2:  [Fetch B][Decode A][     ][     ]
Такт 3:  [Fetch C][Decode B][Exec A ][     ]
...

Идеальное ускорение конвейера из k стадий при бесконечном потоке однородных операций — до k раз по throughput (операций в секунду), но latency одной операции остаётся k тактов.

Проблемы конвейера

• Конфликты по данным — следующая инструкция ждёт результат предыдущей.
• Конфликты по управлению — ветвление (if) ломает предсказание; конвейер очищается (branch misprediction).
• Структурные конфликты — две инструкции хотят один функциональный блок.

На уровне алгоритма конвейеризация — это разбиение цикла на стадии «читать → считать → писать», когда итерации перекрываются (software pipelining). Производительность конвейерных систем разбирается в законах производительности.

---

Векторно-конвейерные компьютеры

Исторически векторные суперкомпьютеры (Cray, ELIAS и др.) сочетали:

1. Векторные регистры длиной 64–512 элементов — SIMD на уровне архитектуры.
2. Конвейер внутри векторного функционального блока — пока складываются элементы 1…8, уже начинается загрузка 9…16.
3. Цепочки (chaining) — результат одной векторной операции напрямую подаётся на вход следующей без записи в память.

Память → [Load vector] → [Vector ADD] → [Vector MUL] → [Store vector]
              ↑________________конвейер________________↑

Современный CPU + AVX и GPU — наследники этой идеи: массовый параллелизм по данным + глубокий конвейер.

Эра	Характеристика	Доступный параллелизм
Векторные машины 1980-х	Длинные векторные инструкции, дорогая память	Десятки–сотни ops/такт на вектор
Супerscalar CPU	Несколько инструкций за такт, out-of-order	2–6 IPC на ядро
Many-core + SIMD	AVX-512, GPU	Тысячи потоков data-parallel
Кластеры	Тысячи узлов MIMD	Зависит от сети и задачи

---

Степень параллелизма архитектуры

Степень параллелизма — сколько операций система может физически выполнять одновременно:

Архитектура	Порядок параллелизма	Ограничение
Скalar SISD	1 (× конвейер)	Одна цепочка зависимостей
Superscalar	2–8 инструкций/такт	Анализ зависимостей в hardware
SIMD (256 bit AVX)	8× float32 за инструкцию	Ширина вектора
GPU SM	1024–2048 потоков/SM	Память, divergence веток
Кластер	число узлов × ядер	Latency сети, Amdahl

Достижимый параллелизм программы не может превысить минимум из:

• параллелизма алгоритма (зависимости в графе — статья 5);
• параллелизма архитектуры;
• эффективности реализации (коммуникации, балансировка).

---

Связь с программированием

Архитектура	Как использовать
Конвейер CPU	Компилятор; избегать длинных цепочек зависимостей
SIMD	Векторизация циклов, intrinsics, GPU kernels
Shared-memory MIMD	OpenMP, std::thread, pthreads
Distributed MIMD	MPI, PGAS (Coarray Fortran)
GPU SIMT	CUDA, OpenCL, SYCL

---

SIMT и SIMD (GPU)

	SIMD (AVX)	SIMT (CUDA)
Модель	Одна инструкция, фиксированная ширина	Много «потоков», одна инструкция, маскирование
Ветвление	Маски или scalar fallback	Warp divergence — разные ветки сериализуются
Масштаб	4–16 элементов/инструкцию	32 (warp) × тысячи потоков
Лучше для	Плотные циклы на CPU	Огромные массивы, matmul, conv

Пример divergence: if (x[i] > 0) f(x[i]); else g(x[i]); — половина warp в f, половина в g → фактически 2× время шага.

---

Конвейер — throughput и latency

Стадии fetch/decode/exec/write = 4 такта, бесконечный поток инструкций без конфликтов:

Такт:     1   2   3   4   5   6   7
Inst A:   F   D   E   W
Inst B:       F   D   E   W
Inst C:           F   D   E   W

• Latency одной инструкции = 4 такта.
• Throughput после заполнения = 1 инструкция/такт (ускорение ×4 к «наивному» без конвейера).

При зависимости add r1,r2; mul r3,r1 — stall между exec и следующим fetch. Software pipelining в HPC разводит итерации цикла по стадиям, как конвейер в законах производительности.

---

VLIW и superscalar (кратко)

• Superscalar — hardware сам ищет независимые инструкции в окне и исполняет параллельно (Intel, AMD).
• VLIW (Very Long Instruction Word) — компилятор упаковывает несколько операций в одно «длинное» слово (Itanium). Параллелизм заложен в компиляцию, не в runtime.

Для прикладного разработчика важнее SIMD + OpenMP, но понимание «кто планирует параллелизм — железо или компилятор» помогает читать отчёты оптимизаторов.

---

Что дальше

• Модели памяти и кластеры — как MIMD-машины соединены и делят данные.
• Модели вычислений — PRAM, обмен сообщениями, топологии.
• Законы производительности — почему архитектурный параллелизм не всегда превращается в speedup.

---