Paralelismo al nivel de instrucciones

Arquitectura de Computadoras

M. C. Felipe Santiago Espinosa

Mayo de 2018

¿Qué es la segmentación o pipelining?

O Técnica para la generación de paralelismo en microprocesadores.

O Consiste en dividir la ejecución de una instrucción en etapas independientes, que pueden trabajar simultáneamente (se realiza un trabajo en cadena).

O En un instante determinado, el procesador está t rabajando sobre un número de instrucciones igual al número de etapas => paralelismo al nivel de instrucciones.

Segmentación

Tipos de caucesO Unifunción: ejecutan un único proceso.O Multifunción: pueden ejecutar varios procesos:

O Estáticos: en un instante determinado sólo pueden ejecutar uno.

O Dinámicos: pueden ejecutar simultáneamente varios procesos.

O Lineal: a cada etapa sólo le puede seguir otra etapa concreta.

O No lineal: se pueden establecer recorridos complejos de las etapas.

Aplicación de la segmentación:O A operaciones aritméticas:

O Ejecutan una o varias operaciones de la ALU.O Pueden ser l ineales (sumas) o no l ineales

(división). Las operaciones son no lineales porque incluyen ciclos.

O Los procesadores actuales incluyen varias ALU’s segmentadas y cada una se puede ocupar de diferentes operaciones.

O A ejecución de instrucciones:O Suelen ser cauces lineales.O Alguna de sus fases puede a su vez sub-

segmentarse (uso de una ALU segmentada para la fase de ejecución).

Cauce no-linealO Una tabla de reserva indica el orden en que trabajan

las etapas para cada tarea.

LatenciaO Número de ciclos que separan el inicio de dos

operaciones (distancia entre las entradas de dos elementos al cauce).

Latencia prohibida: Latencia con la que s e p ro d u c en colisiones (en el ejemplo, 1 es una latencia prohibida)

Latencia permitida: Latencia con la que no se produce colisión (en el ejemplo, 2 es una latencia permitida)

Ciclos de latenciaO Secuencia de latencias permitidas que se puede

repetir indefinidamente.O Ejemplo. Para la función B, se tiene que (1,4) es un ciclo

de latencia:

O ¿Cuál es el ciclo de latencia para la función A?

Arquitectura DLXO El DLX es un microprocesador RISC diseñado

por John Hennessy y David A. Patterson, los diseñadores principales de la arquitectura MIPS.

O El DLX es básicamente un MIPS revisado y simpli f icado con una arquitectura carga-almacenamiento de 32 bits.

O DLX fue pensado principalmente para propósitos educativos

Máquina básica

Máquina segmentada

Clasificaciones de dependenciasO Lectura después de Escritura (RAW, dependencia):

O Una instrucción genera un dato que otra posterior lee (la que se ha visto hasta ahora).

O Escritura después de Escritura (WAW, dependencia en salida):O Una instrucción escribe un dato que otra posterior ya

había escrito;O En una máquina segmentada simple ocurre sólo si se

permite que las instrucciones se adelanten unas a otras.

O Escritura después de Lectura (WAR, antidependencia):O Una instrucción modifica un valor antes de que lo lea

una instrucción anterior.O Tampoco ocurre en un cauce simple.

Instrucciones de mayor complejidad

O Problema: Si el repertorio básico se amplía, habrá instrucciones que tarden más en ejecutarse.O Ejemplo: una multiplicación y un desplazamiento

lógico.O Si el ciclo de reloj se ajusta a la más lenta, con

las rápidas (y con las demás etapas del cauce) se está perdiendo tiempo.

O Si el ciclo de reloj se ajusta a la más rápida, a las lentas no es suficiente con un ciclo.

O Solución: Se segmenta también la fase de ejecución.

Cauce multifuncional

Nuevo flujo de instruccionesO El flujo de instrucciones ahora es:

O Las instrucciones pasan por las fases IF e ID.O A continuación, cada instrucción pasa a la unidad

funcional que le corresponda para su ejecución.O Las instrucciones terminan el recorrido por su

unidad funcional y pasan por las fases MEM y WB.O Es necesario modificar la máquina:

O Añadiendo la tches entre las fases de las unidades funcionales.

O Posibilitando el flujo desde ID hasta cualquier unidad funcional.

O El control se complica.

Ejemplo de ocupaciónMULTD IF ID M1 M2 M3 M4 M5 M6 M7 MM WB

