4. PLANIFICACIÓN DINÁMICA DE INSTRUCCIONES
1
PLANIFICACIÓN DINÁMICA DE INSTRUCCIONES
1. El Concepto
2. Método del Marcador (Scoreboard)
3. Método de Tomasulo
2
1. El Concepto
3
PLANIFICACIÓN DINÁMICA DE INSTRUCCIONES
El concepto
Planificación dinámica de instrucciones
DIV.D F1,F2,F3
ADD.D F4,F5,F1
SUB.D F6,F7,F8
IF ID
IF
EXDIV
ID
IF
EXDIV
ID
IF
EXDIV
ID
IF
EXDIV
ID
IF
EXDIV
ID
IF
EXDIV
ID
IF
. . .
. . .
. . .
¿Por qué “SUB.D” tiene que esperar?
• Múltipleso
• Segmentadaso
• Múltiples y segmentadas
Procesador con unidades funcionales
4
El concepto
Planificación dinámica de instrucciones
• De la etapa IF se encarga una unidad especial que va extrayendo instrucciones y dejándolas en un buffer.
• La etapa ID se desdobla en dos:
ID
Emisión• Decodificación
• Resolución de riesgos estructurales
• Resolución de riesgos RAW
• Lectura de los operandos
Lectura de operandos
• La emisión se realiza en orden.
• Lectura de operandos y ejecución se realiza fuera de orden.
5
El concepto
Planificación dinámica de instrucciones
• Simplifica el diseño de compiladores.
• Maneja los casos en los que las dependencias se desconocen en tiempo de compilación.
• Ejecuta eficientemente código compilado para otro procesador compatible.
• Permite aprovechar la espera por fallo de caché.
• Incrementa notablemente la complejidad del hardware.
• Aparecen riesgos WAR y WAW.
• Complica el tratamiento de las interrupciones.
Ventajas:
Inconvenientes:
6
El concepto
Planificación dinámica de instrucciones
• El marcador (Scoreboard)
• Tomasulo
Estudiaremos dos métodos
7
2. Método del Marcador (Scoreboard)
8
PLANIFICACIÓN DINÁMICA DE INSTRUCCIONES
Método del Marcador
Planificación dinámica de instrucciones
Su objetivo es obtener el rendimiento óptimo de una instrucción por ciclo.
El módulo denominado “Marcador” se encarga de supervisar todo el proceso.
Marcador
FP Mult.
. . .
.
Registros
FP Mult.
FP Div.
FP Sum.
U. Entera
FP Sum.
9
Método del Marcador
Planificación dinámica de instrucciones
El método se estructura en cuatro etapas.
Emisión
Lectura de operandos
Ejecución
Escritura de resultados
10
Método del Marcador
Planificación dinámica de instrucciones
¿Riesgosestructurales?
SI
¿RiesgosWAW?
NO
SI
NO
Reservar U.F. y emitir instrucción
Se comprueba que ninguna instrucción activa tenga el mismo registro destino que la instrucción a emitir.
Se comprueba que la unidad funcional que necesita la instrucción esté libre.
1ª ETAPA
EMISIÓN
11
Método del Marcador
Planificación dinámica de instrucciones
¿RiesgosRAW?
SI
NO
Proporcionar operandos a U.F.
Si alguna instrucción activa tiene que escribir en alguno de los operandos fuente de nuestra instrucción, se espera a que esto ocurra.
2ª ETAPA
LECTURA DE OPERANDOS
12
Método del Marcador
Planificación dinámica de instrucciones
Opera la U.F.
La unidad funcional realiza la operación requerida avisando al marcador al finalizar.
3ª ETAPA
EJECUCIÓN
13
Método del Marcador
Planificación dinámica de instrucciones
¿RiesgosWAR?
SI
NO
Escribir resultado en destino
Si una instrucción emitida anteriormente tiene que leer el registro que se va a escribir, se espera a que se realice la lectura.
4ª ETAPA
ESCRITURA DE RESULTADOS
14
Método del Marcador
Planificación dinámica de instrucciones
Para la implementación, el marcador mantiene
tres estructuras:
Estado de las instrucciones
Estado de las unidades
funcionales
Estado de los registros
Estructuras de implementación.
15
Método del Marcador
Planificación dinámica de instrucciones
Estado de las instrucciones
Hay una entrada por cada instrucción activa donde se indica en cuál de las cuatro fases se encuentra.
Fase
Inst. 1 Escritura resultados
Inst. 2 Ejecución
Inst. 3 Lectura operandos
. . .
. . .
16
Método del Marcador
Planificación dinámica de instrucciones
Hay una entrada por cada unidad funcional.
Busy: Indica si está ocupada.Op: Operación que está realizando.FI: Registro destino.FJ y FK: Registros fuente.QJ y QK: U.F.´s que generan los valores de FJ y FK.RJ y RK: Indican si FJ y FK están listos.
Estado de las unidades
funcionales
Busy Op FI FJ FK QJ QK RJ RK
U.F. 1 si + F1 F4 F8 si si
U.F. 2 si / F2 F1 F12 UF 1 no si
U.F. 3 no
. . .
. . .
. . .
. . .
17
Método del Marcador
Planificación dinámica de instrucciones
Estado de los registros
Indica la U.F. que debe escribir su resultado en ese registro.
Si está en blanco es que el valor del registro está actualizado.
F0 F1 F2 F3 F4 F5
U.F. UF 1 UF 2 UF 4
. . .
. . .F30 F31
UF 2
18
Método del Marcador
Tenemos un procesador con las siguientes características:
• Método del Marcador.• 2 unidades funcionales para la suma que utilizan 2 ciclos.• 2 unidades funcionales para la división que utilizan 20 ciclos.• La escritura de registros se realiza en el primer subciclo de reloj.• La lectura de registros se realiza en el segundo subciclo de reloj.
Ejemplo
Vamos a indicar durante qué ciclos tienen lugar cada una de las fases que se corresponden con la ejecución del siguiente código:
DIV F1,F2,F3ADD F4,F1,F3DIV F5,F6,F7ADD F3,F8,F9DIV F7,F3,F10ADD F7,F11,F12
Planificación dinámica de instrucciones 19
Método del Marcador
Instrucción Emisión Lectura Ejecución Escritura
DIV F1,F2,F3
ADD F4,F1,F3
DIV F5,F6,F7
ADD F3,F8,F9
DIV F7,F3,F10
ADD F7,F11,F12
+
+
/
/
1 2 3 - 22 23
1 - 22
Planificación dinámica de instrucciones 20
Instrucción Emisión Lectura Ejecución Escritura
DIV F1,F2,F3
ADD F4,F1,F3
DIV F5,F6,F7
ADD F3,F8,F9
DIV F7,F3,F10
ADD F7,F11,F12
1 2 3 - 22 23
2 23 RAW 24 - 25 26
2 - 25 1 - 22
Método del Marcador
Planificación dinámica de instrucciones
+
+
/
/
21
Instrucción Emisión Lectura Ejecución Escritura
DIV F1,F2,F3
ADD F4,F1,F3
DIV F5,F6,F7
ADD F3,F8,F9
DIV F7,F3,F10
ADD F7,F11,F12
1 2 3 - 22 23
2 23 RAW 24 - 25 26
2 - 25 1 - 22
3 4 5 - 24 25
3 - 24
Método del Marcador
Planificación dinámica de instrucciones
+
+
/
/
22
Instrucción Emisión Lectura Ejecución Escritura
DIV F1,F2,F3
ADD F4,F1,F3
DIV F5,F6,F7
ADD F3,F8,F9
DIV F7,F3,F10
ADD F7,F11,F12
1 2 3 - 22 23
2 23 RAW 24 - 25 26
2 - 25 1 - 22
3 4 5 - 24 25
3 - 24
4 5 6 - 7 24 WAR
4 - 7
Método del Marcador
Planificación dinámica de instrucciones
+
+
/
/
23
Instrucción Emisión Lectura Ejecución Escritura
DIV F1,F2,F3
ADD F4,F1,F3
DIV F5,F6,F7
ADD F3,F8,F9
DIV F7,F3,F10
ADD F7,F11,F12
1 2 3 - 22 23
2 23 RAW 24 - 25 26
2 - 25 1 - 22
3 4 5 - 24 25
3 - 24
4 5 6 - 7 24 WAR
4 - 7
23 RE 24 25 - 44 45
; 23 - 44
Método del Marcador
Planificación dinámica de instrucciones
+
+
/
/
24
Instrucción Emisión Lectura Ejecución Escritura
DIV F1,F2,F3
ADD F4,F1,F3
DIV F5,F6,F7
ADD F3,F8,F9
DIV F7,F3,F10
ADD F7,F11,F12
1 2 3 - 22 23
2 23 RAW 24 - 25 26
2 - 25 1 - 22
3 4 5 - 24 25
3 - 24
4 5 6 - 7 24 WAR
4 - 7
23 RE 24 25 - 44 45
; 23 - 44
46 WAW 47 48 - 49 50
; 46 - 49
Método del Marcador
Planificación dinámica de instrucciones
+
+
/
/
25
3. Método de Tomasulo
26
PLANIFICACIÓN DINÁMICA DE INSTRUCCIONES
Método de Tomasulo
Planificación dinámica de instrucciones
También intenta conseguir el rendimiento óptimo de una instrucción por ciclo.
No hay un módulo que centralice la supervisión.
Técnica de renombrado de registros para solucionar los riesgos WAR y WAW.
27
Método de Tomasulo
Planificación dinámica de instrucciones
FIFO de instrucciones.
Registros.
28
Método de Tomasulo
Planificación dinámica de instrucciones
Unidades funcionales.
29
Método de Tomasulo
Planificación dinámica de instrucciones
Estaciones de reserva.
Las instrucciones se envían a las estaciones de reserva hasta que están listas para ejecutarse.
30
Método de Tomasulo
Planificación dinámica de instrucciones
Buffers de carga.
Buffers de almacenamiento.
31
Método de Tomasulo
Planificación dinámica de instrucciones
CDB
(Common Data Bus)
Envía los resultados al registro o E.R. en espera.
Si varias instrucciones tienen el mismo registro destino, solo la última actualiza dicho registro.
32
Método de Tomasulo
Planificación dinámica de instrucciones
El método se estructura en tres etapas.
Emisión
Ejecución
Escritura de resultados
33
Método de Tomasulo
Planificación dinámica de instrucciones
1ª ETAPA
EMISIÓN
34
¿Operandosdisponibles?
NOSI
Enviar operandos a la E.R.
Indicar las E.R. con las instrucciones
que los generarán
¿Todos los operandos en
la E.R.?
NO
SI
¿E.R.disponible?
NO
SI
Enviar instrucción a la E.R.
Método de Tomasulo
Planificación dinámica de instrucciones
Ejecutar en la U.F.
2ª ETAPA
EJECUCIÓN
35
Método de Tomasulo
Planificación dinámica de instrucciones
3ª ETAPA
ESCRITURA DE RESULTADOS
Envía los resultados al
CDB
Desde el CDB se reenvía a los
registros o E.R. que lo espere
36
Método de Tomasulo
Planificación dinámica de instrucciones
El tratamiento es similar.
No se permite la ejecución de una instrucción hasta que no se hayan resuelto las instrucciones de salto que la precedan.
LOAD / STORE
INSTRUCCIONES DE SALTO
Buffersde carga y
almacenamiento
Estacionesde reserva
Facilita el tratamiento de las interrupciones.
37
Método de Tomasulo
Planificación dinámica de instrucciones
Para la implementación del método de Tomasulo hay que
agregar cierta información a cada uno de los siguientes
elementos:
Estaciones de reserva
Banco de registros
Buffers de carga
Estructuras de implementación.
Buffers de almacenamiento
38
Planificación dinámica de instrucciones
Hay una entrada por cada estación de reserva.
Busy: Indica si está ocupada la E.R y su U.F.Op: Operación a realizar en la U.F.VJ y VK: Valores de los operandos.QJ y QK: E.R. que generará el operando VJ y VK.
Busy Op VJ VK QJ QK
E.R. 1 si + 10 44
E.R. 2 si / 200 1
E.R. 3 no
. . .
. . .
. . .
Estaciones de reserva
Método de Tomasulo
39
Planificación dinámica de instrucciones
Hay una entrada por cada registro.
QI: E.R. que generará el resultado a almacenar en el correspondiente registro.
QJ
F0
F1 4
F2
. . .
. . .
Banco de registros
Método de Tomasulo
40
Planificación dinámica de instrucciones
Hay una entrada por cada buffer de carga.
Busy: Indica si el buffer está ocupado.A: Dirección de acceso a memoria.
Busy A
B.C. 1 si 200
B.C. 2 si 1000
B.C. 3 no
. . .
. . .
Buffers de carga
Método de Tomasulo
41
Planificación dinámica de instrucciones
Hay una entrada por buffer de almacenamiento.
Busy: Indica si el buffer está ocupado.A: Dirección de acceso a memoria.VI: Valores de los operandos.QI: E.R. que generará el operando VI.
Busy A VI QI
B.A. 1 no
B.A. 2 si 3500 22
B.A. 3 no
. . .
. . .
. . .
Buffers de almacenamiento
Método de Tomasulo
42
Método de Tomasulo
Tenemos un procesador con las siguientes características:
• Método de Tomasulo.• 1 unidad funcional para suma y resta que utiliza 2 ciclos.• 1 unidad funcional para multiplicación y división que utiliza 20 ciclos.• Cada unidad funcional dispone de 2 estaciones de reserva.
Ejemplo
Vamos a indicar durante qué ciclos tienen lugar cada una de las fases que se corresponden con la ejecución del siguiente código:
SUB F1,F2,F3ADD F4,F1,F3DIV F5,F6,F7ADD F3,F8,F9DIV F7,F3,F10ADD F7,F11,F12SUB F13,F13,F7SUB F14,F14,F15
Planificación dinámica de instrucciones 43
Método de Tomasulo
Instrucción Emisión Ejecución Escritura
SUB F1,F2,F3
ADD F4,F1,F3
DIV F5,F6,F7
ADD F3,F8,F9
DIV F7,F3,F10
ADD F7,F11,F12
SUB F13,F13,F7
SUB F14,F14,F15
Planificación dinámica de instrucciones
1 2 - 31 2 - 3 4
ER1 ER2 + -
ER3 ER4 * /
44
Método de Tomasulo
Instrucción Emisión Ejecución Escritura
SUB F1,F2,F3
ADD F4,F1,F3
DIV F5,F6,F7
ADD F3,F8,F9
DIV F7,F3,F10
ADD F7,F11,F12
SUB F13,F13,F7
SUB F14,F14,F15
Planificación dinámica de instrucciones
1
ER1 ER2 + -
ER3 ER4 * /
2 - 31 2 - 3 4
2 - 4 5 - 62 5 - 6 RAW 7
45
Método de Tomasulo
Instrucción Emisión Ejecución Escritura
SUB F1,F2,F3
ADD F4,F1,F3
DIV F5,F6,F7
ADD F3,F8,F9
DIV F7,F3,F10
ADD F7,F11,F12
SUB F13,F13,F7
SUB F14,F14,F15
Planificación dinámica de instrucciones
1
ER1 ER2 + -
ER3 ER4 * /
2 - 31 2 - 3 4
2 - 4 5 - 62 5 - 6 RAW 7
3 4 - 23 24
3 4 - 23
46
Método de Tomasulo
Instrucción Emisión Ejecución Escritura
SUB F1,F2,F3
ADD F4,F1,F3
DIV F5,F6,F7
ADD F3,F8,F9
DIV F7,F3,F10
ADD F7,F11,F12
SUB F13,F13,F7
SUB F14,F14,F15
Planificación dinámica de instrucciones
1
ER1 ER2 + -
ER3 ER4 * /
2 - 31 2 - 3 4
2 - 4 5 - 62 5 - 6 RAW 7
3 4 - 23 24
3 4 - 23
4 7 - 8 RE 9
4 - 6 7 - 8
47
Método de Tomasulo
Instrucción Emisión Ejecución Escritura
SUB F1,F2,F3
ADD F4,F1,F3
DIV F5,F6,F7
ADD F3,F8,F9
DIV F7,F3,F10
ADD F7,F11,F12
SUB F13,F13,F7
SUB F14,F14,F15
Planificación dinámica de instrucciones
1
ER1 ER2 + -
ER3 ER4 * /
2 - 31 2 - 3 4
2 - 4 5 - 62 5 - 6 RAW 7
3 4 - 23 24
3 4 - 23
4 7 - 8 RE 9
4 - 6 7 - 8
24 - 43 RAW
RE5 44
5 - 23 24 - 43
48
Método de Tomasulo
Instrucción Emisión Ejecución Escritura
SUB F1,F2,F3
ADD F4,F1,F3
DIV F5,F6,F7
ADD F3,F8,F9
DIV F7,F3,F10
ADD F7,F11,F12
SUB F13,F13,F7
SUB F14,F14,F15
Planificación dinámica de instrucciones
1
ER1 ER2 + -
ER3 ER4 * /
2 - 31 2 - 3 4
2 - 4 5 - 62 5 - 6 RAW 7
3 4 - 23 24
3 4 - 23
4 7 - 8 RE 9
4 - 6 7 - 8
24 - 43 RAW
RE5 44
5 - 23 24 - 43
6 9 - 10 RE 11
6 - 8 9 - 10
49
Método de Tomasulo
Instrucción Emisión Ejecución Escritura
SUB F1,F2,F3
ADD F4,F1,F3
DIV F5,F6,F7
ADD F3,F8,F9
DIV F7,F3,F10
ADD F7,F11,F12
SUB F13,F13,F7
SUB F14,F14,F15
Planificación dinámica de instrucciones
1
ER1 ER2 + -
ER3 ER4 * /
2 - 31 2 - 3 4
2 - 4 5 - 62 5 - 6 RAW 7
3 4 - 23 24
3 4 - 23
4 7 - 8 RE 9
4 - 6 7 - 8
24 - 43 RAW
RE5 44
5 - 23 24 - 43
6 9 - 10 RE 11
6 - 8 9 - 10
¿WAW?¡NO!
50
Método de Tomasulo
Instrucción Emisión Ejecución Escritura
SUB F1,F2,F3
ADD F4,F1,F3
DIV F5,F6,F7
ADD F3,F8,F9
DIV F7,F3,F10
ADD F7,F11,F12
SUB F13,F13,F7
SUB F14,F14,F15
Planificación dinámica de instrucciones
1
ER1 ER2 + -
ER3 ER4 * /
2 - 31 2 - 3 4
2 - 4 5 - 62 5 - 6 RAW 7
3 4 - 23 24
3 4 - 23
4 7 - 8 RE 9
4 - 6 7 - 8
24 - 43 RAW
RE5 44
5 - 23 24 - 43
6 9 - 10 RE 11
6 - 8 9 - 10
7 12 - 13 RAW 14
7 - 11 12 - 13
51
Método de Tomasulo
Instrucción Emisión Ejecución Escritura
SUB F1,F2,F3
ADD F4,F1,F3
DIV F5,F6,F7
ADD F3,F8,F9
DIV F7,F3,F10
ADD F7,F11,F12
SUB F13,F13,F7
SUB F14,F14,F15
Planificación dinámica de instrucciones
1
ER1 ER2 + -
ER3 ER4 * /
2 - 31 2 - 3 4
2 - 4 5 - 62 5 - 6 RAW 7
3 4 - 23 24
3 4 - 23
4 7 - 8 RE 9
4 - 6 7 - 8
24 - 43 RAW
RE5 44
5 - 23 24 - 43
6 9 - 10 RE 11
6 - 8 9 - 10
7 12 - 13 RAW 14
7 - 11 12 - 13
9 RE 11 - 12 RE 13
9 - 10 11 - 12
52
Método de Tomasulo
Instrucción Emisión Ejecución Escritura
SUB F1,F2,F3
ADD F4,F1,F3
DIV F5,F6,F7
ADD F3,F8,F9
DIV F7,F3,F10
ADD F7,F11,F12
SUB F13,F13,F7
SUB F14,F14,F15
Planificación dinámica de instrucciones
1
ER1 ER2 + -
ER3 ER4 * /
2 - 31 2 - 3 4
2 - 4 5 - 62 5 - 6 RAW 7
3 4 - 23 24
3 4 - 23
4 7 - 8 RE 9
4 - 6 7 - 8
24 - 43 RAW
RE5 44
5 - 23 24 - 43
6 9 - 10 RE 11
6 - 8 9 - 10
7 14
7 - 11 12 - 13
9 RE 11 - 12 RE 13
9 - 10 11 - 12
12 - 13 RAW
53
Método de Tomasulo
Instrucción Emisión Ejecución Escritura
SUB F1,F2,F3
ADD F4,F1,F3
DIV F5,F6,F7
ADD F3,F8,F9
DIV F7,F3,F10
ADD F7,F11,F12
SUB F13,F13,F7
SUB F14,F14,F15
Planificación dinámica de instrucciones
1
ER1 ER2 + -
ER3 ER4 * /
2 - 31 2 - 3 4
2 - 4 5 - 62 5 - 6 RAW 7
3 4 - 23 24
3 4 - 23
4 7 - 8 RE 9
4 - 6 7 - 8
24 - 43 RAW
RE5 44
5 - 23 24 - 43
6 9 - 10 RE 11
6 - 8 9 - 10
7 15
7 - 11 12 - 13
9 RE 11 - 12 RE 13
9 - 10 11 - 12
13 - 14 RAW
RE
7 - 12 13 - 14
54
Top Related