Programant supercomputadors

PROGRAMANT SUPERCOMPUTADORS I!I-IIIIIII. stem vivint un moment historie en plenarevolució tecnologica. Durant la década deIs 40 i amb l'influencia de la Segona ... __ .. Guerra Mundial, es van comen9ar a desenvolupar els primers computadors orientats a executar de forma eficient aplicacions numériques relacionades amb dt1culs militars. Actualment aquestes maquines es denominen supercomputadors, i el seu objectiu és executar a la maxima velocitat possible aplicacions que requereixen gran quantitat d' operacions numériques sobre estructures de dades molt grans. La supercomputació és un tema estrategic de recerca per a páisos com els Estats Units, el Japó, i darrerament també ho és a Europa. L' objectiu d' aquesta col.laboració no és, ni molt menys, donar un curs complert ni tampoc incomplert de com es programa un supercomputador. El que es pretén és il.lustrar el tipus de problemes amb els que un programador es pot trobar a I'hora de programar una d'aquestes maquines, i descriure quina direcció segueix la recerca actual dins d' aquest camp per a tractar els problemes descrits. L' estructura de la resta de l'article és la següent. Inicialment es descriu l' evolució deIs supercomputadors provocada per la gran demanda de potencia de crucul en les aplicacions actuals. Es dóna una idea deIs diferents tipus d'arquitectura, i lORDI GARCIA ALMIÑANA és professor del Departament d'Arquitectura de computadors sistemes operatius a I'ETSETB 32 Jordi Garcia Almiñana quines limitacions té cada un. A continuació s 'introdueix, rnitjancant exemples, la problematica de programar aquest tipus de maquines, amb especial interes en els sistemes que ofereixen la possibilitat de paral.lelitzar. Finalment es dóna una VlSlO de quin tipus d' eines automatiques es necessita per donar suport al programador, i quin és l' estat actual en relació a aquestes necessitats. 1. Arquitectura deis Supercomputadors tres dimensions. Aquest avan9 és el resultat de la unió estreta de diferents arees de recerca, tals com aplicacions, models numerics, llenguatges d'alt nivell, compiladors, sistemes operatius, arquitectura, i disseny de la circuiteria basica. La tecnologia que s'utilitza per fabricar els processadors que apareixen en les maquines d' altes prestacions, pero, esta arribant allírnit físic de la velocitat de la llum. Encara que els components d'un processador assolissin aquesta velocitat, no es podrien executar més que alguns milions A vui en dia els supercomputadors executen models matematics que reemplacen els experiments físics. EIs túnel s de vent es converteixen en simulació aerodinamica, el disseny de cotxes es basa en computadors grafics per comptes d' en prototipus. EIs EIs models basats en d'instruccions per segon. Per poder aconseguir millores significants en aquesta velocitat, els dissenyadors de sistemes centren els seu s esfor90s en l' arquitectura. Basicament es coneixen dues tecniques per a aquesta finalitat: la computadors són el nucli de recerca actual sobre modelatge climatoliJ gic, tecnologia genetica o engznyerza aeroespacial, per citar alguns exemples. models basats en computadors són el nucli de recerca actual sobre modelatge climatologic, tecnologia genetica o enginyeria aeroespacial, per citar alguns exemples. L' increment en la potencia deis supercomputadors es reflexa en dos sentits. Per una banda hi ha nous problemes que es posen a l' abast per a poder ser modelats en els computadors. Per una altre banda permeten trobar rnillors solucions a problemes que ja eren coneguts. Per exemple, problemes en dues dimensions poden ser reformulats en segmentació i el paral.lelisme. La segmentació consisteix en descomposar les operacions en un nombre N d' etapes, cada una de les quals s' executa en un cicle de rellotge. Quan una instrucció passa a executar una etapa determinada, la següent instrucció ja pot comen9ar a executar l'anterior, i així per totes les altres etapes. D' aquesta forma, en cada instant hi pot haver N instruccions executant-se simultaniament, i en cada cicle finalitza l' execució una instrucció. EIs processadors que incorporen aquesta tecnica s' anomenen BURAN N°8 DICIEMBRE 1996 processadors escalars segmentats. Malauradament, el nombre de fases en les que es pot descomposar una instrucció esta molt limitat. Una variant de la segmentació és la vectorització, que consisteix en afegir alllenguatge maquina del processador instruccions que operen sobre vectors (instruccions vectorials), donant nom a1s processadors vectorials. La vectorització consisteix en executar la mateixa operació sobre cada un deIs elements d' un vector a una freqüencia tribuida. Els processadors en array estan orientats a l' execució eficient d' operacions sobre vectors, i consten d'un gran nombre de processadors senzills que executen una mateixa operació sobre diferents elements d' un vector. Aquests processadors estan conectats a un processador escalar de proposit general que controlal' execució de l'aplicació en tot el sistema. Els sistemes multiprocessadors amb memoria compartida estan formats per un conjunt de proces-sadors molt rapids, els quals d' una operació per cicle, reduint així la carrega d'actualitzar els comptadors i punters a cada iteració del bucle. Si es vol explotar el potencial d' aquests tipus de sistemes, els accedeixen a la mateixa memoria a través d'una xarxa d'inter-connexió. En aquest tipus d' arquitectura, els processadors poden treballar de forma conjunta per a resoldre l' aplicació més rapidament, o cada un d'ells pot executar el seu propi programa.Permotius La següent tecnica que permet millorar la velocitat d'un supercomputador es coneix com a paral.lelisme, i es programes s 'han d'escriure deforma que aprofitin o utilitzin al maxim· cada un deis aspectes particulars de cada arquitectura. basa en la replica de les unitats funcionals del processador, o en la replica deis processadors del sistema. Totes les unitats funcionals o els processadors coUaboren, preferiblement a parts iguals, en l'execució de l'aplicació. Segons aquesta classificació i com a exemple de processadors amb varíes unitats funcionals, es pot distingir entre elsprocessadors superescalars i els processadors Very Long Instruction Word. Els primers poden iniciar l' execució de varíes instruccions per cicle, sempre i quan es detecti que les operacions es poden executar de forma independent. Per altre banda els processadors VLIW tenen instruccions llargues formades per un nombre fixe d'instruccions senzilles, les quals són empaquetades per un compilador. El baix cost que assoleixen els microprocessadors descrits anteriorment, permeten la construcció de maquines amb múltiples processadors. Es pot distingir entre elsprocessadors en array, els sistemes multiprocessadors amb memoria compartida, i els sistemes multiprocessadors amb memoria dis- .• RAMAS DE ESTUDIANTES DEL IEEE tecnologics, el nombre de processadors que poden compartir la memoria no pot ser gaire elevat (fins a 16 o 32), ja que resulta difícil que una sola memoria pugui subministrar dades a un nombre elevat de processadors a una velocitat raonable. És per aquest motiu que prenen importancia els sistemes multiprocessadors amb memoria distribuida, també coneguts com a processadors massivament paral.lels, els quals poden arribar a conectarmilers de processadors, cada un deIs quals amb la seva propia memoria. A més, es poden utilitzar els processadors més avan\=ats del moment sense necessitat de fer dissenys específics i cars, i el nombre de processadors del sistema es pot escalar Iacilment en funció de les necessitats de l'usuari. Per a que un grup de processadors coUabori en l' execució d' una aplicació, els processadors intercanvien informació mitjan\=ant una xarxa d'interconexió a través de la qual envien i reben missatges. NormaIment, pero, el temps d' espera en rebre un missatge és una o varíes ordres de magnitud més elevat que el temps d'accés a la propia memoria. Per tant, tot i el potencial teoric que pot arribar a tenir aquest model d'arquitectura, és una qüestió clau el saber distribuir correctament el d1culi les dades entre les memories deIs processadors, de forma que tots executin aproximadament el mateix nombre d' operacions, i que les dades requerides per aquestes es trobin a la memoria local de cada processador. Una descripció molt més detallada de tots aquests sistemes es pot trobar a [1]. 2. Programació de Maquines Paral.leles Si es vol explotar el potencial d'aquests tipus de sistemes, els programes s'han d'escriure de forma que aprofitin o utilitzin al maxim cada un deIs aspectes particulars de cada arquitectura. Normalment, els llenguatges de programació per a supercomputadors ofereixen al programador sentencies o directives que permeten especificar com s'ha d'executar el programa per a que aquest sigui més eficient. Així dons, quan s'escriu un programa per a un sistema multiprocessador amb memona compartida, s'ha d'estructurar el programa de forma que les diferents operacions que s 'han d' executar es puguin repartir facilment per el conjunt de processadors del sistema, i de forma que cada un d'ells pugui realitzar el seu ca1cul amb paraUel amb els altres processadors. Si el multiprocessador té la memoria distribuida, a més del crucul, també s'han de distribuir les dades entre les memories de cada processador. L'objectiu d'aquesta secció és donar una visió general que quin s aspectes s'han de tenir en compte al escriure un programa per a una maquina paraUela. 2.1. Distribució del calcul Hi ha varies formes de descomposar el d1cul d'un programa científico Per una banda es podría partir el programa per les diferents tasques que realitza, cada una de les quals formada per un conjunt de bucles, de forma que cada una d' elles s' assignaria a cada processador. El problema és que de vegades una 33 aplicació no té un nombre suficientment gran de tasques per a poder as signar treball a tots els processadors, o que les tasques no són independents del tot, de forma que quan un processador treballa, els demés s'han d'esperar a que aquest acabi per a poder comen\(ar. Per altre banda, les aplicacions científiques acostumen a utilitzar estructures de dades molt grans, les quals han de ser tractades repetidament dins de bucles. En aquest tipus d' aplicacions, el bucles representen la part computacional més important del programa. El paral.lelisme de dades consisteix en partir els bucles deIs programes de forma que cada processador executi un conjunt de les iteracions. Per exemple, el següent fragment de codi: Exemple 1: do i = 1,40 do j = 1,40 A(i, j) = A(i, j) + 1 enddo enddo podria ser paral.lelitzat assignant les iteracions del bucle i a diferents processadors. En aquest cas els processadors aniran recorrent simultaniament diferents files de la matriu A. El codi que expresa aquesta estrategia de paral.lelització sera del tipus: forall i = 1, 40 do j = 1,40 A(i, j) = A(i, j) + 1 enddo endforall Pero no semprees potparal.lelitzar el bucle que es vol, i de vegades inclús no es pot paral.lelitzar cap bucle sense transformar el codi. Per exemple, en el següent fragment de codi: 34 Exemple 2: do i = 2, 40 do j = 1,40 A(i,j) = A(i - 1,j) + 1 enddo enddo no es pot paral.lelitzar el bucle i, ja que per actualitzar la filai es necessita la fila anterior i-1. És a dir, per a que el resultat de l' execució sigui correcte, no es pot actualitzar una fila si abans no ha estat actualitzada la fila anterior. En aquest cas es diu que hi ha una dependencia en el bucle i, i per tant aquest bucle s'ha d'executar respectant l' ordre sequencial. En canvi si que es pot paral.lelitzar el bucle j. En aquest cas, per a cada fila i de la matriu A, cada processador podria recorrer en paral.lel diferents parts d'aquesta fila. Quan tots els bucles tenen dependencies hi ha altres tecniques que, transformant el codi, permeten extreure certa paral.lelització. La descripció d'algunes d'aquestes tecniques es pot trobar a [2]. 2.2. Distribució de les dades Si el sistema multiprocessador per al qual s' escriu el programa té la memoria distribuida, una decisió important que s'ha de prendre és a on s'emplacen inicialment les dades. Aquesta qüestió esta estretament relacionada amb la paral.lelització del ca1cul, ja que en funció de la porció de l'estructura de dades que tingui un processador, sera més adequat paral.lelitzar un bucle o un altre. Generalment aquest tipus de programes segueixen la owner computes rule, és a dir, el processador propietari de la dada que s'ha de modificar és el responsable d' efectuar el ca1cul. Si un processador té una dada que necessita un altre processador per a efectuar el seu ca1cul, aquests s'han de comunicar mitjancant un missatge enviat per el processador que té la dada cap al processador que ha de fer el ca1cul. El temps que tarda aquest missatge en arribar al seu destí és molt més elevat que el temps d'accés a memoria, per tant també s'ha d'intentar minimitzar el nombre d'accessos remots. Per exemple, assumint que hi ha 4 processadors al sistema, distribuir la matriu A per files significa que cada processador té 10 de les files de la matriu tal i com mostra la següent figura. A nivell derepartició del ca1cul i respectant el owner computes rule, significa que el primer processador és el responsable de recorrer les 10 primeres files de la matriu, el segon processador ho és de les 10 següents files, i així successivament. Colurnnes 1 .. 40 Files 1 .. 10 ~ II .. 20 ~ 21 .. 30 ~ 31 .. 40 .' ~ Tomant a considerar el codi de l'exemple 2 i assumint que A esta distribuida per files, significa que s'ha de particionar el bucle i de forma que cada processador només recorri les 10 files que li correspon. Degut a la dependencia en aquest bucle, cap processador no pot comen\(ar fins que el processador anterior hagi acabat les seves 10 files. A més, per a que el processador 2 pugui comen\(ar a modificar la fila 11, necessita la fila 10, que es troba a la memoria del processador 1. Per tant el bucle s' acabaria executant seqüencialment, amb el retard adicional d'haver d'esperar a rebre una fila sencera del processador anterior. Evidentment en aquest cas la millor alternativa seria partir la matriu A per columnes, de forma que cada processador pugui actualitzar paral.lelament les seves 10 columnes. Hi ha molts altres aspectes que s'han de tenir en compte al distribuir les dades. Per exemple, segons el següent fragment de codi: Exemple 3: do i = 2, 40 do j = 1,40 A(i, j) = B(j, i) + 1 enddo enddo la matriu A es pot distribuir tant per files com per columnes. BURAN N°8 DICIEMBRE 1996 Pero un cop decidit com estara distribuida la matriu A, per exemple per files, seria benefició s adonarse' n que la matriu B hauria d'estar trasposada respecte a la matriu A, és a dir, per columnes. Si no és així, el codi es podria executar igualment en paral.lel, pero hi haura un cost molt elevat en quant a comunicació, ja que la major part de les dades requerides per un processador per a efectuar el calcul estan en la memoria d'un altre processador. 3. Eines de Suport a la Programa:ció Hi ha diferents alternatives per aplicar les tecniques descrites en la secció anterior, en funció del grau de coneixement que el programador d' aplicacions té del seu supercomputador. Per una banda podria ser el mateix programador qui decidís l'estrategia de paral.lelització, usant un llenguatge amb construccions gramador ha de controlar les referencies a dades no locals, insertant oportunament les sentencies de pas de missatges. La gestió de la comunicació a aquest nivell és molt delicada, els programes resultants són difícils de depurar, i dificulta la portabilitat del codi a altres arquitectures. L'estil de programació resultant es pot comparar a la programació en assemblador d'una maquina seqüencial [3]. EIs llenguatges amb paral.lelisme de dades ofereixen al programador la possibilitat d'escriure els programes assumint que les dades són totes globals. El programador només ha d' especificar, mitjancant directives, l' empla~ament de les dades, i el compilador s' encarrega de paral.1eli tzar els bucles corresponents i de generar les sentencies de pas de missatges apropiades. que permetin expresar paral.lelisme. Aquesta tasca, pero, no acostuma a ser gens facil iés propensa als errors. A més, existeixen milions de linies de codi d' aplicacions que inicialment van ser escrites pensant en computadors EIs llenguatges amb paral.lelisme de dades ofereixen al programador la D' aquesta forma, el mateix codi serveix per a multiprocessadors amb memoria compartida i per a multiprocessadors amb memoria distribuida. Actualment s' esta treballant en definir un estandard per aquest tipus de llenguatges [4], i comencen a haver compiladors que porpossibilitat d' escriure els seqüencials, que haurien de ser programes assumint que les dades són tates globals. adaptades a les característiques del supercomputador. Una segona alternativa és deixar que sigui el compilador de la maquina qui s'encarregui de detectar i explotar el possible paral.lelisme de l'aplicació. En aquest cas es faria automaticament una reestructuració del codi seqüencial generant un nou codi paral.lel optimitzat per la maquina en qüestió [2]. Actualment, tots els fabricarits de supercomputadors ofereixen, junt amb la maquina, el propi compilador optimitzador. Si a més, el supercomputador té la memoria distribuida, el pro- • RAMAS DE ESTUDIANTES DEL IEEE ten a terme aquest procés, insertant les corresponents crides de pas de missatge al codi inicial segons la distribució de dades especificada. Encara s'ha de portar a terme molta més recerca en aquest camp per a que els compiladors siguin realment eficients. Malgrat aixo, el programador és encara qui ha d'especificar l'empla~ament de les dades. Aquesta decisió és molt important, ja que fixa el paral.lelisme de l' aplicació i determina la quantitat d' accessos remots que s'han de portar a terme durant l'execució del programa. La distribució optima de les dades depen de l' estructura del programa, del comportament del compilador, i de les característiques de lamaquina. Les eines de distribució automatica de dades [5][6] ajuden al programador en aquesta tasca. A partir de l' anilisi del codi i tenint en compte certes característiques de la maquina, estimen de forma conjunta l'impacte que tenen les possibles distribucions de dades en quant a paral.lelisme i comunicació. Segons aquest anhlisi, inserten al codi original les corresponents directives de distribució de dades, el qual es compila amb algun deIs compiladors descrits anteriorment. L'exit final que puguin tenir aquests tipus d' arquitectures dependra, en bona part, deIs resultats que donin les eines automatiques. La potencia de ca1cul és avui en dia una realitat, pero no servira de res si no hi ha mitjans per poder aprofitar-Ia. Referencies [1] J. L. HENNESSY, D. A. PATTERSON. Computer Architecture: A Quantitative Approach. Second edition. Morgan Kaufmann publishers, San Francisco, CA, 1996. [2] M. WOLFE. Optimizing Supercompilers for Supercomputers. Research monographs in parallel and distributedcomputing. The MIT Press, Cambridge, MA, 1989. [3] P. 1. HATCHER, M. 1. QUINN. Data-Parallel Programming on MIMD Computers. The MIT Press, Cambridge, MA, 1993. [4] C. H. KOELBEL, D. B. LOVEMAN, R. S. SCHREIBER, G. L. STEELE, M. E. ZOSEL. The High Performance Fortran Handbook. Scientific and engineering computation series. The MIT Press, Cambridge, MA, 1994. [5] E. AYGUADÉ, J. GARCIA, M. GIRONES, M. L. GRANDE, 1. LABARTA. DDT: A Research Tool for Automatic data Distribution in HPF. Published in Scientific Programming, special issue on HPF, 1996. [6] J. GARCIA, E. AYGUADÉ, 1. LABARTA. Dynamic Data Distribution with Control Flow Analysis. In proceedings of Supercomputing'96 conference. Pittsburgh, PA, 1996. 35