Густафсонов закон

Густафсонов закон

Густафсонов закон (познат и како Густафсон-Барсисов закон) е закон во компјутерската наука кој вели дека пресметките кои вклучуваат произволно голема збирка од податоци можат ефикасно да се паралелизираат (паралелно извршување). Густафсоновиот закон претставува контраст или целосна спротивност од Амдаловиот закон, според кој со паралелно извршување на фиксна големина од податоци се добива ограничено забрзување. Густафсоновиот закон првпат е опишан од Џон Л. Густафсон и неговиот колега Едвин Х. Барсис:

$S(P)=P-\alpha \cdot (P-1)$

каде P е број на обработувачи, S е забрзувањето, додека $a$ е делот кој не може да се извршува паралелно.

Густафсоновиот закон ги решава недостатоците на Амдаловиот закон, кој не ја искористува целосно компјутерската моќ која станува достапна со зголемувањето на бројот на машини. Густафсоновиот закон смета дека програмерите имаат тенденција кон избирање на големината на проблемите за да одговара на моментално достапната опрема за да се решат проблемите во разумно фиксно време. Како резултат на тоа, ако побрза (повеќе паралелна) опрема стане достапна, поголеми проблеми можат да бидат решени во истото време.

Соодветно на тоа, Густафсон го нарече својот метрички систем размерно забрзување, затоа што во горенаведената формула, S(P) е односот на серискиот и паралелниот дел; првиот дел е размерен со бројот на обработувачи, додека вториот е фиксен или скоро фиксен. Ова е во контраст со Амдаловиот закон, според кој времето на извршување на еден процес има фиксна величина и го споредува со повеќе-процесно паралелно извршување кое се намалува. Поради тоа, Амдаловиот закон се заснова на претпоставката дека проблемот е со фиксна големина; претпоставува дека целосната работа на програмата нема да се промени во однос на машината (бројот на обработувачи). Двата закони претпоставуваат дека делот кој може да се паралелизира е еднакво распределен помеѓу P број на обработувачи.

Резултатот од Густафсоновиот закон беше префрлање целта на истражување на избирање или реформулирање на проблемите така што решавањето на поголем проблем во истото време може да стане возможно. На некој начин, овој закон ја редефинира ефикасноста, поради можноста дека ограничувањата од секвенцијалниот дел од програмата можат да бидат решени со зголемување на целосната моќност.

Изведување на Густафсоновиот закон

Времето на извршување на програма користејќи паралелизација е разложено како:

$(a+b)$

каде $a$ е сериското време и $b$ е паралелното време на некој од P обработувачите. 

Клучната претпоставка на Густафсон и Барсис е дека целокупната работа која треба да се изврши паралелно варира линеарно со бројот на обработувачи кои се користат. Следува практичната импликација дека еден процесор е повеќе спремен од една задача која треба да се изрши паралелно со (вообичаено исти) други задачи. Ова имплицира дека , паралелното време според бројот на процеси, треба да биде фиксно бидејќи P може да варира. Соодветното време за серискиот дел е:

$a+P\cdot b.$

Како резултат на тоа забрзувањето е:

$(a+P\cdot b)/(a+b).$

Дефинирање

$\alpha =a/(a+b)$

за серискиот дел од времето на паралелно изршување имаме:

$S(P)=\alpha +P\cdot (1-\alpha )=P-\alpha \cdot (P-1).$

Како резултат на тоа, ако $\alpha$ има мала вредност, забрзувањето е приближно P, како посакуваното. Може да се случи и $\alpha$ да се намали со зголемување (заедно со големината на проблемот) на P; Ако тоа важи, тогаш S се приближува на P монотоно заедно со растот на P.

Според ова, Густафсоновиот закон го избавува паралелното извршување одАмдаловиот закон. Се заснова на идејата дека ако големината на проблемот дозволено расте монотонично со P, тогаш серискиот дел од целокупното извршување нема на крајот да надвладее. Ова е овозможено од способноста повеќето од задачите кои се извршуваат поединечно да можат да се комбинираат заедно на еден процесор; Од ова следи дека еден процесор може да обезбеди време на повеќе задачи, додека една задача не треба да се извршува на повеќе обработувачи. Ова е исто така правилото за поврзување на проекти на работната површина, каде може да има повеќе проекти на иста работна површина, но само една работна површина за проект.

Метафора од законот

Амдаловиот закон приближно сугерира:

