pg 1de 7

ARQUITECTURA DE SISTEMAS PARALELOS I.

4 INGENIERA INFORMTICA. PRCTICA 3.
BLOQUEOS DE CONTROL, DESENROLLADO DE BUCLES Y PREDICCIN
DINMICA DE SALTOS.

OBJETIVOS.

En esta prctica se trata de estudiar tericamente, y manejar el simulador WinDLX, para analizar una de las tcnicas
estticas ms potentes para reducir los ciclos de bloqueo de datos y de control: el desenrollado de bucles. Tambin
usaremos la herramienta Visual BTB para estudiar y comprender la tcnica dinmica de prediccin de saltos BTB,
analizando los dems tipos de tcnicas de prediccin. Todo lo anterior estar sometido a una fase de optimizacin, basada
en tcnicas simples como reordenacin de cdigo, supresin de dependencias con gasto de nuevos registros, etc., que
intentar minimizar en lo posible los ciclos de bloqueo.

INTRODUCCIN TERICA

1.- Desenrollado de bucles
Vamos a usar como ejemplo el bucle SAXPY con multiplicacin (ver anexo 1) y analizaremos los bloqueos de control
que se producen en la herramienta de simulacin WinDLX. Analizaremos tericamente (en papel) cmo se comportaran
procesadores DLX con la implementacin hardware de otras soluciones y entraremos ms en detalle en la solucin del
desenrollado de bucles.
La tcnica esttica del desenrollado de bucles consiste agrupar varias iteraciones de un bucle en una nica iteracin
(con ms instrucciones que la iteracin original, claro est) de un nuevo bucle. Al ejecutar en una sola iteracin del nuevo
bucle varias iteraciones del bucle inicial, y mediante el uso de nuevos registros temporales, la reordenacin del cdigo y la
variacin de los direccionamientos a memoria en funcin del incremento de los punteros, se reducir el nmero de
bloqueos, y se acelerar la ejecucin.
Hay que tener en cuenta que esta tcnica no se puede aplicar directamente a todos los bucles, sino solamente a los
llamados paralelizables, es decir, aquellos donde las iteraciones se pueden de alguna forma ejecutar en paralelo. Por
ejemplo, cuando las iteraciones son independientes, el bucle es claramente paralelizable; pero cuando una iteracin
depende de los resultados de la anterior, no se puede desenrollar fcilmente tal bucle. Por ejemplo, el bucle normal para
calcular la serie de Fibonacci no se puede desenrollar, puesto que el trmino i-simo depende de los anteriores. Pero el
SAXPY o el bucle ejemplo que trataremos a continuacin son claramente paralelizables:

int i, a, x[M], y[M];
// aqu se inicializan a y los arrays.
for (i=0; i<M; i++) y[i]= x[i] * a ;

Vamos a mostrar el desenrollado de 4 iteraciones de tal bucle trabajando con un lenguaje de alto nivel como el C.
Sencillamente como queremos que se ejecuten en paralelo 4 iteraciones, podramos rescribir el bucle como:

for (i=0; i<M; i+=4)
{
y[i+0]= x[i+0] * a ;
y[i+1]= x[i+1] * a ;
y[i+2]= x[i+2] * a ;
y[i+3]= x[i+3] * a ;
}
De esa forma el bucle original en ensamblador sera algo como:

bucle_orig:LW R2, 0(R1)
MULT R2, R2, R25 ; R25 contiene el valor de a
SW (R3)0, R2
ADDI R1, R1, 4
ADDI R3, R3, 4
SLTI R7, R1, fin_array_x; esta constante apunta al final del array x[M]
BNEZ R7, bucle_orig

Mientras que el bucle desenrollado sera algo como:

bucle_desen:
LW R2, 0(R1)
MULT R2, R2, R25 ; R25 contiene el valor de a
SW (R3)0, R2
Prctica 3. Arquitectura de Sistemas Paralelos 1. Depto ATC.
Pg 2 de 7

LW R2, 4(R1)
MULT R2, R2, R25 ; R25 contiene el valor de a
SW (R3)4, R2

LW R2, 8(R1)
MULT R2, R2, R25 ; R25 contiene el valor de a
SW (R3)8, R2

LW R2, 12(R1)
MULT R2, R2, R25 ; R25 contiene el valor de a
SW (R3)12, R2

ADDI R1, R1, 4*4
ADDI R3, R3, 4*4
SLTI R7, R1, fin_array_x
BNEZ R7, bucle_desen

