Закон Густафсона

Теоретическая формула ускорения в архитектуре компьютера

Эволюция согласно закону Густафсона теоретического ускорения задержки выполнения программы в зависимости от количества процессоров, выполняющих ее, для различных значений a

В компьютерной архитектуре закон Густафсона (или закон Густафсона–Барсиса ^[1] ) дает ускорение времени выполнения задачи, которое теоретически выигрывает от параллельных вычислений , используя гипотетический запуск задачи на одноядерной машине в качестве базовой линии. Другими словами, это теоретическое «замедление» уже распараллеленной задачи при запуске на последовательной машине. Он назван в честь ученого-компьютерщика Джона Л. Густафсона и его коллеги Эдвина Х. Барсиса и был представлен в статье Reevaluating Amdahl's Law в 1988 году. ^[2]

Определение

Густафсон оценил ускорение программы за счет использования параллельных вычислений следующим образом: ${\displaystyle S}$

$${\displaystyle {\begin{aligned}S&=s+p\times N\\&=s+(1-s)\times N\\&=N+(1-N)\times s\end{aligned}}}$$

где

• ${\displaystyle S}$теоретическое ускорение программы с параллелизмом (масштабированное ускорение ^[2] );
• ${\displaystyle N}$количество процессоров;
• ${\displaystyle s}$и — доли времени, затраченного на выполнение последовательных частей и параллельных частей программы соответственно на параллельной системе, где . ${\displaystyle p}$ ${\displaystyle s+p=1}$

Альтернативно можно выразить с помощью : ${\displaystyle S}$ ${\displaystyle p}$

$${\displaystyle {\begin{aligned}S&=(1-p)+p\times N\\&=1+(N-1)\times p\end{aligned}}}$$

Закон Густафсона устраняет недостатки закона Амдаля , который основан на предположении о фиксированном размере проблемы , то есть рабочей нагрузке выполнения, которая не меняется по отношению к улучшению ресурсов. Закон Густафсона вместо этого предполагает, что программисты стремятся увеличивать размер проблем, чтобы полностью использовать вычислительную мощность, которая становится доступной по мере улучшения ресурсов. ^[2]

Густафсон и его коллеги далее наблюдали из своих рабочих нагрузок, что время для последовательной части обычно не растет с ростом проблемы и масштаба системы, ^[2] то есть, фиксировано. Это дает линейную модель между количеством процессоров и ускорением с наклоном , как показано на рисунке выше (который использует разные обозначения: для и для ). Кроме того, масштабируется линейно с , а не экспоненциально в законе Амдаля. ^[2] С этими наблюдениями Густафсон «ожидает распространить [их] успех [в параллельных вычислениях] на более широкий спектр приложений и даже большие значения для ». ^[2] ${\displaystyle s}$ ${\displaystyle N}$ ${\displaystyle S}$ ${\displaystyle 1-s}$ ${\displaystyle P}$ ${\displaystyle N}$ ${\displaystyle a}$ ${\displaystyle s}$ ${\displaystyle S}$ ${\displaystyle s}$ ${\displaystyle N}$

Влияние закона Густафсона заключалось в смещении ^{[ требуется цитата ]} исследовательских целей для выбора или переформулирования проблем таким образом, чтобы решение более крупной проблемы за то же время было возможным. В некотором смысле закон переопределяет эффективность, из-за возможности того, что ограничения, накладываемые последовательной частью программы, могут быть преодолены путем увеличения общего объема вычислений.

Вывод

Время выполнения программы, работающей на параллельной системе, можно разделить на две части:

• часть, которая не получает выгоды от увеличения числа процессоров (последовательная часть);
• часть, которая выигрывает от увеличения числа процессоров (параллельная часть).

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

Без потери общности пусть общее время выполнения на параллельной системе будет . Обозначим последовательное время как , а параллельное время как , где . Обозначим число процессоров как . ${\displaystyle T=1}$ ${\displaystyle s}$ ${\displaystyle p}$ ${\displaystyle s+p=1}$ ${\displaystyle N}$

Гипотетически, при запуске программы на последовательной системе (только один процессор) последовательная часть по-прежнему занимает , а параллельная часть теперь занимает . Время выполнения на последовательной системе составляет: ${\displaystyle s}$ ${\displaystyle Np}$

$${\displaystyle T'=s+Np}$$При использовании в качестве базового значения ускорение для параллельной системы составит: ${\displaystyle T'}$

