Paralelismo a nivel de instrucción (ILP) en SW o HW.
Paralelismo al nivel de bucle es más fácil de ver.
Las dependencias del paralelismo SW definidas por programa se convierten en riesgos si el HW no puede resolverlas.
Dependencias SW: sofisticación del compilador determina si el compilador puede desenrollar bucles.
Las dependencias de Memoria son las más difíciles de determinar.
HW explotando el ILP.
Funciona bien cuando no se pueden conocer las dependencias en run time.
El código para una máquina se ejecuta bien en otras.
Idea clave del Scoreboard: permitir a las instrucciones detrás de una burbuja que prosigan (Decode => Issue instr & read operands).
Permitir la ejecución out-of-order => finalización out-of-order (completion).
Etapa ID verifica los riesgos estructurales & dependencias de datos.
1
SUMARIO
Limitaciones del scoreboard:
No hay hardware para forwarding.
Limitado a instrucciones en bloques básicos (secuencias de código sin saltos) (ventanas pequeñas).
Pequeño número de unidades funcionales (riesgos estructurales), especialmente unidades enteras/load store.
No se emite en caso de riesgo estructural.
Se espera por los riesgos WAR.
Previene los riesgos WAW.
No permite que dos instrucciones terminen el mismo ciclo.
No permite manejar unidades funcionales segmentadas.
Mejoras
Una mejora fácil de introducir es permitir que el algoritmo pueda manejar unidades funcionales segmentadas.
2
SCOREBOARD RESUMEN
Desarrollado para el IBM 360/91 3 años después del CDC 6600 (1966)
Objetivo: Obtener altas prestaciones sin utilizar compiladores especiales
Diferencias entre IBM 360 & CDC 6600 ISA
IBM tiene sólo 2 especificadores de registro/instr vs. 3 en el CDC 6600
IBM tiene 4 FP registros vs. 8 en CDC 6600
¿Por qué estudiarlos? Conducen al Alpha 21264, HP 8000, MIPS 10000, Pentium II, PowerPC 604, …
3
ALGORITHMO DE TOMASULO
Control & buffers distribuidos con Unidades Funcionales(FU) en vez del control y buffers centralizado utilizado en scoreboard;
Los buffers de las FU se denominan “estaciones de reserva”; contienen los operandos pendientes.
Los Registros en las instrucciones son reemplazados por valores o punteros a las estaciones de reserva(RS); esto se denomina renombrado de registros;
Evita los riesgos WAR, WAW.
Hay más estaciones de reserva que registros, por lo que pueden realizar optimizaciones que los compiladores no pueden.
Los resultados de las FU van a las RS, pero no a través de los registros, el Common Data Bus es el que difunde los resultados a todas las FUs.
Load y Stores, se tratan como FUs con RSs también.
Instrucciones Enteras pueden adelantar a los branches, permitiendo las operaciones FP más allá de los bloques básicos en la cola de FP.
4
TOMASULO VS. SCOREBOARD
5
(Gp:) FP adders
(Gp:) Add1
Add2
Add3
(Gp:) FP multipliers
(Gp:) Mult1
Mult2
(Gp:) From Mem
(Gp:) FP Registers
(Gp:) Reservation
Stations
(Gp:) Common Data Bus (CDB)
(Gp:) To Mem
(Gp:) FP Op Queue
(Gp:) Load Buffers
(Gp:) Store
Buffers
(Gp:) Load1
Load2
Load3
Load4
Load5
Load6
TOMASULO: ORGANIZACIÓNEsquema original
Op—Operación a realizar en la unidad (e.g., + or –)
Vj, Vk—Valores de los operandos fuente
Buffers de Store tienen un campo V , resultado a ser almacenado
Qj, Qk—Estaciones de Reserva producen los registros fuente (el valor a escribir)
Nota: No hay flags de ready como en Scoreboard; Qj,Qk=0 => ready
Los buffers de Store sólo tienen Qi para la estación de reserva RS que produce el resultado
Busy—Indica si la estación de reserva or FU esta ocupada
Register result status—Indica qué unidad funcional escribirá en cada registro, si es que hay alguno. En blanco cuando no hay ninguna instrucción pendiente que vaya a escribir ese registro.
6
COMPONENTES DE LAS ESTACIONES DE RESERVA
1. Issue—obtiene la instrucción de la cola de Op (si no hay cola del buffer)
Si la estación de reserva está libre (no hay riesgo estructural), el control emite la instr & envía los operandos (renombrando los registros).
2. Ejecución—opera sobre los operandos (EX)
Cuando ambos operandos están disponibles entonces se ejecuta; Si no están disponibles, se observa el Common Data Bus por el resultado
3. Escritura del resultado—finaliza la ejecución (WB)
Escribe en el Common Data Bus para todas las unidades que esperan; marca la estación de reserva como disponible
Normal data bus: data + destino (“go to” bus)
Common data bus: data + fuente (“come from” bus)
64 bits de datos + 4 bits de dirección fuente de la U.Funcional
Escribe si casa con la U. Funcional esperada (produce el resultado)
Realiza el broadcast
7
7
ETAPAS DEL ALGORITMO DE TOMASULO
8
(Gp:) IF
(Gp:) ID
(Gp:) FP Mult
(Gp:) FP Add
(Gp:) Wb
(Gp:) ExFU1
(Gp:) ExFU2
(Gp:) IS
(Gp:) RSFPmult
(Gp:) RSFPadd
(Gp:) FP Div
(Gp:) RSFPdiv
(Gp:) ExFU3
(Gp:) Bus
Común de
Datos
(Gp:) Cache Instr
(Gp:) Banco Reg
(Gp:) Integer ALU
(Gp:) MEM
(Gp:) Exint
(Gp:) RSInt
(Gp:) Cache
Datos
CAUCE DLX CON TOMASULO
RESUMEN ALGORITMO
9
ESTRUCTURA DE DATOS BÁSICA PARA DLX
10
Instr. status
(Gp:) Reg
(Gp:) ….
(Gp:) r1
(Gp:) r2
(Gp:) r4
(Gp:) r3
(Gp:) rm
Register Result status
Clock
(Gp:) Busy
(Gp:) Op
(Gp:) Uf Entera Rs1
(Gp:) Vj
(Gp:) Vk
(Gp:) Qj
(Gp:) Qk
(Gp:) Uf FP Add Rs1
(Gp:) Uf FP Div Rs1
(Gp:) Uf FP Mult Rs1
(Gp:) Functional Unit status
(Gp:) Uf Entera Rs2
(Gp:) Uf FP Add Rs2
(Gp:) Uf FP Mult Rs2
(Gp:) Uf FP Div Rs2
Página siguiente |