Download Segmentación William Stallings, Organización y Arquitectura de

Segmentación del ciclo de
instr ucción
v.2012
William Stallings, Organización y Arquitectura de Computadores,
Capítulo 11: Estructura y función de la CPU.
John Hennessy – David Patter son, Arquitectura de Computadores –
Un enfoque cuantitativo 1a Edición
Capítulos 5 y 6
(4a Edición, Apéndice A)
Segmentación
El ciclo de instr ucción




Fundamento: Sólo una parte del hardware es utilizado en cada etapa del ciclo de
instr ucción.
Definición: Técnica de implementación (invisible al programador) que superpone, en el
tiempo, las diferentes etapas del ciclo de instrucción. Explotación del par alelismo entre
partes de las instrucciones.
Ejemplo de la línea de montaje (PIPELINE, tubería?). Aumenta productividad, pero desmejora
la latencia (la sincronización entre etapas es costosa).
Es imposible realizar una instrucción en un ciclo de reloj. El óptimo esperable sería realizar
cada etapa del pipeline en un ciclo de reloj, alcanzando una pr oductividad de una
instrucción por ciclo.
Segmentación
El ciclo de instr ucción
Modelo más simple: 3 etapas (3-stage pipeline).
Requisitos:
- registros intermedios
- banco multiport (2+1)
MEM
UC
ALU (Datapath)
← Instrucciones
i
FETCH
FETCH
i+1
DECODIFICACION
DECODIFICACION
EJECUCION DE
EJECUCION DE
LA INSTRUCCION
LA INSTRUCCION
DECODE
DECODE
EXECUTE
EXECUTE
FETCH
FETCH
DECODE
DECODE
EXECUTE
EXECUTE
FETCH
FETCH
DECODE
DECODE
EXECUTE
EXECUTE
n+2
n+3
n+4
i+2
n
CAPTACION DE
CAPTACION DE
LA INSTRUCCION
LA INSTRUCCION
n+1
Ciclos ->
Si la etapa de ejecución es la única que tiene acceso al DATAPATH, es la etapa más larga
(debe acceder a los registros operando, realizar la operación, y almacenar el resultado.
Segmentación
El ciclo de instr ucción
Se pude trasladar el acceso a los registros operando a la etapa de decodificación y
agregar una cuarta etapa de escritura del resultado en registro (WB: write back).
La etapa de ejecución sólo realiza la operación de la ALU. Las etapas 2 y 4
acceden al banco de registros (multiport).
Falta prever el acceso a memoria. Segmentación en 5 etapas
LOAD: F-D-CA-TR-WB
Segmentación
Oper ando en memor ia
STALLINGS
MEMORIA
(programa)
CAPTACION DE
CAPTACION DE
LA INSTRUCCION
LA INSTRUCCION
FI
UC y REGISTROS
DECODIFICACION
DECODIFICACION
DI
CALCULO DIR
CALCULO DIR
DEL OPERANDO
DEL OPERANDO
CO
MEMORIA
(datos)
CAPTACION DEL
CAPTACION DEL
OPERANDO
OPERANDO
FO
ALU
EJECUCION DE
EJECUCION DE
LA INSTRUCCION
LA INSTRUCCION
EI
ESCRITURA DEL
ESCRITURA DEL
OPERANDO
OPERANDO
WO
ALU
CISC:
CISC:operando
operandoen
enmemoria
memoria
REGISTROS
Segmentación
Oper ando en memor ia
Segmentación
Condiciones necesar ias



Las instrucciones deben poder ser descompuestas en k etapas de
menor duración.
Las entradas de cada etapa ki deben estar determinadas únicamente
por las salidas de la etapa anterior ki-1.
Las duraciones de las diferentes etapas ti deben ser comparables. El
clock del pipeline estará determinado por la etapa más lenta
(t=max{ti }).
Latencia
Latenciade
detodas
todaslas
lasinstrucciones
instrucciones==k.t
k.t
Productividad
Productividadmáxima
máxima==1/t
1/t
Segmentación
Mejor a – Pr oductividad vs. latencia




Luego de k-1 ciclos las k etapas del pipeline estarán trabajando.
Teóricamente en ese momento el pipeline tiene la máxima productividad (k
instrucciones simultáneas) hasta que se altere la secuencia (salto o interrupción).
Si aumento el número de etapas, aumenta la productividad, hasta cierto punto (ver
luego).
Si el pipeline tiene k etapas de duración t (duración de la etapa más larga), al
ejecutarse un conjunto de n instrucciones, la mejora obtenida con esta técnica puede
expresarse como:
T
nkt
nk
S=
=
=
→k
T P t ( k −1 ) +nt k+n−1
OBJETIVOS DEL DISEÑADOR: Equilibrar las etapas (igual duración), hacerlas
independientes (que no compartan recursos) y mantenerlas ocupadas (atenuar los efectos de
los saltos y la dependencia de datos)
Segmentación
Límites en la implementación




Retardo adicional al tener que presentar la información entre etapas
en registros intermedios (control de la segmentación).
La única opción es implementar las etapas de igual duración y
todas las instrucciones deben respetarlas.
Aumenta la complejidad de la CPU.
Difícil mantener el cauce completo debido a los r iesgos de l a
segmentación (a continuación).
TIPICO 3-5 ETAPAS
MAXIMO 6-9 ETAPAS
Segmentación
Ejemplos



80486 y Pentium: cinco etapas para instrucciones con enteros (FI, D1, D2, EX, WB)
y ocho para instrucciones de punto flotante.
PowerPC: cuatro etapas para instrucciones con enteros y seis para instrucciones de
punto flotante.
H-P (DLX): cinco etapas (IF, ID, EX, MEM, WB).
Pow er PC: Es una arquitectura de computadoras de tipo RISC introducida en 1990 por la
Alianza AIM, un consorcio de empresas compuesto por Apple, IBM y Motorola, de cuyas
primeras letras, surgió la sigla. Los procesadores de esta familia son producidos por IBM y
Freescale Semiconductor que es la division de semiconductores y microprocesadores de
Motorola, siendo utilizados principalmente en ordenadores o computadores Macintosh de
Apple Computer. Mas información en el sitio de IBM, Arquitecturas Power. Práctica de
repaso: comparación con Pentium en Stallings, capítulos 1, 4 y 11.
Segmentación
HP en cinco etapas
RISC:
RISC:carga/almacenamiento
carga/almacenamiento
DATAPATH
4c < CPI < 5c
1. FI: Captar la instrucción e incrementar PC
1. FI: Captar la instrucción e incrementar PC
2. ID: Decodificar instrucción y captar registros
2. ID: Decodificar instrucción y captar registros
3. EX: Tres opciones: calcular dirección efectiva, ALU o salto
3. EX: Tres opciones: calcular dirección efectiva, ALU o salto
4. MEM: Acceso a memoria (solo carga o almacenamiento) – (Terminan store y saltos: 4c)
4. MEM: Acceso a memoria (solo carga o almacenamiento) – (Terminan store y saltos: 4c)
5. WB: Escribir registro de salida – (Termina el resto: 5c)
5. WB: Escribir registro de salida – (Termina el resto: 5c)
1. Captación (fetch) IF
La instrucción es transferida al registro de instrucción. En dos pasos porque el PC no tiene conexión directa a
memoria.
MAR ← PC; IR ← M[MAR]
2. Decodificación (decode) ID
Decodificación y lectura de los registros involucrados. Puede hacerse simultáneamente por ser campo fijo.
A ← Rs1; B ← Rs2; PC ← PC + 4
3. Ejecución (execute) EX
Operación de la ALU. Depende del tipo de instrucción. Referencia a memoria, salto/bifurcación o instrucción
ALU. No al mismo tiempo.
ALUout ← A op B o
MAR ← A + (IR)16; MDR ← Rd
4. Acceso a memoria (memory access) MEM
Se accede a memoria si es necesario (carga o almacenamiento) con la dirección calculada en el paso anterior. O
realizar el salto.
MDR ← M[MAR]; M[MAR] ← MDR
5. Post-escritura (write-back) WB
Escribir resultado en el registro, tanto si viene de la ALU como si viene de memoria.
Rd ← ALUoutA o MDR
Segmentación
HP en cinco etapas
Segmentación
HP en cinco etapas
Segmentación
HP en cinco etapas
Requisitos:
- registros intermedios
- banco multiport (2 lecturas + 1 escritura)
- memoria de datos e instrucciones separadas
- incrementar PC
- detección temprana de saltos (riesgos de control) + forwarding (dependencias)
Segmentación
ARM7 ( 3) y ARM9 ( 5)
Volver a la pr áctica de
r epaso
Segmentación
Cor tex-M3 en tr es etapas
Segmentación
Riesgos de la implementación
HAZARDS: Situaciones que impiden la ejecución de la próxima instrucción
de la secuencia durante su correspondiente ciclo (el procesador queda
detenido, suspendido, stalled, durante uno o más ciclos). Todas las
instrucciones posteriores son también suspendidas y no se realiza una
nueva captación mientras dure la suspensión.
Clasificación:
 Riesgos estructurales
 Riesgos por dependencia de datos
 Riesgos de control
Segmentación > Riesgos
1. Riesgos estr uctur ales
Sucede cuando un recurso (memoria, alu) debe ser utilizado por varias instrucciones
simultáneamente.
Ejemplo: una instrucción de carga desde memoria impide el acceso durante un ciclo. El
fetch de la instrucción i+3 debe ser suspendido.
Penalidad: 1 ciclo
Segmentación > Riesgos > 1. Estructurales
Ejemplo
Segmentación > Riesgos > 1. Estructurales
Ejemplo (cont)
Segmentación > Riesgos > 1. Estructurales
Reducción de los efectos





Duplicación de recursos, por ejemplo en el caso de la ALU.
Cache de datos e instrucciones independientes, para evitar los
conflictos de memoria.
Un solo acceso a memoria de datos por instrucción (RISC).
Lectura (x2) y escritura (x1) simultánea del banco de registros
(RISC).
Las unidades funcionales de PF pueden ser a la vez segmentadas
para soportar varias instrucciones simultáneas (ver luego).
Segmentación > Riesgos
2. Riesgos por dep. de datos
Sucede principalmente cuando una instrucción requiere un dato generado por
la ejecución de una instrucción anterior que aún no ha finalizado.
Ejemplo:
Penalidad: 2 ciclos
Segmentación > Riesgos > 2. Dependencia de datos
Clasificación
Para dos instrucciones consecutivas los riesgos pueden clasificarse en tres
categorías, siendo la primera la más usual.



RAW (read after write): la segunda instrucción lee un dato antes que la primera
lo genere. Lee el dato antiguo.
WAR (write after read): la segunda escribe un destino antes que sea leído por la
primera. La primera toma el valor incorrecto (nuevo).
WAW (write after write): la segunda escribe un operando antes de que sea
escrito por la primera. Escrituras en orden incorrecto. Queda lo escrito por la
primera.
Segmentación > Riesgos > 2. Dependencia de datos
Reducción de los efectos
ADELANTAMIENTO (forwarding, bypassing)
Camino adicional de HW.
El resultado de la ALU es realimentado a su
entrada, evitando el ciclo de escritura WO.
Penalidad: 1 ciclo (antes 2)
Segmentación > Riesgos > 2. Dependencia de datos
Forwarding
Segmentación > Riesgos > 2. Dependencia de datos
Forwarding (cont)
Extensión de la segmentación para manipular operaciones multiciclo
EMISION DE INSTRUCCIONES
Antes de emitir una nueva instrucción de punto flotante
- Comprobar riesgos estructurales
- Comprobar dependencia de datos RAW
- Comprobar adelantamiento
Extensión de la segmentación para manipular operaciones multiciclo
SEGMENTACION DE LAS UNIDADES FUNCIONALES
Segmentación > Riesgos
3. Riesgos de contr ol
Efecto de las
INTERRUPCIONES
Producidos por las instrucciones de salto.
Ejemplo salto incondicional: no se conoce la dirección de la próxima
instrucción hasta después del FO. Se realiza el fetch de la instrucción
siguiente y luego se descarta.
Penalidad: 3 ciclos
Segmentación > Riesgos > 3. De control
Ejemplo
Salto condicional que SALTA: no se conoce la dirección de la próxima instrucción
hasta después del EI.
Penalidad: 3 ciclos
Segmentación > Riesgos > 3. De control
Ejemplo (cont)
Ejemplo salto condicional que NO SALTA: no se conoce la condición hasta
después del EI, cuando la siguiente instrucción puede continuar.
Penalidad: 2 ciclos
Existe penalidad aunque no salte!
Segmentación > Riesgos > 3. De control
Estadísticas
Las operaciones de control (condicionales o incondicionales) son muy
frecuentes en los programas reales, por lo que pueden reducir drásticamente
la performance del pipeline.
Estadísticas:

20-35% de las operaciones son saltos.

~65% de dichas operaciones toman el salto.

Hay casi el doble de saltos condicionales que de saltos incondicionales.
Segmentación > Riesgos > 3. De control
Reducción de los efectos

Instr uction fetch units y colas de instr ucciones (hardware
adicional)

Buffer de bucles (pequeña cache de instrucciones consecutivas) [CRAY-1]
Útiles solo en el caso de saltos incondicionales.
Segmentación > Riesgos > 3. De control
Reducción de los efectos (cont)
Flujos múltiples:
Se siguen los dos caminos posibles, duplicando las partes iniciales del hardware.
Puede entrar en el cauce una nueva bifurcación.
[IBM 370/168]
Salto r etar dado:
Modificación del ciclo de instrucción, que requiere reordenamiento del código
por parte del compilador.
Luego de cada instrucción de salto hay un branch delay slot: la instrucción
siguiente se ejecuta SIEMPRE.
60-80% efectivo, si no NOP.
[RISC]
Segmentación > Riesgos > 3. De control
Reducción de los efectos (cont)
Pr edicción de saltos:
−
−
Estática

Siempre salta o nunca salta [Motorola 68020]

Depende de la direccion [PowerPC 601]
Dinámica


Uno o dos bits (HW) asociados a cada instrucción de salto [IBM
3090/400]
Tabla de historia de saltos (memoria cache: tabla con dirección de la
instrucción de bifurcación + bits de historia + destino) [AMD 29000]
NOTA: Ejecución especulativa (no solo fetch, comienzo a ejecutar)
Segmentación > Riesgos > 3. De control
Reducción de los efectos (cont)
Esquema típico de predicción dinámica con dos bits: cambiar la predicción solo
si suceden dos predicciones incorrectas consecutivas (ver variantes).
Segmentación > Riesgos
Resumen
RIESGOS
RIESGOSESTRUCTURALES
ESTRUCTURALES
(conflicto
(conflictode
derecursos)
recursos)
RIESGOS
RIESGOSPOR
PORDEPENDENCIA
DEPENDENCIADE
DEDATOS
DATOS
(RAW-WAR-WAW)
(RAW-WAR-WAW)
RIESGOS
RIESGOSDE
DECONTROL
CONTROL
(saltos
(saltos- -interrupciones)
interrupciones)
Segmentación
Sumar io





Las instrucciones son ejecutadas por la CPU como una secuencia de pasos. La ejecución de
instrucciones puede acelerarse sustancialmente utilizando segmentación (pipelining)
Un pipeline se organiza como una secuencia de k etapas. En un cierto instante puede haber k
instrucciones activas en el pipeline. Ejemplo línea de montaje.
Aumentar el número de etapas aumenta la productividad, hasta cierto punto.
Los riesgos (hazards) impiden mantener la máxima tasa. Los riesgos estructurales se deben a
conflictos en la utilización de recursos. También existen riesgos por dependencia de datos
(inevitables) y riesgos de control debidos a las instrucciones de salto.
Las instrucciones de salto pueden deteriorar significativamente la performance del pipeline,
por lo que deben aplicarse técnicas que reduzcan sus efectos.