Computació paral·lela

Supercomputadora de computació paral·lela Blue Gene/P d'IBM

La computació paral·lela és una forma de computació en la qual molts càlculs es fan simultàniament,^[1] operant sobre el principi que sovint es poden dividir problemes grans en altres de més petits, els quals llavors es poden solucionar concurrentment ("en paral·lel"). Hi ha unes quantes formes diferents de computació paral·lela: a nivell de bit, nivell d'instrucció, dades, i paral·lelisme de tasca. El paral·lelisme s'ha emprat durant molts anys, principalment en la computació d'alt rendiment, però l'interès en això ha augmentat últimament a causa de les restriccions físiques que eviten l'escalat de freqüència.^[2] Com què el consum de potència (i consegüentment la generació de calentor) per ordinadors s'ha convertit en una preocupació durant els darrers anys,^[3] la computació paral·lela s'ha convertit en el paradigma dominant en l'arquitectura informàtica, principalment en forma de processadors multi nucli.^[4]

Els ordinadors paral·lels es poden classificar aproximadament segons el nivell en el qual el maquinari dona suport al paral·lelisme -amb ordinadors multi-nucli i els ordinadors multiprocessador que tenen elements de processament múltiples dins d'una única màquina, mentre que els clústers, MPPs, i els grids utilitzen ordinadors múltiples per fer feina en la mateixa tasca. Les arquitectures informàtiques paral·leles especialitzades s'utilitzen a vegades al costat de processadors tradicionals, per accelerar tasques específiques.

Els programes informàtics paral·lels són més difícils d'escriure que els seqüencials,^[5] perquè la concurrència introdueix unes quantes classes noves d'errors de programari potencials, dels quals les condicions de carrera són les més comunes. La comunicació i sincronització entre les subtasques diferents són típicament un dels obstacles més grans per aconseguir el bon rendiment d'un programa paral·lel. El guany de velocitat d'un programa com a resultat de la paral·lelització és governat per la llei d'Amdahl.

Antecedents

Tradicionalment, el programari informàtic s'ha escrit per al càlcul en sèrie. Per resoldre un problema, es construeix un algorisme i s'implementa com a flux en sèrie d'instruccions. Aquestes instruccions s'executen en una unitat central en un ordinador. Només s'executa una instrucció en cada moment, alhora després que la instrucció s'acaba d'executar, la pròxima és executada.^[6]

La computació paral·lela, d'altra banda, utilitza elements de processament múltiples simultàniament per resoldre un problema. Això s'acompleix dividint el problema en parts independents de manera que cada element que processa pugui executar la seva part de l'algorisme simultàniament amb els altres. Els elements de processament poden ser diversos i incloure recursos com un ordinador amb processadors múltiples, uns quants ordinadors connectats, maquinari especialitzat, o qualsevol combinació dels darrers.^[6]

L'escalament de freqüència era la raó dominant per a millores en el rendiment dels computadors de mitjan 1980 fins a 2004. El temps d'execució d'un programa és igual al nombre d'instruccions multiplicades pel temps mitjà per instrucció. Mantenint la resta constant, augmentant la freqüència de rellotges disminueix el temps mitjà del qual considera que executa una instrucció. Un augment en freqüència disminueix així temps d'execució per a tots el programes limitats per la CPU.^[7]

Tanmateix, el consum de potència d'un xip és donat per l'equació P = C × V² × F, on P és potència, C és la capacitància que es canvia per cicle de rellotges (proporcional al nombre de transistors les entrades del qual canvien), V és voltatge, i F és la freqüència de processadors (cicles per segón).^[8] Els increments de la freqüència incrementen la quantitat de potència emprat en un processador. El consum de potència creixent de processadors va conduir a la cancel·lació en maig de 2004 per part d'Intel dels seus processadors de Tejas i Jayhawk, que se cita generalment com el final de l'escalament de freqüència com el paradigma d'arquitectura informàtic dominant.^[9]

La llei de Moore és l'observació empírica que la densitat de transistors en un microprocessador es duplica cada 18 a 24 mesos.^[10] Malgrat assumptes de consum de potència, i nombroses prediccions del seu final, la llei de Moore és encara vigent. Amb el final de l'escalament de freqüència, aquests transistors addicionals (que ja no s'utilitzen per a l'escalament de freqüència) es poden utilitzar per afegir maquinari extra per a la computació paral·lela.

Llei d'Amdahl i Llei de Gustafson

Una representació gràfica de la llei d'Amdahl. L'augment de velocitat d'execució d'un programa per paral·lelització està limitat per la mesura en què el programa es pot paral·lelitzar. Per exemple, si el 90% del programa es pot paral·lelitzar, el màxim augment teòric de velocitat fent servir paral·lelisme seria 10x, no importa que la quantitat de processadors que es facin servir creixi molt.

Òptimament, l'augment de velocitat per paral·lelitzament hauria de ser lineal -duplicant el nombre d'elements de processament hauria de dividir el temps d'execució en dos, i duplicant-lo una segona vegada hauria de reduir una altra vegada a la meitat el temps d'execució. Tanmateix, molt pocs algorismes paral·lels aconsegueixen alçar òptimament la velocitat. La majoria d'ells tenen un augment de velocitat proper a lineal per a nombres petits d'elements de processament, que es va allisant fins a un valor constant per a nombres grans d'elements de processament.

El potencial increment de la velocitat d'un algorisme en una plataforma de computació paral·lela és donat per la llei d'Amdahl, originalment formulada per Gene Amdahl durant els anys 1960.^[11] Aquesta manifesta que una porció petita del programa que no es pot paralitzar limitarà l'augment de velocitat mitjà que permet la paral·lelització. Qualsevol problema matemàtic o d'enginyeria gran constarà típicament d'unes quantes parts paral·lelizables i unes quantes no-paral·lelizables (seqüencials). Aquesta relació és donada per l'equació:

${\displaystyle S={\frac {1}{1-P}}}$

