Если 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 Амдал выступил с двухстраничным текстом. Объяснял почему параллельные компьютеры — плохая идея. Через три года основал компанию с быстрыми одиночными мейнфреймами.
И формула по его мотивам сейчас обязательное чтение для тех, кто проектирует параллельные системы.
ссылка на оригинал статьи https://habr.com/ru/articles/1054424/