capítulo 5 el procesador. introducción factores de desempeño del cpu cantidad de instrucciones ...
TRANSCRIPT
Capítulo 5
El Procesador
Introducción
Factores de desempeño del CPU Cantidad de instrucciones
Determinados por la ISA y el compilador CPI y tiempo de ciclo
Determinados por el Hardware del CPU Se examinarán la implementación de 2 arquitecturas MIPS
Una versión simplificada Una versión segmentada más real
Un subconjunto simple Referencia a memoria: lw, sw, lb, sb Aritmética/lógica: add, sub, and, or, slt, ... Transferencia de control: beq, j, ...
Capítulo 5 — El procesadorCapítulo 5 — El procesador
§4.1
Intro
ducció
n
Ejecución de instrucciones
PC búsqueda de instrucciones Números de registros archivo de registros, leer
registros Dependiendo de la clase de instrucción
Usar ALU para calcular Resultados aritméticos Direcciones de memoria para lectura/escritura
Acceder datos de memoria para lectura/escritura PC PC + 4
Capítulo 5 — El procesadorCapítulo 5 — El procesador
Una Visión del CPU
Capítulo 5 — El procesadorCapítulo 5 — El procesador
Multiplexores
Capítulo 5— El procesadorCapítulo 5— El procesador
No se pueden colocar buses juntos Usar multiplexores
Control (beq, j)
Capítulo 5 — El procesadorCapítulo 5 — El procesador
Diseño lógico básico
La información se codifica en binario Nivel de voltaje bajo = 0, Nivel alto = 1 Un alambre por bit Datos multi-bit codificados en buses multi-alambres
Elementos combinatorios Opera sobre datos La salida es una función de la entrada
Elementos de estado (secuencial) Almacenar información
Capítulo 5 — El procesadorCapítulo 5 — El procesador
Elementos combinatorios
Compuerta AND Y = A & B
Capítulo 5 — El procesadorCapítulo 5 — El procesador
MultiplexorY = S ? I1 :
I0
SumadorY = A + B
Unidad aritmética/lógicaY = F(A, B)
Elementos secuenciales
Registros: almacenar datos en un circuito Utiliza una señal de reloj para determinar cuando actualizar un valor
almacenado Disparado por flancos: actualizar cuando la señal de reloj cambia de 0
a 1
Capítulo 5 — El procesadorCapítulo 5 — El procesador
D
Clk
QClk
D
Q
Elementos secuenciales
Registros con control de escritura Sólo se actualiza con los flancos del reloj cuando la entrada de control es 1 Utilizado cuando un valor almacenado se requiere posteriormente
Capítulo 5 — El procesadorCapítulo 5 — El procesador
D
Clk
Q
Write
Write
D
Q
Clk
Metodología de sincronización
La lógica combinatoria transforma los datos durante los ciclos de reloj Entre los flancos del reloj Entrada desde los elementos de estado, salida a un
elemento de estado Periodos más largos determinan periodos más largos del
reloj
Capítulo 5 — El procesadorCapítulo 5 — El procesador
Construyendo el camino de datos
Camino de datos Elementos que procesan datos y direcciones en el CPU
Registros, ALUs, mux’s, memorias, … Se construirá un camino de datos del MIPS de manera
incremental Se refinará la visión del diseño
Capítulo 5 — El procesadorCapítulo 5 — El procesador
FETCH: Búsqueda de instrucciones
Capítulo 5 — El procesadorCapítulo 5 — El procesador
Registro de 32-bits
Se incrementa por 4 para la siguiente instrucción
Tipos de Instrucciones MIPS
Capítulo 5 — El procesadorCapítulo 5 — El procesador
0 rs rt rd shamt funct
31:26 5:025:21 20:16 15:11 10:6
35 or 43 rs rt dirección
31:26 25:21 20:16 15:0
4 rs rt dirección
31:26 25:21 20:16 15:0
Tipo-R
Lectura/Escritura
Saltos
OPCODE
Tipo-R
Se leen dos registros operadores Se realizan operaciones aritméticas/lógicas Escribir el resultado en un registro
Capítulo 5 — El procesadorCapítulo 5 — El procesador
Lectura/Escritura a Memoria
Leer los registros operadores Calcular la dirección utilizando un corrimiento de 16-bits
Usar la ALU, pero con un corrimiento con extensión de signo Lectura: Leer la memoria y actualizar el registro Escritura: Escribir el valor del registro a la memoria
Capítulo 5 — El procesadorCapítulo 5 — El procesador
Instrucciones de salto condicional
Registros operadores de lectura Comparar operadores
Usar la ALU, restar y verificar la salida a cero Calcular la dirección de destino
Desplazamiento de extensión de signo Corrimiento a la izquierda dos lugares (desplazamiento de una
palabra) Sumar al PC + 4
Calculado previamente por la búsqueda de la instrucción
Capítulo 4 — El procesadorCapítulo 4 — El procesador
Instrucciones de salto condicional
Capítulo 5 — El procesadorCapítulo 5 — El procesador
Sólo re-enrutar alambres
Se replica el bit de signo
Composición de elementos
El primer corte del camino de datos realiza una instrucción en un ciclo de reloj Cada elemento del patrón de datos puede sólo hacer una función
a la vez De esta manera, se necesita separar en dos memorias las
instrucciones y los datos Usar multiplexores donde las fuentes de datos alternos
sean utilizadas por diferentes instrucciones
Capítulo 4 — El procesadorCapítulo 4 — El procesador
Instrucciones tipo: R/lectura/escritura
Capítulo 5 — El procesadorCapítulo 5 — El procesador
Camino de datos completo
Capítulo 4 — El procesadorCapítulo 4 — El procesador
Control de la ALU
La ALU se usa para Lectura/escritura: F = suma Salto: F = resta Tipo-R: F depende del campo funct
Capítulo 5 — El procesadorCapítulo 5 — El procesador
Control de la ALU Función
0000 AND
0001 OR
0010 Suma
0110 Resta
0111 Activar en menos de
1100 NOR
Control de la ALU
Asumiendo una operación de la ALU (ALUOp) derivado del código de operación (opcode) La lógica combinatoria deriva el control de la ALU
Capítulo 5 — El procesadorCapítulo 5 — El procesador
opcode ALUOp Operación funct Función ALU ALU control
lw 00 load word XXXXXX suma 0010
sw 00 save word XXXXXX suma 0010
beq 01 Branch equal XXXXXX restar 0110
R-type 10 Add 100000 sumar 0010
subtract 100010 Restar 0110
AND 100100 AND 0000
OR 100101 OR 0001
set-on-less-than 101010 activar con menor que
0111
La unidad de control principal Las señales de control se derivan de las instrucciones
Capítulo 5 — El procesadorCapítulo 5 — El procesador
0 rs rt rd shamt funct
31:26 5:025:21 20:16 15:11 10:6
35 or 43 rs rt dirección
31:26 25:21 20:16 15:0
4 rs rt Dirección
31:26 25:21 20:16 15:0
Tipo-R
Lectura/Escritura
Salto
opcode
siemprelee
lee, exceptopara lectura
Escribir para tipo-R y Lect_MEM
Extension de signo
Camino de datos con control
Capítulo 5 — El procesadorCapítulo 5 — El procesador
Instrucción tipo-R
Capítulo 5 — El procesadorCapítulo 5 — El procesador
Instrucción de lectura
Capítulo 5 — El procesadorCapítulo 5 — El procesador
Instrucción Salta si es igual
Capítulo 5 — El procesadorCapítulo 5 — El procesador
saltos incondicionales
Jump utiliza direccionamiento de palabras Actualiza el PC con la concatenación de
Los 4 bits mas significativos del PC anterior Dirección de salto de 26-bits y 00
Necesita una señal de control decodificado del opcode
Capítulo 5— El procesadorCapítulo 5— El procesador
2 direccion
31:26 25:0
Jump
Camino de datos con saltos añadidos
Capítulo 5 — El procesadorCapítulo 5 — El procesador
Temas de desempeño
Retardos más largos determinan el periodo del reloj Patrón crítico: instrucción de lectura Instrucción de memoria archivo de registros ALU memoria
de datos archivo de registro No es fácil variar periodos para diferentes instrucciones Se pueden violar principios de diseño
Hacer el caso común el más rápido Se mejorará el desempeño por medio de segmentación
Capítulo 5 — El procesadorCapítulo 5 — El procesador
Segmentación de tareas Lavandería segmentada: ejecución traslapada
El paralelismo mejora el desempeño
Capítulo 5 — El procesadorCapítulo 5 — El procesador
Cuatro cargas: Velocidad
= 8/3.5 = 2.3
Sin parar: Velocidad
= 2n/0.5n + 1.5 ≈ 4= numero de etapas
Segmentado del MIPS
Cinco etapas: un paso por etapa1. IF: Lectura de la instrucción desde la memoria2. ID: Decodificación de la instrucción y lectura del registro3. EX: Ejecutar la operación o calcular la dirección4. MEM: Escribir el operador a la memoria5. WB: Escribir el resultado de nuevo al registro
Capítulo 4 — El procesadorCapítulo 4 — El procesador
Desempeño del segmentado Asumir el tiempo por etapa es
100ps para lectura y escritura de registros 200ps para otras etapas
Comparar el patrón de datos segmentado con el patron de datos de un sólo ciclo
Capítulo 4 — El procesadorCapítulo 4 — El procesador
Instr Busqueda Instr
Leer registro
Op ALU Acceso Memoria
Escibir Registro
Tiempo total
lw 200ps 100 ps 200ps 200ps 100 ps 800ps
sw 200ps 100 ps 200ps 200ps 700ps
R-format 200ps 100 ps 200ps 100 ps 600ps
beq 200ps 100 ps 200ps 500ps
Desempeño del segmentado
Capítulo 4 — El procesadorCapítulo 4 — El procesador
Ciclo-unico (Tc= 800ps)
Segmentado (Tc= 200ps)
Velocidad del segmentado Si todas las etapas están balanceadas
i.e., todas toman el mismo tiempo Tiempo entre instruccionessegmentado
= Tiempo entre instruccionessin_segmetado
Número de etapas Si no están balanceadas, la velocidad es menor Velocidad debido al incremento de producción
(throughput) Latencia (tiempo por cada instrucción) no decrece
Capítulo 4 — El procesadorCapítulo 4 — El procesador
Segmentado y diseño de la ISA
ISA del MIPS diseñada para segmentado Todas las instrucciones son de 32-bits
Fácil de buscar y decodifiar en un ciclo ver x86: Instrucciones de 1- to 17-bytes
Formato con pocas instrucciones y regulares Puede decodificar y leer registros en un paso
Lectura/escritura de direccionamiento Pueden calcular direcciones en la 3ra etapa, accesos
a memoria en la 4ta etapa Alineación de los operadores de memoria
Acceso de memoria toma sólo un ciclo
Capítulo 4 — El procesadorCapítulo 4 — El procesador
Peligros (riesgos) Situaciones que previenen el comienzo de la
siguiente instruccion en el siguiente ciclo Peligro en la estructura
Un recurso que se requiere está ocupado Peligros de datos
Se necesita esperar por las instrucciones previas para completar su lectura/escritura de datos
Peligro de Control El decidir sobre las acciones de control depende de la
instrucción previa
Capítulo 4 — El procesadorCapítulo 4 — El procesador
Peligros de la estructura Hay conflicto para el uso de un recurso En el MIPS segmentado con una memoria simple
Lectura/escritura requiere el acceso a los datos La búsqueda de instrucciones podría estancarse para ese ciclo
Se podría causar una “burbuja” segmentadaDe ahí, los patrones de datos requieren separar la memoria
de instrucciones/datos O separar las caches de instrucciones/datos
Capítulo 4 — El procesadorCapítulo 4 — El procesador
Peligros de datos Para que una instrucción sea completada se necesita
del dato de una instruccion previa add $s0, $t0, $t1sub $t2, $s0, $t3
Capítulo 4 — El procesadorCapítulo 4 — El procesador
Adelantado (bypassing) Utilizar el resultado cuando este es calculado
No hay que esperar por el para que sea almacenado en un registro
Requiere conexiones extras en el patrón de datos
Capítulo 4 — El procesadorCapítulo 4 — El procesador
Peligro de datos uso-lectura No se puede siempre estar en el puesto delantero
Si el valor no se calcula cuando se necesita ¡No se puede ir adelante en el tiempo!
Capítulo 4 — El procesadorCapítulo 4 — El procesador
Programación del código para evitar puestos
Reordenar codigo para evitar el uso de carga de resultados en la siguiente instrucción
Código C para A = B + E; C = B + F;
Capítulo 4 — El procesadorCapítulo 4 — El procesador
lw $t1, 0($t0)lw $t2, 4($t0)add $t3, $t1, $t2sw $t3, 12($t0)lw $t4, 8($t0)add $t5, $t1, $t4sw $t5, 16($t0)
Estancado
Estancado
lw $t1, 0($t0)lw $t2, 4($t0)lw $t4, 8($t0)add $t3, $t1, $t2sw $t3, 12($t0)add $t5, $t1, $t4sw $t5, 16($t0)
11 ciclos13 ciclos
Peligros de control Los brincos determinan el flujo de control
La busqueda de la siguiente instrucción depende del brinco resultante
El segmentado no siempre busca la instruccioón correcta Aún trabajando sobre la etapa ID del brinco
En segmentado en el MIPS Se necesita comparar los registros y calcular el objetivo al inicio
en el segmentado Añadir hardware para hacer ID
Capítulo 4 — El procesadorCapítulo 4 — El procesador
Estancado en un brinco Esperar hasta la respuesta del brinco que se ha
determinado antes de la búsqueda de la siguiente instrucción
Capítulo 4 — El procesadorCapítulo 4 — El procesador
Predicción de un brinco Segmentados más grandes no pueden determinar la
respuesta del brinco de manera afirmativa La penalizacioón del estancamiento se vuelve inaceptable
Predicción del resultado de un brinco Unicamente estar en estancamiento si la predicción es erronea
Segmentado en el MIPS No se puede predecir brincos que no se han realizado Buscar la instrucción después del brinco, sin retardo
Capítulo 4 — El procesadorCapítulo 4 — El procesador
MIPS con predicción no realizada
Capítulo 4 — El procesadorCapítulo 4 — El procesador
Predicción correcta
Predicción incorrecta
Predicción de brinco más realista
Predicción de brinco estadística Basado en comportamiento de brincos típicos Ejemplo: brincos de bucle e instrucciones tipo-if
Predecir brincos tomados hacia atrás Predecir brincos hacia adelante no realizados
Predicción de brincos dinámicos El hardware mide el comportamiento de brincos reales
e.g., grabar la historia reciente de cada brinco Asumir el que comportamiento futuro continuará una tendencia
Cuando sea equivocado, estar en puesto cuando se velve a buscar, y actualizar la historia
Capítulo 4 — El procesadorCapítulo 4 — El procesador
Resumen del segmentado
El segmentado mejora el desempeño por medio del incremento de la producción (throughput) de instrucciones Ejecutar mútilples instrucciones en paralelo Cada instrucción tiene la misma latencia
Hay peligros Estructura, datos, control
El conjunto de instrucciones diseña complejidad de efectos de la implementación del segmentado
Capítulo 4 — El procesadorCapítulo 4 — El procesador
La gran imagen
Patrón de datos segmentado del MIPS
Capítulo 4 — El procesadorCapítulo 4 — El procesador
§4.6
Contro
l de d
ato
s segm
enta
do y
con
trol
WB
MEM
El flujo derecha a izquierda lleva a peligros
Registros segmentados Se necesitan registros entre las etapas
Para mantener información producida en ciclos previos
Capítulo 4 — El procesadorCapítulo 4 — El procesador
Operación de segmentado Flujo ciclo por ciclo de las instrucciones por medio del
patrón de datos del segmentado Diagrama segmentado de un “sólo-ciclo de reloj”
Muestra el uso correcto en un sólo ciclo Resalta los recursos utilizados
ver un diagrama de “múltiples-ciclos-de reloj” Gráfica de operación en el tiempo
Se revisará un diagrama de un “sólo-ciclo-de reloj” para lectura y escritura
Capítulo 4 — El procesadorCapítulo 4 — El procesador
IF para lectura , escritura, …
Capítulo 4 — El procesadorCapítulo 4 — El procesador
ID para lectura, escritura, …
Capítulo 4 — El procesadorCapítulo 4 — El procesador
EX para carga
Capítulo 4 — El procesadorCapítulo 4 — El procesador
MEM para lectura
Capítulo 4 — El procesadorCapítulo 4 — El procesador
WB para lectura
Capítulo 4 — El procesadorCapítulo 4 — El procesador
Número de registro erroneo
Patrón de datos corregido para lectura
Capítulo 4 — El procesadorCapítulo 4 — El procesador
EX para escritura
Capítulo 4 — El procesadorCapítulo 4 — El procesador
MEM para escritura
Capítulo 4 — El procesadorCapítulo 4 — El procesador
WB para escritura
Capítulo 4 — El procesadorCapítulo 4 — El procesador
Diagrama segmentado multi-ciclo Forma mostrando los recursos utilizados
Capítulo 4 — El procesadorCapítulo 4 — El procesador
Diagrama segmentado multi-ciclo
Forma tradicional
Capítulo 4 — El procesadorCapítulo 4 — El procesador
Diagrama segmentado de un sólo-ciclo
Estado de segmentado en un ciclo dado
Capítulo 4 — El procesadorCapítulo 4 — El procesador
Control segmentado (simplificado)
Capítulo 4 — El procesadorCapítulo 4 — El procesador
Control segmentado Señales de control derivadas de las instrucciones
Al igual que en la implementación, se tiene un sólo-ciclo
Capítulo 4 — El procesadorCapítulo 4 — El procesador
Control segmentado
Capítulo 4 — El procesadorCapítulo 4 — El procesador
Peligro de datos en instrucciones de la ALU
Considerando esta secuencia:sub $2, $1,$3and $12,$2,$5or $13,$6,$2add $14,$2,$2sw $15,100($2)
Se puede resolver los peligros con adelantos ¿Cómo se puede detectar para realizar el adelanto?
Capítulo 4 — El procesadorCapítulo 4 — El procesador
§4.7
Pelig
ro e
n lo
s dato
s: adela
nto
vs. p
uesto
Dependencias y adelantos
Capítulo 4 — El procesadorCapítulo 4 — El procesador
Detectando la necesidad para adelantarse
Pasar el numero de los registros junto con el segmentado e.g., ID/EX.RegistroRs = numero de register para RS en
turno con el registrosegmentado Los numeros de registros de operandos de la ALU
en la etapa EX estan dados por ID/EX.RegistroRs, ID/EX.RegistroRt
Peligro de datos cuando1a. EX/MEM.RegistroRd = ID/EX.RegistroRs1b. EX/MEM.RegistroRd = ID/EX.RegistroRt2a. MEM/WB.RegistroRd = ID/EX.RegistroRs2b. MEM/WB.RegistroRd = ID/EX.RegistroRt
Capítulo 4 — El procesadorCapítulo 4 — El procesador
Adelanto delreg segmentEX/MEM
Adelanto delReg segmentMEM/WB
Detectando la necesidad del adelanto
¡Pero sólo en instrucciones de adelanto se escribirá a un registro! EX/MEM.RegWrite, MEM/WB.RegWrite
Y sólo si Rd para esa instruccion es diferente de $zero EX/MEM.RegistroRd ≠ 0,
MEM/WB.RegistroRd ≠ 0
Capítulo 4 — El procesadorCapítulo 4 — El procesador
Patrones de adelanto
Capítulo 4 — El procesadorCapítulo 4 — El procesador
Condiciones para adelanto Peligro en EX
Si (EX/MEM.RegWrite y (EX/MEM.RegistroRd ≠ 0) y (EX/MEM.RegistroRd = ID/EX.RegistroRs)) AdelantoA = 10
Si (EX/MEM.RegWrite y (EX/MEM.RegistroRd ≠ 0) y (EX/MEM.RegistroRd = ID/EX.RegistroRt)) AdelantoB = 10
Peligro en MEM Si (MEM/WB.RegWrite y (MEM/WB.RegistroRd ≠ 0)
y (MEM/WB.RegistroRd = ID/EX.RegistroRs)) AdelantoA = 01
Si (MEM/WB.RegWrite y (MEM/WB.RegistroRd ≠ 0) y (MEM/WB.RegistroRd = ID/EX.RegistroRt)) AdelantoB = 01
Capítulo 4 — El procesadorCapítulo 4 — El procesador
Doble peligro de datos Considere la secuencia:
add $1,$1,$2add $1,$1,$3add $1,$1,$4
Ambos peligros ocurren Se desea usar el más reciente
Revisar la condición de peligro MEM Sólo adelante si la condición de peligro EX no es verdadera
Capítulo 4 — El procesadorCapítulo 4 — El procesador
Condición de adelanto revisada
Peligro MEM Si (MEM/WB.RegWrite y (MEM/WB.RegistroRd ≠ 0)
y no (EX/MEM.RegWrite y (EX/MEM.RegistroRd ≠ 0) y (EX/MEM.RegistroRd = ID/EX.RegistroRs)) y (MEM/WB.RegistroRd = ID/EX.RegistroRs)) AdelantoA = 01
Si (MEM/WB.RegWrite y (MEM/WB.RegistroRd ≠ 0) y no (EX/MEM.RegWrite y (EX/MEM.RegistroRd ≠ 0) y (EX/MEM.RegistroRd = ID/EX.RegistroRt)) y (MEM/WB.RegistroRd = ID/EX.RegistroRt)) AdelantoB = 01
Capítulo 4 — El procesadorCapítulo 4 — El procesador
Patrón de datos con adelanto
Capítulo 4 — El procesadorCapítulo 4 — El procesador
Peligro en el uso de lectura de datos
Capítulo 4 — El procesadorCapítulo 4 — El procesador
Necesita el estancamiento para un ciclo
Detección de peligro de uso de lectura
Verificar cuando se utiliza la instruccion es decodificada en la etapa ID
El número de registro de operando de la ALU en la etapa ID esta dada por IF/ID.RegistroRs, IF/ID.RegistroRt
Peligro cuando se usa lectura ID/EX.MemRead y
((ID/EX.RegistroRt = IF/ID.RegistroRs) o (ID/EX.RegistroRt = IF/ID.RegistroRt))
Si se detecta, estancamiento e insertar burbuja
Capítulo 4 — El procesadorCapítulo 4 — El procesador
¿Cómo estancar el segmentado?
Forzar el control de valores en el registro ID/EX a 0 EX, MEM y WB hacer nop (no-operacion)
Prevenir la actualización del CP y el registro IF/ID El utilizar la instruccion se decodifica de nuevo Siguiendo la instruccioón es buscada de nueva 1-ciclo estancado permite a MEM leer un dato para lw
Se puede sub-sequentemente seguir a la etapa EX
Capítulo 4 — El procesadorCapítulo 4 — El procesador
Estacamiento/burbuja en el segmentado
Capítulo 4 — El procesadorCapítulo 4 — El procesador
El estamiento es colocado aquí
Estancamiento/burbuja en el segmentado
Capítulo 4 — El procesadorCapítulo 4 — El procesador
O, más exactamente, ...
Patrón de datos con detección de peligro
Capítulo 4 — El procesadorCapítulo 4 — El procesador
Estancado y desempeño
El estancado reduce el desempeño Pero se necesita para tener resultados correctos
El compilador puede arreglar el código para evitar peligros y estancamiento Se requiere el conocimiento de la estructura del segmentado
Capítulo 4 — El procesadorCapítulo 4 — El procesador
La gran imagen
Peligro de brincos Si el resultado del brinco es determindo en MEM
Capítulo 4 — El procesadorCapítulo 4 — El procesador
§4.8
Pelig
ros d
el co
ntro
l
CP
Tirar estasinstruciones(colocar valorcontro a 0)
Reduciendo el retardo del brinco
Mover el hardware para determinar el resultado en la etapa ID Sumador de la direccion objetivo Comparador del registro
Ejemplo: brinco tomado36: sub $10, $4, $840: beq $1, $3, 744: and $12, $2, $548: or $13, $2, $652: add $14, $4, $256: slt $15, $6, $7 ...72: lw $4, 50($7)
Capítulo 4 — El procesadorCapítulo 4 — El procesador
Ejemplo: Bronco tomado
Capítulo 4 — El procesadorCapítulo 4 — El procesador
Ejemplo: Brinco tomado
Capítulo 4 — El procesadorCapítulo 4 — El procesador
Peligro de datos para brincos Si la comparación de un registro es el destino de una
2da o 3ra instrucción precedente de la ALU
Capítulo 4 — El procesadorCapítulo 4 — El procesador
…
IF ID EX MEM WB
IF ID EX MEM WB
IF ID EX MEM WB
IF ID EX MEM WB
add $4, $5, $6
add $1, $2, $3
beq $1, $4, target
Se puede resolver utilizando el adelanto
Peligro de datos para brincos
Si la comparación de registros es el destino de una instrucción precedente de la ALU o una 2da instrucción de lectura precedente Se necesita 1 ciclo de estancado
Capítulo 4 — El procesadorCapítulo 4 — El procesador
beq estancado
IF ID EX MEM WB
IF ID EX MEM WB
IF ID
ID EX MEM WB
add $4, $5, $6
lw $1, addr
beq $1, $4, objetivo
Peligro datos para brincos Si un registro de comparacion es el destino de una instruccion
de lectura precedente inmediata Se necesitan 2 ciclos de estancado
Capítulo 4 — El procesadorCapítulo 4 — El procesador
beq estancado
IF ID EX MEM WB
IF ID
ID
ID EX MEM WB
beq estancado
lw $1, addr
beq $1, $0, objetivo
Predicción de brinco dinamico
En un segmentado más profundo y superescalar, la falta sobre un brinco, es más significativa
Usar predicción dinámica Buffer de predicción dinamica (tabla de brinco de historia aka) Indexado por una dirección de una instruccioón brinco reciente Se almacena un resultado (tamado/no tamado) Para ejecutar un brinco
Verificar la tabla, excepto el mismo resultado Comenzar a buscar a partir de venirse abajo u objetivo Si es erroneo, limpiar el segmentado y cambia la predicción
Capítulo 4 — El procesadorCapítulo 4 — El procesador
Predictor de 1-bit: Defecto ¡Brincos de bucles internos con predicciones erroneas dos
veces!
Capítulo 4 — El procesadorCapítulo 4 — El procesador
externo: … …interno: … … beq …, …, interno … beq …, …, externo
Malas predicciones como si fueran realizadas sobre la última iteración del bucle interno
Entonces las malas predicciones no son tomadas sobre la primera iteración alrededor del siguiente bucle
Predictor de 2-bits Sólo cambia la predicción en dos predicciones erroneas
sucesivas
Capítulo 4 — El procesadorCapítulo 4 — El procesador
Calculando el brinco objetivo Inclusive con el predictor, aún se necesita calcular la
dirección objetivo Falta de 1-ciclo por un brinco realizado
Buffer de brinco objetivo Cache de direcciones objetivo Indexados por el CP cuando las instrucciones son buscadas
Si se logra y si la instrucción es tomada por el predictor de brinco, puede buscar el objetivo inmediatamente
Capítulo 4 — El procesadorCapítulo 4 — El procesador
Excepciones e interrupciones Los eventos “inesperados” requieren de un
cambio en el control del flujo Diferentes ISAs utilizan términos diferentes
Excepción Surge dentro del CPU
e.g., opcode no definodo, desbordamiento, llamado a sistema, …
Interrupciones Desde un controlador externo de E/S
Tratar con ellos sin sacrificar el desempeño es difícil
Capítulo 4 — El procesadorCapítulo 4 — El procesador
§4.9
Exce
pcio
nes
Manejo de excepciones En el MIPS, excepciones administradas por un
Coprocesador de Control del Sistema (CP0) Guarda el CP de instrucciones ofensivas (o
interrupciones) En el MIPS: Contador del Programa de Excepciones
(EPC) Guardar la indicacion del problema
En el MIPS: Registro causa Se asumira 1-bit
0 para opcode no definido, 1 para desbordamiento Saltar al administrador en 8000 00180
Capítulo 4 — El procesadorCapítulo 4 — El procesador
Un mecanismo alterno Interrupcion de vectores
Administracion de direcciones determinadas por la causa Ejemplo:
Opcode no definido: C000 0000 desbordamiento: C000 0020 …: C000 0040
Cualquiera de las dos tipos de instrucciones Manejar con la interrupccion, o Saltar a un administrador real
Capítulo 4 — El procesadorCapítulo 4 — El procesador
Acciones del administrador Leer la causa, y transferir el administrador relevante Determinar la accion requerida Si se restablece
Tomar la ccion corectiva usar EPC para regresar al programa
De otra manera Terminar el programa Reportar el error usando EPC, causa, …
Capítulo 4 — El procesadorCapítulo 4 — El procesador
Excepciones en el segmentado
Otra forma de peligro del control Considerando un desbordamiento en la suma en
la etapa EXadd $1, $2, $1 Prevenir $1 de ser sacudido Complar la instrucción previa Tirar add y la instrucción subsecuente Activar los valores de los registros de Cause y EPC Transferir el control al administrador
Es similar a un brinco mal predicho Se usa mucho del mismo hardware
Capítulo 4 — El procesadorCapítulo 4 — El procesador
Segmentado con excepciones
Capítulo 4 — El procesadorCapítulo 4 — El procesador
Propiedades de las excepciones
Excepciones que vuelven a comenzar El segmentador puede tirar la instrucción El administrador se ejecuta, entonces regresa a la instrucción
Vuelve a buscar y se ejecuta desde lo eliminado El CP se guarda en el registro EPC
Se identifica la instrucción causante Realmente PC + 4 se guarda
El administrador se debe de volver a ajustar
Capítulo 4 — El procesadorCapítulo 4 — El procesador
Ejemplo de excepción Excepción sobre add en
40 sub $11, $2, $444 and $12, $2, $548 or $13, $2, $64C add $1, $2, $150 slt $15, $6, $754 lw $16, 50($7)…
Administrador80000180 sw $25, 1000($0)80000184 sw $26, 1004($0)…
Capítulo 4 — El procesadorCapítulo 4 — El procesador
Ejemplo de excepción
Capítulo 4 — El procesadorCapítulo 4 — El procesador
Ejemplo de excepción
Capítulo 4 — El procesadorCapítulo 4 — El procesador
Múltiples excepciones El segmentado se traslapa en multiples
instrucciones Se podrían tener multiples excepciones a la vez
Método simple: manejo de excepciones desde una instrucción temprana Tirar instrucciones subsecuentes Execpxines “precisas”
En segmentados complejos Multiples instrucciones tomadas por ciclo Completado fuera de lugar ¡Mantener las excepciones presisas es difícil!
Capítulo 4 — El procesadorCapítulo 4 — El procesador
Excepciones imprecisas
Solamente parar el segmentado y guardar el estado Incluyendo la(s) causa(s) de la(s) excepcion(es)
Permitir que el administrador trabaje Qué instrucciones tienen excepciones Cuáles para completar o tirar
Puede requerir que se complete “manualmente”
Se simplifica el hardware, pero el administrador en software puede ser más complejo
No es adecuado para segmentado fuera de lugar para multiples temas
Capítulo 4 — El procesadorCapítulo 4 — El procesador
Paralelismos a nivel de instrucciones (ILP)
Segmentado: ejecutar múltiples instrucciones en paralelo Para incrementar ILP
Segmentado profundo Menos trabajo por etapa ciclos de reloj más cortos
Multiples casos Etapas de segmentado replicadas multiples segmentados Comenzar múltiples instrucciones por ciclo de reloj CPI < 1, de manerar que se use Instrucciones Por Cicle (IPC) E.g., 4GHz 4-forma multiples-casos
• 16 BIPS, pico CPI = 0.25, pico IPC = 4 Pero las deendencias se reducen en esta práctica
Capítulo 4 — El procesadorCapítulo 4 — El procesador
§4.1
0 P
ara
lelism
o e
instru
cciones a
vanza
das a
niv
el p
ara
lelo
Multiples casos Casos múltiples estáticos
Compilar grupos de instrucciones para ser tomados juntos en cuanta
Empaquetarlos en “ranuras por casos” El compilador los detecta y evita peligos
Casos múltiples dinámicos El CPU examina la trama de instrucciones para separar cada caso
por ciclo El compilador puede ayudar a reordenar las instrucciones El CPU resuleve peligros utilizando técnicas avanzadas en tiempo
de ejecución
Capítulo 4 — El procesadorCapítulo 4 — El procesador
Speculation “Guess” what to do with an instruction
Start operation as soon as possible Check whether guess was right
If so, complete the operation If not, roll-back and do the right thing
Common to static and dynamic multiple issue Examples
Speculate on branch outcome Roll back if path taken is different
Speculate on load Roll back if location is updated
Capítulo 4 — El procesadorCapítulo 4 — El procesador
Compiler/Hardware Speculation Compiler can reorder instructions
e.g., move load before branch Can include “fix-up” instructions to recover from incorrect guess
Hardware can look ahead for instructions to execute Buffer results until it determines they are actually needed Flush buffers on incorrect speculation
Capítulo 4 — El procesadorCapítulo 4 — El procesador
Speculation and Exceptions What if exception occurs on a speculatively executed
instruction? e.g., speculative load before null-pointer check
Static speculation Can add ISA support for deferring exceptions
Dynamic speculation Can buffer exceptions until instruction completion (which may not
occur)
Capítulo 4 — El procesadorCapítulo 4 — El procesador
Static Multiple Issue Compiler groups instructions into “issue packets”
Group of instructions that can be issued on a single cycle Determined by pipeline resources required
Think of an issue packet as a very long instruction Specifies multiple concurrent operations Very Long Instruction Word (VLIW)
Capítulo 4 — El procesadorCapítulo 4 — El procesador
Scheduling Static Multiple Issue Compiler must remove some/all hazards
Reorder instructions into issue packets No dependencies with a packet Possibly some dependencies between packets
Varies between ISAs; compiler must know! Pad with nop if necessary
Capítulo 4 — El procesadorCapítulo 4 — El procesador
MIPS with Static Dual Issue Two-issue packets
One ALU/branch instruction One load/store instruction 64-bit aligned
ALU/branch, then load/store Pad an unused instruction with nop
Capítulo 4 — El procesadorCapítulo 4 — El procesador
Address Instruction type Pipeline Stages
n ALU/branch IF ID EX MEM WB
n + 4 Load/store IF ID EX MEM WB
n + 8 ALU/branch IF ID EX MEM WB
n + 12 Load/store IF ID EX MEM WB
n + 16 ALU/branch IF ID EX MEM WB
n + 20 Load/store IF ID EX MEM WB
MIPS with Static Dual Issue
Capítulo 4 — El procesadorCapítulo 4 — El procesador
Hazards in the Dual-Issue MIPS More instructions executing in parallel EX data hazard
Forwarding avoided stalls with single-issue Now can’t use ALU result in load/store in same packet
add $t0, $s0, $s1load $s2, 0($t0)
Split into two packets, effectively a stall
Load-use hazard Still one cycle use latency, but now two instructions
More aggressive scheduling required
Capítulo 4 — El procesadorCapítulo 4 — El procesador
Scheduling Example Schedule this for dual-issue MIPS
Capítulo 4 — El procesadorCapítulo 4 — El procesador
Loop: lw $t0, 0($s1) # $t0=array element addu $t0, $t0, $s2 # add scalar in $s2 sw $t0, 0($s1) # store result addi $s1, $s1,–4 # decrement pointer bne $s1, $zero, Loop # branch $s1!=0
ALU/branch Load/store cycle
Loop: nop lw $t0, 0($s1) 1
addi $s1, $s1,–4 nop 2
addu $t0, $t0, $s2 nop 3
bne $s1, $zero, Loop sw $t0, 4($s1) 4
IPC = 5/4 = 1.25 (c.f. peak IPC = 2)
Loop Unrolling Replicate loop body to expose more parallelism
Reduces loop-control overhead Use different registers per replication
Called “register renaming” Avoid loop-carried “anti-dependencies”
Store followed by a load of the same register Aka “name dependence”
• Reuse of a register name
Capítulo 4 — El procesadorCapítulo 4 — El procesador
Loop Unrolling Example
IPC = 14/8 = 1.75 Closer to 2, but at cost of registers and code size
Capítulo 4 — El procesadorCapítulo 4 — El procesador
ALU/branch Load/store cycle
Loop: addi $s1, $s1,–16 lw $t0, 0($s1) 1
nop lw $t1, 12($s1) 2
addu $t0, $t0, $s2 lw $t2, 8($s1) 3
addu $t1, $t1, $s2 lw $t3, 4($s1) 4
addu $t2, $t2, $s2 sw $t0, 16($s1) 5
addu $t3, $t4, $s2 sw $t1, 12($s1) 6
nop sw $t2, 8($s1) 7
bne $s1, $zero, Loop sw $t3, 4($s1) 8
Dynamic Multiple Issue “Superscalar” processors CPU decides whether to issue 0, 1, 2, … each cycle
Avoiding structural and data hazards Avoids the need for compiler scheduling
Though it may still help Code semantics ensured by the CPU
Capítulo 4 — El procesadorCapítulo 4 — El procesador
Dynamic Pipeline Scheduling Allow the CPU to execute instructions out of order to
avoid stalls But commit result to registers in order
Examplelw $t0, 20($s2)addu $t1, $t0, $t2sub $s4, $s4, $t3slti $t5, $s4, 20
Can start sub while addu is waiting for lw
Capítulo 4 — El procesadorCapítulo 4 — El procesador
Dynamically Scheduled CPU
Capítulo 4 — El procesadorCapítulo 4 — El procesador
Results also sent to any waiting reservation stations
Reorders buffer for register writes Can supply
operands for issued instructions
Preserves dependencies
Hold pending operands
Register Renaming Reservation stations and reorder buffer effectively
provide register renaming On instruction issue to reservation station
If operand is available in register file or reorder buffer Copied to reservation station No longer required in the register; can be
overwritten If operand is not yet available
It will be provided to the reservation station by a function unit
Register update may not be required
Capítulo 4 — El procesadorCapítulo 4 — El procesador
Speculation Predict branch and continue issuing
Don’t commit until branch outcome determined Load speculation
Avoid load and cache miss delay Predict the effective address Predict loaded value Load before completing outstanding stores Bypass stored values to load unit
Don’t commit load until speculation cleared
Capítulo 4 — El procesadorCapítulo 4 — El procesador
Why Do Dynamic Scheduling? Why not just let the compiler schedule code? Not all stalls are predicable
e.g., cache misses Can’t always schedule around branches
Branch outcome is dynamically determined Different implementations of an ISA have different
latencies and hazards
Capítulo 4 — El procesadorCapítulo 4 — El procesador
Does Multiple Issue Work?
Yes, but not as much as we’d like Programs have real dependencies that limit ILP Some dependencies are hard to eliminate
e.g., pointer aliasing Some parallelism is hard to expose
Limited window size during instruction issue Memory delays and limited bandwidth
Hard to keep pipelines full Speculation can help if done well
Capítulo 4 — El procesadorCapítulo 4 — El procesador
The BIG Picture
Power Efficiency Complexity of dynamic scheduling and speculations requires
power Multiple simpler cores may be better
Capítulo 4 — El procesadorCapítulo 4 — El procesador
Microprocessor Year Clock Rate Pipeline Stages
Issue width
Out-of-order/ Speculation
Cores Power
i486 1989 25MHz 5 1 No 1 5W
Pentium 1993 66MHz 5 2 No 1 10W
Pentium Pro 1997 200MHz 10 3 Yes 1 29W
P4 Willamette 2001 2000MHz 22 3 Yes 1 75W
P4 Prescott 2004 3600MHz 31 3 Yes 1 103W
Core 2006 2930MHz 14 4 Yes 2 75W
UltraSparc III 2003 1950MHz 14 4 No 1 90W
UltraSparc T1 2005 1200MHz 6 1 No 8 70W
The Opteron X4 Microarchitecture
Capítulo 4 — El procesadorCapítulo 4 — El procesador
§4.1
1 R
eal S
tuff
: The A
MD
Opte
ron
X4 (B
arce
lona) P
ipelin
e
72 physical registers
The Opteron X4 Pipeline Flow For integer operations
Capítulo 4 — El procesadorCapítulo 4 — El procesador
FP is 5 stages longer Up to 106 RISC-ops in progress
Bottlenecks Complex instructions with long dependencies Branch mispredictions Memory access delays
Fallacies Pipelining is easy (!)
The basic idea is easy The devil is in the details
e.g., detecting data hazards
Pipelining is independent of technology So why haven’t we always done pipelining? More transistors make more advanced techniques
feasible Pipeline-related ISA design needs to take account of
technology trends e.g., predicated instructions
Capítulo 4 — El procesadorCapítulo 4 — El procesador
§4.1
3 Fa
llacie
s and
Pitfa
lls
Pitfalls Poor ISA design can make pipelining harder
e.g., complex instruction sets (VAX, IA-32) Significant overhead to make pipelining work IA-32 micro-op approach
e.g., complex addressing modes Register update side effects, memory indirection
e.g., delayed branches Advanced pipelines have long delay slots
Capítulo 4 — El procesadorCapítulo 4 — El procesador
Concluding Remarks ISA influences design of datapath and control Datapath and control influence design of ISA Pipelining improves instruction throughput
using parallelism More instructions completed per second Latency for each instruction not reduced
Hazards: structural, data, control Multiple issue and dynamic scheduling (ILP)
Dependencies limit achievable parallelism Complexity leads to the power wall
Capítulo 4 — El procesadorCapítulo 4 — El procesador
§4.1
4 C
on
cludin
g R
em
arks