Закон Густавсона - Википедия - Gustafsons law

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

В компьютерная архитектура, Закон Густафсона (или же Закон Густафсона – Барсиса^[1]) дает теоретические ускорение в задержка выполнения задания в фиксированное время исполнения чего можно ожидать от системы, ресурсы которой улучшены. Он назван в честь компьютерного ученого. Джон Л. Густафсон и его коллега Эдвин Х. Барсис, и был представлен в статье Переоценка закона Амдала в 1988 г.^[2]

Определение

Густафсон оценил ускорение S получено с помощью N процессоров (вместо одного) для задачи с порядковой дробью s (который не выигрывает от параллелизма) следующим образом:^[2]

${ Displaystyle S = N + (1-N) s}$

Используя различные переменные, закон Густафсона можно сформулировать следующим образом:^{[нужна цитата ]}

${ displaystyle S _ { text {latency}} (s) = 1-p + sp,}$

куда

• S_{задержка} - теоретическое ускорение задержки выполнения всей задачи;
• s - это ускорение задержки выполнения той части задачи, которая выигрывает от улучшения ресурсов системы;
• п это процент исполнения нагрузка всей задачи, касающейся той части, которая извлекает выгоду из улучшения ресурсов системы до улучшения.

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

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

Вывод

Задачу, выполняемую системой, ресурсы которой улучшены по сравнению с исходной аналогичной системой, можно разделить на две части:

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

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

Обозначена рабочая нагрузка выполнения всей задачи до улучшения ресурсов системы. ${ displaystyle W}$. Он включает рабочую нагрузку выполнения той части, которая не получает выгоды от улучшения ресурсов, и рабочую нагрузку выполнения той, которая получает от этого выгоду. Доля рабочей нагрузки выполнения, которая выиграет от улучшения ресурсов, обозначается как ${ displaystyle p}$ Следовательно, дробь, относящаяся к той части, которая не получила бы выгоды от этого ${ displaystyle 1-p}$. потом

${ Displaystyle W = (1-p) W + pW.}$

Это выполнение той части, которая выигрывает от улучшения ресурсов, которое ускоряется в несколько раз. ${ displaystyle s}$ после улучшения ресурсов. Следовательно, рабочая нагрузка на выполнение той части, которая не получает от этого выгоды, остается прежней. Теоретическая рабочая нагрузка на выполнение ${ Displaystyle W (s)}$ всей задачи после улучшения ресурсов тогда

${ Displaystyle W (s) = (1-p) W + spW.}$

Закон Густафсона дает теоретические ускорение в задержка выполнения всей задачи в установленное время ${ displaystyle T}$, что дает

${ displaystyle S _ { text {latency}} (s) = { frac {TW (s)} {TW}} = { frac {W (s)} {W}} = 1-p + sp.}$

Приложения

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

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

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

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

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

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

Ограничения

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

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

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

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

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

Рекомендации