Один процессор — хорошо. Два — лучше. А тысяча? Разбираемся, как ускорить вычисления, разделяя работу между ядрами, и почему бесконечно ускорять нельзя.
Параллельные вычисления — это когда задача разбивается на части, и каждая часть выполняется одновременно на своём процессоре.
Современные процессоры имеют 4–16 ядер, видеокарты — тысячи. Но параллелизм — не панацея: часть кода всегда выполняется последовательно, и это ограничивает ускорение.
Закон Мура замедляется — частота не растёт, растут ядра
До 2005 г. процессоры ускорялись за счёт повышения тактовой частоты (Гц). Но выше ~4 ГГц чип перегревается. С тех пор рост производительности идёт через увеличение числа ядер.
Одна операция применяется ко многим данным одновременно. Пример: применить фильтр ко всем пикселям изображения.
Разные ядра выполняют разные задачи одновременно. Пример: одно ядро рендерит видео, другое сжимает файл.
Почему бесконечное число ядер не даёт бесконечного ускорения
Джин Амдал (1967) вывел формулу максимального ускорения при распараллеливании:
Программа: 80% можно распараллелить (p = 0.8), 20% — строго последовательно. 4 ядра:
Ускорение в 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×, даже с миллионом ядер.
Четыре типа архитектур по числу потоков команд и данных
Майкл Флинн (1966) разделил все компьютеры на 4 класса по количеству потоков команд (Instruction) и данных (Data):
| Класс | Команды | Данные | Пример |
|---|---|---|---|
| SISD | 1 | 1 | Обычный одноядерный процессор |
| SIMD | 1 | много | GPU, векторные инструкции (SSE/AVX) |
| MISD | много | 1 | Теоретический (почти не используется) |
| MIMD | много | много | Многоядерные CPU, кластеры, суперкомпьютеры |
Разбиение команды на стадии — как конвейер на заводе
Каждая команда процессора проходит несколько стадий. Вместо того чтобы ждать завершения одной команды, процессор начинает следующую, пока предыдущая ещё на конвейере:
Для k стадий и n команд: T = k + (n − 1) тактов.
Без конвейера: T = k × n. Выигрыш: примерно в k раз при большом n.
Потоки, мьютексы, deadlock — как не сломать параллельную программу
| Процесс | Поток (thread) | |
|---|---|---|
| Память | Своя (изолирован) | Общая с другими потоками процесса |
| Создание | Медленное (fork) | Быстрое |
| Обмен данными | Через IPC (трубы, сокеты) | Напрямую через общую память |
| Безопасность | Высокая (изоляция) | Низкая (race condition) |
Два потока одновременно читают и пишут одну переменную. Результат непредсказуем.
Поток A ждёт ресурс B, поток B ждёт ресурс A. Оба ждут вечно.
Потоки не заблокированы, но бесконечно уступают друг другу, не продвигаясь.
| Механизм | Назначение |
|---|---|
| Мьютекс (mutex) | Взаимоисключающая блокировка: только один поток может владеть ресурсом |
| Семафор | Обобщение мьютекса: разрешает N потокам одновременно |
| Барьер | Все потоки ждут, пока последний не дойдёт до барьера |
| Атомарная операция | Операция, которая выполняется целиком или не выполняется вообще |
Измените долю параллельного кода (p) и число ядер (N) — калькулятор покажет ускорение, эффективность и теоретический предел.
Нажмите на класс — увидите описание, примеры и SVG-схему.
Одна команда, одни данные. Классический одноядерный процессор фон Неймана. Команды выполняются строго последовательно.
Примеры: Intel 8086, ранние ПК. Сейчас встречается в микроконтроллерах.
Одна команда, много данных. Одна инструкция применяется ко многим элементам одновременно.
Примеры: GPU (тысячи ядер обрабатывают пиксели), SSE/AVX в CPU (векторные операции). Идеально для графики, нейросетей, обработки сигналов.
Много команд, одни данные. Разные процессоры применяют разные операции к одним данным.
Практически не используется. Иногда так описывают конвейер (разные стадии — разные операции над одной командой).
Много команд, много данных. Каждый процессор выполняет свою программу над своими данными.
Примеры: многоядерные CPU (Intel Core i7, AMD Ryzen), кластеры, суперкомпьютеры. Самый распространённый класс современных систем.
Измените количество стадий конвейера и команд — увидите такты выполнения и выигрыш.
Дано 3 процесса с разным временем выполнения. Расположите их на временной шкале для одного ядра CPU. Попробуйте сначала последовательно, потом с I/O-ожиданием (процесс уходит в WAITING, освобождая CPU).
Процесс A захватил Сканер и ждёт Принтер. Процесс B захватил Принтер и ждёт Сканер. Оба заблокированы! Измените порядок запросов ресурсов, чтобы избежать взаимной блокировки.