ARQUITECTURA DE SISTEMAS PARALELOS 1 BOLETÍN DE EJERCICIOS. TEMA 2: DEPENDENCIAS DE DATOS.

1. Para un DLX que resuelve los saltos en ID, tiene todas las capturas adelantadas posibles (bypass) y escribe los operandos en el primer semiciclo de WB y los lee en el segundo de ID, se pide:

a) Construir una tabla que calcule el número de ciclos de bloqueo para instrucciones enteras consecutivas con dependencia real. Poner en la ordenada las fases que pueden generar el dato (el valor del registro de destino) y en abscisa las fases que lo leen (el mismo valor de algún registro fuente), indicando también los tipos de instrucciones que se corresponden con las fases de abscisas y ordenadas.

b) Indicar cuáles serían los ciclos de bloqueo si las instrucciones que tiene la dependencia no son consecutivas, sino que están separadas por k (k>0) instrucciones sin ningún tipo de dependencia.

NOTA: este problema está propuesto en la segunda práctica de Arquitectura de Sistemas Paralelos 1, de 4º Ingeniería Informática de la Universidad de Sevilla.

2. Sea el siguiente fragmento de código, donde R2 apunta inicialmente al último elemento de un array de diez enteros, y donde la variable princ_array apunta al principio de tal array:

bucle: LW R1, 0(R2) SUBI R1, R1, #1 SW 0(R2), R1 SUBUI R2, R2, #4 SLTI R8, R2, princ_array BEQZ R8, bucle

Suponiendo que todos los accesos a caché aciertan, calcular para un DLX: a) Dar una posible traducción del código a un lenguaje de alto nivel.

b) Mostrar con flechas todas las dependencias reales y antidependencias del código. Explicar por qué afectarán a los siguientes apartados.

c) Mostrar el diagrama de ejecución en cadena de las fases para un DLX que no tiene ningún tipo de captura adelantada (bypass), suponiendo sólo que la escritura de registros de la fase WB se realiza en el primer semiperiodo y la lectura de ID en el segundo. Supóngase que en cualquier salto se congela la cadena y que se resuelve en dirección de destino y condición en la fase ID. Hallar el CPIbloqueo del código.

d) Mostrar el diagrama de ejecución en cadena de las fases para un DLX que tiene todas las capturas adelantadas posibles (bypass). Supóngase que cualquier salto utiliza la apuesta por no tomado y que se resuelve en la fase ID. Hallar el CPIbloqueo del código y la aceleración entre ésta ejecución y la del apartado anterior.

3. Con el objeto de acelerar el reloj, una versión acelerada del DLX encadenado básico, denominada DLXACEL, implementa las etapas siguientes:

IF1 IF2 ID1 ID2 EX1 EX2 WB • IF1, IF2: buscan en caché de instrucciones.

• ID1: empieza decodificación, accede a registros, resuelve saltos completamente (SALTOS).

• ID2: termina decodificación, calcula dirección efectiva de instrucciones de acceso a memoria.

• EX1: empieza y termina instrucciones ALU simples (ALUSI), como todas las comparaciones (SET) y las lógicas. Empieza instrucciones complejas (ALUCO) como las ADD, SUB, MULT etc. Empieza acceso al caché de datos.

• EX2: termina las ALUCO. Termina acceso al caché de datos.

• WB: escribe en fichero de registros.

Se pide: Detectar todos los bloqueos de datos por dependencia real entre dos instrucciones consecutivas de cualquier tipo (ALUCO, ALUSI, LD, ST, SALTOS), suponiendo que existen todos los caminos de desvío (bypass) posibles. Se puede calcular creando una tabla con la latencia en ordenadas y la lectura de datos en abscisas. ¿Qué parejas de instrucciones tendrán bloqueos si la fase EX2 no recibe entradas de bypass? NOTA: este problema ha sido tomado del examen del primer cuatrimestre de Arquitectura de Sistemas Paralelos 1, de 4º Ingeniería Informática de la Universidad de Sevilla.

ARQUITECTURA DE SISTEMAS PARALELOS 1 BOLETÍN DE EJERCICIOS. TEMA 2: DEPENDENCIAS DE DATOS.