ADDD IF ID A1 A2 A3 A4 MM WB

LD IF ID EX MM WB

SD IF ID EX MM WB

O Se supone que las instrucciones no tienen dependencias entre sí.

O Las fases en cursiva indican cuándo se necesitan los datos.

O Las fases en negrita indican cuándo se generan los resultados.

Complicaciones de la multifunción

O Aumentan las posibilidades de dependencia (y por lo tanto de detenciones).O Algunas unidades funcionales están segmentadas y

pueden tener varias instrucciones en ejecución.O Diferentes unidades funcionales pueden estar activas

simultáneamente.O Las detenciones serán más largas, puesto que el cauce

es más largo (dependiendo de la unidad funcional).O Las instrucciones no tienen por qué terminar en orden:

O Puede haber dependencias WAW.O Puede haber varias instrucciones en la fase WB a la vez

(hay riesgo de conflicto estructural).O La buena noticia es que las antidependencias WAR no

pueden darse.

Ejecución multifuncional con dependencias

O Hay dependencias RAW de cada instrucción con la anterior. Esto implica detenciones (P : paro)

O Si sólo se tiene una memoria para instrucciones y datos, también hay dependencias estructurales.

Paralelismo al nivel de instrucciones

O La meta es reducir el CPI

CPI Segmentado = CPI Ideal +detenciones estructurales +detenciones por dependencia de datos +detenciones por riesgos de control

O El paralelismo dentro de un bloque es limitadoO El tamaño típico de un bloque es de 3 a 6

instrucciones.O Debe optimizarse a través de brincosO La clave para mejorar el rendimiento consiste en

eliminar las detenciones (o parones)

Técnicas a revisarO Planificación de instrucciones:

O Planificación estática: reordenación y desenrollo de bucles.

O Renombramiento de registros.O Planificación dinámica: Algoritmo de

Tomasulo.

O La predicción de saltos también ayuda a reducir los riesgos de control.

Reordenación de códigoO Consiste en reordenar las instrucciones para

eliminar detenciones.O Se debe tener cuidado con las dependencias.O Ejemplo: un programa que suma un escalar a

cada elemento de un arreglo de 1000 números en punto flotante:

for (i = 0; i < 1000; i = i + 1)x[i] = x[i] + s;

O Son operaciones puntuales, es decir, no hay dependencias entre iteraciones.

Reordenación de códigoO El código que correspondiente al bucle es:

bucle: ld f0,0(r1)addd f4,f0,f2sd 0(r1),f4subi r1,r1,8bnez r1,bucle

Reordenación de códigoO Consideremos las siguientes latencias:

Productor Consumidor Latencia

FP ADD FP ALU 3 ciclos

FP ADD Store 2 ciclos

Load FP ALU 1 ciclo

Load Store 0 ciclos

Load INT ALU 1 ciclo

INT ALU INT ALU 0 ciclos

O Con las latencias, la ejecución del bucle es:instrucción ciclo

bucle: ld f0,0(r1) 1detención 2addd f4,f0,f2 3detención 4detención 5sd 0(r1),f4 6subi r1,r1,8 7detención 8bnez r1,bucle 9retardo por brinco 10

O Tiempo de ejecución: 10 ciclos por iteración, 5 ciclos perdidos por riesgos (50%)

O Un cambio de orden elimina dos detenciones:

instrucción ciclobucle: ld f0,0(r1) 1

detención 2addd f4,f0,f2 3subi r1,r1,8 4detención 5sd 8(r1),f4 6bnez r1,bucle 7retardo por brinco 8

O Tiempo de ejecución: 8 ciclos por iteración, 3 ciclos perdidos por riesgos (37.5%)

O La ejecución es 1.25 veces más rápida.

Recargo por iteraciónO En cada iteración se debe:

O Leer un elemento del arregloO Sumar el escalarO Almacenar el resultado

O Al pasar de una iteración a otra se tiene un “costo” de 3 ciclos por recargo.O Incremento del contadorO Brinco

O El 37.5 % es el costo de tiempo por recargo en cada iteración

O Para reducir el costo por recargo es conveniente desenrollar el lazo.

Desenrollado de buclesO Se copia el cuerpo del bucle n veces para

trabajar sobre n elementos del arreglo en cada iteración.

O Cada iteración del nuevo bucle incluye n iteraciones del bucle original.

Bucle originalinstrucción ciclo