$${\displaystyle S={\frac {T'}{T}}={\frac {s+Np}{s+p}}={\frac {s+Np}{1}}=s+Np}$$

Подставляя или , можно получить несколько форм из предыдущего раздела. ${\displaystyle p=1-s}$ ${\displaystyle s=1-p}$

Приложения

Применение в исследованиях

Закон Амдаля предполагает, что вычислительные требования останутся прежними при увеличении вычислительной мощности. Другими словами, анализ тех же данных займет меньше времени при увеличении вычислительной мощности.

С другой стороны, Густафсон утверждает, что большая вычислительная мощность приведет к более тщательному и полному анализу данных: пиксель за пикселем или единица за единицей, а не в большем масштабе. Там, где было бы невозможно или непрактично моделировать воздействие ядерного взрыва на каждое здание, машину и их содержимое (включая мебель, прочность конструкции и т. д.), поскольку такой расчет занял бы больше времени, чем было доступно для предоставления ответа, увеличение вычислительной мощности побудит исследователей добавлять больше данных для более полной имитации большего количества переменных, что даст более точный результат.

Применение в повседневных компьютерных системах

Закон Амдаля выявляет ограничение, например, в способности нескольких ядер сокращать время, необходимое компьютеру для загрузки операционной системы и готовности к использованию. Если предположить, что процесс загрузки был в основном параллельным, учетверение вычислительной мощности в системе, загрузка которой заняла одну минуту, может сократить время загрузки до чуть более пятнадцати секунд. Но все большее и большее распараллеливание в конечном итоге не смогло бы ускорить загрузку, если бы какая-либо часть процесса загрузки была изначально последовательной.

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

Ограничения

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

Алгоритмы с нелинейным временем выполнения могут столкнуться с трудностями в использовании преимуществ параллелизма, «раскрываемого» законом Густафсона. Снайдер ^[3] указывает на алгоритм, который означает, что удвоение параллелизма дает всего лишь около 26% увеличения размера проблемы. Таким образом, хотя и возможно занять огромный параллелизм, это может дать мало преимуществ по сравнению с исходным, менее параллельнм решением — однако на практике все еще наблюдаются значительные улучшения. ${\displaystyle O(N^{3})}$

Хилл и Марти ^[4] также подчеркивают, что методы ускорения последовательного выполнения все еще необходимы, даже для многоядерных машин. Они указывают, что локально неэффективные методы могут быть глобально эффективными, если они сокращают последовательную фазу. Кроме того, Ву и Ли ^[5] изучили влияние энергии и мощности на будущие многоядерные процессоры на основе закона Амдаля, показав, что асимметричный многоядерный процессор может достичь наилучшей возможной энергоэффективности , активируя оптимальное количество ядер, учитывая, что величина параллелизма известна до выполнения.

Аль-Хаянни, Рафиев и др. разработали новые модели ускорения и потребления энергии, основанные на общем представлении гетерогенности ядра, называемом гетерогенностью нормальной формы, которая поддерживает широкий спектр гетерогенных многоядерных архитектур. Эти методы моделирования направлены на прогнозирование энергоэффективности системы и диапазонов производительности, а также облегчают исследования и разработки на уровне аппаратного и системного программного обеспечения. ^{[6] [7]}

Смотрите также

• Масштабируемый параллелизм
• закон Паркинсона
• Парадокс Джевонса

Ссылки

1. МакКул, Майкл Д.; Робисон, Арч Д.; Рейндерс, Джеймс (2012). «2.5 Теория производительности». Структурированное параллельное программирование: шаблоны для эффективных вычислений . Elsevier. стр. 61–62. ISBN 978-0-12-415993-8.
2. Густафсон, Джон Л. (май 1988 г.). «Переоценка закона Амдаля». Сообщения ACM . 31 (5): 532–3. CiteSeerX 10.1.1.509.6892 . doi :10.1145/42411.42415. S2CID  33937392. 
3. Снайдер, Лоуренс (июнь 1986 г.). «Архитектуры типов, общая память и следствие скромного потенциала» (PDF) . Annu. Rev. Comput. Sci . 1 : 289–317. doi :10.1146/annurev.cs.01.060186.001445.
4. Хилл, Марк Д.; Марти, Майкл Р. (июль 2008 г.). «Закон Амдаля в эпоху многоядерных процессоров». IEEE Computer . 41 (7): 33–38. CiteSeerX 10.1.1.221.8635 . doi :10.1109/MC.2008.209. UW CS-TR-2007-1593. 
5. Донг Хёк Ву; Хсиен-Хсин С. Ли (декабрь 2008 г.). «Расширение закона Амдаля для энергоэффективных вычислений в эпоху многоядерных процессоров». IEEE Computer . 41 (12): 24–31. CiteSeerX 10.1.1.156.3907 . doi :10.1109/mc.2008.494. S2CID  6136462. 
6. Рафиев, Ашур; Аль-Хаянни, Мохаммед АН; Ся, Фэй; Шафик, Ришад; Романовский, Александр; Яковлев, Алекс (2018-07-01). «Модели масштабирования ускорения и мощности для гетерогенных многоядерных систем». Труды IEEE по многомасштабным вычислительным системам . 4 (3): 436–449. doi :10.1109/TMSCS.2018.2791531. ISSN  2332-7766. S2CID  52287374.
7. Аль-Хаянни, Мохаммед А. Ноаман; Ся, Фэй; Рафиев, Ашур; Романовский, Александр; Шафик, Ришад; Яковлев, Алекс (июль 2020 г.). «Закон Амдаля в контексте гетерогенных многоядерных систем – обзор». IET Computers & Digital Techniques . 14 (4): 133–148. doi : 10.1049/iet-cdt.2018.5220 . ISSN  1751-8601. S2CID  214415079.