SOLUCIONES

1 SOLUCIÓN: e) Para resolver este problema hemos de tener en cuenta que en un procesador encadenado, el número de ciclos y el número de

instrucciones que se ejecutan son el mismo, mientras que CPI=CPIideal=1. Eso quiere decir que, ante la existencia de una dependencia real, el número de ciclos de bloqueo cuando la fase de generación del dato (el valor del registro de destino) y la de lectura (el uso del valor del mismo registro como fuente) es la misma, es cero. Esto es evidente ya que el desvío permite capturar en el ciclo justo el dato, como se representa en el siguiente cronograma genérico, donde el desvío se representa por una flecha doble:

Instrucción que genera dato en la fase Fj F1 F2 … Fj … Fn Instrucción que lee dato en la misma fase Fj F1 F2 … Fj … Fn

Sin embargo si la instrucción primera genera el dato en la fase posterior a la fase en que la segunda instrucción necesita el dato, habrá que introducir tantos ciclos de bloqueo como sea esa diferencia, a pesar de que se disponga del desvío necesario entre ambas fases. En el siguiente cronograma se dibujan los dos ciclos de bloqueo debido a una generación en la fase Fj+1, y una lectura en la Fj-1, con el desvío como una flecha doble:

Instrucción que genera dato en la fase Fj+1 F1 … Fj-2 Fj-1 Fj Fj+1 … … Instrucción que lee dato en la misma fase Fj-1 F1 … Fj-2 ⎯ ⎯ Fj-1 Fj

Contrariamente, si se genera en cualquier fase anterior, el número de ciclos de bloqueo será evidentemente cero, ya que el valor necesitado está disponible incluso antes.

Para medir el retraso en el cálculo del dato de la instrucción que lo genera, se suele trabajar con:

• La duración de la fase EX menos 1, si el dato se genera al final de la fase EX.

• O como la diferencia de fases entre la fase que lo genera y la EX.

Con esa definición las instrucciones ALU generan un dato con un retraso de 0 ciclos; las de carga, con 1; etc.

Por otra parte, la fase en la instrucción que lee el dato lo necesita se suele denominar “emisión de la instrucción”. Así las instrucciones ALU tienen su emisión en EX, los saltos en ID, etc. Algunas instrucciones necesitan dos operandos en dos fases distintas, por ejemplo las de almacenamiento necesitan el registro base en EX y el dato que se va a almacenar en MEM.

Entonces según lo expuesto anteriormente, la tabla pedida deberá tener en la diagonal principal cero ciclos de bloqueo, dado que en ella la generación y emisión se hace en la misma fase. Según se vaya retrasando la generación (mayor retraso), es decir al bajar una casilla, se irá incrementando en uno el número de ciclos de bloqueo. También según se vaya adelantado la emisión de la instrucción se irá añadiendo un ciclo de bloqueo, es decir al irse desplazando una casilla a la izquierda. El resultado se expone en la siguiente tabla, donde la diagonal principal se ha sombreado:

Fase de emisión

Fase de

generación (retraso)

ID

EX

MEM

WB

ID (-1) 0 0 0 0

EX (0) 1 0 0 0

MEM (1) 2 1 0 0

WB (2) 3 2 1 0

Fase posterior a WB (3) 4 3 2 1

Número de ciclos de bloqueo de datos

Por último, falta clasificar la generación (retraso del dato generado) y la emisión de las instrucciones del DLX. En la siguiente tabla se han resumido éstas:

Tipo de Instrucción Genera el dato Retraso Emisión

ALU EX 0 EX

Carga MEM 1 EX (registro base)

Almacenamiento No genera - EX (registro base)

MEM (dato almacenado)

Salto condicional No genera - ID (registro de condición)

Para el DLX entero la tabla de ciclos de bloqueo para las distintas instrucciones sería:

Emisión

Instrucciones

Instrucciones

(Fase de generación)

ID

Saltos

EX

Cargas (Reg base)

Almac. (Reg base)

ALU

MEM

Almac. (dato almac.)

ALU (fase EX) 1 0 0

Cargas (fase MEM) 2 1 0

