Llei de Gustafson

En les ciències de la computació, la Llei de Gustafson (també coneguda com a Llei de Gustafson-Barsis)^[1] estableix que qualsevol problema suficientment gran pot ser eficientment paral·lelitzat, donant el speedup teòric en la latència de l'execució d'un programa que pot esperar-se d'un sistema on els seus recursos han millorat. La llei pren el seu nom degut al nord-americà John L. Gustafson i el seu company de treball, Edwin H. Barsis, i va ser presentada a l'article Reevaluating Amdahl's Law, l'any 1988.^[2]

La Llei de Gustafson està molt lligada a la Llei d'Amdahl. Aquests darrer posa límit a la millora que es pot obtenir gràcies a la paral·lelització, donat un conjunt de dades de grandària fixa, oferint així una visió pessimista del processament paral·lel. Per contra la Llei de Gustafson ofereix un nou punt de vista i així una visió positiva dels avantatges del processament paral·lel.

Definició

Gustafson va estimar que el speedup S guanyat utilitzant P processadors (en comptes de solament un) per a una tasca amb una part sequencial α es podria definir de la següent forma:

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

Utilitzant diferents variables, la Llei de Gustafson pot ser formulada de la següent forma

$S_{\text{latència}}(s)=1-p+sp,$

S _latència és l'speedup teòric de l'execució de tota la tasca.
s és l'speedup en latència de tota la part que es beneficia de l'augment de recursos, la part paral·lelitzable.
p és el percentatge de l'execució que es beneficiara de la millora del augment de recursos, és a dir el percentatge de part paral·lela.

La Llei de Gustafson aborda les limitacions de la Llei d'Amdahl, la qual no escala la disponibilitat del poder de còmput a mesura que el nombre de màquines augmenta. La Llei de Gustafson proposa que els programadors tendeixen a establir la grandària dels problemes per utilitzar al màxim el poder de computació a mesura que aquests recursos milloren. Per tant, si es disposa d'un equipament més ràpid, problemes de major magnitud de treball es podran resoldre en el mateix temps.

L'impacte que va causar la llei de Gustafson va provocar un canvi de direcció en els objectius de recerca en l'àmbit de la computació. Aquests havien de reformular els problemes basant-se en la idea d'augmentar els treball a mesura que augmenten els recursos de cómput sense afectar l'interval de temps d'execució. En particular, la llei redefineix l'eficiència com una necessitat per minimitzar la part seqüencial d'un programa, fins i tot si això incrementa la quantitat total de càlculs.

Derivació

El temps d'execució d'un programa en una computadora paral·lela es descompon en:

$(a+b)$

on a és el temps seqüencial i b és el temps paral·lel, en qualsevol dels P processadors.

La suposició clau de Gustafson i Barisis és que la quantitat total de treball a realitzar en paral·lel varia linealment amb el nombre de processadors. Això implica que b (el temps de processament en paral·lel per procés) deu ser fix mentre P varia. El temps corresponent per al processament seqüencial és:

$a+P\cdot b.$

El speedup (acceleració) és, en concordança:

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

Definint:

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

com la fracció seqüencial del temps d'execució en paral·lel, obtenim

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

Per tant, si α és petit, l'acceleració és aproximadament P. Fins i tot es pot donar el cas en què α disminueixi mentre P juntament amb la grandària del problema augmenti; si això es compleix, S s'aproxima a P monòtonament amb el creixement de P.

D'aquesta forma, la Llei de Gustafson aparenta rescatar el processament en paral·lel de la Llei d'Amdahl. La idea es basa en el fet que si la grandària d'un problema pot créixer linealment amb P, la fracció seqüencial de la càrrega de treball no serà suficientment significativa com per suposar una limitació.

Metàfora de la conducció

La Llei d'Amdahl aproximadament suggereix:

«

Suposem que un cotxe està viatjant entre dues ciutats que es troben a 60 kilòmetres de distància i ja ha estat una hora viatjant la meitat del recorregut a 30 kilòmetres per hora. Sense importar com viatgi de ràpid en l'altra meitat és impossible assolir una velocitat mitjana de 90 kilòmetres abans de finalitzar el trajecte. Això és degut al fet que s'ha pres 1 hora i ha de recórrer 60 km. Encara que viatgi infinitament de pressa només arribaria a una velocitat mitjana de 60 kilòmetres per hora.

»

La Llei de Gustafson aproximadament enuncia:

«

Suposem que un cotxe ha estat viatjant un temps per sota els 90 kilòmetres per hora. Tenint la distància i temps suficient per viatjar, el cotxe podria assolir eventualment una mitjana de 90 kilòmetres per hora sense importar quant o a quina velocitat hagi viatjat.

Per exemple, si el cotxe ha estat 1 hora viatjant a 30 kilòmetres per hora, podria assolir la mitjana de 90 kilòmetres per hora conduint a 120 kilòmetres per hora durant 2 hores o a 150 kilòmetres per hora durant 1 hora, etcètera.

»

Aplicacions

Aplicacions en la recerca

La Llei d'Amdahl pressuposa que els requeriments de còmput es mantindran invariables donat l'increment de la capacitat de processament. En altres paraules, l'anàlisi de la mateixa quantitat de dades pren menys temps quan hi ha més poder de còmput.