on S és el guany de la velocitat del programa (com a factor del seu temps d'execució seqüencial original), i P és la fracció que és parallelizable. Si la porció seqüencial d'un programa són un 10% del temps d'execució, no podem aconseguir més que un 10× de guany, sense tenir en compte quants processadors són afegits. Això posa un límit superior sobre la utilitat d'afegir més unitats d'execució paral·leles. "Quan una tasca no es pot dividir a causa de restriccions seqüencials, l'aplicació de més esforç no té cap efecte sobre el pla. La gestació d'un nen porta nou mesos, no importa quantes dones siguin assignades."^[12]

La llei de Gustafson és una altra llei en l'enginyeria informàtica, estretament relacionada a la llei d'Amdahl. Es pot formular com:

Suposi que una tasca té dues parts independents, A i B. B ocupa aproximadament un 25% del temps del càlcul sencer. Amb esforç, un programador pot ser capaç de fer cinc vegades més ràpida aquesta part, però aquest només redueix una mica el temps per al càlcul sencer. Per contrast, un pot necessitar realitzar menys feina per fer part A dues vegades més ràpid. Això farà molt més ràpid el càlcul que optimitzant la part B, tot i que B aconseguia major alçada de velocitat (5× contra 2×).

${\displaystyle S(P)=P-\alpha (P-1)\,}$

a on P és el nombre de processadors, S és l'augment de velocitat, i la part no-paral·lelitzable del procés.^[13] La llei d'Amdahl suposa un problema de mida fixa i que la mida de la secció seqüencial és independent del nombre de processadors, mentre que la llei de Gustafson no fa aquestes suposicions.

Dependències

Entendre dependències de dades és fonamental per implementar algoritmes paral·lels. Cap programa no es pot executar més de pressa que la cadena més llarga de càlculs dependents (conegut com el camí crític), ja que els càlculs que depenen de previs càlculs en la cadena s'han d'executar en ordre. Tanmateix, la majoria dels algoritmes no consisteixen en només una cadena llarga de càlculs dependents; hi ha normalment oportunitats d'executar càlculs independents en paral·lel.

Siguin P_i i P_j dos fragments de programa. Les condicions de Bernstein^[14] descriuen quan és que els dos són independents i es poden executar en paral·lel. Per a P_i, siguin I_i totes les variables d'entrada i O_i les variables de sortida, i de la mateixa manera per a P_j. P _i i P_j són independents si satisfan

• ${\displaystyle I_{j}\cap O_{i}=\varnothing ,\,}$
• ${\displaystyle I_{i}\cap O_{j}=\varnothing ,\,}$
• ${\displaystyle O_{i}\cap O_{j}=\varnothing .\,}$

La violació de la primera condició presenta una dependència de flux, corresponent a la primera declaració que produeix un resultat utilitzat per la segona declaració. La segona condició representa una antidependència, quan sobreescriu la primera declaració una variable necessitada per la segona expressió. La tercera i darrera condició representa una dependència de sortida: Quan dues instruccions escriuen a la mateixa localització, el resultat final ha de venir de la darrera instrucció executada.^[15]

Consideri el seguir funcions, que demostren unes quantes classes de dependències:

1: funcio Dep(a, b)
2: c := a·b
3: d := 2·c
4: fi funcio

L'operació 3 no pot ser executada abans de l'operació 2 (o inclús en paral·lel), perquè l'operació 3 empra el resultat de l'operació 2. Viola la condició 1, introduint així una dependència de flux.

En aquest exemple, no hi ha cap dependència entre les instruccions, així totes poden ser executades en paral·lel.

Les condicions de Bernstein no deixen que la memòria sigui compartida entre processos diferents. Per a allò, algun mitjà per forçar una ordenació entre accessos és necessari, com semàfors, barreres o algun altre mètode de sincronització.

Condicions de carrera, exclusió mutua, sincronització i parallel slowdown

Les subtasques en un programa paral·lel sovint s'anomenen fils. Algunes arquitectures informàtiques paral·leles utilitzen versions més petites, lleugeres de fils coneguts com a fibres, mentre que altres utilitzen versions més grans conegudes com a processos. Tanmateix, "fils" és generalment acceptat com a terme genèric per|per a subtasques. Els fils necessitaran sovint actualitzar alguna variable que s'hi comparteix. Les instruccions entre els dos programes es poden intercalar en qualsevol ordre. Per exemple, consideri el seguir programa:

Fil A	Fil B
1A: Llegir variable V	1B: Llegir variable V
2A: Afegir 1 a la variable V	2B: Afegir 1 a la variable V
3A Escriure de nou a la variable V	3B: Escriure de nou a la variable V

Si la instrucció 1B s'executa entre 1 A i 3 A, o si instrucció 1A és executada entre 1B i 3B, el programa produirà dades incorrectes. Això es coneix com a condició de carrera. El programador ha d'utilitzar un pany per proporcionar exclusió mútua. Un pany és una estructura de llengua de programació que deixa un fil prendre control d'una variable i impedieix a uns altres fils llegir-la o escriure-la, fins que aquella variable s'obri. El fil que posi el pany és lliure d'executar la seva secció crítica (la secció d'un programa que exigeix accés exclusiu a alguna variable), i obrir les dades quan s'acaba.Per això, per garantir l'execució correcta del programa, el programa citat es pot reescriure utilitzar panys:

Thread A	Thread B
1A: Lock variable V	1B: Lock variable V
2A: Llegir variable V	2B: Llegir variable V
3A: Afegir 1 a la variable V	3B: Afegir 1 a la variable V
4A Escriure de nou a la variable V	4B: Escriure de nou a la variable V
5A: Unlock variable V	5B: Unlock variable V

Un fil tancarà reeixidament la variable V, mentre l'altre fil estarà tancat -incapaç de continuar fins que V s'obri una altra vegada. Això garanteix execució correcta del programa. Els panys, mentre necessari d'assegurar execució de programa correcta, poden alentir en gran manera un programa.

Tancar múltiples variables que utilitzen panys no atòmics introdueix la possibilitat d'interbloqueig de programa. Un pany atòmic tanca variables múltiples alhora. Si no els pot tancar tots, no tanca cap d'ells. Si dos fils cadascun necessiten tancar les dues mateixes variables que utilitzen panys no atòmics, és possible que un fil tancarà un d'ells i el segon fil tancarà la segona variable. En tal cas, cap fil no pot completar, i resultats d'interbloqueig.