Ntese que han desaparecido una buena cantidad de instrucciones de incremento de punteros (R1 y R3) y de saltos del
bucle original de la traza del cdigo desenrollado: son las llamadas instrucciones de exceso o sobrecarga (en ingls
overhead). Ntese tambin que tal cantidad guarda una proporcin directa con el nmero de iteraciones desenrolladas. Sin
embargo las instrucciones de cmputo y acceso a memoria (las realmente tiles en este bucle) siguen siendo las mismas.
Pero para obtener ms velocidad en la ejecucin, se pueden reducir los bloqueos de datos reordenando el bucle
desenrollado. La forma ms fcil es entrelazar las diferentes iteraciones (slo las instrucciones realmente tiles), de
forma que las instrucciones que tienen dependencia RAW se alejan:

bucle_entrel: LW R2, 0(R1)
LW R20, 4(R1)
LW R21, 8(R1)
LW R22, 12(R1)

MULT R2, R2, R25 ; R25 contiene el valor de a
MULT R20, R20, R25 ; R25 contiene el valor de a
MULT R21, R21, R25 ; R25 contiene el valor de a
MULT R22, R22, R25 ; R25 contiene el valor de a

SW (R3)0, R2
SW (R3)4, R20
SW (R3)8, R21
SW (R3)12, R22

ADDI R1, R1, 4*4
ADDI R3, R3, 4*4
SLTI R7, R1, fin_array_x
BNEZ R7, bucle_entrel

Notar como se han renombrado registros en este proceso para que las dependencias ficticias (WAW y WAR)
desaparezcan. Por tanto, la cantidad de iteraciones que se pueden desenrollar depende claramente de la cantidad de
registros disponible (en un procesador CISC este proceso es prcticamente imposible).
En el proceso anterior, se ha supuesto que M es divisible por 4. En caso de que no fuera as habra que dejar unas
cuantas iteraciones (exactamente el resto de M/4, es decir M mod 4, o M%4) fuera de la iteracin del nuevo bucle. Por
ejemplo, se suelen dejar antes del nuevo bucle (lo que sera un cdigo de comienzo, prembulo o arranque, en ingls
startup):
for (i=0; i<M%4; i++) y[i]= x[i] * a ;
for (i=M%4; i<M; i+=4)
{
y[i+0]= x[i+0] * a ;
y[i+1]= x[i+1] * a ;
y[i+2]= x[i+2] * a ;
y[i+3]= x[i+3] * a ;
}
El alumno debe hacer como ejercicio el mismo desenrollado pero trabajando en ensamblador, para ello, tener en
cuenta el siguiente guin:
1. Copiamos n veces la iteracin, renombrando registros para cada iteracin.
Sea

n
s iteracione
el nmero de nuevas iteraciones. As, (iteraciones mod n) son las iteraciones que faltan para
completar el total.
Prctica 3. Arquitectura de Sistemas Paralelos 1. Depto ATC.
Pg 3 de 7
Por tanto el nmero total de iteraciones ser:
n s iteracione
n
s iteracione
s iteracione mod +

=

2. Eliminamos los saltos intermedios (el ltimo no).
3. Sustituimos los decrementos poniendo en los almacenamientos dicha operacin como inmediato.
Bucle: LD

SD 0(R1),F4

SD 8(R1),F4

SD 8*(n-1)(R1),F4
SUBI R1,R1,#n*8
RBNEZ R1,Bucle
4. Reorganizamos el cdigo de las n iteraciones como mejor convenga. Entrelazar es la forma ms fcil. Tambin ayuda
subir las instrucciones de overhead hacia arriba para evitar riesgos RAW.

Por ejemplo, sea 1 salto por cada 5 instrucciones (3 de cmputo y acceso a memoria, una de incremento de puntero y
un salto), es decir un 20% de saltos. Realizando un desenrollado de 4 iteraciones quedara 1 salto por cada 4*3+2=14
instrucciones, es decir, un 7%, casi un tercio. Como el CPI
control
es proporcional a la frecuencia o porcentaje de saltos,
estamos reducindolo aprox. a la tercera parte. Adems, si reordenando se consiguieran 0 bloqueos de datos en 4
iteraciones conseguiramos CPI
datos
=0, lo que acercara el CPI al ideal de 1 instr/ciclo.

