Post on 15-Aug-2020
transcript
INSTITUTO POLITECNICO NACIONAL CENTRO DE INVESTIGACION EN COMPUTACION
LABORATORIO DE MICROTECNOLOGIA Y SISTEMAS EMBEBIDOS
DISEÑO DE UN PROCESADOR SUPERESCALAR CON EJECUCIÓN FUERA DE ORDEN USANDO LENGUAJES DE DESCRIPCIÓN DE HARDWARE (VHDL)
L1
INSTRUCTION CACHE
FETCH IFQ
AL
LO
CA
TIO
N &
RE
NA
ME
MA
PP
ER
/DIS
PA
TC
H
BRANCH
PREDICTOR
DE
CO
DE
Int. R
eg
.
File
FP
Re
g.
File
L1
DATA CACHE
L2
UNIFIED CACHE
Integer
FUs
DATA
PREFETCHING
PC BY
PA
SS
FP
FUs
IIQ
IFQ
LSQ
ROB
08/02/2008 REPORTE TECNICO FINAL (SIP-20070319)
Este reporte describe de forma detallada la operación y el diseño de un
procesador superescalar con ejecución fuera de orden utilizando lenguajes
de descripción de hardware, en particular VHDL.
Diseño de un procesador superescalar con ejecución fuera de orden Usando lenguajes de descripción de hardware
(VHDL)
Página 1
Diseño de un procesador superescalar con ejecución fuera de orden
Usando lenguajes de descripción de hardware (VHDL)
O B J E T I V O G E N E R A L
Generar el código HDL de un procesador superescalar con ejecución fuera de orden, utilizando
herramientas de diseño como QuartusII (Altera), ISE-Foundation (Xillinx), etc. probarlo en el simulador de
la herramienta de desarrollo y en un dispositivo programable en campo FPGA.
O B J E T I V O S P A R T I C U L A R E S
Diseño de los circuitos del procesador utilizando VHDL, Definir el conjunto de instrucciones del procesador
para crear la tabla de decodificación en HDL, Definir la arquitectura del procesador mediante los estados
del “pipeline” para crear el camino de datos y de instrucciones, Interconectar los módulos que conforman
al procesador, desarrollar documentación. El código se distribuirá por web mediante licencia de código
abierto, a fin de promover el desarrollo y la investigación en arquitecturas de computadoras en las
universidades del país.
R E S U M E N
Una de las características clave en los procesadores modernos para extraer el máximo paralelismo de las
aplicaciones que ejecutan es la capacidad de ejecutar múltiples instrucciones en un mismo ciclo de reloj,
para lograr esto, la maquinaria completa del procesador se ha hecho muy compleja, haciendo cada vez más
difícil su evaluación y su diseño. En la evaluación de nuevas ideas de investigación en el área de
arquitectura de computadoras, la simulación (soft-simulator) juega un papel importante y todo indica que
es la mejor opción, sin embargo para un diseño físico o un análisis de comportamiento más real es
necesario un diseño en hardware de base (hard-simulator), donde las nuevas ideas puedan ser
incorporadas y más tarde puedan ser cargadas a un dispositivo lógico programable. El objetivo de este
proyecto es describir una infraestructura HDL para el diseño y simulación de procesadores superescalares.
I N T R O D U C C I Ó N
La estructura de los procesadores superescalares, incluye las etapas de extracción, decodificación,
renombrado de registros, asignación de recursos, envió a ejecución, la ejecución propia, escritura a
registros, fin de la ejecución y liberación de los recursos. Los primeros procesadores superescalares
ejecutaban cada etapa en un ciclo de reloj, los procesadores modernos han dividido las etapas en dos o
más sub-etapas para incrementar la frecuencia de operación. Aquellas etapas que realizan más de una
operación indivisible en el mismo ciclo, son llamadas etapas de operación atómica. Cada etapa es separada
por un “Latch”, el cual almacena los datos de la etapa previa para que los valores correctos pasen a la
próxima etapa. Las instrucciones se ejecutan a la velocidad a la que se ejecuta cada etapa involucrando
diversas líneas de ejecución en paralelo, al utilizar recursos que se replican, por lo que es posible iniciar la
ejecución de varias operaciones en cada ciclo. Los principales recursos son: memorias cache de datos y de
instrucciones, bancos de registros físicos para enteros y para punto flotante, búfer de reordenamiento,
colas para instrucciones de enteros, de punto flotante y de acceso a memoria y las unidades de ejecución.
Diseño de un procesador superescalar con ejecución fuera de orden Usando lenguajes de descripción de hardware
(VHDL)
Página 2
En este trabajo se describe un modelo típico, con similitudes a procesadores como el Alpha 21264 y MIPS
R10000. Las secciones siguientes describen los estados que componen al modelo del procesador
superescalar.
E T A P A 1 : E S T R A C C I O N D E I N S T R U C C I O N E S
El primer estado es responsable de extraer las instrucciones de la memoria de programa, este estado debe
almacenar las N instrucciones y el contador de programa PC en un registro intermedio para enviarlas al
próximo estado, y calcular la próxima dirección de memoria para extraer las próximas N instrucciones. La
figura 1 muestra los principales componentes del estado de extracción de instrucciones. El registro
intermedio es una memoria FIFO, llamada cola de instrucciones extraídas, y se usa para almacenar las N
instrucciones y sus correspondientes contadores de programa PC o direcciones de memoria en cada ciclo
del procesador.
INSTRUCTON
MEMORY
IL1
(MEMORY FILE )
FIF
O
Fe
tch
Qu
eu
e
4 Instructions
ADD
BRANCH
PREDICTOR
1
Mu
x
0
+ 4
Ta
ke
n 0
, N
o-t
ak
en
1
Address
PC Register
Data
Br
Ad
dre
ss
CLKRD
Figura 1. Componentes de la etapa de extracción de instrucciones
Para mantener buen rendimiento y bajo tráfico en los accesos a memoria, los procesadores deben extraer y
decodificar las instrucciones a mayor velocidad de la que se ejecutan [8], la etapa de extracción en cada
ciclo de reloj lee una línea completa de la memoria de instrucciones, cada línea está organizada con cuatro
instrucciones consecutivas, aproximadamente el 24% en los programas SPECint y 5% en los programas
SPECfp de las instrucciones dinámicas son instrucciones de salto y estas están referenciadas al contador de
programa. Como las direcciones efectivas de los saltos no pueden calcularse en el mismo ciclo, cuando el
salto es tomado no se puede conocer la próxima dirección de memoria para el próximo ciclo de extracción
de instrucciones, Un predictor de saltos, resuelve en parte este problema[9]. Para nuestro modelo N es
igual a 4 y el predictor de saltos es el más simple siempre predice que el salto no se tomara, de esta forma
siempre se calcularan las direcciones efectivas de los saltos y no se tendrán equivocaciones, por otro lado
la memoria cache L1 se modela mediante un archivo que contiene el programa que se ejecutará. El
predictor de saltos y la unidad de control de acceso a memoria (conocida como MMU) son módulos que
merece especial atención y se deja para trabajos futuros.
Diseño de un procesador superescalar con ejecución fuera de orden Usando lenguajes de descripción de hardware
(VHDL)
Página 3
E T A P A 2 : R E N O M B R A D O , D E C O D I F I C A C I Ó N Y A S I G N A C I Ó N D E R E C U R S O S
2 . 1 R E N O M B R A D O
La segunda etapa es responsable del renombrado de registros, la decodificación de las instrucciones, y de
asignación de recursos. Dependiendo de su tipo (entera o punto flotante, incluidas las de acceso a
memoria) se envían a las unidades de renombrado. Una unidad de renombrado, posee una RAT-Register
Alias table- ó Tabla de registros renombrados indexada por los registros lógicos fuentes para extraer los
registros físicos que han sido asignados en ciclos anteriores y renombra el registro lógico destino actual con
un registro físico de un grupo de registros libres. Los procesadores modernos implementan la unidad de
renombrado de registros usando tablas de registros renombrados las cuales graban el mapeo entre
registros lógicos y registros físicos. El reto es el mapeo en paralelo de las N instrucciones extraídas de la
memoria en cada ciclo, esto requiere de la ejecución simultanea de 2N búsquedas de los registros lógicos
fuentes y N búsquedas de registros lógicos destino en la RAT. Adicionalmente se requiere de N-1
operaciones de chequeo de dependencias entre las instrucciones que se extraen en un mismo ciclo y para
finalizar se requieren de N operaciones de renombrado. En nuestra propuesta la lista de registros libres
está distribuida en cuatro memorias FIFO de 32 entradas y las RAT’s están implementadas en cuatro
memorias SRAM de 2 puertos de escritura y 1 puerto de lectura, con 32-entradas de 7-bits.
124
120
.
.
.
8
4
0
125
121
.
.
.
9
5
1
126
122
.
.
.
10
6
2
127
123
.
.
.
11
7
3
FIFO FIFO FIFO FIFO
SR
C1
I2
SR
C2
I2
SR
C1
I3
SR
C2
I3
SR
C1
I4
SR
C2
I4
Dest_I1
Dest_I2
Dest_I3
Dest_I4
Src1_I1
Src2_I1
SR
C1
I3
SR
C2
I3
SR
C1
I4
SR
C2
I4
SR
C1
I4
SR
C2
I4
Src1_I2
Src2_I2
Dependency
Check
Logic
Src1_I3
Src2_I3
Src1_I4
Src2_I4
1
2
3
4
5
6
7
8
M1
M2
M3
M4
M5
M6
M7
M8
M9
M1
0
M1
1
M1
2
PhySrc1_I1
PhySrc2_I1
PhySrc1_I2
PhySrc2_I2
PhySrc1_I3
PhySrc2_I3
PhySrc1_I4
PhySrc2_I4
PhyDest_I1
PhyDest_I2
PhyDest_I3
PhyDest_I4
ABCD
Figura.2 Componentes de la etapa de renombrado de Registros Lógicos a Registros Físicos
Las tablas de renombrado de registros enteros (INT) y de punto flotante (FP) contienen las asignaciones de
registros lógicos a físicos. La unidad de renombrado de FP graba los registros lógicos f0-f31 en una
memoria RAM multipuerto de 32 entradas de 7-bits, la unidad de renombrado de enteros graba los
registros lógicos r0-r31 en una memoria RAM multipuerto de 32 entradas de 7-bits[8].
Diseño de un procesador superescalar con ejecución fuera de orden Usando lenguajes de descripción de hardware
(VHDL)
Página 4
2 . 2 D E C O D I F I C A C I Ó N
La etapa de decodificación de instrucciones recibe una instrucción de 32 bits del conjunto de instrucciones
de la arquitectura MIPS IV elegida para este diseño (ver figura 3).
31 26 25 21 20 16 15 11 10 06 05 0
OPCODE SRC1 SRC2 DEST SHIFT FUNTION
REGISTER ENCODING
31 26 25 21 20 16 15 0
OPCODE SRC1 DEST IMMEDIATE
IMMEDIATE ENCODING
31 26 25 0
OPCODE IMMEDIATE
JUMP ENCODING
Figura.3 Formato del código de operación de las instrucciones MIPS IV
Por cada instrucción, regresa el código de operación, una bandera que indica si la instrucción es un salto o
no, una bandera que indica si es salto y liga, en caso de que la instrucción sea de salto. Los campos de los
registros rs, rt, rd, sa y el campo de inmediato, se leen al momento de decodificar; sin importar que no se
usen y todos pues no influyen en el comportamiento general del programa.
Fu
nti
on
3
Fu
nti
on
2
Fu
nti
on
0
Fu
nti
on
1
CONTROL
OPCODE 0
OPCODE 1
OPCODE 2
OPCODE 3
SRC1 SRC2
IQ
DEST
Funtions Enable
Figura 4. Tabla de control de decodificación de instrucciones
Algunos datos importantes para la ejecución de la instrucción como es el vector de recursos a utilizar
(unidad funcional que ejecutara la instrucción) los saca de la tabla de control de decodificación de
instrucciones que viene implementada dentro del módulo y que contiene información para cada una de las
instrucciones que existen dentro de la arquitectura MIPS IV, para eso primero determina qué tipo de
instrucción es con una serie de comparaciones.
Diseño de un procesador superescalar con ejecución fuera de orden Usando lenguajes de descripción de hardware
(VHDL)
Página 5
E T A P A 3 : L O G I C A D E E M I S I Ó N D E I N S T R U C C I O N E S
La lógica de emisión de instrucciones se compone de tres estructuras, cola de instrucciones de enteros, cola
de instrucciones de punto flotante y cola de instrucciones de acceso a memoria. El estado de emisión de
instrucciones es responsable de enviar las instrucciones listas para ejecución a sus respectivas unidades
funcionales. Una instrucción esta lista para su ejecución cuando todos los valores de los registros fuente
han sido calculados y están disponibles. La ejecución fuera de orden se lleva a cabo por la disponibilidad de
los valores de los registros fuente; una instrucción espera en la cola hasta que sus operándos han sido
calculados, después es enviada a una unidad funcional para su ejecución [3, 5].
AL
LO
CA
TIO
N &
RE
NA
ME
MA
PP
ER
/DIS
PA
TC
H
IIQ
IFQ
LSQ
ROB
Figura.5 Lógica de emisión de instrucciones
3 . 1 E L B U F F E R D E R O E R D E N A M I E N T O ( R O B )
El ROB o también llamado “lista de instrucciones activas” [8, 7] es tradicionalmente utilizado en
procesadores fuera de orden con la intención de construir un estado exacto del procesador; este es
esencialmente una memoria FIFO, con entradas almacenadas en orden de programa [4]. Al momento que
las instrucciones son despachadas, se cargan en el ROB a la entrada indicada por el apuntador de cola y son
retiradas a los registros arquitecturales en orden de programa indicado por el apuntador de cabecera.
Auxiliándose con copias de las RAT en cada ciclo, el ROB permite al procesador restablecerse desde un
estado exacto cuando ocurren excepciones. El ROB almacena: el contador de programa PC, bits bandera de
instrucciones especulativas, cola a la que fue asignada la instrucción, entrada de la cola, registro destino,
para invalidar entradas en la cola y valores de registros calculados, así como liberar registros físicos.
Issue-bit
Branch-bit
Executed-bit
Current Destination Register
Tail Pointer Register Head Pointer Register
Old Destination Register
Program Counter
Valid-bit
1 RD Ports [BTB]
4 RD Port[Commit]
4 WR Port [Execution]
8 WR Port [Issue]
4 WR Port [Dispatch]
Figura 6. Buffer de reordenamiento
Diseño de un procesador superescalar con ejecución fuera de orden Usando lenguajes de descripción de hardware
(VHDL)
Página 6
3 . 2 M O D E L O D E C O L A S D E I N S T R U C C I O N E S
La cola de instrucciones es una estructura del procesador para almacenar las instrucciones decodificadas
hasta que sus operándos fuentes estén disponibles antes de ser emitidas a las unidades de ejecución. La
figura 7, muestra la organización general de la cola de instrucciones. El despacho de instrucciones a las
colas de emisión está organizada en primera instancia por el Mapper ésta unidad funciona como un
multiplexor seleccionando las instrucciones de acuerdo al tipo (enteras, de punto flotante, de acceso a
Memoria, etc.) para enviarlas a las colas de instrucciones correspondientes. El Mapper escribe en la sección
RAM (Payload) la información completa de las instrucciones, ésto incluye: el código de operación, los
registros fuente, el registro destino y bits de bandera. En la sección CAM se escriben ambos registros
fuente, y en la lógica de selección se escribe el código de la unidad funcional que la instrucción utiliza para
su ejecución. La lógica de asignación de cada cola debe ofrecer en cada ciclo una entrada libre por puerto
de escritura, y actualizar la cola con nuevas instrucciones, que ocuparan los espacios que dejan libres las
instrucciones que fueron emitidas a las unidades funcionales. Las instrucciones que se emiten a las
unidades funcionales escriben la etiqueta del registro destino a un bus dedicado para tal efecto (Tag bus),
éstas se envían a las memorias CAM de las colas correspondientes para despertar instrucciones
dependientes.
INT Queue
Payload RAM
CAM
Wakeup
SE
LE
CT
ION
Lo
gic
AL
LO
CA
TIO
N
Lo
gic FP Queue
Payload RAM
CAM
Wakeup
SE
LE
CT
ION
Lo
gic
AL
LO
CA
TIO
N
Lo
gic
TAG BUS From INT FP and L/S Queues
I0 I1 I2 I3 F0 F1 F2 F3MAPPER
Figura 7. Modelo de colas de instrucciones
La cola de enteros puede despertar sucesores en ella misma, en la cola de FP y en la cola de Ld/St. Mientras
la cola de FP sólo puede despertar instrucciones en ella misma, la cola de L/S puede despertar sucesores en
ambas colas de enteros y punto flotante. La lógica de selección de instrucciones es la responsable de elegir
las instrucciones que están listas para ser ejecutadas. Cuando más de una instrucción contiende por la
misma unidad funcional, un circuito de prioridad resuelve este conflicto, normalmente eligiendo la
instrucción de mayor edad. La lógica de Wakeup y la lógica de Selección de instrucciones, constituyen
ambas una operación atómica, ésto implica que la operación completa deberá terminar en el mismo ciclo,
para que el Wakeup y la selección de instrucciones dependientes pueda iniciar en el ciclo siguiente, de esta
forma las cadenas de instrucciones dependientes puedan ser ejecutadas en ciclos consecutivos.
3 . 3 L O G I C A D E A S I G N A C I Ó N D E I N S T R U C C I O N E S
Las colas basadas en arreglo RAM-CAM sin soporte para compactar, deben reutilizar los “huecos” que
dejan las instrucciones que se han enviado a ejecución. Contrario a la lógica de selección y la lógica de
Wakeup, la lógica de asignación de instrucciones para estas colas casi no ha sido estudiada. En esta sección
se presenta una forma simple de controlar las asignaciones de instrucciones mediante listas de “huecos”.
Diseño de un procesador superescalar con ejecución fuera de orden Usando lenguajes de descripción de hardware
(VHDL)
Página 7
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
N X
fre
e lis
t
N X
De
co
de
rs
Section
CAM
Payload
RAM
Figura 8. Modelo de asignación
Las instrucciones que se envían a ejecutar, escriben la dirección de la posición que ocupaban en una
memoria FIFO para formar la lista de entradas libres, esto mejora la distribución de uso de las entradas,
porque siempre se asigna una nueva instrucción al último hueco usado. Si la cola de instrucciones está
totalmente llena en un momento determinado, una señal de paro se envía a la etapa anterior (Mapper). De
lo contrario, la lógica de asignación acepta nuevas instrucciones, decodificando en cada ciclo una entrada
de la lista de “huecos”. El número de listas/decodificador es igual al número de puertos de escritura de la
cola.
3 . 4 L O G I C A D E D E S P E R T A D O D E I N S T R U C C I O N E S
La lógica de Wakeup se lleva a cabo en la sección CAM (ver figura 9) ésta es la responsable de despertar a
las instrucciones que esperan a que sus operándos estén disponibles. Cuando una instrucción termina su
ejecución, el identificador del registro destino (Tag), se envía por buses dedicados hacia las CAM’s de las
colas correspondientes. Cada instrucción compara el identificador del registro de resultado Tagn con sus
propios identificadores de operándos fuente Op1 y Op2. Aquellos identificadores de operándos fuentes que
resulten idénticos son marcados como disponibles OpnRdy. Luego la instrucción se marca como susceptible
de ser ejecutada si todos sus operándos están disponibles.
Tag
0
Tag
1
Tag
2
Tag
3
OR OR
Inst n-1
Inst 0
Inst n-2
Op2 RdyOp2 TagOp1 TagOp1 Rdy
OR OR
Op2 TagOp1 Tag
OR OR
Op1 Rdy Op2 Rdy
Op2 TagOp1 TagOp1 Rdy Op2 Rdy
Figura 9. Modelo de la sección CAM
Diseño de un procesador superescalar con ejecución fuera de orden Usando lenguajes de descripción de hardware
(VHDL)
Página 8
La figura 9 muestra de forma detallada la organización de la sección CAM en la cola de instrucciones,
asumiendo un ancho de emisión de cuatro instrucciones, se requieren de ocho comparadores por cada
entrada de la cola, todas las comparaciones idealmente deben realizarse en un solo ciclo de reloj para
permitir despertar hasta cuatro instrucciones por ciclo. Si uno ó más operándos están ya disponibles
cuando la instrucción se escribe inicialmente en la cola, se prenden inmediatamente los bits OpnRdy, si uno
ó más de sus operándos no están disponibles, la instrucción espera en la cola hasta que estos sean
generados por las instrucciones productoras.
3 . 5 L O G I C A D E S E L E C C I Ó N D E I N S T R U C C I O N E S
El módulo nombrado Selection Logic (en la figura 8) almacena información de las unidades de ejecución que
han sido asignadas a las instrucciones durante la etapa de decodificación formando un vector de recursos y
en combinación con las señales de instrucciones listas para ejecución y la disponibilidad de unidades
funcionales genera las señales de solicitud de ejecución.
F.U
. L
ate
nc
y
Co
un
ters
Op
Rd
y1
Op
Rd
y2
Op
Rd
y1
Op
Rd
y2
Op
Rd
y1
Op
Rd
y2
Op
Rd
y1
Op
Rd
y2
FU A
FU C
FU B
FU D
Re
so
urc
es
ve
cto
r
RA
0
RB
0
RC
0
RD
0
RA
1
RB
1
RC
1
RD
1
RA
2
RB
2
RC
2
RD
2
RA
3
RB
3
RC
3
RD
3
Figura 10. Lógica de solicitud de ejecución
Dependiendo del tipo de cola, ésta puede emitir instrucciones a un número determinado de unidades
funcionales, la figura 10 muestra la lógica para generar las solicitudes de ejecución además de los
contadores de latencia de las unidades funcionales identificadas como A, B, C y D, las mismas a las cuales la
cola puede emitir instrucciones. Cuando una unidad funcional está libre, su contador de latencia envía una
señal a lo largo del arreglo de vectores de recursos, si una instrucción está lista para ejecutarse, los bits de
Ready de sus operándos fuente habilitan los Latches del vector de recursos. Los vectores de recursos
asignados son almacenados con cada entrada de la cola permitiendo generar las solicitudes de ejecución
para cada instrucción de forma independiente. Cuando dos ó más instrucciones compiten por una misma
unidad funcional, un circuito de prioridad resuelve el conflicto asignando la unidad funcional a la
instrucción de mayor prioridad.
Para al modelo base hemos usado el circuito diseñado para el procesador MIPS R10000 mostrado en la
figura 11. El circuito es de prioridad fija, inicia con la entrada cero (mayor prioridad) y trabaja hacia arriba,
las entradas activas de mayor prioridad cancelan las entradas activas de menor prioridad[2].
Diseño de un procesador superescalar con ejecución fuera de orden Usando lenguajes de descripción de hardware
(VHDL)
Página 9
An
y_
Re
q_
A
VC
C
RD
3
RD
0
RD
1
RD
2
IA0
IA1
IA2
IA3
CL
K
VC
C
CL
K
VC
C
CL
K
VC
C
CL
K
VC
C
CL
K
RC
3
RC
0
RC
1
RC
2
RB
3
RB
0
RB
1
RB
2
RA
3
RA
0
RA
1
RA
2
ID0
IC0
IB0
ID1
IC1
IB1
ID2
IC2
IB2
ID3
IC3
IB3
An
y_
Re
q_
B
An
y_
Re
q_
C
An
y_
Re
q_
D
VC
C
CL
K
Figura 11. Circuito de prioridad fija
Un circuito de prioridad se requiere para cada una de las señales de solicitud de ejecución
representadas como RAn, RBn, RCn, y RDn, generando las señales intermedias IAn, IBn, ICn, IDn más
Any_Req_X, donde X= A, B, C y D unidades funcionales. Dependiendo del tamaño de la cola de
instrucciones, se puede requerir de más etapas para generar la señal de permiso de ejecución. Las
etapas posteriores utilizan las señales Any_Req_X como entradas, las salidas de la segunda etapa
validan las solicitudes de la primera etapa por tipo de unidad funcional, como se muestra en la figura
12. Generando las señales de selección de palabra WL, para este ejemplo la cola tiene 4 puertos de
emisión y cada entrada tiene 4 señales WLpe, donde p es el puerto y e la entrada de la cola. Un puerto
se asigna a sólo una unidad de ejecución.
An
y_
Re
q_
A
An
y_
Re
q_
B
An
y_
Re
q_
C
An
y_
Re
q_
D
IA3
IB3
IC3
ID3
IA1
IB1
IC1
ID1
IA0
IB0
IC0
ID0
IA2
IB2
IC2
ID2
An
y_
Re
q_
A
An
y_
Re
q_
B
An
y_
Re
q_
C
An
y_
Re
q_
D
IA3
IB3
IC3
ID3
IA1
IB1
IC1
ID1
IA0
IB0
IC0
ID0
IA2
IB2
IC2
ID2
An
y_
Re
q_
A
An
y_
Re
q_
B
An
y_
Re
q_
C
An
y_
Re
q_
D
IA3
IB3
IC3
ID3
IA1
IB1
IC1
ID1
IA0
IB0
IC0
ID0
IA2
IB2
IC2
ID2
RA
0R
B0
RC
0R
D0
RA
1R
B1
RC
1R
D1
RA
2R
B2
RC
2R
D2
RA
3R
B3
RC
3R
D3
An
y_
Re
q_
A
An
y_
Re
q_
B
An
y_
Re
q_
C
An
y_
Re
q_
D
IA3
IB3
IC3
ID3
IA1
IB1
IC1
ID1
IA0
IB0
IC0
ID0
IA2
IB2
IC2
ID2
RA
0R
B0
RC
0R
D0
RA
1R
B1
RC
1R
D1
RA
2R
B2
RC
2R
D2
RA
3R
B3
RC
3R
D3
RA
0R
B0
RC
0R
D0
RA
1R
B1
RC
1R
D1
RA
2R
B2
RC
2R
D2
RA
3R
B3
RC
3R
D3
RA
0R
B0
RC
0R
D0
RA
1R
B1
RC
1R
D1
RA
2R
B2
RC
2R
D2
RA
3R
B3
RC
3R
D3
WL
00
WL
10
WL
20
WL
30
WL
01
WL
11
WL
21
WL
31
WL
02
WL
12
WL
22
WL
32
WL
03
WL
13
WL
23
WL
33
WL
04
WL
14
WL
24
WL
34
WL
05
WL
15
WL
25
WL
35
WL
06
WL
16
WL
26
WL
36
WL
07
WL
17
WL
27
WL
37
WL
08
WL
18
WL
28
WL
38
WL
09
WL
19
WL
29
WL
39
WL
0A
WL
1A
WL
2A
WL
3A
WL
0B
WL
1B
WL
2B
WL
3B
WL
0C
WL
1C
WL
2C
WL
3C
WL
0D
WL
1D
WL
2D
WL
3D
WL
0E
WL
1E
WL
2E
WL
3E
WL
0F
WL
1F
WL
2F
WL
3F
Figura 12. Arbitro de selección completo
Diseño de un procesador superescalar con ejecución fuera de orden Usando lenguajes de descripción de hardware
(VHDL)
Página 10
3 . 5 L O G I C A D E E N V I O A E J E C U C I Ó N
Las instrucciones susceptibles de ser ejecutadas y de mayor prioridad en la cola son seleccionadas por el
árbitro para ser emitidas a las unidades funcionales. La figura 13 ejemplifica la lógica de emisión, se han
considerado instrucciones de tres registros, una instrucción puede tener 0, 1 ó 2 operándos fuentes. La
lógica de selección asigna una instrucción a cada puerto de emisión de la cola, en el mismo ciclo de reloj
(CLK1) los Latches son habilitados para que los operándos fuente indexen el banco de registros físicos, un
bit en el formato de instrucción selecciona un par de multiplexores en caso de que existan valores
inmediatos. Las unidades funcionales leen sus entradas a través de la red de paso de valores (bypass) del
banco de registros ó de cualquier otra unidad funcional. El Latch de registro destino se habilita cuando la
unidad funcional ha finalizado la ejecución (CLK2/CLK3) para que el registro destino pueda despertar
sucesores y para que el banco de registros sea actualizado, note que CLK2 y CLK3 operan a los mismos
períodos que las latencias de las unidades funcionales respectivas.
INT Queue
Payload RAM
SE
LE
CT
ION
Lo
gic
LatchLatch
Dest
TagSrc1
Tag
Src2 Tag/
(Inm)
CLK1
DEMUX
MUX
CLK2Latch
Bypass Network
FU A
LatchLatch
Dest
Tag
Src1
Tag
Src2 Tag/
(Inm)
CLK1
DEMUX
MUX
CLK3Latch
FU B
TAG BUS From INT FP and L/S Queues
INT Physical Register File
ADD_A0 ADD_A1
DAT_A0 DAT_A1
ADD_A2
DAT_A3
ADD_B0 ADD_B1
DAT_B0 DAT_B1
ADD_B2
DAT_B2
Figura 13 Lógica de la cola de instrucciones (solo se ilustran dos puertos de emisión)
ISSUE I0
SELECT I1
EXECUTION I0
ISSUE I1
WRITE
BACK I0
EXECUTION I1
SELECT I2
ISSUE I2
SELECT I3
EXECUTION I2
ISSUE I3
WAKEUP I0
WAKEUP I3
WAKEUP I1
WAKEUP I2
SELECT I4
REGISTERS READ 0
DECODE READ WRITE TO ALU PORT
ISSUE I4
WRITE
BACK I1
REGISTERS READ 1
DECODE READ WRITE TO ALU PORT
REGISTERS READ 2
DECODE READ WRITE TO ALU PORT
REGISTERS READ 3
DECODE READ WRITE TO ALU PORTEXECUTION I
3
REGISTERS READ 4
DECODE READ WRITE TO ALU PORT
8 FO4
Figura 14 Fases de Wakeup, select e issue en la ejecución de instrucciones
Diseño de un procesador superescalar con ejecución fuera de orden Usando lenguajes de descripción de hardware
(VHDL)
Página 11
La Figura 14 muestra la segmentación para ciclos consecutivos de ejecución, las unidades funcionales usan
la red de bypass, y las operaciones de Wakeup y Select tienen que ser ejecutadas en un ciclo para
instrucciones con latencias de un ciclo.
3 . 6 L O G I C A D E A C C E S O A M E M O R I A
Una unidad de acceso a memoria, se compone por un buffer de traducción de direcciones de virtuales a
físicas TLB, una memoria cache de datos, y una LSQ, comúnmente como un par de colas ordenadas por
edad, totalmente asociativas [6]. LSQ realiza las siguientes cinco funciones:
1) Almacenar direcciones y valores de instrucciones ST para su retiro en orden de programa: cada
entrada guarda la dirección de memoria de la instrucción STA y el valor a almacenar TSD, mas bits
de banderas; cuando una instrucción ST es retirada del ROB, la entrada correspondiente se retira
de la cola de ST.
2) Almacenar direcciones y valores de instrucciones LD: cada entrada incluye campos de dirección
LDA y de valor LDD de la instrucción mas bits de banderas; la estructura se usa para detectar
violación de orden y puede disparar un mecanismo de limpieza en las etapas del procesador, si el
campo STA de una instrucción ST de mayor edad coincide con el campo LDA de una instrucción LD
ejecutada de forma especulativa.
3) Adelantar valores de instrucciones ST a instrucciones LD más jóvenes: cuando una instrucción LD
se emite para ejecución, se investiga en la cola de ST si el campo de direcciones LDA coincide con
alguna dirección STA de las instrucciones ST de mayor edad, si esto sucede el valor se adelanta
mediante la lectura del campo de datos STD. En otro caso la instrucción LD puede ejecutarse sin
causar violación de orden, a este mecanismo se conoce como “desambiguación de memoria”.
4) Detección de violación de orden entre instrucciones LD/ST: el orden de ejecución de las
instrucciones en un procesador fuera de orden es importante, porque instrucciones LD que
dependan de las instrucciones ST, pueden devolver valores erróneos si la carga LD se ejecuta antes
que el almacenamiento ST.
5) Detección de violaciones de consistencia: Los procesadores con características de
multiprocesadores tales como el Alpha 21264 o el Power4 usan la cola de acceso a memoria para
forzar un modelo de consistencia de memoria, por prevención de violaciones en instrucciones ST
remotas entre instrucciones de carga LD emitidas fuera de orden.
3 . 6 . 1 O P E R A C I Ó N D E L A C O L A D E A C C E S O A M E M O R I A
Las colas de acceso a memoria, se diseñan con un par de memorias FIFO para operaciones de carga y
almacenamiento las cuales mantienen sus valores en orden de programa y un par de memorias CAM de
igual tamaño que almacenan las direcciones de memoria, la figura 15 muestra una arquitectura típica de la
cola de acceso a memoria. Las instrucciones de memoria en estado de decodificación son separadas en dos
operaciones: el cálculo de la dirección efectiva y la instrucción de acceso a memoria propiamente, la
primera es la suma de dos registros de 64-bits o la suma de un registro de 64-bits más un valor inmediato
de 16 bits, esta instrucción se asigna a la cola de enteros y la segunda se asigna a la cola de acceso a
memoria, la entrada correspondiente de la memoria CAM se reserva para guardar la dirección cuando esta
haya sido calculada.
Diseño de un procesador superescalar con ejecución fuera de orden Usando lenguajes de descripción de hardware
(VHDL)
Página 12
Con cada nueva instrucción que se asigna a una de las FIFO’s que componen la cola de acceso a memoria la
edad de la otra FIFO también se escribe, para conocer los limites de búsqueda en el adelanto de valores y
en las acciones para evitar violaciones de orden.
TPR HPR
TPR HPR
LD inst
ST inst
LOAD BUFFER
STORE BUFFER
SEND TO EXECUTION
LD
DS
TA
AG
EL
DD
LD
AA
GE
Figura 15. Arquitectura de la cola de acceso a memoria
Cada FIFO tiene dos registros apuntadores: HPR apuntador de cabecera y TPR apuntador de cola. TPR
apunta a la entrada de la FIFO para asignar nuevas instrucciones o para limpieza de instrucciones
especulativas, HPR apunta a la entrada de la FIFO para retirar instrucciones. Cuando una instrucción LD es
asignada a la cola de instrucciones, se indaga en la cola de instrucciones ST (almacenamiento) por una
instrucción de mayor edad que la instrucción de carga para paso de valores. El campo AGE de las colas de
acceso a memoria, tienen lógica para invalidar de manera selectiva las entradas de las memorias CAM (LDA
y STA) para cada una de las tres operaciones de búsqueda, adelantado de datos, detección de violación de
orden y detección de violación de consistencia.
E T A P A 4 : E J E C U C I Ó N
En esta etapa es en donde cualquier operación o cálculo de dirección se realiza, IQ, FPQ y LSQ envían sus
instrucciones listas para ejecución a sus unidades de ejecución libres. Las unidades funcionales son
agrupadas por el tipo de operación que realizan en unidades de ejecución de enteros y unidades de
ejecución de punto flotante, como es el caso de los procesadores Alpha 21264 o el MIPS R10000.
Unidades de ejecución de enteros: se componen por sumadores, unidades lógicas, unidades de
desplazamiento, unidades de cálculo de direcciones de saltos condicionales, unidades de multiplicación y
división. Cada unidad funcional tiene dos puertos de entrada de 64-bits que son cargados desde el banco
de registros físicos.
Unidades de ejecución de punto flotante: son más complejas que las de enteros, primero los valores son
organizados en formatos IEEE Std 754 de simple y doble precisión en el banco de registros. Las unidades
funcionales y la red de paso de valores, usan un formato que explícitamente almacena los 11-bits de
exponente y los 53-bits de mantisa. Los operándos se descomprimen en la lectura y se comprimen antes de
ser escritos de nuevo al banco de registros. La compresión-descompresión se implementa por un
Diseño de un procesador superescalar con ejecución fuera de orden Usando lenguajes de descripción de hardware
(VHDL)
Página 13
multiplexor de 2-entradas que selecciona los bits de acuerdo al formato de simple o doble precisión, esta
lógica esta localizada entre la unidad funcional y el banco de registros. La unidad de ejecución de punto
flotante se compone de los siguientes componentes: sumador, multiplicador y lógica de divisor/raíz-
cuadrada. El sumador puede ejecutar operaciones de suma, resta, comparación y conversión de formato. El
multiplicador ejecuta múltiples operaciones en un arreglo completo de doble precisión. por ejemplo en el
procesador MIPS R10000 dos unidades iterativas independientes calculan operaciones de división y raíz
cuadrada, esta unidad comparte puertos del banco de registros con el multiplicador. Todas las unidades
son totalmente segmentadas con la misma velocidad de ciclo de repetición. Por ejemplo, el sumador en el
primer estado sustrae los exponentes, selecciona el operando más largo y alinea la mantisa más pequeña
en un registro de desplazamiento de 55-bits. El segundo estado suma o resta dependiendo de la operación
y signo de los operándos. Una suma puede producir un acarreo que requiere de un desplazamiento de 1-bit
a la derecha para post normalización y redondeo después del resultado generado. Para evitar introducir
retardos, un sumador paralelo de acarreos encadenados genera ambas versiones del resultado de la suma
+1 y +2, el procesador selecciona +2 si la operación requiere post-normalización [8].
E T A P A 5 : E S C R I T U R A A R E G I S T R O S ( W R I T E B A C K )
El estado de escritura de registros es responsable de actualizar valores en ambos bancos de registros, de
enteros y de FP. Las unidades de ejecución leen sus operándos de los bancos de registros y escriben sus
resultados directamente en el mismo banco de registros. Estos resultados pueden ser pasados mediante
una red de multiplexores (baypass) a cualquiera de las unidades de ejecución como operándos fuente de
nuevas instrucciones que inician su ejecución.
from STORE Queue, Jump Register and
move-to-floating point instructions
AL
U2
AL
U1
AC
U
M
M
To LS Queue
RdPort 1
RdPort 2
RdPort 3
RdPort 4
RdPort 5
RdPort 7
RdPort 6
WrPort 1
WrPort 2
WrPort 3
from LOAD Queue, Branch-and-link
and move from floating point
instructions
M
Imm from Int. Queue CONTROL
Int Register File
from STORE Queue, Jump Register and
move-to-floating point instructions
AD
DM
UL
T
M
M
RdPort 1
RdPort 2
RdPort 3
RdPort 4
RdPort 5
WrPort 1
WrPort 2
WrPort 3
from LOAD Queue, Branch-and-link
and move from floating point
instructions
FP Register File
CONTROL
Figura 16. Bancos de registros físicos de a) Enteros y b) F.P.
Los bancos de registros físicos de enteros y de punto flotante mostrados en la figura 16, requieren de un
número de puertos de lectura y escritura como unidades funcionales tengan, considerando dos puertos de
lectura y uno de escritura por cada unidad de ejecución incluida la unidad de cálculo de direcciones.
Adicionalmente un puerto de lectura y uno de escritura se usa para operaciones de carga LD y
movimientos entre los registros de anteros y punto flotante. Vectores de condición del tamaño del banco
de registros por un bit indican: valor cero y valor especulativo o graduado, sus puertos operan en paralelo
Diseño de un procesador superescalar con ejecución fuera de orden Usando lenguajes de descripción de hardware
(VHDL)
Página 14
con el correspondiente banco de registros. El vector de valor cero permite a instrucciones de movimientos
condicionales de enteros y flotantes verificar un solo bit de condición en vez de un registro completo, el
vector de valor especulativo indica si las instrucciones que producen estos valores se han graduado o no,
nuestro modelo utiliza bancos de 128 registros físicos. Es posible la ejecución de instrucciones
dependientes en cada ciclo por la red de paso de valores, en los procesadores modernos esta red de paso
de valores es construida generalmente con multiplexores. Un procesador con una red de paso de valores
completo permite a cualquier unidad funcional leer sus entradas de los resultados que producen cualquiera
de las unidades de ejecución, antes de que sea escrito en el banco de registros. La lógica de paso de valores
consiste de dos componentes buses de datos y control, un modelo de paso de valores completo sobre
unidades funcionales de dos entradas requiere ni22 buses de valores, donde i es el ancho de emisión
de instrucciones y n son los etapas del procesador después del estado que produce el primer valor [1, 5].
R E S U L T A D O S Y C O N C L U S I O N E S
1. Se ha podido generar el código HDL de un procesador superescalar con ejecución fuera de orden,
utilizando herramientas de diseño de la empresas líderes en el campo, -QuartusII (Altera), ISE-
Foundation (Xillinx)-
2. Se han probado vario módulos en el simulador de la herramienta de desarrollo.
3. Se ha generado bibliografía para docencia e investigación en el área de arquitectura de computadoras
y sistemas embebidos.
4. Se han generado dos tesis de maestría, una para graduarse en el semestre A08, y un segundo para
graduarse en el semestre A09.
5. A partir del cierre del presente proyecto, el código se distribuye por web (www.microse.cic.ipn.mx )
sin ninguna restricción, a fin de promover el desarrollo y la investigación en arquitecturas de
computadoras en las universidades del país.
I M P A C T O
El proyecto tiene un impacto a nivel educativo muy importante, pues no existe a la fecha una
infraestructura pública de este tipo en el IPN y en ninguna universidad mexicana.
Aunque para poder medir el impacto real se requiere de difundir mas este proyecto y promover su uso,
una de las medidas que se tomaron, es distribuir por web sin restricción alguna el proyecto completo,
desde el código VHDL, material para clase, manuales, y prácticas de laboratorio a fin de promover el
desarrollo y la investigación en arquitecturas de computadoras en las universidades del país.
Diseño de un procesador superescalar con ejecución fuera de orden Usando lenguajes de descripción de hardware
(VHDL)
Página 15
T R A B A J O S F U T U R O S
El trabajo del “core” del procesador Alligator_SP no se acaba con este proyecto, este requiere de
mantenimiento y mejora continua, a fin de robustecer el diseño.
Se requiere generar nuevas propuestas para:
1. Una unidad de manejo de memoria MMU
2. Una unidad de Entrada Salida
3. Una unidad de Video de alta definición
4. Un sistema operativo embebido, etc.
R E F E R N C I A S
[1] P. S. Ahuja, D. W. Clark and A. Rogers, The performance impact of incomplete bypassing in processor pipelines., 28th Annual international Symposium on Microarchitecture, IEEE Computer Society, Ann Arbor, Michigan, United States, 1995, pp. 36-45.
[2] J. G. Delgado-Frias and J. Nyathi, A VLSI High-Performance Encoder with Priority Lookahead, Great Lakes Symposium on VLSI, 1998, pp. 59.
[3] J. A. Farrell and T. C. Fischer, Issue Logic For A 600 MHz Out-of-order Execution, IEEE Journal of Solid-State Circuits, 33 (1998), pp. 707-712.
[4] G. Kucuk, O. Ergin, D. Ponomarev, O. Ergin and K. Ghose, Complexity-Effective Reorder Buffer Designs
for Superscalar Processors, IEEE Transaction on Computer, 53 (2004), pp. 653-665. [5] S. Palacharla, N. P. Jouppi and J. E. Smith, Complexity-effective superscalar processors, 24th Annual
international Symposium on Computer Architecture, Denver, Colorado, United States, 1997, pp. 206-218.
[6] I. Park, C. L. Ooi and T. N. Vijaykumar, Reducing Design Complexity of the Load/Store Queue, 36th
IEEE/ACM International Symposium on Microarchitecture, 2003, pp. 411.
[7] D. Ponomarev, G. Kucuk and K. Ghose, Energy-Efficient Design of the Reorder Buffer, 12th International Workshop on Integrated Circuit Design. Power and Timing Modeling, Optimization and Simulation, Springer-Verlag, 2002, pp. 289 - 299.
[8] K. C. Yeager, The MIPS R10000 Superscalar Microprocessor, IEEE Micro, 16 (1996), pp. 28-40. [9] T.-Y. Yeh and Y. N. Patt, Alternative implementations of two-level adaptive branch prediction, 19th
annual international symposium on Computer architecture, ACM Press, Queensland, Australia, 1992, pp. 124-134.