CAPÍTULO 2

Problema 1:

T0 T1 T2 T3 T4
S1 A B A B
S2 A B A
S3 B AB

= [3] = [1, 2, 4]
= [1, 2] = [3, 2]

0 1 0 0 1 0 1 1
= =
0 0 1 1 0 1 1 0

Diagrama de Estados

0010 0100 0110 0000 1011 1011

A1 OR = B4 OR =
0001 0011 0011 0000 0110 0110
0001 0100 0101 0000 1011 1011
A2 OR = B4 OR =
0000 0011 0011 0000 0110 0110
0000 0100 0100 0000 0100 0100
A4 OR = A4 OR =
0000 0011 0011 0000 0011 0011
0000 1011 1011 0000 1011 1011
B3 OR = B3 OR =
0000 0110 0110 0000 0110 0110
0000 1011 1011 0000 1011 1011
B4 OR = B4 OR =
0000 0110 0110 0000 0110 0110
0001 0100 0101
A3 OR =
0000 0011 0011
0101 1011 1111
B1 OR =
0011 0110 0111
0000 1011 1011
B4 OR =
0000 0110 0110
0011 0100 0111
A1 OR =
0001 0011 0011
0000 0100 0100
A4 OR =
0000 0011 0011
0001 1011 1011
B3 OR =
0000 0110 0110
0000 1011 1011
B4 OR =
0000 0110 0110
0001 0100 0101
A2 OR =
0000 0011 0011
0000 0100 0100
A4 OR =
0000 0011 0011
0001 1011 1011
B3 OR =
0000 0110 0110

1
 A4

0100
0011
A4
A1

A2
A4 A4
B3

0110 0111 B4 1111 0101 A2

0011 0011 0111 0011
A1

B3 A3
B4
B4 B1
B3
B4 B3
B4

1011
0110

B4

Problema 2:
En un cauce multifuncional con la tabla de reservas siguiente, ¿Cuál es el tiempo mínimo (en
ciclos) que tardaría en ejecutarse la secuencia de seis instrucciones ABCBAC si se utiliza una
estrategia de tipo avaricioso?

Solución:

T0 T1 T2 T3
S1 AC BC
S2 ABC A A
S3 B C

= [1,2] = [2] = [2]

= [1,2] = [0] = [2]
= [1,2] = [2] = [2]

1 1 1 0 1 0
= 1 1 = 0 0 = 1 0
1 1 1 0 1 0

2/18
Diagrama de Estados A3

A1 C1
10
A4 11 10
11 10
11
C3
B2

A1
10
B3
00 B1
10

B2
B2

C1
B1
11
11 B1 01
00 11 11
11 10
11

B1

A1 A4 B1 B2 B3 C1 C3 A1 B1 C1 B1 B2 B1 A3 B2
01 00 01 00 00 01 00 01 01 01 01 00 01 00 00
00 00 00 00 00 00 00 01 01 01 00 00 01 00 00
01 00 01 00 00 01 00 01 01 01 01 00 01 00 00
OR OR OR OR OR OR OR OR OR OR OR OR OR OR OR
11 11 10 10 10 10 10 11 10 10 10 10 10 11 10
11 11 00 00 00 10 10 11 00 10 00 00 00 11 00
11 11 10 10 10 10 10 11 10 10 10 10 10 11 10
= = = = = = = = = = = = = = =
11 11 11 10 10 11 10 11 11 11 11 10 11 11 10
11 11 00 00 00 10 10 11 01 11 00 00 01 11 00
11 11 11 10 10 11 10 11 11 11 11 10 11 11 10

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
A4
B3
C1
B1
A3
C3

La secuencia ABCBAC tarda 16 ciclos en ejecutarse.

Nota: Este problema esta tomado del solucionario del ingeniero, nótese que el diagrama de tiempos no tiene sentido.