bucle: ld f0,0(r1) 1addd f4,f0,f2 3sd 0(r1),f4 6subi r1,r1,8 7bnez r1,bucle 9

Desenrollando 4 vecesinstrucción ciclo

bucle: ld f0,0(r1) 1addd f4,f0,f2 3sd 0(r1),f4 6ld f6,-8(r1) 7addd f8,f6,f2 9sd -8(r1),f8 12ld f10,-16(r1) 13addd f12,f10,f2 15sd -16(r1),f12 18ld f14,-24(r1) 19addd f16,f14,f2 21sd -24(r1),f16 24subi r1,r1,32 25bnez r1,bucle 27riesgo por el brinco 28

Mejora del rendimientoO Código original: 12 ciclos de reloj como un costo por

recargo en 4 iteraciones.

O Con el lazo desarrollado 4 veces: 3 ciclos de reloj como un costo por recargo.

O ¿Cuánto mejora la ejecución al desenrollar el lazo por 4 iteraciones sin emplear reordenamiento de instrucciones?

O Al tener más instrucciones en cada iteración, el reordenamiento ayuda a anular detenciones.

instrucción ciclobucle: ld f0,0(r1) 1

ld f6,-8(r1) 2ld f10,-16(r1) 3ld f14,-24(r1) 4addd f4,f0,f2 5addd f8,f6,f2 6addd f12,f10,f2 7addd f16,f14,f2 8sd 0(r1),f4 9sd -8(r1),f8 10subi r1,r1,32 11sd 16(r1),f12 12 ; 16 – 32 = -16sd 8(r1),f16 13 ; 8 – 32 = -24bnez r1,bucle 14riesgo por el brinco 15

O ¿Cuánto mejoró el rendimiento al combinar las dos técnicas?

Desenrollo de buclesO En el ejemplo anterior, el bucle sólo va a iterar

250 veces.O En general, el número de iteraciones del bucle

original (m) debe ser un múltiplo del factor de desenrollo (n).

O Si ‘m’ no es múltiplo de ‘n’, el bucle original se remplaza por dos consecutivos:O El primero, con cuerpo igual al original, se ejecuta

m mod n veces.O El segundo, con cuerpo desenrollado n veces, se

ejecuta m/n veces (división entera).

Renombre de registros

O Se trata de una técnica para eliminar dependencias “falsas”.

O Básicamente consiste en utilizar más registros de los que el programador consideró.

O El renombre de registros puede ser un paso previo al reordenamiento.

Renombre de registrosO En el siguiente código aparentemente hay

más dependencias de las reales:

1 or r5,r0, cte2 ld r6,0(r5)3 ld r8,8(r5)4 ld r9,16(r5)5 ld r7,24(r5)6 add r1,r8,r97 add r8,r9,r78 st 0(r8),r19 ld r8,0(r6)

Renombre de registrosO En el siguiente código aparentemente hay

más dependencias de las reales:

1 or r5,r0, cte2 ld r6,0(r5)3 ld r8,8(r5)4 ld r9,16(r5)5 ld r7,24(r5)6 add r1,r8,r97 add r8,r9,r78 st 0(r8),r19 ld r8,0(r6)

Renombre de registros

or r5,r0, cteld r6,0(r5)ld r8,8(r5)ld r9,16(r5)ld r7,24(r5)add r1,r8,r9add r8,r9,r7st 0(r8),r1ld r8,0(r6)

or f1,r0, cteld f2,0(f1)ld f3,8(f1)ld f4,16(f1)ld f5,24(f1)add f6,f3,f4add f7,f4,f5st 0(f7),f6ld f8,0(f2)

r5 f1

r6 f2

r8 f3

R9 f4

r7 f5

r1 f6

r8 f7

r8 f8

Renombre de registros

1 or f1,r0, cte2 ld f2,0(f1)3 ld f3,8(f1)4 ld f4,16(f1)5 ld f5,24(f1)6 add f6,f3,f47 add f7,f4,f58 st 0(f7),f69 ld f8,0(f2)

Renombre de registros

Planeación dinámicaO El reordenamiento para la ejecución se realiza por

hardware.

O O b j e t i vo : e l i m i na r de tenc i o n e s i n n e c e s a r i a s . Consideremos el siguiente código:

divd f0,f2,f4addd f10,f0,f8subd f12,f8,f14

O La segunda instrucción no se puede ejecutar hasta que primera genere f0.

O Esto impide que se ejecute la tercera, aunque tenga todos sus datos preparados => detención innecesaria.

