Параллельные вычисления

Содержание и основные понятия

← Вернуться к оглавлению
Alterna · глава 7 · страница 7.1
Параллельные вычисления
Один процессор — хорошо. Два — лучше. А тысяча? Разбираемся, как ускорить вычисления, разделяя работу между ядрами, и почему бесконечно ускорять нельзя.
Параллельные вычисления
— это когда задача разбивается на части, и каждая часть выполняется одновременно на своём процессоре.
Современные процессоры имеют 4–16 ядер, видеокарты — тысячи. Но параллелизм — не панацея: часть кода всегда выполняется последовательно, и это ограничивает ускорение.
ФГОС · базовый
ЕГЭ · № 22
01
Зачем параллелить?
Закон Мура замедляется — частота не растёт, растут ядра
Предел частоты
До 2005 г. процессоры ускорялись за счёт повышения
тактовой частоты
(Гц). Но выше ~4 ГГц чип перегревается. С тех пор рост производительности идёт через
увеличение числа ядер
.
Два типа параллелизма
📊
Параллелизм данных
data parallelism
Одна операция применяется ко многим данным одновременно. Пример: применить фильтр ко всем пикселям изображения.
🔀
Параллелизм задач
task parallelism
Разные ядра выполняют разные задачи одновременно. Пример: одно ядро рендерит видео, другое сжимает файл.
Связь с главой 2
В главе 2 (ПК) мы видели многоядерные процессоры на материнской плате. Теперь разберём, как они работают вместе.
02
Закон Амдала
Почему бесконечное число ядер не даёт бесконечного ускорения
Формула
Джин Амдал (1967) вывел формулу максимального ускорения при распараллеливании:
S = 1 / ((1 − p) + p / N)
p — доля параллельного кода (0–1), N — число ядер
Пример
Программа: 80% можно распараллелить (p = 0.8), 20% — строго последовательно. 4 ядра:
S = 1 / (0.2 + 0.8/4) = 1 / (0.2 + 0.2) = 1 / 0.4 =
2.5
Ускорение
в 2.5 раза
, хотя ядер 4. Последовательные 20% — «бутылочное горлышко».
Предел Амдала
При N → ∞:
S_max = 1 / (1 − p)
. Для p = 0.9: максимум 10×. Для p = 0.99: максимум 100×.
Ловушка ЕГЭ
Ускорение
никогда
не превышает
1/(1-p)
, сколько бы ядер ни добавляли. Если p = 0.5, максимум — 2×, даже с миллионом ядер.
03
Классификация Флинна
Четыре типа архитектур по числу потоков команд и данных
Майкл Флинн (1966) разделил все компьютеры на 4 класса по количеству потоков
команд
(Instruction) и
данных
(Data):
Класс
Команды
Данные
Пример
SISD
1
1
Обычный одноядерный процессор
SIMD
1
много
GPU, векторные инструкции (SSE/AVX)
MISD
много
1
Теоретический (почти не используется)
MIMD
много
много
Многоядерные CPU, кластеры, суперкомпьютеры
Запомнить
SISD
— ваш старый ПК.
SIMD
— видеокарта.
MIMD
— современный многоядерный процессор или суперкомпьютер.
04
Конвейерная обработка
Разбиение команды на стадии — как конвейер на заводе
Идея конвейера
Каждая команда процессора проходит несколько стадий. Вместо того чтобы ждать завершения одной команды, процессор начинает следующую, пока предыдущая ещё на конвейере:
Такт 1
IF (ком.1)
Такт 2
ID (ком.1)
IF (ком.2)
Такт 3
EX (ком.1)
ID (ком.2)
IF (ком.3)
Такт 4
WB (ком.1)
EX (ком.2)
ID (ком.3)
IF (ком.4)
IF — загрузка
ID — декодирование
EX — выполнение
WB — запись
Рис. 1.
4-стадийный конвейер: после заполнения каждая команда завершается за 1 такт
Формула конвейера
Для
k
стадий и
n
команд:
T = k + (n − 1)
тактов.
Без конвейера:
T = k × n
. Выигрыш: примерно в
k
раз при большом n.
Пример
4 стадии, 100 команд: конвейер = 4 + 99 =
103
такта. Без конвейера = 4 × 100 =
400
тактов. Ускорение ≈ 3.9×.
05
Многопоточность и синхронизация
Потоки, мьютексы, deadlock — как не сломать параллельную программу
Процесс vs Поток
Процесс
Поток (thread)
Память
Своя (изолирован)
Общая с другими потоками процесса
Создание
Медленное (fork)
Быстрое
Обмен данными
Через IPC (трубы, сокеты)
Напрямую через общую память
Безопасность
Высокая (изоляция)
Низкая (race condition)
Проблемы параллелизма
🏁
Race Condition
состояние гонки
Два потока одновременно читают и пишут одну переменную. Результат непредсказуем.
🔒
Deadlock
взаимная блокировка
Поток A ждёт ресурс B, поток B ждёт ресурс A. Оба ждут вечно.
⏳
Livelock
живая блокировка
Потоки не заблокированы, но бесконечно уступают друг другу, не продвигаясь.
Механизмы синхронизации
Механизм
Назначение
Мьютекс (mutex)
Взаимоисключающая блокировка: только один поток может владеть ресурсом
Семафор
Обобщение мьютекса: разрешает N потокам одновременно
Барьер
Все потоки ждут, пока последний не дойдёт до барьера
Атомарная операция
Операция, которая выполняется целиком или не выполняется вообще
4 условия deadlock
1. Взаимоисключение (ресурс занят одним). 2. Удержание и ожидание (держу одно, жду другое). 3. Нет принудительного изъятия. 4. Кольцевое ожидание (A→B→C→A). Если убрать хотя бы одно — deadlock невозможен.
Связь с ЕГЭ № 23, 26
Понимание параллельных процессов и диаграмм Ганта помогает в задачах ЕГЭ №23 (подсчёт траекторий — ветвление = параллельные пути) и №26 (обработка данных с приоритетами и временем — планирование как у ОС).
📐
Калькулятор закона Амдала
подвигайте ползунки · смотрите ускорение
интерактив
Измените долю параллельного кода (p) и число ядер (N) — калькулятор покажет ускорение, эффективность и теоретический предел.
Параллельный код (p)
80%
Число ядер (N)
4
2.50
Ускорение (S)
62.5%
Эффективность (S/N)
5.00
Предел (N→∞)
🏷️
Классификация Флинна
кликните на карточку · подробности
интерактив
Нажмите на класс — увидите описание, примеры и SVG-схему.
SISD
Single Instruction, Single Data
Одна команда, одни данные.
Классический одноядерный процессор фон Неймана. Команды выполняются строго последовательно.
Примеры: Intel 8086, ранние ПК. Сейчас встречается в микроконтроллерах.
SIMD
Single Instruction, Multiple Data
Одна команда, много данных.
Одна инструкция применяется ко многим элементам одновременно.
Примеры: GPU (тысячи ядер обрабатывают пиксели), SSE/AVX в CPU (векторные операции). Идеально для графики, нейросетей, обработки сигналов.
MISD
Multiple Instruction, Single Data
Много команд, одни данные.
Разные процессоры применяют разные операции к одним данным.
Практически не используется. Иногда так описывают конвейер (разные стадии — разные операции над одной командой).
MIMD
Multiple Instruction, Multiple Data
Много команд, много данных.
Каждый процессор выполняет свою программу над своими данными.
Примеры: многоядерные CPU (Intel Core i7, AMD Ryzen), кластеры, суперкомпьютеры. Самый распространённый класс современных систем.
🏭
Конвейер: визуализация
настройте стадии и команды · сравните с без-конвейерным
интерактив
Измените количество стадий конвейера и команд — увидите такты выполнения и выигрыш.
Стадий конвейера (k)
4
Команд (n)
6
9
Конвейер (тактов)
24
Без конвейера
2.67×
Ускорение
📊
Ты — планировщик ОС
диаграмма Ганта · перетаскивай процессы на временную шкалу
интерактив
Дано 3 процесса с разным временем выполнения. Расположите их на временной шкале для одного ядра CPU. Попробуйте сначала последовательно, потом с I/O-ожиданием (процесс уходит в WAITING, освобождая CPU).
P1: Вычисления
3 такта
I/O: 0 тактов
P2: Чтение файла
2 такта CPU
I/O: 3 такта (после CPU)
P3: Сеть
1 такт CPU
I/O: 2 такта (после CPU)
CPU
P2 I/O
P3 I/O
Общее время:
—
Загрузка CPU:
—
Среднее ожидание:
—
🔒
Симулятор взаим