Los cambios a realizar a un bucle deben ser tiles para tres cosas:
1. Darse cuenta de la cantidad de paralelismo que puede o no extraerse de un cdigo.
2. Intentar fijar las condiciones por las cuales pueden intercambiarse las instrucciones. Para ello, el compilador debera:
- Ajustar los offset para cambiar direcciones,
- determinar qu iteraciones son independientes para poder desenrollarlas,
- usar registros diferentes para evitar dependencias,
- analizar las direcciones de memoria que acceden los LD/SD para poder saber si son intercambiables,
- atender a las dependencias reales y conservar su orden,
-
3. Intentar resolver o eliminar las dependencias ficticias.
4. Intentar eliminar los ciclos de bloqueo por dependencias reales.

2.- Prediccin dinmica de saltos.

En esta prctica suponemos que trabajamos con un procesador RISC DLX, dotado en su fase ID del hardware
necesario para resolver los saltos.
Recordar que la tcnica de implementacin de saltos que Apuesta por No Tomado (NT) es la solucin inherente al
pipeline bsico. En ella se opta por suponer que el salto nunca se tomar y se comienza a ejecutar la siguiente instruccin
en memoria tras el salto. Slo cuando la apuesta sea errnea (salto sea T) se perder un ciclo, repitiendo IF de la
instruccin de la otra rama.
Sin embargo cuando se dispone de un cach de prediccin de saltos (Branch Prediction Buffer, BPB) y de otro
cach de direcciones de destino de los saltos (Branch Target Buffer, BTB), se puede predecir dinmicamente el
comportamiento de un salto. Con tal prediccin se podrn buscar y ejecutar las instrucciones de la rama predicha por la
BPB, segn la direccin de destino que indique la BTB. De esta manera, al hacer IF de la instruccin de salto, se
consultara la BTB y sabramos no slo la prediccin, sino la direccin de la siguiente instruccin a ejecutar, de manera
que en el siguiente ciclo comenzara la instruccin predicha, sin bloqueos.
Los bloqueos vendran cuando la prediccin fallara o no se acertara en la cach BTB. Cuando hay un fallo de acceso a
la cach BTB (el salto no est en la cach y no hay prediccin) o un fallo de prediccin, es en la etapa ID cuando esto es
detectado, incrementndose el CPI para estos casos.
En el siguiente grfico se especifica cuntos ciclos de bloqueo se van a considerar para cada caso en esta prctica. Se
supone que existe una BTB que almacena la direccin predicha de todos los saltos (ya sean predichos NT o T) y que se
accede en IF. La BPB almacena una informacin completa de la historia de los saltos y se accede en ID, en paralelo con la
resolucin del salto, de forma que la actualizacin de la mquina de estados de prediccin se hace justo al final de tal fase
ID.

Prctica 3. Arquitectura de Sistemas Paralelos 1. Depto ATC.
Pg 4 de 7
Enviar PC a cach
de instr y BTB
Enviar PC
predicho
a
IF y BTB
Acierto
BTB?
Fue
salto?
Error de
predicc.?
Actualizar
BTB
Mala prediccin.
Actualizar BTB si
cambia la pred.
Prediccin
correcta
NO SI
SI
NO
NO
SI
1 ciclo de bloqueo si NT
2 ciclos de bloqueo si T

1 ciclo de bloqueo
2 ciclos de bloqueos si
cambia la pred.
0 ciclos de bloqueos
IF
ID
EXE
Ejecucin normal. 0
ciclos de bloqueos


ESTUDIO PREVIO

1.- Desenrollado de bucles

En el anexo 1 se encuentra el bucle SAXPY en cdigo DLX. Realice el desenrollado sistemtico de 2 y 3 iteraciones
(son dos desenrollados) del bucle.

2.- Prediccin dinmica de saltos (BTB)

Se va a manejar un simulador llamado VisualBTB que simula la evolucin de las mquinas BTB (Branch Target
Buffer, Buffer de destino de saltos) para distintos bits de historia (de 1 a 16) y bits de correlacin (de 0 a 16). La entrada
que recibe VisualBTB para simular la evolucin de la BTB es muy simple, pero suficiente para entender el mecanismo de
las BTB. Se trata de una traza de ejecucin con el formato llamado din:
FORMATO DE LA TRAZA:
Est compuesto por dos campos. El primer campo est formado por un carcter e indica el tipo de acceso a la
memoria cach que se realiza. El segundo campo (separado por un espacio) indica la direccin del acceso y se presenta en
formato hexadecimal, con la opcin de tener como prefijo 0x, siendo de longitud mxima de 32 bits. En el caso de que
fuera menor de 32 bits se le aadiran ceros a la izquierda.
Los diferentes caracteres que permite este formato para indicar el tipo de acceso son:
- 0 : lectura, realiza una lectura de datos en la cach.
- 1: escritura, realiza una escritura de datos en la cach.
- 2: instruccin, realiza una lectura de instrucciones en la cach.
Para esta prctica slo es necesario usar el tipo de acceso 2. Con esto, Visual BTB detecta qu saltos hay el programa
por los cambios de PC (si un salto nunca se toma, Visual BTB slo tiene la opcin de considerar que no es un salto). Para
ello realiza una comprobacin nada ms cargar la traza, dando una pasada completa a la traza.