Molts programes paral·lels exigeixen que les seves subtasques actuïn en sincronia. Això exigeix l'ús d'una barrera. Les barreres s'implementen típicament utilitzant un pany de programari. Una classe d'algoritmes, coneguts com sense panys i sense esperes, conjuntament evita l'ús de panys i barreres. Tanmateix, aquesta enfocament és generalment difícil d'implementar i requereix estructures de dades dissenyades correctament.

No tota la paral·lelització resulta en un augment de la velocitat. Generalment, a mesura que una tasca es divideix en més i més fils, aquells fils gasten una porció sempre creixent del seu temps en comunicar-se l'un amb l'altre. Finalment, la despesa des de la comunicació domina el temps passat resolent el problema, i més paral·lelització (és a dir, partint la càrrega de treball sobre fins i tot més fils) augmenta més que no pas disminueix la quantitat de temps necessària per acabar. Això es coneix com a alentiment paral·lel.

Paral·lelisme fi, Paral·lelisme gruixat, i embarrassing parallelism

Les aplicacions es classifiquen sovint segons cada quant necessiten les seves subtasques sincronitzar-se o es comuniquen l'una amb l'altra. Una aplicació exhibeix paral·lelisme fi si les seves subtasques han de comunicar gaires vegades per segon; exhibeix paral·lelisme gruixat si no comuniquen gaires vegades per segon, i és embarrassing parallel si ells rarament o mai han de comunicar. Les aplicacions embarrassing parallelism es consideren les més fàcils per paral·lelitzar.

Models de consistència

Leslie Lamport va ser el primer a definir el concepte de consistència sequencial.

Els llenguatges de programació paral·lels i els ordinadors paral·lels han de tenir un model de consistència (també conegut com un model de memòria). El model de consistència defineix regles per a com ocorren les operacions en memòria informàtica i com es produeixen resultats.

Un dels primers models de consistència era el model de consistència seqüencial de Leslie Lamport. La consistència seqüencial és la propietat d'un programa paral·lel que la seva execució paral·lela produeix els mateixos resultats que un programa seqüencial. Específicament, un programa és seqüencialment coherent si "... els resultats de qualsevol execució és igual com si les operacions de tots els processadors s'executessin en algun ordre seqüencial, i les operacions de cada processador individual apareguin en aquesta seqüència en l'ordre especificat pel seu programa"^[16]

La memòria transaccional de software és un tipus comú de model de consistència. Aquesta pren en préstec a la teoria de base de dades el concepte de transaccions atòmiques i els aplica a accessos de memòria.

Matemàticament, aquests models es poden representar d'unes quantes maneres. Les Xarxes de Petri, que eren introduïdes a la tesi doctoral de Carl Adam Petri de 1962, era un primer intent de codificar les regles de models de consistència. La teoria de flux de dades construïda més tard damunt aquests, i les arquitectures de flux de dades es creaven per implementar físicament les idees de teoria de flux de dades. Començant als últims anys 1970,càlculs de procés com elcàlcul de sistemes comunicants i comunicació de processos seqüencials es desenvolupaven per permetre raonament algebraic sobre sistemes compostos de components que interaccionen. Més addicions recents a la família de càlcul de procés, com el càlcul pi, han afegit la capacitat per raonar sobre topologies dinàmiques. Les lògiques com el TLA+ de Lamport, i models matemàtics com les traces i diagrames d'esdeveniment d'actor, també s'han desenvolupat per descriure el comportament de sistemes concurrents.

Taxonomia de Flynn

Michael J. Flynn creava un dels primers sistemes de classificació per a ordinadors paral·lels (i seqüencial) i programes, ara coneguts com la taxonomia de Flynn. Flynn classificava programes i ordinadors per si estaven operant utilitzant un conjunt únic o conjunts múltiples d'instruccions, si aquelles instruccions estaven utilitzant un conjunt de dades únic o múltiple o no.

La classificació instrucció única, dada única (en anglès, single-instruction-single-data,SISD) és equivalent a un programa totalment seqüencial. La classificació instrucció única, dades múltiples (en anglès single-instruction-multiple-data, SIMD) és anàlega a fer la mateixa operació repetidament per sobre d'un conjunt de dades gran. Això es fa comunament en aplicacions de processament de senyal. Instrucció única, dades múltiples (MISD) és una classificació rarament utilitzada. Mentre que les arquitectures informàtiques per tractar amb això s'ideaven (com systolic arrays), es materialitzaven poques aplicacions que encaixen amb aquesta classe. Els programes múltiple-instrucció-múltiple-dades (MIMD) són de bon tros el tipus més comú de programes paral·lels.

Segons David Patterson i John L. Hennessy, "Algunes màquines són híbrids d'aquestes categories, naturalment, però aquest model clàssic ha sobreviscut perquè és simple, fàcil entendre, i dona una bona primera aproximació. És també -potser a causa de la seva fàcil comprensió- l'esquema més emprat.^[17]

Tipus de paral·lelismes

Paral·lelismes a nivell de bit

Des de l'adveniment dels circuits integrats a molt gran escala (VLSI) la tecnologia de fabricació de xips informàtics durant els anys 1970 fins a aproximadament 1986, alçar velocitat en l'arquitectura d'un ordinador era aconseguida doblant-se la longitud de les paraules -la quantitat d'informació que un processador pot executar per cicle.^[18] Augmentant la mida de paraula redueix el nombre d'instruccions que el processador ha d'executar per fer una operació en variables les mides del qual són més grans que la llargada de la paraula. Per exemple, on un processador de 8 bits ha d'afegir dos enters de 16 bits, el processador ha d'afegir primer els 8 bits menys significatius de cada enter que utilitza la instrucció d'addició estàndard, llavors afegir el 8 bits més significatius que utilitzen una instrucció d'addició amb carry i el bit de carry des de l'addició dels bits baixos; així, un processador de 8 bits exigeix que dues instruccions completin una única operació, on un processador de 16 bits podria completar l'operació amb una única instrucció.

Històricament, els microprocessadors de 4 bits es reemplaçaven pels de 8 bits, llavors 16 bits, llavors microprocessadors de 32 bits. Aquesta tendència generalment arribà al final amb la introducció de processadors de 32 bits, que ha estat un estàndard en computació de propòsit general durant dues dècades. No fins últimament (circa. 2003-2004), amb l'adveniment d'arquitectures de x86-64, els processadors de 64 bits s'han fet comuns.