Número de ciclos de bloqueo de datos para instrucciones enteras del DLX

Por tanto, en el DLX entero existen 6 combinaciones de dependencia real entre fases.

f) Para calcular el número de ciclos de bloqueo de datos entre instrucciones no consecutivas, sólo hemos de tener en cuenta que mientras se inserten instrucciones independientes entre las que tienen la dependencia real se está ejecutando con CPI=1, lo que quiere decir que se está insertando un ciclo, o retrasando un ciclo la instrucción que necesita el dato. Por tanto, la diagonal principal se traslada una casilla a la izquierda, para esas combinaciones se produce el desvío exactamente en ese ciclo. La conclusión es que se reducen en uno los ciclos de bloqueo, y la tabla para instrucciones con dependencia real separadas por una instrucción queda:

Emisión

Instrucciones

Instrucciones

(Fase de generación)

ID

Saltos

EX

Cargas (Reg base)

Almac. (Reg base)

ALU

MEM

Almac. (dato almac.)

ALU (fase EX) 0 0 0

Cargas (fase MEM) 1 0 0

Análogamente, cuando las instrucciones dependientes están separadas por dos instrucciones independientes, la tabla es:

Emisión

Instrucciones

Instrucciones

(Fase de generación)

ID

Saltos

EX

Cargas (Reg base)

Almac. (Reg base)

ALU

MEM

Almac. (dato almac.)

ALU (fase EX) 0 0 0

Cargas (fase MEM) 0 0 0

Por tanto en el DLX entero no existe ningún ciclo de bloqueo de datos por dependencia RAW cuando todas estas se separan por dos instrucciones (sin RAW). En general, si existen q instrucciones sin ningún tipo de dependencia de datos entre dos con dependencia real, hay que reducir el número de ciclos de bloqueo en q (siendo siempre como mínimo cero).

Por último, debe tenerse en cuenta que el caso de insertar instrucciones con dependencia real es de otra índole, ya que el CPI de las instrucciones añadidas no es el ideal, y por ejemplo un ciclo de bloqueo de datos puede ser utilizado para las dos dependencias. Pongamos por caso el siguiente:

LW R1, 0(R2) SUBI R3, R1, #1 BEQZ R1, etiqueta

Según las tablas anteriores, en este fragmento de código habría un ciclo de bloqueo entre las dos primeras instrucciones, y habría otro bloqueo para las instrucciones LW y BEQZ. Sin embargo ambos ciclos no son aditivos, y el cronograma final nos muestra que la ejecución conduce a un ciclo de bloqueo nada más y se producirían dos desvíos en el mismo ciclo:

Ciclos 1 2 3 4 5 6 7 8 LW R1, 0(R2) IF ID EX MEM WB SUBI R3, R1, #1 IF ID — EX MEM WB BEQZ R1, etiqueta IF — ID EX MEM WB

2 SOLUCIÓN: (Este problema está propuesto en el libro de Hennessy-Patterson)

g) En este caso el registro R2 apunta inicialmente al final de un array de enteros de 32 bits, cuyos elementos se capturan en el registro R1, se decrementan y se almacenan otra vez en el array. Así hasta el principio del array. Por tanto un bucle que haga este recorrido hacia atrás podría servir. Por ejemplo, si r2 es un puntero que apunta al final del array:

int i, *r2; for (i=0; i<10; i++)

{ *(r2)= *(r2)-1; r2=r2-1; }

O también utilizando indexación del array (llámese éste a) en lugar de punteros: int i, a[10] ; for (i=9; i>=0; i--)

{ a[i]= a[i]-1; }

h) Vamos a mostrar con una flecha continua las dependencias reales, y con una flecha discontinua las antidependencias en el siguiente código. Todas las flechas nacen de los registros destino y acaban en los fuente:

bucle: LW R1, 0(R2) SUBI R1, R1, #1

SW 0(R2), R1 SUBUI R2, R2, #4

SLTI R8, R2, princ_array BEQZ R8, bucle

