1 Motivación Muy importantes 1) Dificultades en obtener (y gestionar) ciclos de reloj muy cortos 2) Límites en el patrón de localidad de los datos Importantes 3) Lentitud en la decodificación de instrucción Solución: Introducir el conocimiento “a priori” de que muchas aplicaciones científicas trabajan con vectores -> Arquitecturas de carácter específico. - Disminución en los riesgos de control (está implícito en designar una instrucción como “vectorizable”

2 Arquitectura Vectorial Propiedades Clave: w Las instrucciones utilizan operandos escalares y vectoriales w Normalmente, redundancia de recursos para potenciar paralelismo entre UFV’s

3 Procesadores vectoriales Características de las máquinas vectoriales wInstrucciones que operan sobre vectores (arrays lineales de números FP) wSistema de Memoria: bancos de memoria entrelazados de forma peculiar El acceso a vectores de tamaño grande cuyas componentes tienen direcciones no consecutivas hacen ineficiente el uso de una cache. Características de las instrucciones vectoriales wPermiten gran nivel de segmentación La operación se realiza de forma independiente sobre cada com- ponente, sin dependencias de datos. wCada instrucción vectorial es equivalente a un bucle. Ventaja añadida: normalmente se evita examinar el salto del bucle. Disminuye el tamaño del código. wInstrucciones de carga vectoriales Leer un vector en memoria, cuya componentes están en direcciones de memoria que siguen un patrón de acceso conocido, permite ob- tener una componente por ciclo, una vez transcurrido el número de ciclos determinado por la latencia de la Memoria.

4 Clasificación según almacenamiento de los operandos wMáquinas vectoriales con registros Todas las instrucciones vectoriales (menos cargas) operan con vectores almacenados (por instrucciones de carga previas) en registros (vectoriales). Todas las máquinas actuales son de este tipo (CRAY,CONVEX, etc.) wMáquinas vectoriales memoria-memoria Todas las instrucciones vectoriales leen sus operandos y escriben los resultados en Memoria. Fueron de este tipo las primeras máquinas vectoriales (CDC) Procesadores vectoriales

5 Arquitectura vectorial básica (DLXV. Basada en CRAY-I) Registros vectoriales 8 Rg. Vectoriales, cada uno de 64 componentes (dobles palabras) El Banco de Registros Vectoriales (BRV) tiene dos puertos de lectura y uno de escritura Registros escalares 32 Rg. Propósito general y 32 específicos FP. Unidades Funcionales 5 UF completamente segmentadas Unidad de Control Detecta riesgos estructurales y dependencias

6 Procesadores vectoriales Memoria principal Carga/almacenamiento vectorial suma/resta FP multiplicación FP división FP Entero Lógico Registros escalares Registros vectoriales

7 Multiprocesador Vectorial con Memoria Compartida P 1 P 2 P N SINCRONISMO PROCESADORES REGISTROS MEMORIAS PRIVADAS CACHE MEMORIA COMUN (INSTRUC. + DATOS)

8 Multiprocesador Vectorial con Memoria Compartida PROBLEMA: [Paralelizar [Balanceo de carga [Sincronización/Comunicación [Coherencia de la información [Límite tecnológico para N, en función del nivel de memoria que comparten [El compilador no ve bien: ä Niveles de memoria ä Privada/Compartida ä Comunicación/Sincronización

9 Procesadores vectoriales Arquitectura Vectorial básica Instrucciones vectoriales Notación: ADDV, ADDSV El resultado de una instrucción vectorial siempre es un vector Operación: en cada ciclo lee dos componentes de cada operando vector y escribe una componente resultado en el BRV Instrucciones vectoriales en DLXV InstrucciónOperandosFunción Vectorial ADDVV1,V2,V3Suma elementos de V2 y V3, después pone cada resultado en V1. ADDSVV1,F0,V2Suma F0 a cada elemento de V2, después pone cada resultado en V1. SUBVV1,V2,V3Resta elementos de V3 desde V2, después pone cada resultado en V1 SUBVSV1,V2,F0Resta F0 de los elementos de V2, después pone cada resultado en V1 SUBSVV1,F0,V2Resta elementos de V2 de F0, después pone cada resultado en V1 MULTVV1,V2,V3Multiplica elementos de V2 y V3, después pone cada resultado en V1 MULTSVV1,F0,V2Multiplica F0 por cada elemento de V2, después pone cada resultado en V1 DIVVV1,V2,V3Divide elementos de V2 por V3, después pone cada resultado en V1. DIVVSV1,V2,F0Divide elementos de V2 por F0, después pone cada resultado en V1 DIVSVV1,F0,V2Divide F0 por elementos de V2, después pone cada resultado en V1 LVV1,R1Carga registro vectorial V1 desde memoria comenzando en la dirección R1

10 InstrucciónOperandos Función Vectorial SVR1,V1Almacena registro vectorial V1 en memoria comenzando en la dirección R1 LVWSV1,(R1,R2)Carga V1 desde la dirección en R1 con separación en R2, p.ej.,R1+i. R2 LVIVl, (R1+V2)Carga V1 con un vector cuyos elementos están en R1+V2(i), es decir, V2 es un índice SVI(R1+V2),V1Almacena V1 con un vector cuyos elementos están en R1+V2(i), es decir, V2 es un índice CVIV1,R1Crea un vector de índices almacenando en V1 los valores 0, 1. R1, 2. R1, …, 63. R1 en V1 SVWS (R1,R2),V1Almacena V1 desde dirección en R1 con separación en R2, p.ej.,Rl+i. R2 S_VV1, V2Compara (EQ, NE,GT,LT,GE,LE) los elementos de V1 y V2. Si la condición es S_SVcierta pone un 1 en el bit correspondiente del vector: en cualquier otro caso pone 0. Pone el vector de bits resultante en un registro de máscara vectorial (VM). La instrucción S_SV realiza la misma comparación pero utilizando un valor escalar como operando. POPR1,VMCuenta los ls en el registro de máscara vectorial y almacena la cuenta en R1 CVMPone todo el registro de máscara vectorial a 1. MOVI2SVLR,R1Transfiere el contenido de R1 al registro de longitud vectorial MOVS2IR1,VLRTransfiere el contenido de registro de longitud vectorial a R1. MOVF2SVM,F0Transfiere el contenido de F0 al registro de máscara vectorial MOVS2F0,VMTransfiere el contenido del registro de máscara vectoria a F0

11 (Parallel) vectorcomputers SM-MIMD Computer(ns)CPUsCPU (Mflop/s)(Mflop/s) peak totalpeak single max clock cycle Cray 24.1 4 488 1952 Cray 32.016100016000 Cray Y-MP6.0 8 333 2667 Cray C904.016100016000 Fujitsu VP26004.0 14000 Hitachi S-820/804.0 12000 NEC SX-32.9 4550022000

12 Procesamiento Escalar vs. Vectorial Multiplicación Matricial DO i = 1,n DO j=1,n DO k= 1,n C(i,j)= C(i,j)+A(i,k)*B(k,j) ENDDO Código Escalar … loadf f2, (r2); load C(i,j) loop: loadf f3, (r3); load A(i, k) loadf f4, (r4); load B(k,j) mypf f3,f3,f4; A(i,k)*B(k,j) addf f2,f2,f3; update C(i,j) store f2 (r2); store C(i,j) addi r1,r1,#4; incr. ptr. A(i,k+1) addi r3,r3,#4; incr. ptr. B(k+1,j) bnz r1,loop:; branch to loop if (r1/4).eq. n)... j i C A B j i cij Aik Bkj

13 Procesamiento Escalar vs. Vectorial Multiplicación Matricial DO i = 1,n DO k=1,n DO j= 1,n C(i,j)= C(i,1:n)+A(i,k)*B(k,j) ENDDO Código Vectorial … LV V2, (r2); load A(i,k) LV V3,(r3); load B(k, j) MULTV v3,v2,v3; A(i,k)*B(k,j)... j i C A B j i cij Aik Bkj

14 Procesadores vectoriales Control de la longitud del vector - Longitud natural: tamaño de los registros vectoriales (MVL) - Registro de longitud vectorial (VLR): contiene la longitud del vector actual (valor en VLR MVL) Vectores de tamaño MVL: poner tamaño en VLR. Las instruccio- nes vectoriales toman este tamaño de vector. Vectores de tamaño n MVL:seccionamiento - Seccionamiento (strip mining) Técnica de generación de código con operaciones vectoriales de tamaño menor o igual que MVL n mod MVL MVL  n/(MVL)  veces < > < Código de DAXPY para un vector de tamaño n > MVL ini=1; VLR= (n mod MVL); for (i=0; i n/MVL;i++) { for (j=ini;j ini+VLR-1) {Y(j)=a*X(j)+Y(j) ini=ini+VLR; VLR=MVL; } < <

15 Procesadores vectoriales Ejemplo de código vectorial Código vectorial que traduce un bucle (S/D)AXPY (simple/doble precisión A por X plus Y): For (i=1, i

16 Código DLXV para DAXPY LDF0,a; carga escalar a LVV1,Rx; carga vectorX MULTSVV2,F0,V1; multiplicación vector-escalar LVV3,Ry; carga vector Y ADDVV4,V2,V3; suma SVRy,V4; almacena el resultado Ventajas del código vectorial Se buscan 6 instrucciones, frente a más de 600. Diagrama temporal Procesador escalar: técnicas desenrrolle bucles o segmentación software? Procesador vectorial DLXV T(n)= tiempo para completar una operación vectorial de longitud n. T arranque = profundidad de la segmentación de la UF V iniciación = 1 si UF totalmente segmentada T(n) = T arranque + n · V iniciación

17 Ejercicio Sea la siguiente tabla de penalizaciones de arranque en DLXV con todas las unidades funcionales completamente segmentadas: Suma vectorialPenalización de arranque = 6 Multiplicación vectorialPenalización de arranque = 7 División vectorialPenalización de arranque = 20 Carga vectorialPenalización de arranque = 12 (Adicionalmente, el tiempo consumido en escribir y después leer el contenido de un registro es de 4 ciclos. Encontrar: 1) Diagrama temporal del código DAXPY (suponiendo operaciones vectoriales no encadenadas. 2) Velocidad sostenida y número efectivo de operaciones de punto flotante por ciclo de reloj para la secuencia: MULTV V1,V2,V3 ADDVV4,V5,V6

18 Procesadores vectoriales Modelo del rendimiento de un bucle vectorizado (sin encadenan.) Ejemplo: El bucle For (I=1; i 200,i++) A(i)=s*B(i) se transforma en el siguiente código vectorial: _> ADDIR2,R0,#1600; no bytes en vector ADDR2,R2,Ra; fin de vector A ADDIR1,R0,#8; longitud de seccionamiento MOVI2SVLR,R1; longitud de vector ADDIR1,R0,#64; longitud en bytes ADDIR3,R0,#64; longitud de vector ; de otras piezas. LVV1,Rb; carga B MULTVSV2,V1,Fs; vector · escalar SVRa,V2; almacena A ADDRa,Ra,R1; siguiente sección de A ADDRb,Rb,R1; siguiente sección de B ADDIR1,R0,#512; longitud total de vector ; (en bytes) MOVI2SVLR,R3; inicializa longitud a 64 SUBR4,R2,Ra; en el fin de A? BNZR4,LOOP; si no, volver atrás BASE BUCLE

19 Podemos distinguir tres componentes del tiempo de ejecución: T base : es el coste temporal del código de inicialización y parámetros de seccionamiento. Consta únicamente de instrucciones escalares y se considera una sola vez. T bucle : coste de ejecución del código escalar para inicializar el tamaño de cada sección del vector, incrementar los contadores y ejecutar cada salto del bucle del secc. T arranque : tiempo de arranque de cada iteración del secc. (suma de los costes de arranque de las instrucciones vectoriales) T elemento : tiempo en producir un elemento resultado de la secuencia vectorial ignorando los costes de arranque (normalmente un ciclo por cada instrucción vectorial del cuerpo del bucle) En el ejemplo, T elemento = 3 y T arranque = 12(LV) + 4 + 7 (MUL) + 4 La detención de 4 ciclos entre instrucciones dependientes son necesarios para escribir y luego leer los operandos.

20 Procesadores vectoriales Medidas de rendimiento en procesadores vectoriales Velocidad en MFLOPS = nº OPF por seg./10 6 R(n) = Velocidad en MFLOPS sobre un vector de longitud n Relación entre R(n) y T(n) en un bucle vectorizable R(n) = (nº OPF por iteración *n/T(n) * t ciclo ) * 10 -6 = (nº OPF por iteración * frecuencia / (T(n)/n)*10 -6 T (n)/n: nº ciclos por iteración R  = lim R(n) para n ->  N 1/2 = min { n/R(n) _ R  / 2 } N v = min { n/velocidad vectorial _ velocidad escalar } > > Ejemplo: Rendimiento de un bucle SAXPY (encadenamiento, MVL = 64 y frecuencia de 80 MHz) Código vectorial LVV1, Rx; carga el vector x MULTSVV2,S1,V1; vector  escalar-encadenado a LV X LVV3,Ry; carga el vector Y ADDVV4,V2,V3; suma aX + Y, encadenado a LV Y SVRy,V4; almacena el vector Y

21 Cálculo de T (m) con encadenamiento OperaciónComienza enCompleta en Comentarionúmero de reloj LV V1, Rx012+64=76Latencia simple MULTV a,V112+1=1313+7+64=84Encadenada a LV LV V2, Ry76+1=7777+12+64=153Comienzan después del pri- mer LV hecho (contención de memoria) ADDV V3,V1,V277+1+12=9090+6+64=160Encadenada a MULTV y LV SV Ry,V3160+1+4=165165+12+64=241Debe esperar en ADDV: no enca- denado (contención de memoria) T(n) = 10 + [n/64] * (15+49)+3n; pero [n/64] _ n/64 + 1, luego T(n) _ 4n +74; R(n) = 2*80*n/4n + 74; R  = 2*80/4= 40 MFLOPS; Si n < 64 T(n) = 3n + 74; para calcular N 1/2 debemos utilizar este valor deT(n). Por tanto R(n)= 160 n/3n + 74 > 20 --> n > 14,8, es decir n 1/2 = 15; Para calcular N v debemos estimar el tiempo de una iteración escalar: 10 + 12+ 12 + 7+ 6 = 47; T(n) N v = 2 < <

22 Procesadores vectoriales Medidas de rendimiento en procesadores vectoriales Rendimiento de SAXPY en DLXV con algunas mejoras Más canales de acceso a memoria (CRAY X-MP tiene 3) T arranque para el caso de 3 canales OperaciónComienza enCompleta en Comentarionúmero de reloj LV V1, Rx012+64=76Latencia sencilla MULTV a,V112+1=1313+7+64=84Encadenado a LV LV V2, Ry22+12+ +64=78Comienza inmediatamente ADDV V3,V1,V213+1+7=2121+6+64=91Encadenado a MULTV y LV SV Ry,V321+1+6=2828+12+64=104Encadenado a ADDV En este caso T elemento = 1 y resulta Por ejemplo: T 66 = T base + [ ] · T bucle + T elemento ) + 66 · T elemento T 66 = 10 + 2 ·(15+40)+66 · 1 = 186 66 64

23 Emisión de instrucciones vectoriales más flexibles Permitir que una operación vectorial comience a utilizar una UF antes de que se haya completado otra operación anterior: el coste de arranque solo se conta- biliza una vez. Mejora el rendimiento para vectores largos. Ejemplo: SAXPLY en DLXV con 2 canales más de memoria y emisión flexible que Permita solapamiento costes de arranque y seccionamiento. Como T n = n + 40 + 10 + 15 = n + 65 lim = lim = 1 T n n n +65 n n ->  R  = = 160 MFLOPS 2· 80 MHz 1

24 Procesadores vectoriales Modelo del rendimiento de un bucle vectorizado (sin encadenam.) T bucle y T base se establecen experimentalmente porque el código escalar correspon- diente puede solaparse con código vectorial: 15 y 12 ciclos respectivamente Tiempo total T(n) de ejecución de una secuencia vectorial de tamaño n será T n = T base + · (T bucle + T arranque ) + n · T elemento n MVL y en el caso del ejemplo T 200 = 10 + (4) ·(15 + T arranque ) + 200 · 3 T 200 = 10 + 4 · (15 + T arranque ) + 600 = 670 + 4 · T arranque Modelo del rendimiento de un bucle vectorizado (encadenamiento) Los Registros Vectoriales se tratan como un grupo de registros individuales. Permite el adelan- tamiento: una instrucción vectorial puede comenzar cuando las componentes individuales de su operando vectorial estan disponibles (cortocircuito) No encadenada 7 64 46 MULTV ADDV Total = 145 Encadenada 6 64 ADDV 7 64 MULTV Total = 77