miniatura|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,Almasi, G.S. and A. Gottlieb (1989). Highly Parallel Computing. Benjamin-Cummings publishers, Redwood City, CA. 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.S.V. Adve et al. (November 2008). "Parallel Computing Research at Illinois: The UPCRC Agenda" (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." 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,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". la computació paral·lela s'ha convertit en el paradigma dominant en l'arquitectura informàtica, principalment en forma de processadors multi nucli.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."
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 empren 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, 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.
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.
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.
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).Rabaey, J. M. (1996). Digital Integrated Circuits. Prentice Hall, p. 235. 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.Flynn, Laurie J. "Intel Halts Development of 2 New Microprocessors". The New York Times, May 8, 2004. Retrieved on April 22, 2008.
La llei de Moore és l'observació empírica que la densitat de transistors en un microprocessador es duplica cada 18 a 24 mesos. 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 miniatura|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'aquests 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.Amdahl, G. (April 1967) "The validity of the single processor approach to achieving large-scale computing capabilities". Proceedings of AFIPS Spring Joint Computer Conference, Atlantic City, N.J., AFIPS Press, p. 483–85. 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ó:
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."Brooks, Frederick P. Jr. The Mythical Man-Month: Essays on Software Engineering, Chapter 2 – The Mythical Man Month.
La llei de Gustafson és una altra llei en l'enginyeria informàtica, estretament relacionada a la llei d'Amdahl. Es pot formular com:
miniatura|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×).
a on P és el nombre de processadors, S és l'augment de velocitat, i la part no-paral·lelitzable del procés.Reevaluating Amdahl's Law (1988). Communications of the ACM 31(5), p. 532–33. 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 Pi i Pj dos fragments de programa. Les condicions de BernsteinBernstein, A. J. (October 1966). "Program Analysis for Parallel Processing,' IEEE Trans. on Electronic Computers". EC-15, p. 757–62 descriuen quan és que els dos són independents i es poden executar en paral·lel. Per a Pi, siguin Ii totes les variables d'entrada i Oi les variables de sortida, i de la mateixa manera per a Pj. P i i Pj són independents si satisfan
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.Roosta, Seyed H. (2000). "Parallel processing and parallel algorithms: theory and computation". Springer, p. 114.
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ó.