Las dependencias reales afectan evidentemente a la ejecución del DLX en cuanto son posibles causas de ciclos de bloqueo. Las antidependencias son importantes a la hora de reordenar el código, ya que la existencia de una de ellas entre dos instrucciones, exige que la segunda instrucción nunca pueda adelantar a la primera. Aunque las dependencias ficticias se pueden eliminar renombrando registros, cuando van unidas a dependencias reales en un bucle (es decir, con una dependencia de control), no tiene sentido el renombrado y por tanto no se pueden eliminar directamente. Este hecho se da en el caso del registro R2: si se renombra el registro destino de SUBUI por ejemplo a R20 (y por tanto el de SLTI), habría que modificar también los registros índices de LW y SW a R20 e igualmente habrá que modificar el registro fuente de SUBUI a R20. Note que cuando el bucle itere, tales instrucciones dependen del destino de SUBUI. Pero En conclusión, el bucle queda igual pero con R20 en lugar de R2, y las antidependencias siguen existiendo.

i) Para el cronograma o diagrama de ejecución en cadena, vamos a bloquear la cadena en cualquier dependencia real los ciclos necesarios hasta que la fase WB esté en el mismo ciclo que ID, ya que se permite la escritura previa a la lectura en este caso. Esto supone dos ciclos de bloqueo por cada dependencia real entre instrucciones consecutivas.

Suponemos en tal cronograma primero que el salto se toma, lo cual ocurrirá durante 9 veces, ya que en la última iteración se saldrá del bucle. No obstante en este apartado el comportamiento del salto será el mismo dado que la cadena se congela ante un salto. En el cronograma, se muestra la fase IF de la instrucción siguiente al salto ya que hasta que éste no termine de decodificarse, la máquina no congelará la cadena, y por tanto tal fase IF se ejecuta, aunque seguidamente se aborta. Además en la fase ID ya se resuelve el salto y por tanto se busca la instrucción de destino. Para calcular el CPIbloqueo,c del apartado c contamos los ciclos de bloqueo de datos, que son 8, y los de control que es 1, ya se tome o no el salto, debido a la fase IF que se aborta. Como son 6 instrucciones, tenemos:

CPIdatos= 3̂3.168= ciclos/instr ; CPIcontrol= 6̂1.0

61= ciclo/instr

CPIbloqueo,c = CPIdatos + CPIcontrol + CPIestruct + CPIMEM= 5.1 ciclo/instr

j) Para el cronograma del DLX con desvíos, sólo bloquearemos la cadena en las dependencias reales de las instrucciones Load y en los saltos de instrucciones consecutivas, como se calculó en el problema 1 de este boletín. Como vemos en el cronograma, en este código tendremos un ciclo de bloqueo por la pareja del primer Load y el SUBI y otro por la pareja SLTI y BEQZ. Los caminos de desvío se muestran con una flecha doble.

CPIdatos= 3̂3.062= ciclos/instr

Para calcular los bloqueos de control, suponemos en tal cronograma primero que el salto se toma, lo cual ocurrirá durante 9 veces, ya que en la última iteración se saldrá del bucle. En este apartado el comportamiento del salto es distinto en función de si se toma o no. Si se toma, la cadena apuesta por no tomado, busca la instrucción siguiente pero en el siguiente ciclo la aborta, es decir falla la apuesta. Pero si no se toma, la apuesta acierta, y la fase IF de la instrucción siguiente al salto es válida y se continúa ejecutando tal instrucción. Por eso, si el salto es tomado, la penalidad es un ciclo y si es no tomado es cero ciclos. Por tanto, siendo FNT el porcentaje o frecuencia de saltos no tomados y FT el de saltos tomados:

Pcontrol,cond = FNT CBNT + FT CBT = 9.011090

101

=×+× ciclos.

instrciclosPFCPIsaltosTipos

jjcontroljsaltocontrol / 15.09.0

61

1,, =×== ∑

=

Por último el CPIbloqueo,d del apartado d será:

CPIbloqueo,d= CPIdatos + CPIcontrol + CPIestruct + CPIMEM= 3̂48.0 ciclos/instr

La aceleración entre esta máquina y la del apartado anterior es la relación de CPI, ya que el número de instrucciones es el mismo y el periodo también:

69.13̂48.01

5.11

,

, =++

=++