3/18
Problema 3:
Se han encontrado posibles alternativas para la ejecución de una función F en un
cauce con 4 etapas S1, S2, S3, S4. La alternativa 1 visita las etapas según la secuencia
S1 S3 S1 S3 S2 S3 S4, y la alternativa 2 en el orden S1 S2 S3 S4 S2 S3. ¿Cuál de las dos
alternativas permite ejecutar un número mayor de funciones por unidad de tiempo?

Solución:

Hallando los diagramas de estado:

Alternativa 1:

1 2 3 4 5 6 7
S1 X X
S2 X
S3 X X X
S4 X

= [2, 4]

= (1010)

1 0101 OR 1010 = 1111

3 0001 OR 1010 = 1011
3 0001 OR 1010 = 1011
5 0000 OR 1010 = 1010

1010 1
3

1011 5 1111

5+1
= = 3
2

Alternativa 2:

1 2 3 4 5 6
S1 X
S2 X X
S3 X X
S4 X

= [3]

4/18
 = (100)

1 010 OR 100 = 110

2 001 OR 100 = 101
2 010 OR 100 = 110
1 011 OR 100 = 111
4 000 OR 100 = 100

2 100
4
1

101 111

110
1

1+1+4
= = 2
3

La productividad máxima se define como:

á = lim ( ) = lim = lim

→ → ( ) → + ∗ ( − 1)

1 1
á = lim = lim = =
→ + ∗ − → ∗ ∗

1 0.33
á = =
3∗

1 0.5
á = =
2∗

La segunda alternativa permite ejecutar el mayor número de funciones.

Obtenga la ganancia en velocidad que ofrece cada una de las alternativas con
respecto a su ejecución sin cauce para 500 operaciones teniendo en cuenta que sin
cauce la función requiere un tiempo de 15ns, que las etapas del cauce suponen unos
tiempos de ejecución de 4ns para S1, 5ns para S2, 2ns para S3, 4ns para S4 y que
además los registros de acoplo entre etapas introducen un retardo de 0.25ns.

(500) = 500 ∗ 15 = 7500

= á [ 1, 2, 3, 4] +

= á [4 ,5 ,2 ,4 ] + 0.25

5/18
 =5 + 0.25 = 5.25

=7 ∗ 5.25 = 36.75

= 3 ∗ 5.25 = 15.75

∗ 15 ∗ 500
( )= = = 0.9498
+ ∗ ( − 1) 36.75 + 15.75 ∗ (500 − 1)

=6 ∗ 5.25 = 31.5

= 2 ∗ 5.25 = 10.5

∗ 15 ∗ 500
( )= = = 1.4228
+ ∗ ( − 1) 31.5 + 10.5 ∗ (500 − 1)

Problema 4:
Un circuito que implementa una operación en Top=450ns se ha segmentado mediante
un cauce lineal con cuatro etapas de duración, T1=100ns, T2=125ns, T3=125ns,
T4=100ns, respectivamente, separadas por un registro de acoplo que introduce un
retardo de 25ns. ¿Cuál es la máxima ganancia de velocidad posible?

= á [ 1, 2, 3, 4] +

= á [100 , 125 , 125 , 100 ] + 25

= 125 + 25 = 150

450
= = =3
150

¿Cuál es la máxima productividad del cauce?

1 1
á = = = 6.67
150

¿A partir de qué números de operación ejecutadas se consigue una productividad del

90% de la productividad máxima?

= ∗ =4∗

1
( ) = 0.9 ∗ = =
150 + ( − 1) 4 ∗ 150 + ( − 1) ∗ 150

= 27

6/18
Problema 5:
La operación de multiplicación de números en punto flotante en un determinado
procesador tiene una latencia de 25ns. Tras aplicar una serie de benchmarks se ha
observado que esta operación se utiliza en un número muy significativo de
ocasiones, con lo que el equipo de arquitectos se ha planteado desarrollar una
implementación de multiplicación segmentada de 4 etapas que siga la siguiente
secuencia de operación: S1 S2 S3 S1 S2 S4 S4 S3. Si la latencia de las etapas S1, S2, S3,
S4 son de 6ns, 5ns, 4ns, 5ns respectivamente y los registros de acoplo entre las
etapas necesitan 1ns para cargarse ¿Cuál es la ganancia y la productividad máxima
que se puede obtener con esta nueva implementación?