En el ejemplo que se va a simular se usarn mquinas de 2 bits de historia. La mquina de 2 bits es la de la figura .


0/T 1/T
2/NT 3/NT
T
T
T
T
NT
NT
NT
NT



Prctica 3. Arquitectura de Sistemas Paralelos 1. Depto ATC.
Pg 5 de 7
El ejemplo que se va a simular consistir en dos bucles anidados, es decir se trata de un programa como:

Bucle:
; ms cdigo del bucle interno
Branch1 R4, Bucle
; ms cdigo del bucle externo
Branch2 R3, Bucle
Ntese que el tipo de salto (BEQZ, BNEZ, etc.) no tiene importancia en esta prctica, ya que slo se pretende
predecir si es T o NT (Tomado o No Tomado). La etiqueta Bucle sirve para el bucle externo y el interno. Las direcciones
son las siguientes: la etiqueta Bucle es la 0x20, la direccin del primer salto es la 0x30 y la del segundo 0x40; o sea el
programa ensamblado sera (los caracteres 0x no son necesarios en la traza, por defecto sta es hexadecimal):

20: instruccin 1
24: instruccin 2
28: instruccin 3
2C: instruccin 4
30: instruccin de salto: Si condicin salta a 20
34: instruccin 5
38: instruccin 6
3C: instruccin 7
40: instruccin de salto: Si condicin salta a 20
44: instruccin 8
48: instruccin 9
4C: instruccin 10
50: instruccin 11

De esa forma la traza del programa ir pasando por las direcciones 20 a la 30 para iterar el primer bucle y de la 20 a la
40 para el segundo, englobando al primer bucle.
El simulador de BTB tiene almacenado el comportamiento de los saltos en un array binario, donde 1 es T y 0 NT.
En la siguiente figura se muestra el final de la ejecucin de otro ejemplo diferente de bucles anidados. El asterisco *
indica que Visual BTB ha detectado que tal instruccin es un salto
La pantalla se divide en cuatro partes:
Estado, donde se muestra la historia de las ltimas operaciones realizadas por el simulador.
Cach BTB. Aparece el contenido de cada lnea as como el estado de las mquinas. En este caso por tener 2 bits
de correlacin tiene 4 columnas y por tener 2 bits de historia, en cada casilla (fila y columna) se tiene una mquina
de 2 bits, o sea de 4 estados posibles llamados sencillamente 0, 1, 2 y 3. Tambin aparece el registro de
correlacin o desplazamiento que se inicializa (por defecto) a 00 (NT,NT)
Ventana de traza, donde aparece el fichero de traza con un * en cada instruccin de salto.
Las estadsticas separadas por categoras de fallos por distintas causas.
Haciendo doble click en una lnea de la BTB se puede ver el estado de las mquinas y la siguiente prediccin para
dicho salto. Desde la barra de tareas o los mens se puede modificar el nmero de bits de historia, el nmero de bits de
correlacin y el tamao de la cach (nmero de lneas).
La ejecucin de la traza puede hacerse paso a paso, de una vez o de tramo en tramo.

El alumno debe previamente a la realizacin de la prctica.
Comprender la evolucin de la mquina de estados de dos bits y Calcular cul sera la traza de ejecucin del
ejemplo dado para 5 iteraciones del bucle externo y 5 del interno.


Prctica 3. Arquitectura de Sistemas Paralelos 1. Depto ATC.
Pg 6 de 7


REALIZACIN EN EL LABORATORIO

1. Bloqueos de control y desenrollado de bucles.

a) El simulador WinDLX slo permite una tcnica de tratamiento de los saltos. Comprobar cul es sta, viendo los
bloqueos de control y el comportamiento del salto cuando el salto se toma y cuando no se toma. Calcular el
CPI
bloqueocontrol
y la duracin de las 10 iteraciones (quitar los NOP de tal cdigo que introduzca el simulador o estn
en el anexo).
b) Simular en el WINDLX el cdigo desenrollado de 2 iteraciones, reordenando el cdigo para minimizar bloqueos
de datos. Calcular el CPI, CPI
bloqueodatos
, CPI
bloqueocontrol
, CPI
estructural
del programa (bucle SAXPY) completo