=dbloqueoideal

cbloqueoideal

CPICPICPICPI

A

Es decir la máquina con caminos de desvío es un 69% más rápida, cifra que justifica plenamente la introducción de los desvíos (el cambio de la técnica del salto contribuye muy poco a esta aceleración), a pesar de la complejidad hardware que supongan.

Ciclos 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 LW R1, 0(R2) IF ID EX MEM WB SUBI R1, R1, #1 IF — — ID EX MEM WB SW 0(R2), R1 — — IF — — ID EX MEM WB SUBUI R2, R2, #4 — — IF ID EX MEM WB SLTI R8, R2, princ_array IF — — ID EX MEM WB BEQZ R8, bucle — — IF — — ID EX MEM WB Instr. Siguiente — — IF Abortada LW R1, 0(R2) IF ID EX MEM WB SUBI R1, R1, #1 IF — — ID

Cronograma del apartado c

Ciclos 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

LW R1, 0(R2) IF ID EX MEM WB SUBI R1, R1, #1 IF ID — EX MEM WB SW 0(R2), R1 IF — ID EX MEM WB SUBUI R2, R2, #4 — IF ID EX MEM WB SLTI R8, R2, princ_array IF ID EX MEM WB BEQZ R8, bucle IF — ID EX MEM WB Instr. Siguiente — IF Abortada LW R1, 0(R2) IF ID EX MEM WB SUBI R1, R1, #1 IF ID — EX MEM WB

Cronograma del apartado d.

3 SOLUCIÓN: k) Para detectar todos los bloqueos de datos entre dos instrucciones consecutivas teniendo todos los caminos de desvío, podemos

usar el mismo razonamiento que en el problema 1 del boletín 3 usando la tabla para instrucciones que generan un dato con cierta duración en ordenadas, e instrucciones que lo leen en cierta fase en abscisas. Hemos de detectar antes qué fases generan datos y cuáles los leen (en qué fase se emiten las instrucciones). Según la especificación de la máquina se puede obtiene que las fases que generan un dato (tienen algún registro de destino) son:

• EX1: genera el dato de las ALU simples (ALUSI). La duración es 1.

• EX2: genera el dato de las ALUCO y de las cargas de memoria. La duración es 2.

El resto de instrucciones no genera un dato (en algún registro de destino) para poder ser usado por otra instrucción. Por otra parte las fases en que alguna instrucción hace uso de algún registro fuente son: • ID1: Los saltos necesitan el registro de condición, ya que se resuelve completamente.

• ID2: Las instrucciones de acceso a memoria necesitan el registro base para calcular la dirección efectiva.

• EX1: Las instrucciones ALU simples (ALUSI) y las ALU complejas (ALUCO) necesitan sus operandos. Las de almacenamiento necesitan el dato ya que se empieza acceso al caché de datos (también se podía haber considerado que en este primer ciclo de acceso al caché, se está decodificando la dirección y comprobando las etiquetas, dejando para el segundo ciclo la escritura del dato, y por tanto sería en EX2 la lectura del operando fuente. En este problema se considera la opción anterior).

En total la tabla tendrá dos fases en la ordenadas y tres en abscisas, y por igual razonamiento que en el problema 1 del boletín 3, asignamos cero ciclos de bloqueo a la diagonal principal (sombreada en la tabla) e incrementamos al bajar o mover a la izquierda una casilla. Por tanto todos los posibles bloqueos por dependencia real se resumen en la tabla siguiente:

Fases de Emisión

Instrucciones

Instrucciones

(Fases de generación)

ID1

Saltos

ID2

Cargas y Almac. (Reg base)

EX1

ALUSI, ALUCO y Almac. (dato almacenado)

ALUSI (fase EX1, lat=0) 2 1 0

Cargas y ALUCO (fase EX2, lat=1)

3 2 1

La última cuestión de este apartado pregunta qué parejas de instrucciones tendrán bloqueos si la fase EX2 no recibe entradas de bypass. La respuesta es ninguna pareja, ya que la fase EX2 no usa ningún operando fuente como se ha visto en la descripción anterior, es decir, realmente la fase EX2 no tiene entradas de bypass.