Planeación dinámicaO Se pretende que una instrucción, con sus operandos

disponibles, no se quede paralizada si tiene la posibilidad de ejecutarse, aunque otra instrucción previa esté bloqueada.

O Para ello, la fase ID se divide en dos:O Lanzamien to : Decod i f i cac ión y comprobac ión de

dependencias estructurales (en orden del programa).O Lectura de operandos: Espera por operandos; cuando están

listos, se leen y se pasa a ejecutar (no necesariamente respetando el orden del programa)

O De esta forma, una instrucción puede adelantar a otra que esté bloqueada por dependencias.

O La idea es que el código se “reordena” solo, de forma dinámica y según la situación del cauce.

Planeación dinámicaO Ventajas:

O La reordenación se realiza en forma dinámica.O El compilador es más sencillo.O Además, la reordenación en t iempo de

compilación sólo es válida para el cauce concreto con el que se trabaja: ahora es más general.

Planeación dinámicaO Desventajas:

O El hardware es más complejo.O Ahora se pueden dar las dependencias WAR

y WAW.O Hay que tener cuidado con las excepciones

(interrupciones).

Algoritmo de TomasuloO Robert Tomasulo IBM 360/91 (1967).O Características “malas” de la computadora IBM

360:O Sólo 4 registros de punto flotante en doble

precisión.O Accesos a memoria lentos.O Grandes atascos en punto flotante.

O Tomasulo diseñó un algoritmo para contrarrestar estas características “malas”.

O El algoritmo de Tomasulo rastrea cuándo los operandos de una instrucción están listos para minimizar detenciones por dependencias RAW.

O Introduce el renombrado de registros para minimizar detenciones por dependencias WAW y WAR.

O La IBM 360/91 contaba con dos unidades de punto flotante: una para sumas y otra para multiplicaciones.

O En estaciones de reserva se mantiene a las instrucciones mientras esperan ingresar a la unidad de punto flotante que corresponda.O La del sumador de 2 niveles y la del multplicador

de 3 niveles.

O La distribución de los resultados se efectúa directamente por medio del bus común de datos (CDB), sin necesidad de pasar por los registros.

O Con la estructura de la máquina, las fases del cauce son:

O Lanzamiento.O Ejecución.O Almacenamiento.

Algoritmo de Tomasulo

Lanzamiento:O Se toma una instrucción de la cola.O Si hay espacio en su estación de reserva, se coloca

ahí.O Si los operandos están en el banco de registros, se

envían a la estación de reserva.O Si no hay espacio en la estación de reserva se

produce una detención por riesgo estructural.O Si los operandos no están en el banco de registros,

se indican las unidades funcionales que los producen en Qj y Qk.O Esta operación introduce un renombramiento de

registros implícito.

Ejecución:O Si falta algún operando, se vigila el CDB.O Cuando están listos los dos, se ejecuta la

operación.

Almacenamiento:O Cuando termina la ejecución, los resultados

se ponen en el CDB. De ahí van a los registros y a las UF que los esperen.

Renombrado de registrosO El renombrado de registros queda implícito y oculto:

O Hay 11 fuentes de datos:O 6 entradas del buffer de cargas (loads),O 3 entradas en la estación de reserva de suma yO 2 entradas en la estación de reserva de multiplicación.

O A cada operando en la fase de lanzamiento se le da un identificador de 4 bits, que indica qué fuente proporciona el dato. O (0 si ya está listo)

O De esta manera se extiende el número de registros de 4 a 11.

Estaciones de reservaO Cada entrada en las estaciones de reserva contiene

los siguientes campos:

O Op: operación que se tiene que ejecutar.O Qj,Qk: La estación de reserva que producen los

operandosO (0 si listo o no necesario).

O Vj,Vk: valor de los operandos.O Ocup: si la entrada está ocupada.

O Sólo es válida la información de Q o V (no ambas a la vez).

Registros y buffers para almacenamiento

O Información que se almacena en cada registro y en los buffers de almacenamiento (stores):O Qi: estación de reserva que genera el valor

que se enviará a memoria.O V: valor que se enviará a memoria.

Algoritmo de Tomasulo (Ejemplo)

O Se analizará la ejecución del siguiente código:Ld f6,34(r2)Ld f2,45(r3)Multd f0,f2,f4Subd f8,f6,f2Divd f10,f0,f6Addd f6,f8,f2