Paral·lelisme a nivell d'instrucció

Un pipeline canònic de cinc etapes a una màquina RISC (IF = Fetch d'Instrucció, ID = Decodificació d'Instrucció, EX = Execució, MEM = Accés a memòria, WB = Torna a escriure al registre)

Un programa informàtic és, en essència, un corrent d'instruccions executades per un processador. Aquestes instruccions es poden reordenar i combinar-se a grups que s'executen més tard en paral·lel sense canviar el resultat del programa. Això es coneix com a paral·lelisme de nivell d'instrucció. Els avenços en el paral·lelisme a nivell d'instrucció dominaven arquitectura informàtica del mig-1980 fins al mig-1990.^[19]

Els processadors moderns tenen pipelines (canonades) d'instrucció de múltiples etapes. Cada etapa al pipeline correspon a una acció diferent que el processador realitza en aquella instrucció en aquella etapa; un processador amb un pipeline de n etapes pot tenir fins a n instruccions diferents en etapes diferents d'acabament. El canònic exemple d'un processador de pipelined és un processador de RISC, amb cinc etapes: fetch d'instrucció, descodificar, executar, access a memòria, i escritura de memòria. El Pentium 4 processador tenia una canonada de 35 etapes.^[20]

Un processador superescalar amb pipelines de cinc etapes,capaç de tractar dues instruccions per cicle. Pot tenir dues instruccions en cada etapa del pipeline, per a un total de fins a 10 instruccions (mostrat en verd) essent executades simultàniament.

A més a més a paral·lelisme de nivell d'instrucció del pipelining, alguns processadors poden tractar més d'una instrucció alhora. Aquests se saben com processadors superescalars. Les instruccions es poden agrupar només si no hi ha dependència de dades entre elles. Scoreboarding i l'algorisme de Tomasulo (que és similar a scoreboarding però fa ús de rebateig de registre) són dues de les tècniques més comunes per a l'execució fora d'ordre que implementa i paral·lelisme a nivell d'instrucció.

Paral·lelisme de dades

El paral·lelisme de dades és paral·lelisme inherent a bucles de programa, que se centra a distribuir les dades a través de nusos de computació diferents per ser processats en paral·lel. "Paral·lelitzar bucles sovint porta seqüències d'operació similars o funcions(no necessàriament idèntiques) que s'executen en elements d'una estructura de dades gran."^[21] Moltes aplicacions científiques mostren paral·lelisme de dades.

Una dependència portada per bucle és la dependència d'una iteració de bucle a la sortida d'una o més iteracions prèvies. Les dependències portades per bucle eviten la paral·lelització de bucles. Per exemple, consideri el seguir pseudocodi que computa els primers pocs nombres de Fibonacci:

1: PREV2 := 0
2: PREV1 := 1
3: CUR := 1
4: do:
5: CUR := PREV1 + PREV2
6: PREV2 := PREV1
7: PREV1 := CUR
8: while (CUR < 10)

Aquest bucle no es pot paral·lelitzar perquè CUR depèn d'ell mateix (PREV1) i PREV2, els quals es computen en cada iteració de bucle. Ja que cada iteració depèn del resultat de l'anterior, no es poden realitzar en paral·lel. A mesura que la mida d'un problema augmenta, la quantitat de paral·lelisme de dades disponible normalment fa el mateix.^[22]

Paral·lelisme de tasca

El paral·lelisme de tasca és la característica d'un programa paral·lel en què “es poden realitzar càlculs totalment diferents damunt el mateix o diferents conjunts de dades ".^[21] Això contrasta amb paral·lelisme de dades, on el mateix càlcul es realitza en els mateixos o diferents conjunts de dades. El paral·lelisme de tasca no redueix normalment amb la mida d'un problema.^[22]

Hardware

Memòria i comunicació

La memòria principal en un ordinador paral·lel és o bé memòria compartida (compartida entre tots els elements de processament en un espai d'adreça únic), o bé memòria distribuïda (en el qual cada element de processament té el seu propi espai d'adreçament local).^[23] Memòria distribuïda es refereix al fet que la memòria es distribueixi lògicament, però sovint impliqui que es distribueixi físicament també. La memòria compartida distribuïda és una combinació dels dos enfocaments, on l'element de processament té la seva pròpia memòria local i accés a la memòria en processadors no locals. Els accessos a memòria local són típicament més ràpids que els accessos a memòria no local.

Una visió lògica d'una arquitectura d'accés a memòria no-uniforme (Non-Uniform Memory Acces,NUMA). Els processadors a un directori poden accedir a la memòria d'aquell directori amb menys latència que amb la que poden accedir a l'altre directori de memòria.

Les arquitectures informàtiques en les quals es pot accedir a cada element de memòria principal amb temps d'espera igual i amplada de banda es coneixen com a sistemes d'Accés de Memòria Uniforme (en Anglès Uniform Memory Access,UMA). Típicament, allò pot ser aconseguit només per un sistema de memòria compartit, en el qual la memòria no es distribueix físicament. Un sistema que no té aquesta propietat es coneix com a Accés de Memòria No Uniforme (NUMA) arquitectura. Els sistemes de memòria distribuïts tenen accés de memòria no uniforme.