Solución:

1 2 3 4 5 6 7 8
S1 X X
S2 X X
S3 X X
S4 X X

= [1, 3, 5]

= (10101)

2 00101 OR 10101 = 10101

4 00001 OR 10101 = 10101

2
10101
4

2
= =2
1

= á [ 1, 2, 3, 4] +

= á [6 ,5 ,4 ,5 ]+1

=6 +1 =7

=8 ∗7 = 56

=2∗7 = 14

7/18
La productividad máxima se define como:

á = lim ( ) = lim = lim

→ → ( ) → + ∗ ( − 1)

1
á = lim = lim =
→ + ∗ − → ∗

1 1
á = = = 71.43
14

∗ ∗
á = lim ( ) = lim = lim
→ → ( ) → + ∗ ( − 1)

∗ ∗
á = lim = lim =
→ + ∗ − → ∗

25
á = = = 1.7857
14

Problema 6:
Las 4 etapas S1, S2, S3, S4 de un cauce multifuncional se utilizan por las instrucciones
del tipo A de la forma S1, S2, S1, S3, S1, S4, S1 y por las instrucciones del tipo B de la
forma S1, S4, S1, S3, S1, S2, S1. Escriba las matrices de colisiones cruzadas y
determine cuál es la productividad máxima del cauce para una secuencia de
instrucciones del tipo A (es decir A, A, A,…) teniendo en cuenta que la frecuencia de
reloj es de 500 MHz.

Solución:

1 2 3 4 5 6 7
S1 AB AB AB AB
S2 A B
S3 AB
S4 B A

= [2, 4, 6] = [2, 4, 6]
= [2, 4, 6] = [2 ,4, 6]

1 0 1 0 1 0 1 0 1 0 1 0
= =
1 0 1 0 1 0 1 0 1 0 1 0

Para calcular la productividad máxima para una secuencia del tipo A solo debemos
tener en cuenta el vector de colisiones que nos genera el siguiente diagrama de
estados.

8/18
 = (101010)

1 010101 OR 101010 = 111111

3 000101 OR 101010 = 101111
5 000001 OR 101010 = 101011
5 000001 OR 101010 = 101011
3 000101 OR 101010 = 101111
5 000001 OR 101010 = 101011

1
5
101010

3 101011 5
111111 5
7

101111
3

7+1
= = 4
2

La productividad máxima se define como:

á = lim ( ) = lim = lim

→ → ( ) → + ∗ ( − 1)

1
á = lim = lim =
→ + ∗ − → ∗

1 1
á = = = 125
∗ 1
4∗( )
500

9/18
Problema 7:
Supongamos que las etapas de una unidad funcional segmentada S1, S2, S3, S4 y S5
se utilizan en el orden S1, S3, S5, S1, S3, S4, S1, S3, S2, S5, S4, S2. ¿Cuál es el tiempo
(número de ciclos) de latencia de inicio del cauce?

12 Ciclos

¿Cuál es la tabla de reservas y el vector de colisiones inicial?

1 2 3 4 5 6 7 8 9 10 11 12
S1 X X X
S2 X X
S3 X X X
S4 X X
S5 X X

= [3, 5, 6, 7]

= (1110100)

Si se supone que el cauce está vacío inicialmente y se introduce una operación, ¿Es
posible introducir otra pasados 5 ciclos?

No es posible ya que el quinto ciclo es una latencia prohibida.

¿Cuál es el número mínimo de ciclos que hay que esperar?

Las latencias no prohibidas son 1, 2, 4; por lo tanto habría que esperar un ciclo como
mínimo para introducir una nueva operación.

¿Cuáles son las latencias prohibidas en ese caso una vez que se ha introducido la
segunda operación?

Las nuevas latencias prohibidas serian 1, 3, 5, 6, 7.

10/18
Problema 8:
Se pretende utilizar un cauce con cuatro etapas, A, B, C, D, para aumentar el
rendimiento en la ejecución de una unidad funcional F. Las etapas se pueden utilizar
según una de las dos secuencias S1 y S2 siguientes:

S1: ABACACABD
S2: ADBCCABD

Si la duración de cada etapa (incluyendo el registro de acoplo) es de 50ns, y la

operación que implementa la unidad funcional F sin pipeline tarda 350ns en
ejecutarse ¿Cuál de las dos posibilidades es mejor?

1 2 3 4 5 6 7 8 9
A S1 S2 S1 S1 S2 S1
B S1 S2 S2 S1
C S1 S2 S2 S1
D S2 S2 S1

1: = ∗ = 50 ∗ 9 = 450
2: = ∗ = 50 ∗ 8 = 400

La primera posibilidad

¿Por qué?

Debido a que nos ofrece una mayor productividad.

11/18
¿Cuáles son los valores máximos para la productividad, la eficacia y la ganancia del
cauce en cada una de las secuencias de utilización, S1 y S2?

Para S1:

1 2 3 4 5 6 7 8 9
A S1 S1 S1 S1
B S1 S1
C S1 S1
D S1

= [2, 4, 6]

= (101010)

1 010101 OR 101010 = 111111

3 000101 OR 101010 = 101111
5 000001 OR 101010 = 101011
5 000001 OR 101010 = 101011
3 000101 OR 101010 = 101111
5 000001 OR 101010 = 101011

3 101010 7

5 1
101111 5 111111

101011
3

3+5
= = 4
2

= 450

= 4 ∗ 50 = 200

á = lim ( ) = lim = lim

→ → ( ) → + ∗ ( − 1)

1
á = lim = lim =
→ + ∗ − → ∗

12/18
 1 1
á = = =5
200

∗ ∗
á = lim ( ) = lim = lim
→ → ( ) → + ∗ ( − 1)

∗ ∗
á = lim = lim =
→ + ∗ − → ∗

350
á = = = 1.75
200

∗ ∗
á = lim ( ) = lim = lim
→ → ∗ ( ) → ∗( + ∗ ( − 1))

∗ ∗
á = lim = lim =
→ ∗( + ∗ − ) → ∗ ∗ ∗

350
á = = = 0.1944
∗ 200 ∗ 9

Para S2

1 2 3 4 5 6 7 8
A S2 S2
B S2 S2
C S2 S2
D S2 S2

= [1, 4, 5, 6]

= (111001)

2 001110 OR 111001 = 111111

3 000111 OR 111001 = 111111

111001 111111

2 3

2+7
= = 4.5
2

13/18
 = 400

= 4.5 ∗ 50 = 225

á = lim ( ) = lim = lim

→ → ( ) → + ∗ ( − 1)

1
á = lim = lim =
→ + ∗ − → ∗

1 1
á = = = 4.44
225

∗ ∗
á = lim ( ) = lim = lim
→ → ( ) → + ∗ ( − 1)

∗ ∗
á = lim = lim =
→ + ∗ − → ∗

350
á = = = 1.556
225

∗ ∗
á = lim ( ) = lim = lim
→ → ∗ ( ) → ∗( + ∗ ( − 1 ))

∗ ∗
á = lim = lim =
→ ∗( + ∗ − ) → ∗ ∗ ∗

350
á = = = 0.1944
∗ 225 ∗ 8

14/18
Problema 9:
Se tiene un cauce multifuncional con 4 etapas S1, S2, S3, S4que puede ejecutar dos
tipos de operaciones X e Y. Las operaciones del tipo X recorren en cauce según la
secuencia S2, S4, S3, S1, S1, S2 mientras que las del tipo Y lo hacen en el orden S1, S2,
S1, S2, S3, S4. El bucle interno de un programa realiza intensivamente la secuencia de
operaciones X, Y, Y, X, X, Y, Y, Y. ¿Cuánto tiempo tardaría en ejecutarse el tiempo del
bucle si la frecuencia de reloj es 1GHz?

Solución:

1 2 3 4 5 6
S1 Y Y X X
S2 X Y Y X
S3 X Y
S4 X Y