O Suponiendo las siguientes latencias:ld, sd: 3 ciclosaddd, subd: 2 ciclosmultd: 5 ciclosdivd: 19 ciclos

Algoritmo de Tomasulo (Ejemplo)

O Punto de partida: el código se encuentra en esta situación:

¡Ojo! Esta información no se encuentra físicamente en ninguna tabla. Se muestra para facilitar la comprensión.

Estado del procesador:O Estaciones de reserva:

O Estado de los registros:

Avance en la ejecuciónO Cuando multd está lista para escribir:

O Note que hay una detención estructural del addd por almacenamiento simultáneo con el multd.

O La suma puede terminar adelantándose a la instrucción divd.

Estado del procesador:O Estaciones de reserva:

O Estado de los registros:

Algoritmo de Tomasulo:Un ejemplo basado en un lazo

O Para entender la capacidad del algoritmo de Tomasulo de eliminar riesgos WAW y WAR a través del renombrado dinámico de registros es conveniente analizar un programa con un lazo.

O La secuencia multiplica los elementos de un arreglo por un escalar en F2:

O Analice la ejecución del código y notará que con la predicción de brincos tomados el lazo será desenrrollado dinámicamente. (pág. 102 de Computer Architecture: A Quantitative Approach Fourth Edition)

Tomasulo en procesadores actuales

O En general los micros con planificación dinámica son capaces de emitir y ejecutar varias instrucciones a la vez y su arquitectura es muy potente.

O Uno de los primeros microprocesadores con planif. dinámica fue el Motorola PowerPC 620 (1995). Es un ejemplo muy bueno: su cadena (4 fases: IF ID IS EX) y arquitectura es muy similar al algoritmo clásico Tomasulo. Poseía pocas estaciones de reserva (R.S., reserve stations) por cada UF.O Dos unidades enteras simples (1 ciclo).O Una unidad entera compleja (3 a 20 ciclos) para MULT y DIV

enteras.O Una unidad de carga-almacenamiento (1 ciclo si acierta en caché).O Una unidad de punto flotante (31 ciclos DIVFP, 2 ciclos ADDFP y

MULTFP).O Y una unidad de saltos, que actualiza una tabla en caso de fallo de

predicción.

Power PC 620 (similar al Tomasulo clásico)

O Pentium Pro (su parte INT es idéntica al P.II, P.III y similar al P4). Su cadena es de 11 fases. Posee 40 R.S. comunes a todas las UF:O Dos unidades enteras (1 ciclo). Una de ellas se

usan para saltos (actualiza BTB en caso de fallo de predicción). La otra se usa también para multiplicaciones y divisiones enteras.

O Dos unidades FP para multiplicaciones y divisiones de punto flotante. Realmente solo puede empezar en el mismo ciclo una de ellas.

O Una unidad de carga (1 ciclo).O Una unidad de almacenamiento más compleja.

O MIPS R10000 (similar a los actuales). Posee 16 R.S. para INT, 16 para FP y 16 para Ld-St:O Dos unidades enteras (una también sirve para

saltos, y la otra para MULT INT).O Una unidad para cálculo de direcciones de acceso

a memoria (para carga-almacenamiento).O Una unidad de punto flotante simple (sólo para

ADD-FP).O Una unidad de punto flotante compleja (DIV, MULT,

SQRT-FP).O Las unidades funcionales suelen ser

segmentadas excepto en las divisiones.

PLANIFICACIÓN ESTÁTICA VS. DINÁMICARESUMEN: PROS Y CONTRAS

PLANIFICACIÓN ESTÁTICA PLANIFICACIÓN DINÁMICA

Menos Hardware Complicación del hardware

Compilador más difícil El compilador no optimiza

El compilador debe conocer la arquitectura Transparente al usuario

Dependencia: compilación-rendimiento

El hardware extrae el rendimiento que puede

El tamaño del código puede crecer ⇒ más fallos de caché Tamaño de código no se toca

El compilador no puede conocer los valores de los registros (dir. acceso)

En tiempo de ejecución se conocen los valores de registros (dir. acceso)

Puede necesitar muchos registros de usuario

No necesita muchos registros de usuario (son internos, ocultos al usuario; ej. CISC)

ConclusiónO Dos Tendencias:

O Esta disyuntiva se está dando actualmente con microprocesadores avanzados, aunque cada vez se traspasa más funcionalidad al hardware.

Hw Simple y Compilador Complejo vs. Hw Complejo y

Compilador Simple