Gustafson, d'altra banda, argumenta que més poder de còmput causarà que les dades siguin analitzades més profunda i acuradament: píxel per píxel o unitat per unitat, en lloc de ser analitzats a gran escala. On no seria possible o pràctic simular l'impacte d'una detonació nuclear amb totes les construccions, objectes de l'entorn i els seus continguts (incloent-hi mobles, accessoris, etc.) donat que els càlculs per realitzar-ho prendrien més temps del disponible per donar una resposta, l'increment del poder de còmput incita als investigadors a afegir més dades per simular més variables, oferint resultats més precisos.

Aplicacions quotidianes en sistemes computacionals

La Llei d'Amdahl presenta limitacions, per exemple, a l'hora d'utilitzar múltiples nuclis per reduir el temps emprat a encendre l'ordinador i que estigui llest per ser utilitzat. Assumint que el procés d'inicialització és majoritàriament paral·lelitzable, quadruplicant el poder de còmput en un sistema que pren un minut per carregar, podria carregar en tan sols 15 segons. Si alguna part del procés d'inici fos essencialment seqüencial, ni hi hauria èxit en seguir augmentant la paral·lelització, és a dir, no s'aconseguiria fer un inici més ràpid.

La Llei de Gustafson argumenta que un augment per quatre del poder de còmput comportaria, en canvi, un increment similar en les capacitats del sistema. Si un minut de temps d'inici d'un sistema és acceptable per a la majoria dels usuaris, llavors això és un punt d'inici des d'on incrementar les funcionalitats i característiques del sistema. El temps d'inici del sistema operatiu es mantindrà igual (és a dir, un minut) però el nou sistema inclourà millors característiques gràfiques i funcionalitats per a l'usuari.

Limitacions

Alguns problemes no tenen fonamentalment grans quantitats de dades. Per exemple, processar una dada per ciutadà del món creix un baix per cent anualment. El punt principal de la llei de Gustafson és que tals problemes no són els que més poden explotar els avantatges del paral·lelisme.

Els algorismes no lineals poden trobar dificultats en aprofitar el paral·lelisme exposat a la Llei de Gustafson. Snyder ^[3] demostra que si un algorisme O(N³) duplica concurrència de còmput, permetrà només un augment d'un 26% de la quantitat de dades sense que el speedup disminueixi. Per tant, mentre sigui possible ocupar àmpliament la concurrència, fer-ho pot comportar avantatge relativament petit sobre la solució original; no obstant això a la pràctica han ocorregut millores considerables.

Hill and Marty^[4] emfatitza a més que mètodes per accelerar l'execució seqüencial encara són necessaris, fins i tot per a màquines amb nuclis múltiples. Ells assenyalen que mètodes localment ineficients poden ser globalment eficients quan es redueix la fase seqüencial. Addicionalment, Woo and Lee^[5] estudien la implicació d'energia i potència en processadors futurs de múltiples nuclis basats en la llei de Amdahl, mostrant que un processador multinúcli asimètric pot aconseguir la màxima eficiència energètica possible mitjançant l'activació del nombre òptim de nuclis atès que la quantitat de paral·lelisme és coneguda abans de l'execució.

Referències

↑ McCool, Michael D.; Robison, Arch D.; Reinders, James. «2.5 Performance Theory». A: Structured Parallel Programming: Patterns for Efficient Computation. Elsevier, 2012, p. 61–62. ISBN 978-0-12-415993-8.
↑ Reevaluating Amdahl's Law, John L. Gustafson, Communications of the ACM, volum 31 (maig 1988)
↑ Type Architectures, Shared Memory, and The Corrolary of Modest Potential Snyder, Lawrence (juny 1986).
↑ Hill, Mark D.; Marty, Michael R. «Amdahl's Law in the Multicore Era». IEEE Computer, 41, 7, 7-2008, pàg. 33–38. DOI: 10.1109/MC.2008.209. UW CS-TR-2007-1593.
↑ Dong Hyuk Woo; Hsien-Hsin S. Lee «Extending Amdahl's Law for Energy-Efficient Computing in the Many-Core Era». IEEE Computer, 41, 12, 12-2008, pàg. 24–31. Arxivat de l'original el 2012-10-10. DOI: 10.1109/MC.2008.530 [Consulta: 2 maig 2018]. Arxivat 2012-10-10 a Wayback Machine.

Vegeu també

[spp-1] McCool, Michael D.; Robison, Arch D.; Reinders, James. «2.5 Performance Theory». A: Structured Parallel Programming: Patterns for Efficient Computation. Elsevier, 2012, p. 61–62. ISBN 978-0-12-415993-8.

[reevaluating-amdahl-2] Reevaluating Amdahl's Law, John L. Gustafson, Communications of the ACM, volum 31 (maig 1988)

[Snyder1986-3] Type Architectures, Shared Memory, and The Corrolary of Modest Potential Snyder, Lawrence (juny 1986).

[Hill&Marty2008-4] Hill, Mark D.; Marty, Michael R. «Amdahl's Law in the Multicore Era». IEEE Computer, 41, 7, 7-2008, pàg. 33–38. DOI: 10.1109/MC.2008.209. UW CS-TR-2007-1593.

[Woo&Lee2008-5] Dong Hyuk Woo; Hsien-Hsin S. Lee «Extending Amdahl's Law for Energy-Efficient Computing in the Many-Core Era». IEEE Computer, 41, 12, 12-2008, pàg. 24–31. Arxivat de l'original el 2012-10-10. DOI: 10.1109/MC.2008.530 [Consulta: 2 maig 2018]. Arxivat 2012-10-10 a Wayback Machine.

[1]

[2]

[3]

[4]

[5]