Els sistemes informàtics fan ús de memòries cau- memòries petites d'amagatalls, ràpides situades a la vora del processador que emmagatzemen còpies provisionals de valors de memòria (a prop en tant el sentit físic i lògic). Els sistemes informàtics paral·lels tenen dificultats amb les memòries cau, que poden emmagatzemar el mateix valor a més d'una localització, amb la possibilitat d'execució de programa incorrecta. Aquests ordinadors exigeixen un sistema de coherència cau, que enregistra de valors de cau i estratègicament els depura, així assegurant execució de programa correcta. Bus sniffing és un dels mètodes més comuns per enregistrar a quins valors s'està accedint (i així s'hauria de depurar). Dissenyant sistemes de coherència cau d'alt rendiment i grans és un problema molt difícil en l'arquitectura informàtica. Com a resultat, les arquitectures informàtiques de memòria compartida no escalen així com ho fan els sistemes de memòria distribuïda.^[23]

Les comunicacions processador-processador i processador-memòria es poden implementar en hardware d'unes quantes maneres, incloent-hi mitjançant memòria compartida (multiporta o multiplexat), un commutador de barres creuades, un bus compartit o una xarxa interconectada d'una miríada de topologies incloent-hi estrella, anell, arbre, hypercube, hypercube gras (un hypercube amb més d'un processador en un nus), o xarxa n-dimensional.

Els ordinadors paral·lels basats damunt xarxes interconnectades necessiten tenir alguna classe d'encaminament per permetre el pas de missatges entre nusos que no estan connectats directament. És probable que el medi utilitzat per comunicació entre els processadors sigui jeràrquic en màquines de multiprocessadors grans.

Classes de computadors paral·lels

Els ordinadors paral·lels es poden classificar aproximadament segons el nivell en el qual el maquinari dona suport a paral·lelisme. Aquesta classificació és amplament anàloga a la distància entre nusos de computació bàsics. Aquests no són mútuament exclusius; per exemple, els clusters de multiprocessadors simètrics són relativament comuns.

Computació multinucli

Un processador multi-nucli és un processador que inclou unitats d'execució múltiples ("nuclis"). Aquests processadors difereixen de processadors superescalars, que poden tractar instruccions múltiples per cicle des d'un corrent d'instrucció (fil); per contrast, un processador multi nucli pot tractar múltiples instruccions per cicle des de múltiples corrents d'instrucció. Cada nucli en un processador multi nucli pot potencialment també ser superescalar -és a dir, en tots els cicles, cada nucli pot tractar múltiples instruccions des d'un corrent d'instrucció.

El multifil simultani (del qual l'HyperThreading d'Intel és el més conegut) era una primera forma de pseudomultinucleisme. Un processador capaç de multifil simultani té només una unitat d'execució ("nucli"), però quan aquella unitat d'execució està desocupada (com durant un “caché miss”), utilitza aquella unitat d'execució per processar un segon fil. Les famílies de processadors Intel Core i Intel Core 2 son les primeres arquitectures multi nucli veritables d'Intel. El microprocessador Cell d'IBM, dissenyat per a l'ús en la Sony PlayStation 3, és un altre processador multi nucli prominent.

Multiprocessament simètric

Un multiprocessador simètric (SMP) és un sistema informàtic amb múltiples processadors idèntics que comparteixen memòria i es connecten mitjançant un bus.^[17] La disputa de bus evita l'escalament de les arquitectures de bus. Com a resultat, els SMPs generalment no comprenen més de 32 processors.^[24] "A causa de la mida petita dels processadors i la reducció significativa en els requisits amplada de banda de bus aconseguida per caus grans, tals multiprocessadors simètrics són extremadament rendibles, a condició que una quantitat suficient d'amplada de banda de memòria existeixi."^[25]

Computació distribuïda

Un ordinador distribuït (també anomenat un multiprocessador de memòria distribuïda) és un sistema informàtic de memòria distribuïda en el qual els elements de processament estan connectats per una xarxa. Els ordinadors distribuïts són altament escalables.

Computació de cluster

A cluster Beowulf

Un cluster és un grup d'ordinadors feblement ajuntats que funcionen junts de prop, de manera que en alguns aspectes es puguin considerar com un únic computador.^[26] els clusters són compostos de múltiples màquines independents connectades per una xarxa. Mentre que les màquines en un cluster no han de ser simètriques, l'equilibratge de càrrega és més difícil si no hi estan. El tipus més comú de cluster és el cluster Beowulf, que és un cluster implementat en múltiples ordinadors d'aparador comercials idèntics connectats amb una àrea local d'Ethernet TCP/IP.^[27] La tecnologia Beowulf era originalment desenvolupada per Thomas Sterling i Donald Becker. La vasta majoria dels superordinadors de TOP500 són clusters.^[28]

Processament paral·lel massiu

Un processador massivament paral·lel (MPP) és un únic ordinador amb molts processadors interconnectats. Els MPPs tenen moltes de les mateixes característiques que els clusters, però els MPPs han especialitzat interconnectar xarxes (mentre que els clusters utilitzen hardware de mercaderia per la interconnexió). Els MPPs també tendeixen a ser més grans que elsclusters, típicament tenint "molt més" que 100 processors.^[29] En un MPP, "cada CPU conté la seva pròpia memòria i còpia del sistema operatiu i aplicació. Cada subsistema es comunica amb els altres mitjançant una interconnexió d'alta velocitat."^[30]

Un armari del Blue Gene, qualificat com el supercomputador més ràpid del món segons al rànquing TOP500 d'11/2008. Blue Gene és un processador paral·lel massiu.

Blue Gene, la quarta supercomputadora més rápida en el món segons al ranking TOP500 de 2008, és un MMP.

Computació de reixat

La computació de reixat (en anglès, Grid computing) és la forma més distribuïda de computació paral·lela. Fa ús d'ordinadors que es comuniquen sobre la Internet per treballar en un problema donat. A causa de l'estret amplada de banda i temps d'espera extremadament alts disponible en la Internet, la computació de reixat típicament tracta només amb problemes embarrassingly parallel. Moltes aplicacions de computació de reixat s'han creat, de les quals SETI@home i Folding@Home en són els exemples més coneguts.^[31]

La majoria de les aplicacions de computació de reixat utilitzen middleware, software que està entre el sistema operatiu i l'aplicació per gestionar els recursos de la xarxa i estandarditzar la interfici de software. El middleware de computació de reixat més comú és la Infraestructura Oberta Berkeley per a la Computació de Xarxa (BOINC). Sovint, el software de computació de reixat fa ús de “cicles sobrers", realitzant càlculs de vegades quan un ordinador està ociós.

Computadors paral·lels especialitzats

Dins de computació paral·lela, hi ha dispositius paral·lels especialitzats que romanen a les àrees d'interés. Mentre no són específics d'un domini, tendeixen a ser aplicables a només unes quantes classes de problemes paral·lels.

Computació reconfigurable amb FPGAs

La computació reconfigurable és l'ús d'una FPGA com a co-processador per un computador de propòsit general. Un FPGA és, en essència, un xip informàtic que es pot reconnectar per a una tasca donada.

Els FPGAs poden ser programats amb llengües de descripció de hardware com VHDL o Verilog. Tanmateix, la programació en aquestes llengües pot ser tediosa. Uns quants venedors han creat llenguatges C a HDL que intenten emular la sintaxi i/o semàntica del llenguatge de programació C, amb què la majoria dels programadors estan familiaritzats. Els C a HDL més coneguts són Mitrion-C, Impuls C, DIME-C, i Handel-C. Els subconjunts específics de SystemC basat en C++ també es poden utilitzar per a aquest propòsit.

La decisió d'AMD d'obrir la seva tecnologia de HyperTransport a venedors de tercers s'ha convertit en la tecnologia que permet la computació d'alt rendiment reconfigurable.^[32] Segons Michael R. D'Amour, Director General de Corporació Informàtica de DRC "quan vàrem entrar per primera vegada a AMD, ens anomenaven els lladres de sòcols.' Ara ens anomenen companys."^[32]

Computació de propòsit general en unitats de processament de gràfics (GPGPU)

La computació de propòsit general en unitats de processament de gràfics (GPGPU) és una tendència bastant recent en la investigació d'enginyeria informàtica. Les GPUs són coprocessadors que s'han optimitzat fortament per al processament de gràfics per ordinador.^[33] Els gràfics per ordinador és un camp dominat per operacions paral·leles de dades – en particular d'operacions amb matrius d'àlgebra lineal.

Al començament, els programes de GPGPU utilitzaven les APIs de gràfics normals per als programes que s'executaven. Tanmateix, recentment uns quants llenguatges de programació nous i plataformes s'han construït per fer càlculs de propòsit general en GPUs tant amb Nvidia com amb AMD traguent entorns de programació amb CUDA i CTM respectivament. Uns altres llenguatges de programació de GPU són BrookGPU, PeakStream, i RapidMind. Nvidia també ha tret productes específics per al càlcul en la seva sèrie Tesla.

Circuits integrats d'aplicació específica

Article principal: ASIC

Uns quants circuit integrat específic d'aplicació (ASIC) aproximacions han estat ideats per tractar amb aplicacions paral·leles.^[34][35][36]

Com que un ASIC és (per definició) específic a una aplicació donada, es pot plenament optimitzar per a aquella aplicació. Com a resultat, per a una aplicació donada, un ASIC tendeix a superar en rendiment a un ordinador d'ús general. Tanmateix, són creats ASICs per litografia de Raig X. Aquest procés exigeix una màscara, que pot ser extremadament cara. Una única màscara pot costar sobre un milió als EUA dollars.^[37] (el més petit els transistors requirits per al xip, el més cara la màscara serà.) Mentrestant, els augments del rendiment en la computació de propòsit general gradualment (com descrit per Llei de Moore) tendeix a destruir aquests guanys en només una o dues generacions de xip.^[32] Cost inicial Alt, i la tendència de ser avançat per la computació d'ús general governada per la llei de Moore, ha deixat infactibles els ASICs per a la majoria de les aplicacions de computació paral·leles. Tanmateix, se n'han construït algunses. Un exemple és la màquina de peta-flop RIKEN MDGRAPE-3 que utilitza ASICs personalitzats per a la simulació de dinàmica molecular.

Processadors de vector

El Cray-1 és el processador de vectors més famós

Un processador vectorial és un CPU o sistema informàtic que pot executar la mateixa instrucció en conjunts grans de dades. "Els processadors vectorials tenen operacions d'alt nivell que funcionen enarrays lineals de nombres o vectors. Una operació vectorial d'exemple és A = B × C, on l'A, B, i C són cada un vectors de 64 elements de 64 bits en coma flotant cadascun."^[38] Estan estretament relacionats amb la classificació de Flynn SIMD.^[38]

Els ordinadors Cray es tornaren famosos pels seus ordinadors de processament vectorial els anys 1970 i el 1980. Tanmateix, els processadors de vectors -ambdós com les CPUs i els ordinadors complets- han desaparegut generalment. Els jocs d'instruccions dels processadors moderns inclouen algunes instruccions de processament vectorials, com amb AltiVec i Streaming SIMD Extensions (SSE).

Software

Llenguatges de programació paral·lela

S'han creat llenguatges de programació concurrents, biblioteques, APIs, i models de programació paral·lels per programar ordinadors paral·lels. Aquests es poden generalment dividir en classes basades en les suposicions que fan sobre l'arquitectura de memòria subjacent – memòria compartida, memòria distribuïda, o memòria distribuïda compartida. Els llenguatges de programació de memòria compartida es comuniquen manipulant variables de memòria compartides. La memòria distribuïda utilitza pas de missatges. Els fils POSIX i OpenMP són dues de la son dues de les APIs de memòria compartida més emprades, mentre que l'Interfici de Pas de Missatges (MPI) és l'API de sistema de pass de missatges més amplament utilitzada.^[39] Un concepte utilitzat programant programes paral·lels és el concepte de futur, on una part d'un programa promet donar una dada exigida a una altra part d'un programa en un temps futur.

Paral·lelització automàtica

La paral·lelització automàtica d'un programa seqüencial per un compilador és el sant graal de computació paral·lela. Malgrat dècades de treball per investigadors de compilador, la paral·lelització automàtica només ha tingut un èxit limitat.^[40]

Els principals llenguatges de programació paral·lels romanen o explícitament paral·leles o (en el millor dels casos) parcialment implícit, en el qual un programador dona les directives de compilador per a la paral·lelització. Alguns llenguatges de programació implícitament paral·lels existeixen – SISAL, Parallel Haskell, i (per FPGAs) Mitrion-C.

Application checkpointing

Quan més gran i més complex és un ordinador, més pot funcionar malament i el més curt el temps mitjà entre fracassos. Checkpointing d'aplicació és una tècnica per la qual el sistema informàtic pren una "foto" de l'aplicació – un registre de totes les assignacions de recursos actuals i estats variables, semblants a un abocament de memòria; aquesta informació es pot utilitzar per restaurar el programa si l'ordinador hagués de fallar. Checkpointing d'aplicació significa que el programa s'hagi de reprendre des de només el seu últim punt de control en lloc que des del començament. Per a una aplicació que es pot executar durant mesos, això és crític. Checkpointing d'aplicació es pot utilitzar per facilitar migració de procéssos.

Aplicacions

A mesura que els ordinadors paral·lels es tornen més grans i més ràpids, es torna factible resoldre problemes que prèviament prenien temps per executar. La computació paral·lela s'utilitza en una gamma àmplia de camps, des de biociència de la informació (per fer plegament de proteïna) fins a economia (per fer simulació en les finances matemàtiques). Els tipus comuns de problemes trobats en aplicacions paral·leles de computació són:

Història

L'ILLIAC IV, "potser el més infame dels supercomputadors"

Els orígens de paral·lelisme veritable (MIMD) es remunten a Luigi Federico Menabrea i el seu "Esbós del Motor Analític Inventat per Charles Babbage".^[41]IBM va presentar el 704 el 1954, durant un projecte amb Gene Amdahl, qui n'era un dels principals arquitectes. Es convertia en el primer ordinador comercial disponible en utilitzar commandes d'aritmètica de punt flotant plenament automàtics.^[42]

L'abril de 1958, S. Gill (Ferranti) discutia la programació paral·lela i la necessitat de bifurcació i espera.^[43] També el 1958, investigadors d'IBM de qui el John Cocke i Daniel Slotnick parlaven l'ús de paral·lelisme en càlculs numèrics per primer cop.^[44] La Corporació Burroughs presentada el D825 el 1962, un ordinador de quatre processador que accedia fins a 16 mòduls de memòria a través d'un llistó switch.^[45] 1967, Amdahl i Slotnick publicaven un debat sobre la viabilitat de processament paral·lel en la Conferància de la Federació Americana de les Societats de Tractament de la Informació.^[44] Era durant aquest debat que la llei d'Amdahl s'encunyava per definir el límit d'augment de velocitat a causa de paral·lelisme.

El 1969, l'empresa dels EUA Honeywell introduïa el seu primer sistema Multics, un sistema de multiprocessadors simètric capaç de córrer fins a vuit processadors en parallel.^[44] C.mmp, un projecte multiprocessador a Carnegie Mellon University de 1970, era "entre els primers multiprocessadors amb més que algun processador".^[46] "El primer multiprocessador connex d'autobusos amb caus "snooping" era la Sinapsi N+1 en 1984."

Els ordinadors paral·lels SIMD es poden remuntar als anys 1970. La motivació darrere primers ordinadors de SIMD era amortitzar el retard de porta de la unitat de control del processador sobre instructions.^[47] En 1964, Slotnick havia proposat construint un ordinador massivament paral·lel per al Lawrence Livermore National Laboratory.^[44] el Seu disseny era finançat per l'EUA Air Force, que era el primer esforç de computació paral·lela de SIMD, ILLIAC IV.^[44] La clau al seu disseny era un paral·lelisme bastant alt, amb fins a 256 processadors, que deixaven la màquina funcionar amb conjunts de dades grans en el que és més tard es coneixeria com a processament vectorial. Tanmateix, ILLIAC IV era anomenat "el més infame de superordinadors", perquè el projecte estava només un quart completat, però va portar 11 anys i costava gairebé quatre vegades l'estimació l'original.^[48] Quan finalment va estar preparat per executar la seva primera aplicació real el 1976, era sobrepassat per superordinadors comercials existents com el Cray-1.

Referències

1. Almasi, G.S. and A. Gottlieb (1989). Highly Parallel Computing. Benjamin-Cummings publishers, Redwood City, CA.
2. S.V. Adve et al. (November 2008). "Parallel Computing Research at Illinois: The UPCRC Agenda" Arxivat 2008-12-09 a Wayback Machine. (PDF). Parallel@Illinois, University of Illinois at Urbana-Champaign. "The main techniques for these performance benefits – increased clock frequency and smarter but increasingly complex architectures – are now hitting the so-called power wall. The computer industry has accepted that future performance increases must largely come from increasing the number of processors (or cores) on a die, rather than making a single core go faster."
3. Asanovic et al. Old [conventional wisdom]: Power is free, but transistors are expensive. New [conventional wisdom] is [that] power is expensive, but transistors are "free".
4. Asanovic, Krste et al. (December 18, 2006). "The Landscape of Parallel Computing Research: A View from Berkeley" (PDF). University of California, Berkeley. Technical Report No. UCB/EECS-2006-183. "Old [conventional wisdom]: Increasing clock frequency is the primary method of improving processor performance. New [conventional wisdom]: Increasing parallelism is the primary method of improving processor performance ... Even representatives from Intel, a company generally associated with the 'higher clock-speed is better' position, warned that traditional approaches to maximizing performance through maximizing clock speed have been pushed to their limit."
5. Patterson i Hennessy, 1998, p. 715.
6. Barney, Blaise. «Introduction to Parallel Computing». Lawrence Livermore National Laboratory. Arxivat de l'original el 2013-06-29. [Consulta: 9 novembre 2007].
7. Hennessy i Patterson, 2002, p. 43.
8. Rabaey, J. M. (1996). Digital Integrated Circuits. Prentice Hall, p. 235. ISBN 0-13-178609-1
9. Flynn, Laurie J. "Intel Halts Development of 2 New Microprocessors". The New York Times, May 8, 2004. Retrieved on April 22, 2008.
10. Moore, Gordon E. «Cramming more components onto integrated circuits» (PDF). Electronics Magazine p. 4, 1965. Arxivat de l'original el 2008-02-18. [Consulta: 11 novembre 2006].
11. Amdahl, G. (April 1967) "The validity of the single processor approach to achieving large-scale computing capabilities". In Proceedings of AFIPS Spring Joint Computer Conference, Atlantic City, N.J., AFIPS Press, p. 483–85.
12. Brooks, Frederick P. Jr. The Mythical Man-Month: Essays on Software Engineering. Chapter 2 – The Mythical Man Month. ISBN 0-201-83595-9
13. Reevaluating Amdahl's Law Arxivat 2012-06-23 a Wayback Machine. (1988). Communications of the ACM 31(5), p. 532–33.
14. Bernstein, A. J. (October 1966). "Program Analysis for Parallel Processing,' IEEE Trans. on Electronic Computers". EC-15, p. 757–62
15. Roosta, Seyed H. (2000). "Parallel processing and parallel algorithms: theory and computation". Springer, p. 114. ISBN 0-387-98716-9
16. Lamport, Leslie (September 1979). "How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs", IEEE Transactions on Computers, C-28,9, p. 690–91.
17. Patterson i Hennessy, 1998, p. 748.
18. Culler, David E.; Jaswinder Pal Singh and Anoop Gupta (1999). Parallel Computer Architecture - A Hardware/Software Approach. Morgan Kaufmann Publishers, p. 15. ISBN 1-55860-343-3
19. Culler et al. p. 15.
20. Patt, Yale (April 2004). "The Microprocessor Ten Years From Now: What Are The Challenges, How Do We Meet Them? (wmv). Distinguished Lecturer talk at Carnegie Mellon University. Retrieved on November 7, 2007.
21. Culler et al. p. 124.
22. Culler et al. p. 125.
23. Patterson i Hennessy, 1998, p. 713.
24. Patterson i Hennessy, 1998, p. 714.
25. Patterson i Hennessy, 1998, p. 549.
26. What is clustering? Webopedia computer dictionary. Retrieved on November 7, 2007.
27. Beowulf definition. Arxivat 2012-10-10 a Wayback Machine. PC Magazine. Retrieved on November 7, 2007.
28. Architecture share for 06/2007 Arxivat 2007-11-14 a Wayback Machine.. TOP500 Supercomputing Sites. Clusters make up 74,60% of the machines on the list. Retrieved on November 7, 2007.
29. Hennessy i Patterson, 2002, p. 537.
30. MPP Definition. Arxivat 2013-05-11 a Wayback Machine. PC Magazine. Retrieved on November 7, 2007.
31. Kirkpatrick, Scott (January 31, 2003). "Computer Science: Rough Times Ahead". Science, Vol. 299. No. 5607, p. 668 - 669. DOI: 10.1126/science.1081623
32. D'Amour, Michael R., Chief Operating Officer, DRC Computer Corporation. "Standard Reconfigurable Computing". Invited speaker at the University of Delaware, February 28, 2007.
33. Boggan, Sha'Kia and Daniel M. Pressel (August 2007). GPUs: An Emerging Platform for General-Purpose Computation Arxivat 2016-12-25 a Wayback Machine. (PDF). ARL-SR-154, U.S. Army Research Lab. Retrieved on November 7, 2007.
34. Maslennikov, Oleg (2002). "Systematic Generation of Executing Programs for Processor Elements in Parallel ASIC or FPGA-Based Systems and Their Transformation into VHDL-Descriptions of Processor Element Control Units". Arxivat 2020-02-11 a Wayback Machine. Lecture Notes in Computer Science, 2328/2002: p. 272.
35. Shimokawa, Y.; Y. Fuwa and N. Aramaki (18–21 November 1991). A parallel ASIC VLSI neurocomputer for a large number of neurons and billion connections per second speed. IEEE International Joint Conference on Neural Networks. 3: p. 2162–67.
36. Acken, K.P.; M.J. Irwin, R.M. Owens (July 1998). "A Parallel ASIC Architecture for Efficient Fractal Image Coding". The Journal of VLSI Signal Processing, 19(2):97–113(17)
37. Kahng, Andrew B. (June 21, 2004) "Scoping the Problem of DFM in the Semiconductor Industry Arxivat 2008-01-31 a Wayback Machine.." University of California, San Diego. "Future design for manufacturing (DFM) technology must reduce design [non-recoverable expenditure] cost and directly address manufacturing [non-recoverable expenditures] – the cost of a mask set and probe card – which is well over $1 million at the 90 nm technology node and creates a significant damper on semiconductor-based innovation."
38. Patterson i Hennessy, 1998, p. 751.
39. The Sidney Fernbach Award given to MPI inventor Bill Gropp Arxivat 2011-07-25 a Wayback Machine. refers to MPI as the "the dominant HPC communications interface"
40. Shen, John Paul and Mikko H. Lipasti (2005). Modern Processor Design: Fundamentals of Superscalar Processors. McGraw-Hill Professional. p. 561. ISBN 0-07-057064-7. "However, the holy grail of such research - automated parallelization of serial programs - has yet to materialize. While automated parallelization of certain classes of algorithms has been demonstrated, such success has largely been limited to scientific and numeric applications with predictable flow control (e.g., nested loop structures with statically determined iteration counts) and statically analyzable memory access patterns. (e.g., walks over large multidimensional arrays of float-point data)."
41. Menabrea, L. F. (1842). Sketch of the Analytic Engine Invented by Charles Babbage. Bibliothèque Universelle de Genève. Retrieved on November 7, 2007.
42. da Cruz, Frank. «Columbia University Computing History: The IBM 704». Columbia University, 2003. [Consulta: 8 gener 2008].
43. Parallel Programming, S. Gill, The Computer Journal Vol. 1 #1, pp2-10, British Computer Society, April 1958.
44. Wilson, Gregory V. «The History of the Development of Parallel Computing». Virginia Tech/Norfolk State University, Interactive Learning with a Digital Library in Computer Science, 1994. [Consulta: 8 gener 2008].
45. Anthes, Gry. «The Power of Parallelism». Computerworld, 19-11-2001. Arxivat de l'original el 2008-01-31. [Consulta: 8 gener 2008].
46. Patterson i Hennessy, 1998, p. 753.
47. Patterson i Hennessy, 1998, p. 749.
48. Patterson i Hennessy, 1998, p. 749–50: "Although successful in pushing several technologies useful in later projects, the ILLIAC IV failed as a computer. Costs escalated from the $8 million estimated in 1966 to $31 million by 1972, despite the construction of only a quarter of the planned machine ... It was perhaps the most infamous of supercomputers. The project started in 1965 and ran its first real application in 1976.".

Bibliografia

• Patterson, David; Hennessy, John L. Computer Organization and Design (en anglès). Second Edition. Morgan Kaufmann Publishers, 1998. ISBN 1-55860-428-6. 
• Hennessy, John L.; Patterson, David A. Computer Architecture: A Quantitative Approach (en anglès). 3rd edition. Morgan Kaufmann, 2002. ISBN 1-55860-724-2.