Да претпоставиме дека една кола се движи помеѓу два градови кои се оддалечени 96 километри и веќе има поминето пола од растојанието за еден час движејќи се со брзина од 48 километри на час. Без разлика колку брзо се движи колата во следната половина, не е возможно да се достигне брзина од 144 км/ч пред да пристигне колата во вториот град. Бидејќи колата има поминето 1 час возејќи , а вкупното растојание кое треба да се помине е 96 километри, со возење бесконечно брзо ќе се достигне брзина од само 96 км/ч.

 Густафсоновиот закон пак го имплицира следното: 

Претпоставете дека колата веќе се движи со брзина помала од 144 км/ч. Доколку има доволно време и растојание кое треба да го помине, средната брзина на колата секогаш може евентуално да достигне брзина од 144 км/ч, без разлика колку брзо или бавно до сега таа се движела. Пример, ако колата поминала еден час со брзина од 48 км/ч, може да се стигне до крајното одредиште со возење два часа со брзина 193 км/ч или еден час со брзина 241 км/ч и така натаму.

Примена

Примена во истражувањето

Законот на Амдал претпоставува дека пресметувачките барања ќе останат исти, со оглед на зголемената моќ на обработката. Со други зборови, една анализа на истите податоци ќе одземе помалку време доколку имаме поголема пресметувачка моќ.

Од друга страна, Густафсон тврди дека поголема пресметувачка моќ ќе доведе до подетално и целосно анализирани податоци; пиксел по пиксел или дел по дел, а не на поголем опсег. Каде што немаше да биде возможно или практично да се симулира влијанието на јадрена детонација на секоја зграда, автомобил и нивната внатрешност (вклучувајќи мебел, структурна сила и друго), бидејќи таквата пресметка ќе одземе повеќе време отколку што беше на располагање за да се дојде до одговорот, зголемувањето на пресметувачката моќ ќе ѓи поттикне истражувачите да додадат повеќе податоци за да се симулираат поцелосно повеќе променливи, давајќи поточен резултат.

Примена во секојдневни компјутерски системи

Амдаловиот закон открива ограничување во, на пример, способноста на повеќе јадра да го намалат времето што е потребно на еден компјутер да го подигне оперативниот систем и да биде подготвен за работа. Да претпоставиме дека процесот на подигање (бутирање) беше главно паралелен, со четирикратно зголемување на пресметувачката моќ на систем на кој му беше потребно една минута за да се вчита може да дојде до намалување на времето до нешто повеќе од петнаесет секунди. Но со поголема и поголема паралелизација евентуално нема да успееме да го забрзаме подигнувањето уштре повеќе, ако било кој дел од бутирачкиот процес е сериски (секвенцијален). 

Густафсоновиот закон тврди дека четирикратно зголемување на компјутерската моќ наместо тоа ќе доведе до зголемување на сличните очекувања за тоа на што е способен системот. Ако времето од една минута е прифатливо за повеќето корисници, тогаш тоа е почетна точка од која треба да се зголемат способностите и функциите на системот. Времето што е потребно за да се подигне оперативниот систем ќе остане исто, односно една минута, но новиот систем ќе вклучува повеќе графички или лесни за употреба опции.

Ограничувања

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

Алгоритми со нелинеарно време на извршување може ќе биде тешко да ѓи искористат придобивките од паралелизмот “изложени” со законот на Густафсон. Снајдер истакува дека алгоритам со O(N³) време на извршување, со двојно зголемување на конкурентноста добива само околу 26% зголемување на големината на проблемот. Според тоа, иако може да биде возможно да се заземе поголемата конкурентност, тоа може да донесе мала предност во однос на оригиналото, помалку конкурентното решение - сепак, во пракса постојат огромни подобрувања.

Хил и Марти исто така нагласуваат дека методите на забрзување на серискиот дел сè уште се потребни, дури и за повеќејадрени машини. Тие истакнуваат дека локално неефикасните методи можат да бидат глобално ефикасни кога ќе го намалат серискиот дел. Понатаму, Ву и Ли ја имаат проучувано импликацијата на енергија и моќност на идните повеќејадрени машини заснована на Амдаловиот закон, што покажува дека асиметричен повеќејадрен процесор може да постигне најдобра можна енергетска ефикасност со активирање на оптимален број јадра, доколку износот на паралелизам е претходно познат пред извршувањето.