Processador vectorial

De Viquipèdia
Dreceres ràpides: navegació, cerca

En computació, un processador vectorial és una unitat de processament central (CPU) que implementa un conjunt d'instruccions les quals operen en matrius unidimensionals de dades anomenats vectors. La principal diferència entre un processador vectorial i un escalar rau en el fet que el processador vectorial és capaç de descodificar instruccions els operands de les quals són vectors complets, mentre que les instruccions d'un processador escalar només poden operar sobre elements de dades individuals. Els processadors vectorials poden millorar en gran mesura el rendiment en certes càrregues de treball, en particular la simulació numèrica i tasques similars. Els computadors vectorials van aparèixer en la dècada de 1970 i es van establir com a disseny dominant en els supercomputadors, però, la ràpida caiguda de la relació preu-rendiment dels dissenys de microprocessadors convencionals va conduir a la desaparició dels supercomputadors vectorials al final dels anys 1990.[1] A l'actualitat, la majoria dels microprocessadors convencionals contenen un repertori d'instruccions vectorials les quals els fan capaços d'operar sobre vectors. La conversió d'un programa o algorisme corresponent a un processador escalar a un altre vectorial s'anomena vectorització.

Processament vectorial[modifica | modifica el codi]

Taula 1. Operacions vectorials.