Hallar
la aceleracin entre a) y b).
c) Simular en el WINDLX el cdigo desenrollando sistemticamente de 3 iteraciones del mismo. Notar que 3 no es
divisor de 10 y sobra una iteracin (se suele poner antes del bucle). y calcular el CPI, CPI
bloqueodatos
, CPI
bloqueocontrol
,
CPI
estructural.
del programa completo. Hallar la aceleracin entre a) y c).

2. Prediccin dinmica de saltos: BTB.

Primer ejemplo: Ejecutar el programa VisualBTB. Crear el fichero de traza correspondiente al bucle anidado
descrito en la preparacin de esta parte para el caso de 5 iteraciones del bucle interior y 5 del bucle exterior. Probar
con nmeros de lnea siempre potencias de 2. Entender la evolucin de la BTB.

Anotar el porcentaje de aciertos y finalmente calcular el nmero de ciclos de bloqueo en funcin de lo explicado en el
apartado de preparacin de la prctica para un DLX.

Contestar a las siguientes cuestiones:
a) Ejecutar la traza para una BTB(2,2) de 2 bits de historia y 2 de correlacin con 8 lneas de BTB, con estado
inicial de las mquinas de estado 2, y bits de correlacin inicial tambin a 0. Cul es el CPI
bloqueos
del
programa (usar para ello el modelo del DLX de la pgina 1, distinguiendo a qu casos corresponde cada fallo de
BTB)? El porcentaje de acierto en la BTB? El porcentaje de acierto de la prediccin?
b) Cul es el estado de la mquina de la columna apuntada por T,T en el registro de correlacin, para el salto 0x30
tras la ejecucin completa del primer bucle interno?
c) Ejecutando la traza para una BTB de 4 lneas, Qu mquina (de que columna y lnea) predice el salto 40 la
tercera vez que se va a ejecutar (antes de ejecutarlo, puesto que se est prediciendo)? Qu predice? Acert?

ANEXO 1

;*********** WINDLX PRACTICA 4 A.S.P. 1 *************
;*********** EVALUACION DE BLOQUEOS DE DATOS Y CONTROL *************

.data ;*** ARRAY PARA X, Y
arrayx: .word 1,2,3,4,5,6,7,8,9,10 ;/* declarado con 10 elementos, mltiplos de 1 */
arrayy: .word 3,6,9,12,15,18,21,24,27,30 ;/* declarado con 10 elementos, mltiplos de 3 */
;/* el resultado del bucle ser los mltiplos de 7 en arrayy*/
finaly: .space 4 ;/* apunta a la direccin posterior al final de x */


.text ; ********** EMPIEZA CODIGO ************
addi r2, r0, arrayy
addi r1, r0, arrayx
addi r28, r0, 4 ; registro r28 para contener la constante (no interesa usar operandos inmediatos)

bucle: ; ********** EMPIEZA BUCLE SAXPY ************
lw r4, 0(r1)
lw r6, 0(r2)
mult r5, r4, r28 ; r28 contiene la constante 100b
addi r2, r2, 4
addi r1, r1, 4
seq r7, r2, finaly
add r6, r5, r6
sw -4(r2), r6
beqz r7, bucle
Fin: ;*** fin programa
trap 0 ; INTERRUPCION SOFTWARE DE FIN DE PROGRAMA (devuelve control al S.O.)
Prctica 3. Arquitectura de Sistemas Paralelos 1. Depto ATC.
Pg 7 de 7
ARQUITECTURA DE SISTEMAS PARALELOS I
4 INGENIERIA INFORMATICA
PRACTICA 3: DESENROLLADO DE BUCLES, BLOQUEOS DE CONTROL Y
PREDICCIN DINMICA DE SALTOS.
NUM GRUPO:
ALUMNOS:

TABLA DE RESULTADOS:
Ejercicio 1
a)
CPI
control

b)
Cdigo










CPI



CPI
control



Aceler.:

CPI
datos




CPI
estruct

c)
Cdigo













CPI




CPI
control




Aceler.:

CPI
datos


Ejercicio 2
A
CPI
bloqueos control
:





% Acierto BTB: % Acierto Prediccin:
B
Estado mquina T,T:


Siguiente prediccin de mquina T,T:
C
Mquina:


Prediccin: Acert prediccin?: