Если 95% вашей задачи выполняется параллельно - максимальное ускорение 20 раз. Хоть 8 процессоров, хоть 8 тысяч. Потолок встроен в задачу, не в железо.

Это закон Амдала. Сформулирован в 1967-м на конференции AFIPS в статье с названием "Validity of the Single Processor Approach to Achieving Large Scale Computing Capabilities" - то есть "В защиту одиночного процессора". Амдал пришел объяснить, почему массовый параллелизм не даст обещанного выигрыша для многих реальных задач.

А что за формула и что она говорит

Закон записывается так:

S = 1 / ((1 - P) + P/N)

Где S - ускорение, P - доля задачи, поддающаяся параллельному выполнению, N - количество процессоров. При N стремящемся к бесконечности: S_max = 1 / (1 - P).

Кстати, в оригинале 1967 года этой алгебраической записи нет. Амдал изложил аргумент качественно - две страницы текста. Современную формальную запись систематизировали позднее.

Что жеж это значит? 90% параллельного кода - максимум 10x. 95% - максимум 20x. 99% - максимум 100x. Дальше потолок. И совершенно не важно сколько ядер добавить.

По версии Амдала, скажем так, около 40% реальных вычислительных задач приходится на последовательную часть - обслуживание данных, управление памятью. По его оценке, если вынести эти доп. расходы на отдельный процессор, реальный выигрыш составит 5-7x - но никак не линейное ускорение с числом процессоров. Аргумент был направлен против сторонников массивно-параллельных архитектур: обещанного роста не будет.

Кто такой Амдал

Джин Амдал родился в 1922-м в Южной Дакоте, получил докторскую по теоретической физике в Висконсине, пришел в IBM в 1952-м. До закона он успел стать одним из трех главных архитекторов IBM System/360 - вместе с Фредом Бруксом и Герритом Блааувом. System/360 определила облик корпоративных вычислений на десятилетия - единая архитектура с совместимостью кода между машинами разного класса производительности.

В 1967-м он работал в IBM Advanced Computing Systems Laboratory в Менло-Парке. В индустрии шел спор - а будущее, собственно, за мощными одиночными процессорами или за параллельными машинами из многих слабых? Амдал выступил с математическим аргументом в пользу первых.

Через три года, в октябре 1970-го, он ушел из IBM и основал Amdahl Corporation. Компания делала мейнфреймы - машины с быстрым одиночным процессором, программно совместимые с IBM, но дешевле. Первый продукт, Amdahl 470 V/6, отгрузили в 1975-м. В 1997-м компанию поглотила Fujitsu.

Человек, сформулировавший закон о пределах параллелизма, построил бизнес на продаже быстрых одиночных процессоров. Ну и логика тут вполне очевидна, хех.

Где прячется последовательная часть

Закон Амдала часто читают примерно так - оптимизируй параллельную часть. И это ошибка. Потому как он говорит ровно обратное - найди последовательную часть и уменьши ее. Параллельная часть - не проблема. Проблема - те 5%, которые нельзя распараллелить.

В конкурентном программировании - это блокировки. Когда несколько потоков пытаются захватить один мьютекс, они выстраиваются в очередь. Это момент чисто последовательного выполнения. Сотня потоков не помогает, если каждый из них ждет один лок. Больше того - по мере добавления потоков конкуренция за блокировки растет, и эффективная последовательная доля увеличивается. Реальное поведение оказывается пессимистичнее даже того, что предсказывает закон.

В языках с управляемой памятью - это сборщик мусора. Паузы на сборку - чисто последовательные. Параллельные алгоритмы сборки снижают, но не устраняют эффект.

В распределенных системах это консенсус. Протоколы согласования по природе последовательны. Нельзя параллельно договориться о порядке событий. Raft, Paxos - в каждом есть лидер, через которого идут записи.

Тут, кстати, и становится понятно почему lock-free структуры данных, MVCC в базах данных и в конечном счете модели без строгой согласованности - это все попытки уменьшить последовательную долю. Не архитектурная мода, а прямое следствие формулы.

Густафсон и слабое масштабирование

В мае 1988-го в журнале Communications of the ACM (издание Ассоциации вычислительной техники) вышла статья Джона Густафсона и Эдвина Барсиса "Reevaluating Amdahl's Law" - "Переосмысление закона Амдала".

Густафсон работал в Сандийской национальной лаборатории - американском ядерном исследовательском центре. У него был 1024-процессорный гиперкуб. Команда получала ускорение больше 1000x - конкретно 1021x на задаче анализа механических напряжений. По грубому прочтению Амдала такие результаты казались почти невозможными. Противоречие?

А вот и нет. Был другой исходный вопрос.

Амдал предполагал, что есть фиксированная задача. Добавляешь процессоры - хочешь решить ее быстрее. Это называется сильное масштабирование. При нем закон Амдала точен.

Густафсон наблюдал немного другое. Исследователи, получив больше процессоров, не решали ту же задачу быстрее - они брали задачу большего масштаба. Симуляцию с более высоким разрешением, с большим числом частиц, с более точной сеткой. Последовательная часть при этом остается примерно постоянной по времени, а параллельная растет. Это слабое масштабирование.

При слабом масштабировании ускорение может расти почти линейно с числом процессоров при малой последовательной доле. Та работа получила премию Гордона Белла (Gordon Bell Award) на конференции по компьютерной технике COMPCON в 1988 году - именно как демонстрация реального масштабирования, которое по грубому прочтению Амдала казалось недостижимым.

Опять же, это не опровержение закона Амдала. Это другая постановка задачи. Закон Амдала описывает одну ситуацию, закон Густафсона - другую. Обе правды.

Как это выглядит сейчас

Современная параллельная задача - обучение нейронных сетей на нескольких GPU. Вычисления прямого и обратного прохода - параллельная часть. Каждый GPU считает свои градиенты независимо.

Но потом их нужно синхронизировать. Операция коллективного сведения (All-Reduce) - каждое устройство обменивается градиентами со всеми остальными, суммирует их, обновляет параметры. Сам обмен может идти параллельным алгоритмом, но следующий шаг обучения не начнется, пока барьер синхронизации не снят. Это и есть последовательный узел.

При медленном межузловом соединении коммуникационная часть может занимать значительную долю времени итерации - в некоторых конфигурациях больше половины, хотя конкретная цифра сильно зависит от топологии кластера, типа соединения и архитектуры модели. Добавление GPU помогает считать быстрее, но не устраняет время синхронизации. Закон выполняется.

Именно поэтому в крупных кластерах такое внимание к пропускной способности межузловых соединений - NVLink (высокоскоростная шина GPU от Nvidia), InfiniBand (сетевой стандарт для высокопроизводительных кластеров) - и к алгоритмам, перекрывающим вычисления с передачей данных. Попытка уменьшить эффективную последовательную долю. Та же задача что у Густафсона в 1988-м, просто на другом железе.

Вот, а в 1967-м на конференции AFIPS Амдал выступил с двухстраничным текстом. Объяснял почему параллельные компьютеры - плохая идея. Через три года основал компанию с быстрыми одиночными мейнфреймами.

И формула по его мотивам сейчас обязательное чтение для тех, кто проектирует параллельные системы.