Problema Tomasulo

Problema
Utilizando el algoritmo de Tomasulo para realizar la ejecución de la siguiente secuencia de instrucciones:
i1:
i2:
i3:
i4:

MULTD
MULTD
ADDD
ADDD

F2,F2,F6
F4,F2,F6
F2,F4,F6
F6,F2,F6

a) Muestre la evolución de los registros en coma flotante (FLR) y de las estaciones de reserva (RS) para todos
los ciclos que sean necesarios. Considere las siguientes hipótesis de partida:
 Para reducirel número de ciclos máquina se permite que la FLOS distribuya hasta dos instrucciones en
cada ciclo según el orden del programa.
 Una instrucción puede comenzar su ejecución en el mismo ciclo en que se distribuye a una estación de
reserva.
 La operación suma tiene una latencia de dos ciclos y la de multiplicación de tres ciclos.
 Se permite que una instrucción reenvíe su resultado ainstrucciones dependientes durante su último ciclo
de ejecución. De esta forma una instrucción a la espera de un resultado puede comenzar su ejecución en
el siguiente ciclo si detecta una coincidencia.
 Los valores de etiqueta 01, 02 y 03 se utilizan para identificar las tres slots de la estación de reserva de la
unidad funcional de suma, mientras que 04 y 05 se utilizan para identificar las dos slots dela estación de
reserva de multiplicación/división. Estos valores de etiqueta son los ID de los slots de las estaciones de
reserva.
 Inicialmente, el valor de los registros es F0=2.0, F2=2.5, F4=4.0 y F6=3.0.
b) Dibuje el gráfico de flujo de datos de la secuencia de instrucciones que aparece en el problema reflejando con
claridad todas las dependencias de datos que existen y qué registros lasprovoca.
c) Calcule el límite del flujo de datos para esa secuencia de instrucciones.
Solución
a)
Ciclo 1: Se distribuyen i1 e i2 en orden.
RS
ID

RS

Eti_1 Ope_1 Eti_2 Ope_2

ID

FR

Eti_1 Ope_1 Eti_2 Ope_2

ID

Bit Ocu

Etiq.

Dato

01

04 (i1)

00

2.5

00

3

F0

02

05 (i2)

04

--

00

3

F2

1

04

2.5

F4

1

05

4

03

Mult/Div
Suma/Resta

2

3

F6

Ciclo 2: Se distribuyen i3 e i4 enorden.
RS
ID

RS

Eti_1 Ope_1 Eti_2 Ope_2

ID

FR

Eti_1 Ope_1 Eti_2 Ope_2

ID

Bit Ocu

Etiq.

Dato

01 (i3)

05

--

00

3

04 (i1)

00

2.5

00

3

F0

02 (i4)

01

--

00

3

05 (i2)

04

--

00

3

F2

1

01

2.5

F4

1

05

4

F6

1

02

3

03

Mult/Div
Suma/Resta

1/4

2

Ciclo 3: Al final del ciclo 3, la instrucción i1 finaliza su ejecución y emite su ID (04). En ese momento, todos
los camposetiquetados que contienen el valor 04 insertan el resultado emitido.
RS
ID

RS

Eti_1 Ope_1 Eti_2 Ope_2

ID

FR

Eti_1 Ope_1 Eti_2 Ope_2

ID

Bit Ocu

Etiq.

Dato

01 (i3)

05

--

00

3

04 (i1)

00

2.5

00

3

F0

02 (i4)

01

--

00

3

05 (i2)

04

--

00

3

F2

1

01

2.5

F4

1

05

4

F6

1

02

3

Etiq.

Dato

03

Mult/Div
Suma/Resta

2

Ciclo 4:
RS
ID

RS

Eti_1 Ope_1 Eti_2 Ope_2

ID01 (i3)

05

--

00

3

04

02 (i4)

01

--

00

3

05 (i2)

FR

Eti_1 Ope_1 Eti_2 Ope_2

ID

Bit Ocu

2

F0
00

03

7.5

00

3

Mult/Div
Suma/Resta

F2

1

01

2.5

F4

1

05

4

F6

1

02

3

Etiq.

Dato

Ciclo 5:
RS
ID

RS

Eti_1 Ope_1 Eti_2 Ope_2

ID

01 (i3)

05

--

00

3

04

02 (i4)

01

--

00

3

05

03

Eti_1 Ope_1 Eti_2 Ope_2

2/4

ID

Bit Ocu

2

F0
00

7.5
Mult/Div

Suma/Resta

FR00

3

F2

1

01

2.5

F4

1

05

4

F6

1

02

3

Ciclo 6: Al final del ciclo 6 finaliza la ejecución de i2.
RS
ID

RS

Eti_1 Ope_1 Eti_2 Ope_2

ID

01 (i3)

05

--

00

3

04

02 (i4)

01

--

00

3

05

FR

Eti_1 Ope_1 Eti_2 Ope_2

ID

Bit Ocu

Etiq.

2

F0
00

03

7.5

00

3

Mult/Div
Suma/Resta

Dato

F2

1

01

2.5

F4

1

05

4

F6

1

02

3

Etiq.

Dato

Ciclo 7:
RS
ID

RS

Eti_1 Ope_1Eti_2 Ope_2

ID

Eti_1 Ope_1 Eti_2 Ope_2

FR
ID

01 (i3)

00

22.5

00

3

04

F0

02 (i4)

01

--

00

3

05

F2

03

Mult/Div
Suma/Resta

Bit Ocu

2
1

01

22.5

F4
F6

2.5

1

02

3

Etiq.

Dato

Ciclo 8: Al final del ciclo 8 finaliza la ejecución de i3.
RS
ID

RS

Eti_1 Ope_1 Eti_2 Ope_2

ID

Eti_1 Ope_1 Eti_2 Ope_2

FR
ID

01 (i3)

00

22.5

00

3

04

F0

02 (i4)

01

--

00

3

05

F2

03...