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 prou 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:
Utilitzant diferents variables, la Llei de Gustafson pot ser formulada de la següent forma
- 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:
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:
El speedup (acceleració) és, en concordança:
Definint:
com la fracció seqüencial del temps d'execució en paral·lel, obtenim
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:Plantilla:CitacióLa Llei de Gustafson aproximadament enuncia:Plantilla:Citació
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(N3) 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
Vegeu també
- ↑ Plantilla:Ref-llibre
- ↑ 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).
- ↑ Plantilla:Ref-publicació
- ↑ Plantilla:Ref-publicació Plantilla:Webarchive