= [1, 5] = [1 ,2, 3, 4]
= [1 ,2, 3, 4] = [2]

1 0 0 0 1 0 1 1 1 1
= =
0 1 1 1 1 0 0 0 1 0

En el problema 2 se mostro como es que se consigue la ruta a partir del diagrama de

estados completo, esta vez no realizaremos el diagrama de estados completo sino
solamente los estados que nos interesan para poder conseguir la ruta que nos piden.

00000 10001 10001

X6 OR =
00000 01111 01111
00000 01111 01111
Y5 OR =
00000 00010 00010
00111 01111 01111
Y1 OR =
00001 00010 00011
00000 10001 10001
X5 OR =
00000 01111 01111
00100 10001 10101
X2 OR =
00011 01111 01111
00000 01111 01111
Y5 OR =
00000 00010 00010
00001 01111 01111
Y3 OR =
00000 00010 00010
00000 10001 10001
X5 OR =
00000 01111 01111

15/18
 X6
Y5

10001 01111
01111 00010
X5
X2 Y1
Y3
X5

10101 01111
01111 00011

Y5

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
X6
Y5
Y1
X5
X2
Y5
Y1
Y3
X5

El tiempo que tarda en ejecutarse esta secuencia es de 27 ciclos.

¿Cuál es la productividad máxima del cauce para esta secuencia?

Si el reloj es de 1GHz entonces la secuencia de operación tardará 28ns, pero podremos

empezar una nueva secuencia cada 27ns.

á = lim ( ) = lim = lim

→ → ( ) → + ∗ ( − 1)

1 1
á = lim = lim = =
→ + ∗ − → ∗ 27

1
á = ∗8 = 296.296
27

16/18
Problema 10:
Una función F va a implementar un cauce con 5 etapas S1, S2, S3, S4, S5de forma que
visita las etapas según la secuencia S1, S5, S1, S4, S3, S2, S1, S4, Obtenga la ganancia
en velocidad con respecto a la ejecución sin un cauce para 200 operaciones, teniendo
en cuenta que sin cauce la función requiere un tiempo de 16ns y que las etapas del
cauce suponen unos tiempos de ejecución de 4ns para S1, S4 y S5, 5ns para S2, y
3ns para S3 (incluyendo los retardos de los registros de acoplo) ¿Cuál es la
productividad en función al número de operaciones?

Solución:

1 2 3 4 5 6 7 8
S1 X X X
S2 X
S3 X
S4 X X
S5 X

= [2, 4, 6]

= (101010)

1 010101 OR 101010 = 111111

3 000101 OR 101010 = 101111
5 000001 OR 101010 = 101011
5 000001 OR 101010 = 101011
3 000101 OR 101010 = 101111
5 000001 OR 101010 = 101011

3 101010 7

5 1
101111 5 111111

101011
3

5+3
= =4
2

( )= á [ 1, 2, 3, 4] +

( )= á [3 ,4 ,5 ]=5

17/18
 =8 ∗5 = 40

=4∗5 = 20

∗ 5 ∗ 200
( )= = = 0.796
+ ∗ ( − 1) 40 + 20 ∗ (200 − 1)

Determine los valores de productividad máxima y ganancia máxima.

á = lim ( ) = lim = lim

→ → ( ) → + ∗ ( − 1)

1
á = lim = lim =
→ + ∗ − → ∗

1 1
á = = = 50
20

∗ ∗
á = lim ( ) = lim = lim
→ → ( ) → + ∗ ( − 1)

∗ ∗
á = lim = lim =
→ + ∗ − → ∗

16
á = = = 0.8
20

Problema 11:
Un procesador segmentado tiene 5 etapas, IF, ID, EX, MEM y OS, y todas tardan un
ciclo excepto la etapa de ejecución (EX) que, según las instrucciones, puede tardar 2
o 3 ciclos. ¿Cuál es la velocidad pico de ese procesador si funciona a 500 MHz?

¿Qué mejora podría implementar para mejorar esa velocidad pico?

¿Qué valor alcanzaría entonces?

18/18