SISDобычный процессор
Один поток команд обрабатывает один элемент данных за раз. Обычный цикл на одном ядре.
Больше двух. А иногда и двадцати не хватит. Эта страница объясняет почему: законы Амдала и Густафсона можно покрутить руками, а в конце браузер сам проведёт эксперимент на ядрах вашего компьютера.
Частота. Представьте одного повара. Двадцать лет подряд он каждый год начинал двигаться быстрее, и любое блюдо готовилось быстрее само собой. С 2004 года быстрее он не может: перегреется. Зато поваров на кухне стало 24. Теперь, чтобы ужин был готов раньше, работу надо между ними делить.
Закон Амдала. Готовим ужин: нарезать овощи (30 минут) и сварить суп (30 минут). Овощи режут хоть десять поваров, каждому по кусочку, и вместе они управятся за 3 минуты. А суп варится 30 минут, сколько поваров вокруг кастрюли ни стой. Один повар готовит ужин 60 минут, десять — 33. Не в десять раз быстрее, а меньше чем в два. Суп — это та часть работы, которую нельзя разделить. Подвигайте ползунок и посмотрите, сколько поваров стоят без дела.
Закон Густафсона. А если задача не «этот ужин быстрее», а «накормить больше гостей за тот же час»? Десять поваров нарежут в десять раз больше овощей, пока варится тот же суп. Вот тут они окупаются почти полностью. Переключите режим выше: время не меняется, а гостей становится всё больше.
Потоков больше, чем ядер. Десять поваров на кухне, где всего две доски для нарезки. Восемь стоят и ждут, да ещё мешают друг другу пройти. Так ведёт себя программа, которая запустила больше потоков, чем у процессора ядер: быстрее не становится, а иногда становится медленнее.
Эксперимент. Расчётам верить нельзя, нужен секундомер. Если десять поваров не дали ускорения, диагнозов два: либо суп слишком долгий (большая неделимая часть), либо повара толкаются (накладные расходы). Лечатся они по-разному, и параграф 1.5 показывает, как их различить.
| На кухне | В теории | В веб-сервисе |
|---|---|---|
| Повара | Ядра, потоки p | Пул потоков Tomcat, ForkJoinPool, консьюмеры Kafka, поды в Kubernetes |
| Суп, который варится 30 минут | Последовательная доля f | Один synchronized, одна база под блокировкой, одна партиция Kafka, цепочка вызовов A → B → C |
| Десять поваров, а ужин всего вдвое быстрее | Потолок Амдала 1/f | «Подняли 20 подов, а RPS вырос в 3 раза». Все ждут одну базу |
| Больше гостей за тот же час | Густафсон | Горизонтальное масштабирование: не быстрее один запрос, а больше запросов в секунду |
| Поваров больше, чем досок | Потоков больше, чем ядер | 200 потоков на 4 ядрах: CPU-задачи мешают друг другу; задачи, которые ждут сеть, — нормально |
| Повара толкаются | Накладные расходы, Карп–Флэтт | Переключение контекста, борьба за lock, GC, сериализация |
Правило для микросервисов. Самый медленный неделимый участок задаёт потолок всей системы. Пока он есть, добавлять инстансы почти бесполезно: сначала убирают «суп», потом зовут поваров.
Закон Мура говорит о транзисторах: их число на кристалле удваивается примерно каждые два года. До середины 2000-х это давало и рост тактовой частоты, и однопоточная программа ускорялась сама, без усилий программиста.
Около 2004 года частота упёрлась в стену. Потребляемая мощность растёт быстрее частоты, и кристалл на 5 ГГц нельзя охладить обычным воздухом. Транзисторы продолжают дешеветь, но тратятся теперь на новые ядра, кэш и векторные блоки.
Отсюда главный вывод раздела: программа, которая использует одно ядро, на новом процессоре почти не быстрее, чем на старом. Чтобы использовать современный процессор, программа должна быть параллельной.
Майкл Флинн в 1966 году предложил делить вычислительные системы по двум признакам: сколько потоков команд и сколько потоков данных они обрабатывают одновременно. Получается четыре класса. На схемах синим текут команды, коричневым данные. Наведите на класс, чтобы рассмотреть его поближе.
Один поток команд обрабатывает один элемент данных за раз. Обычный цикл на одном ядре.
Одна команда применяется сразу ко многим данным. Так работают AVX-инструкции и графические процессоры.
Разные команды над одними данными. Встречается в отказоустойчивых системах: три алгоритма считают одно и то же, результат выбирается голосованием.
Разные команды над разными данными. Потоки Java на многоядерном процессоре относятся сюда, как и кластеры.
В любой программе есть часть, которую нельзя распараллелить: чтение входа, инициализация, слияние результатов. Обозначим её долю f. Джин Амдал в 1967 году заметил, что именно она ограничивает ускорение, сколько бы процессоров ни было.
Подвигайте ползунки. Полоса ниже показывает время программы: коричневая часть последовательная и не сжимается, синяя параллельная и делится на число ядер. Справа — сами ядра: видно, сколько из них реально работает.
Джон Густафсон в 1988 году возразил: на практике, получив больше процессоров, люди не решают ту же задачу быстрее, а решают задачу побольше за то же время. Прогноз погоды считают не за минуту вместо часа, а с более мелкой сеткой за тот же час.
Тогда последовательная часть остаётся прежней, а параллельная растёт вместе с числом ядер, и ускорение почти линейно. Законы не противоречат друг другу: они описывают разные ситуации, которые называют сильным и слабым масштабированием.
Теория проверяется замером. Ускорение S = T₁ / Tₚ, эффективность E = S / p. Есть и обратная метрика Карпа–Флэтта: по замеренному ускорению она восстанавливает последовательную долю. Если она постоянна, мешает последовательный код; если растёт с числом потоков, мешают накладные расходы или нехватка ядер.
Кнопка ниже запускает вычисление π как интеграла ∫₀¹ 4/(1+x²) dx на 1, 2, 4… потоках (Web Workers) прямо в этом браузере. У каждого потока своя дорожка: видно, как они делят работу. Считать будет несколько секунд.
| Потоки | T, мс | S | E | Карп–Флэтт |
|---|---|---|---|---|
| 1 | 2112 | 1,00 | 100 % | — |
| 2 | 1084 | 1,95 | 97 % | 0,027 |
| 4 (ядер 2) | 1075 | 1,96 | 49 % | 0,345 |
Java 21, ExecutorService, медиана из 5 запусков после 3 прогревочных.
Потоки Java выполняются как потоки операционной системы на разных ядрах, поэтому именно на Java удобно проверять законы этого раздела. Три способа разложить одну и ту же сумму на ядра, от явного к декларативному.
static double kernel(long from, long to, double h) { double sum = 0.0; for (long i = from; i < to; i++) { double x = (i + 0.5) * h; sum += 4.0 / (1.0 + x * x); } return sum; }
Одна и та же функция во всех вариантах, иначе JIT скомпилирует их по-разному, и сравнение будет нечестным.
// диапазон делится на p равных блоков try (var pool = Executors.newFixedThreadPool(p)) { List<Future<Double>> parts = new ArrayList<>(); for (int k = 0; k < p; k++) { long from = n * k / p, to = n * (k + 1) / p; parts.add(pool.submit(() -> kernel(from, to, h))); } double sum = 0; for (var f : parts) sum += f.get(); return sum * h; }
Явный контроль: видно, где создаются потоки и где собираются результаты. Потоки не пишут в общие переменные, гонок нет.
protected Double compute() { if (to - from <= THRESHOLD) return kernel(from, to, h); long mid = (from + to) >>> 1; var left = new SumTask(from, mid, h); left.fork(); // в очередь double right = new SumTask(mid, to, h).compute(); return right + left.join(); }
Рекурсивное деление пополам. Свободные потоки забирают задачи из чужих очередей (work-stealing), нагрузка выравнивается сама.
return LongStream.range(0, n).parallel() .mapToDouble(i -> { double x = (i + 0.5) * h; return 4.0 / (1.0 + x * x); }) .sum() * h;
Самая короткая запись. Внутри тот же ForkJoinPool, но число потоков задаётся общим пулом, а не программой.
| Способ | T(1), мс | T(2), мс | Ускорение | |π − π*| |
|---|---|---|---|---|
| Последовательный цикл | 2209 | — | 1,00 | 7,5·10⁻¹⁵ |
| ExecutorService | 2159 | 1110 | 1,94 | 3,1·10⁻¹⁵ |
| ForkJoinPool | 1959 | 981 | 2,00 | 4,4·10⁻¹⁶ |
| parallel stream | 1966 | 1048 | 1,88 | 4,4·10⁻¹⁶ |