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

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

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

В компьютерной архитектуре закон Густавсона (или закон Густавсона-Барсиса ^[1] ) дает ускорение времени выполнения задачи, которое теоретически выигрывает от параллельных вычислений , используя в качестве основы гипотетический запуск задачи на одноядерной машине. Другими словами, это теоретическое «замедление» уже распараллеленной задачи, если она выполняется на последовательной машине. Он назван в честь ученого-компьютерщика Джона Л. Густавсона и его коллеги Эдвина Х. Барсиса и был представлен в статье «Переоценка закона Амдала» в 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] являются фиксированными. Это дает линейную модель между количеством процессоров и ускорением с наклоном , как показано на рисунке выше (на котором используются разные обозначения: for и for ). Кроме того, в соответствии с законом Амдала масштабируется линейно, а не экспоненциально. ^[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 Теория производительности». Структурированное параллельное программирование: шаблоны для эффективных вычислений . Эльзевир. стр. 61–62. ISBN 978-0-12-415993-8.
2. Густавсон, Джон Л. (май 1988 г.). «Переоценка закона Амдала». Коммуникации АКМ . 31 (5): 532–3. CiteSeerX 10.1.1.509.6892 . дои : 10.1145/42411.42415. S2CID  33937392. 
3. Снайдер, Лоуренс (июнь 1986 г.). «Архитектура типов, общая память и следствие скромного потенциала» (PDF) . Анну. Ред. Компьютер. Наука . 1 : 289–317. doi : 10.1146/annurev.cs.01.060186.001445.
4. Хилл, Марк Д.; Марти, Майкл Р. (июль 2008 г.). «Закон Амдала в эпоху многоядерности». IEEE-компьютер . 41 (7): 33–38. CiteSeerX 10.1.1.221.8635 . дои : 10.1109/MC.2008.209. УВ CS-TR-2007-1593. 
5. Дон Хёк У; Сянь-Синь С. Ли (декабрь 2008 г.). «Расширение закона Амдала для энергоэффективных вычислений в эпоху многоядерности». IEEE-компьютер . 41 (12): 24–31. CiteSeerX 10.1.1.156.3907 . дои : 10.1109/mc.2008.494. S2CID  6136462. 
6. Рафиев, Ашур; Аль-Хаянни, Мохаммед А.Н.; Ся, Фэй; Шафик, Ришад; Романовский, Александр; Яковлев, Алекс (01.07.2018). «Модели ускорения и масштабирования мощности для гетерогенных многоядерных систем». Транзакции IEEE в многомасштабных вычислительных системах . 4 (3): 436–449. дои : 10.1109/TMCSS.2018.2791531. ISSN  2332-7766. S2CID  52287374.
7. Аль-Хаянни, Мохаммед А. Ноаман; Ся, Фэй; Рафиев, Ашур; Романовский, Александр; Шафик, Ришад; Яковлев, Алексей (июль 2020 г.). «Закон Амдала в контексте гетерогенных многоядерных систем - обзор». IET Компьютеры и цифровая техника . 14 (4): 133–148. doi : 10.1049/iet-cdt.2018.5220 . ISSN  1751-8601. S2CID  214415079.