Un operand vectorial conté una seqüència de n elements, anomenats components, on n és la longitud del vector. Cadascun dels components del vector és un escalar de qualsevol tipus (enter, punt flotant, etc). Els operadors vectorials poden tenir una de les següents cinc formes (podria haver-hi alguna més, però no tenen interès pràctic):

  • f1: V →V (operació vectorial unitària)
  • f2: V × V → V (operació vectorial binària)
  • f3: V → K (reducció unitària)
  • f4: V × V → K (reducció binària)
  • f5: K × V → V (operació d'escalat)

on V i K representen, respectivament, un espai vectorial i un cos.

En la taula 1 es poden veure una sèrie d'exemples d'operadors vectorials. En aquesta taula, a, b, c ∈ V, ai, bi, i ci són, respectivament, les components i-èssimes d'aquests vectors, s ∈ K i n = dim V.

Casos especials d'operacions vectorials binàries són les operacions d'empaquetament i desempaquetament, on un dels vectors actua com a màscara i el vector resultat té una mida diferent a la dels operands. Aquestes operacions tenen molta utilitat en el tractament de matrius disperses, que són matrius amb la majoria dels seus elements nuls.

Les màquines vectorials proporcionen operacions que treballen sobre vectors. Una instrucció vectorial és equivalent a l'execució d'un bucle complet d'operacions ordinàries, on cada iteració treballa sobre cadascuna de les components del vector. Les operacions vectorials tenen alguns avantatges sobre les escalars:

  • En les operacions vectorials, cada resultat és independent dels anteriors. Això permet efectuar els càlculs en un processador segmentat sense que existeixin conflictes per dependències de dades.
  • Una simple instrucció vectorial substitueix a moltes escalars. Per això, el coll d'ampolla produït per la lectura d'aquesta instrucció és petit, comparat amb el que produiria tot el conjunt d'instruccions escalars equivalents.
  • Les instruccions vectorials que necessiten accedir a memòria ho fan amb un patró d'accés fix (normalment adjacents). Això facilitarà la seva lectura paral·lela mitjançant una memòria entrellaçada. En qualsevol cas, si no es disposés de memòries entrellaçades, les posicions de memòria adjacents es carregaran a la memòria cau, amb el consegüent estalvi de temps.
  • Si s'utilitza una instrucció vectorial, evitarem el risc de control de salt de bucle, que es produiria si processéssim les instruccions escalars equivalents en un processador segmentat.

Per totes aquestes raons, les operacions vectorials poden executar-se d'una forma molt més ràpida que la seqüència d'instruccions escalars equivalents sobre el mateix conjunt de dades, per això la tendència al disseny i fabricació de màquines vectorials en aplicacions on aquest tipus d'operacions s'utilitzen amb suficient freqüència.

Segmentació i processadors vectorials[modifica | modifica el codi]

Vist l'anterior, sembla clar que els computadors vectorials han de basar la seva unitat d'execució en un processador segmentat que prendrà una per una totes les components del vector i les anirà processant sense dependències de dades ni control durant l'execució de tota la instrucció vectorial. La majoria dels computadors vectorials actuals treballen d'aquesta manera. Una altra possibilitat més costosa és la divisió funcional, mantenint una unitat d'execució per a cada component del vector. L'alt cost d'aquesta solució no sol justificar-la. Per altra part, aquest tipus de solució precisa que els vectors tinguin una longitud limitada; amb un processador segmentat, les components poden anar entrant i sortint per la llera sense límit de components, encara que, evidentment, un vector més llarg trigarà més temps en processar-se.

Arquitectura dels processadors vectorials[modifica | modifica el codi]

Fig 1. Processador vectorial memòria-memòria.

Una primera versió, molt simplificada, de processador vectorial és el mostrat a la figura 1. Aquest tipus de màquina representa un processador vectorial memòria-memòria que és capaç d'extreure dos vectors de memòria i operar sobre ells. L'inconvenient d'aquest tipus de màquina seria el coll d'ampolla que suposarien els accessos a memòria. Per pal·liar aquest problema, es poden realitzar les següents millores:

  1. Augmentar l'amplada de banda de la memòria: això s'aconsegueix entrellaçant la memòria, de forma que aquesta tingui varis mòduls i es pugui accedir simultàniament a diverses posicions consecutives que es trobin en mòduls diferents
  2. Afegir una memòria intermèdia de major velocitat entre la memòria i el processador. Una forma de fer això, a més a més d'incorporar una memòria cau, és afegir un banc de registres vectorials.

Per a tot això, és habitual que els processadors vectorials disposin d'un banc (o múltiples bancs) de registres vectorials que facin de memòria intermèdia; es parla, llavors, de processadors vectorials registre-registre. Per altra banda, la majoria dels processadors vectorials actuen com coprocessadors d'un processador escalar convencional que tracta les instruccions no vectorials. Això fa que l'arquitectura d'un computador vectorial actual sigui la que es mostra a la figura 2. Com es pot veure, els computadors vectorials poden considerar-se com computadors del tipus SIMD en la Taxonomia de Flynn, però, s'ha de tenir en compte que, si bé els computadors vectorials executen la mateixa instrucció sobre dades diferents, aquestes dades formen part del mateix flux. Per això, en alguns casos, a aquestes màquines se'ls anomenen SIMD-vectorials.[2]

Fig 2. Processador vectorial registre-registre

Rendiment dels processadors vectorials[modifica | modifica el codi]

Basant-nos en l'anterior, es presenta un model per avaluar el rendiment dels processadors vectorials. Es prendrà per a fer aquesta avaluació, un càlcul vectorial sobre vectors de n components en un bucle que s'hagi de seccionar. En el càlcul d'aquest rendiment intervenen les següents variables:[3]

  1. El temps necessari per a processar cada component en una iteració del bucle. Denominarem aquest temps tp.
  2. El temps d'inicialització de cada bucle provocat pel seccionament. Aquest temps es pot desglossar en dues parts: el temps del codi escalar necessari pel seccionament (ts) i el temps d'arrencada de la instrucció vectorial (ta).
  3. El temps ocupat per l'arrancada del programa, càrrega inicial dels vectors en els registres, etc. (tb).
  4. Màxim nombre de components que el vector es capaç d'allotjar (MVL).

Amb tot això, el temps necessari per al càlcul total serà:

El guany de temps respecte a un processador segmentat escalar rau, més que en la millora del temps de càlcul pròpiament dit, en el temps necessari per a llegir i descodificar les instruccions. També es pot guanyar temps si es disposa de diversos fluxos aritmètics perquè sigui possible executar diverses instruccions vectorials de forma simultània.

Hi ha alguns paràmetres que poden ajudar a avaluar la qualitat d'un processador vectorial referits a la longitud del vector que s'estigui tractant, aquests són:

  • Rn: és la velocitat en MFLOPS sobre un vector de longitud n. Per extensió i de forma ideal R és la velocitat del processador per a un vector de longitud infinita. La diferència entre aquestes mesures indicaran les penalitzacions en el rendiment degudes a la longitud finita dels vectors.
  • N1/2: és la longitud necessària per assolir una velocitat de R/2.
  • Nv: és la longitud necessària per fer el mode vectorial més ràpid que l'escalar. Aquesta mesura avalua les pèrdues de rendiment a causa a les operacions addicionals necessàries en el procés vectorial respecte a l'escalar.

A continuació es veu una forma d'avaluar l'eficiència dels processadors vectorials: sigui r la relació entre les velocitats de procés vectorial i escalar, i sigui fv la fracció de codi vectoritzable. Prenent com a unitat el temps que trigaria a executar-se el procés si la màquina fos totalment escalar, tindrem que el guany de velocitat d'un processador vectorial serà:

L'eficiència del sistema vindria donada, doncs, per:

Aquestes expressions es refereixen al cas ideal en què el processador vectorial no tingui pèrdues per causes diferents del codi no vectoritzable. Per altra banda, les expressions anteriors no són més que una altra forma d'expressar la llei d'Amdahl.

Característiques dels llenguatges pel processament vectorial[modifica | modifica el codi]

L'ús de llenguatges seqüencials en computadors vectorials pot fer perdre el paral·lelisme d'un algorisme vectoritzable. És, per tant, necessària l'existència de llenguatges adequats als computadors vectorials. Aquests llenguatges haurien de tenir una sèrie de propietats per a expressar el paral·lelisme dels algorismes i així poder explotar l'arquitectura vectorial amb més eficiència:

  • Flexibilitat per a declarar diferents classes d'objectes amb diferents estructures i formes d'emmagatzemament. El llenguatge ha de poder expressar les diferents formes d'emmagatzemar les components d'un mateix objecte: per files, columnes, diagonals, etc.
  • Efectivitat per a la manipulació de matrius i vectors dispersos, és a dir, matrius o vectors amb la majoria dels seus elements nuls. Les matrius disperses són molt habituals en problemes reals, per això, el llenguatge de programació ha de poder subministrar els medis per emmagatzemar-les de forma eficient sense ocupar excessiva memòria.
  • Disposar d'operacions vectorials natives que treballin directament amb les estructures de dades anteriorment declarades sense necessitat de bucles. Serà el compilador del llenguatge el que transformi aquestes operacions d'alt nivell en les instruccions vectorials de la màquina. Moltes vegades, el nombre de components del vector declarat en el llenguatge d'alt nivell, serà superior a la capacitat dels registres vectorials. Per això, el compilador haurà d'aplicar la tècnica de seccionament per a descompondre algunes instruccions vectorials d'alt nivell, en unes altres instruccions vectorials més senzilles que puguin executar-se amb la capacitat d'emmagatzemament dels registres vectorials de la màquina. Això no significa, però, que aquests llenguatges no admetin la programació mitjançant bucles. Això és a causa que poden haver moltes operacions combinades que tan sols poden detallar-se mitjançant bucles específics. Evidentment, el llenguatge vectorial no pot tenir com operacions natives totes les possibles combinacions d'operacions vectorials, encara que sí les més freqüents.

Exemple: Cilk Plus.[modifica | modifica el codi]

Intel Cilk Plus inclou un conjunt d'anotacions que permeten als usuaris expressar operacions d'alt nivell en matrius o seccions d'arrays sencers. Aquestes anotacions ajuden al compilador a vectoritzar eficaçment l'aplicació. Cilk Plus permet aplicar operacions C / C ++ a múltiples elements de la matriu en paral·lel, i també proporciona un conjunt de funcions internes que es poden utilitzar per dur a terme les operacions vectorials.[4]

A tall d'exemple, a continuació es mostra un fragment de codi C que expressa la funció clàssica SAXPY (Single-Precision A·X Plus Y):

void Saxpy()
{
    for (int i=0; i<N; i++)
    {
        y[i] = (a * x[i]) + y[i];
    }
}

El següent codi expressa la mateixa funció, però amb notació vectorial Cilk Plus. Cal destacar que en aquest fragment de codi es prescindeix de l'ús de bucles:[5]

void Saxpy()
{
    y[:] = (a * x[:]) + y[:] 
}

Compiladors per a processadors vectorials[modifica | modifica el codi]

Un compilador amb capacitat de vectoritació analitza si les instruccions situades dins dels bucles poden executar-se en paral·lel i genera codi amb instruccions vectorials. Quant més capaç sigui el compilador en vectoritzar el codi, el rendiment millorarà en la mateixa mida. En això rau la importància dels compiladors vectorials. Existeixen importants dificultats en la vectorització del codi. Aquestes dificultats rauen en les instruccions de control, especialment en les condicionals, en les dependències de dades, en les indexacions indirectes (és a dir, components de vectors o matrius que són l'índex d'altres vectors o matrius) que es resolen a temps d'execució. La indexació indirecta és un dels tractaments més comuns de les matrius disperses. Les etapes d'un compilador són les següents:

  1. Anàlisi lèxic.
  2. Anàlisi sintàctic.
  3. Anàlisi semàntic (com a conseqüència d'aquest anàlisi es genera un codi intermedi).
  4. Optimització del codi.
  5. Generació de codi final.

En un compilador amb vectorització, les dues primeres fases no canvien. El codi generat a partir de l'anàlisi semàntic ha de ser codi vectorial i s'hi ha de sotmetre en la següent etapa a una sèrie d'optimitzacions diferents de les dels compiladors convencionals. Aquesta optimització vectorial afectarà, entre altres, als següents aspectes:

  • Reducció de constants en compilació: Això significa que el compilador ha d'avaluar totes les expressions que pugui en temps de compilació. Aquest tipus de reducció, que habitualment s'efectua per a codi escalar, adquireix alguns nous aspectes en el codi vectorial, com per exemple evitar la inicialització d'un vector en l'execució, inicialitzant-lo completament en temps de compilació.
  • Trasllat d'expressions invariants: freqüentment els bucles més interns inclouen operacions que, en determinades condicions, poden ser traslladades a una zona més externa. Aquesta acció s'anomena trasllat de codi.

Alguns exemples de compiladors capaços de vectoritzar són:

Exemples clàssics de computadors vectorials[modifica | modifica el codi]

A continuació es mostren alguns exemples clàssics de computadors vectorials. Alguns d'ells estan ja obsolets, però són exemples clàssics que s'han de mencionar per la importància que van tenir al seu moment.

El Cray-1 de Cray Reseach[8][modifica | modifica el codi]

Una Cray-1 preservada en el Deutsches Museum.

El Cray-1, operatiu des de 1976, es pot considerar com el primer computador vectorial. Com molts supercomputadors, necessitava un processador auxiliar per efectuar tasques d'administració, E/S, etc. D'aquesta forma, el Cray-1 només es dedicava a la computació pura. El Cray-1 posseïa tres seccions: la secció de computació, la secció de memòria i la secció d'E/S.

La secció de memòria està organitzada en 8 o 16 bancs amb 72 mòduls per banc (1 mòdul per bit) dels que 8 són per a detecció i correcció d'errors: el sistema pot detectar fins a 2 errors i corregir 1, sent la paraula eficaç de memòria de 64 bits. La memòria és entrellaçada amb 16 vies.

La màquina disposa de tres tipus de registres: registres de direcció, registres escalars i registres vectorials, havent 8 registres de cada classe. També existeixen uns registres temporals, tant escalars com de direccions, que actuen a manera de memòries cau per a dades i direccions. Existeixen 64 registres temporals de cada una d'aquestes classes. Disposa també de 4 bancs de registres temporals d'instruccions. Els registres de direccions tenen 24 bits, els escalars 64 i els vectorials tenen 64 registres components de 64 bits cadascun. La màquina disposa d'un registre de longitud que indica la longitud dels operands vectorials. Si la longitud dels vectors del problema és major, s'ha de recórrer a la tècnica de seccionament. Els continguts dels registres vectorials es transfereixen des de memòria indicant la direcció inicial, l'increment i la longitud del vector.

El sistema disposa de 12 unitats funcionals segmentades dividides en quatre grups: vectorials (enteres i de punt flotant), escalars i de direccions. Cada unitat funcional pot treballar amb total independència de la resta, pel que totes poden funcionar concurrentment sempre que no hi hagin conflictes quant als registres que utilitzin. Les unitats funcionals poden accedir directament als registres primaris, però no als temporals.

Quant al control, un registre fa les funcions de comptador de programa. Les instruccions poden tenir tant 16 com 32 bits, per això, el registre d'instrucció té dues parts: el CIP (current instruction parcel, part de la instrucció en curs) i el LIP (low instrucction parcel, part baixa de la instrucció), ambdues de 16 bits. 

Altres registres de la màquina són el VM (vector mask, registre de màscara per a vectors), que s'utilitza per a operacions d'empaquetament i desempaquetament de vectors.

El Cyber-205 de Control Data[9][modifica | modifica el codi]

Aquesta màquina és un curiós exemple de computador vectorial memòria-memòria. Per això, la memòria d'aquesta màquina és molt ràpida i està entrellaçada amb quatre vies. L'avantatge que aquest computador sigui del tipus memòria-memòria rau en què la longitud dels vectors pot ser molt gran. Concretament en el Cyber-204, la longitud màxima dels vectors és de 65635 paraules. El control de l'execució de les instruccions resideix en la unitat escalar, que rep i descodifica les instruccions procedents de la memòria i les reparteix entre els diferents blocs en funció del seu tipus: escalar, vectorial o de cadena (aquí la paraula cadena es refereix a cadenes de bits); a partir d'aquí, diferents instruccions poden executar-se de manera concurrent en diferents unitats funcionals. La unitat aritmètica escalar té cinc processadors aritmètics segmentats i treballa amb operands escalars de 32 i 64 bits. La unitat vectorial pot disposar d'1, 2 o 4 processadors aritmètics que també disposen de diverses lleres que poden efectuar diverses operacions sobre operands de 32 i 64 bits. La unitat de cadena serveix per a processar vectors de control, o vectors de màscara, que són molt útils per a treballar amb matrius i vectors dispersos. Aquests vectors de control també són útils per accedir a vectors no consecutius en memòria. Aquest processador està capacitat per a efectuar encadenament entre les diverses lleres, de forma que pot fer que la sortida d'una llera vagi directament a l'entrada d'una altra.

El IBM-3090[10][modifica | modifica el codi]

El processament vectorial d'aquesta màquina és una opció anomenada vector facility. El sistema disposa de 16 registres de 32 bits que poden unir-se de dos en dos per a convertir-se en 8 registres de 64 bits. Qualsevol dels registres pot contenir tant nombres enters com representats en punt flotant (de 32 o 64 bits). En el disseny de l'arquitectura no es determina de forma concreta la longitud dels registres vectorials que poden oscil·lar entre 8 i 512. En la implementació del 3090 es va elegir el nombre de 128. Aquesta elecció es va deure a un compromís entre el temps perdut en les arrancades, que serà alt si els registres són petits, perquè s'hauria d'efectuar més arrancades d'instruccions vectorials si els vectors són llargs, i el temps empleat en la càrrega i emmagatzemament dels registres vectorials, que serà tant o més gran com més longitud tinguin. La màquina disposa d'alguns registres de control: el registre de màscara vectorial, el registre de l'estat vectorial i el comptador de l'activitat vectorial.

Una de les característiques més importants d'aquesta màquina és el seu repertori d'instruccions vectorials, la qual conté instruccions de tipus CVF (funcions vectorials compostes), tals com multiplicar i sumar, multiplicar i restar, etc., això dóna molta agilitat i velocitat a les operacions sense haver de recórrer a l'encadenament.

Computadors vectorials a l'actualitat[modifica | modifica el codi]

A partir del 2015 la majoria de les CPU d'ús comú implementen arquitectures que compten amb instruccions per a una forma de processament de vectors amb múltiples conjunts de dades, tal com es mostra a la figura 2, normalment conegudes com SIMD (Single Instruction, Multiple Data). Els exemples més comuns inclouen instruccions MMXSSE i AVX d'Intel x86, NEON a arquitectures ARM, extensió VIS de Sparc i AltiVec de PowerPC.[11] Tècniques de processament de vectors també operen en el maquinari de les consoles de videojocs i en els acceleradors de gràfics o GPU's.[12] L'any 2000, IBMToshiba i Sony van col·laborar per a crear el processador Cell, que consisteix en un processador escalar i vuit processadors SIMD, que troben el seu ús en la PlayStation 3 de Sony entre d'altres aplicacions.[13]

Cas real de vectorització: ús d'instruccions vectorials de l'arquitectura x86[modifica | modifica el codi]

A continuació es mostra el codi ASM, resultat de compilar el codi Saxpy mostrat anteriorment, mitjançant el compilador GCC v6.1.0 amb opcions de vectorització, en un processador d'arquitectura x86 que posseeix el repertori d'instruccions SEE:

        xor     %rax,%rax               // neteja el registre %rax.
        movss   %xmm1, 0x200bcf(%rip)   // mou al registre %xmm1 el valor d'a.
        shufps  %xmm1, %xmm1, $0x0      // reparteix el valor d'a a cadascun dels blocs escalars del registre vectorial %xmm1.
bucle:  movaps  %xmm0, 0x601080(%rax)   // carrega 4 valors consecutius des de la posició de memòria amb index 0x601080+%rax (vector x), al registre %xmm0.
        mulps   %xmm0, %xmm1            // multiplica cadascun dels 4 elements escalars que conté el registre %xmm0 amb els 4 elements pertinents del registre %xmm1 i guarda el resultat al registre %xmm0.
        addps   %xmm0, 0x60acb0(%rax)   // suma cadascun dels 4 elements escalars que conté el registe %xmm0 amb els 4 elements pertinents, allotjats desde la posició de memòria 0x60acb0+%rax (vector y) i guarda el resultat al registre.
        movaps  %0x60acb0(%rax), %xmm0  // emmagatzema el contingut del registre %xmm0 a la posició de memòria %0x60acb0+%rax. 
        add     %0x10, %rax             // suma 16 unitats al valor actual de %rax per a indexar la càrrega dels registres a la següent iteració (4bytes x 4floats = 16)
        cmp     %rax, $0x9c40           // compara el valor del registre %rax amb el valor que conté la posició de memòria $0x9c40.
        jne     bucle                   // si encara no ha acabat el bucle, torna a executar les instruccions des de l'etiqueta bucle.

Cal destacar com el compilador ha seccionat el bucle, fent quatre vegades menys iteracions que en una versió de codi totalment escalar, ja que en cada registre vectorial caben quatre elements de tipus Float de 4 Bytes (els registres xmm de l'arquitectura x86 tenen una mida de 16 Bytes).

Vegeu també[modifica | modifica el codi]

Bibliografia i referències[modifica | modifica el codi]

  1. «Billion-transistor architectures». IEEE Computer, Setembre 1997, pàg. 46-48.
  2. Germain-Renaud, C., & Sansonnet, J.P.. Les ordinateurs massivement paralleles. (en francès). Armand Colin Editeur., 1993. 
  3. Hennessy, J.L., & Patterson, D.A.. Computer Architecture. A Quantitative Approach. (en anglès). Morgan Kaufmann Publishers., 1990. 
  4. «Pàgina oficial de Cilk Plus» (en anglès).
  5. «Exemples d'anotació vectorial amb Cilk Plus.» (en anglès).
  6. «Pàgina oficial del compilador GCC.» (en anglès).
  7. «Pàgina oficial del compilador ICC.» (en anglès).
  8. RUSSELL, R.M.. The CRAY-1 Computer System. (en anglès), 1978. 
  9. «Cyber documentation.» (en anglès). University of Kent.
  10. «3090 Processor Complex» (en anglès). IBM.
  11. Stewart, Josh An Investigation of SIMD instruction sets, 2005.
  12. NVIDIA’s Next Generation CUDA Compute Architecture, 2009.
  13. Hoefler, Torsten The Cell Processor -A short Introduction-, 2005.