Escalação Dinâmica
Algorítmo de Tomasulo
DAP Spr.‘98 ©UCB 1
Revisão: Três Partes do Scoreboard
1.Status da instrução — em qual dos 4 passos a instrução
se encontra
2. Status da unidade funcional — indica o estado da
unidade funcional (FU), através dos campos:
Busy — indica se a unidade está ocupada ou não
Op — operação a ser realizada pela unidade (ex., + ou –)
Fi — registrador de destino
Fj, Fk — número dos registradores fonte
Qj, Qk — unidades funcionais produzindo dados para Fj, Fk
Rj, Rk — Flags indicando se Fj, Fk estão prontos
3. Status do registrador destino — Indica qual unidade
funcional irá escrever em cada registrador.
DAP Spr.‘98 ©UCB 2
Exemplo de Scoreboard Ciclo 3
Instruction status
Instruction
Read
j
k
LD
F6
34+
R2
LD
F2
45+
R3
MULTDF0
F2
F4
SUBD F8
F6
F2
DIVD
F0
F6
F8
F2
F10
ADDD F6
Issue
operands complete Result
1
2
Functional unit status
Time Name
ExecutionWri te
3
dest
S1
S2
FU for j
FU for k
Fj?
Fk?
Fj
Fk
Qj
Qk
Rj
Rk
Busy
Op
Fi
Integer
Yes
Load
F6
Mult1
No
Mult2
No
Add
No
Divide
No
F2
F4
R2
Yes
Register result status
Clock
3
F0
FU
F6
F8
F10
F12
...
F30
Integer
Emite MULT? Não, espera emissão do segundo LD
DAP Spr.‘98 ©UCB 3
Exemplo de Scoreboard Ciclo 9
Instruction status
Instruction
Read
j
k
Issue
Execution Wri te
operands complete Result
LD
F6
34+
R2
1
2
3
4
LD
F2
45+
R3
5
6
7
8
MULTDF0
F2
F4
6
9
SUBD F8
F6
F2
7
9
DIVD
F0
F6
8
F8
F2
F10
ADDD F6
Functional unit status
Time Name
dest
S1
S2
FU for j
FU for k
Fj?
Fk?
Op
Fi
Fj
Fk
Qj
Qk
Rj
Rk
Mult
F0
F2
F4
Yes
Yes
Yes
Sub
F8
F6
F2
Yes
Yes
Yes
Div
F10
F0
F6
Mult1
No
Yes
F0
F2
F4
F6
F8
F10
...
F30
Add
Divide
Busy
Integer
No
10 Mult1
Yes
Mult2
No
2 Add
Divide
Register result status
Clock
9
•
FU
Mult1
F12
Lê operandos para MULT & SUBD? Emite ADDD?
DAP Spr.‘98 ©UCB 4
Exemplo de Scoreboard Ciclo 17
Instruction status
Instruction
Read
j
k
Issue
Execution Wri te
operands complete Result
LD
F6
34+
R2
1
2
3
4
LD
F2
45+
R3
5
6
7
8
MULTDF0
F2
F4
6
9
SUBD F8
F6
F2
7
9
11
12
DIVD
F0
F6
8
F8
F2
13
14
16
F10
ADDD F6
Functional unit status
Time Name
Busy
Integer
dest
S1
S2
FU for j
FU for k
Fj?
Fk?
Op
Fi
Fj
Fk
Qj
Qk
Rj
Rk
Mult
F0
F2
F4
Yes
Yes
Yes
Yes
No
Yes
...
F30
No
2 Mult1
Yes
Mult2
No
Add
Yes
Add
F6
F8
F2
Divide
Yes
Div
F10
F0
F6
Mult1
F0
F2
F4
F6
F8
F10
Register result status
Clock
17
FU
Mult1
Add
F12
Divide
Escreve resultado de ADDD? Não, perigo WAR
DAP Spr.‘98 ©UCB 5
Exemplo de Scoreboard Ciclo 62
Instruction status
Instruction
Read
j
k
Issue
Execution Wri te
operands complete Result
LD
F6
34+
R2
1
2
3
4
LD
F2
45+
R3
5
6
7
8
MULTDF0
F2
F4
6
9
19
20
SUBD F8
F6
F2
7
9
11
12
DIVD
F0
F6
8
21
61
62
F8
F2
13
14
16
22
F10
ADDD F6
Functional unit status
Time Name
Busy
Integer
No
Mult1
No
Mult2
No
Add
No
0 Divide
No
dest
S1
S2
FU for j
FU for k
Fj?
Fk?
Op
Fi
Fj
Fk
Qj
Qk
Rj
Rk
F2
F4
F6
F8
F10
F12
...
F30
Register result status
Clock
62
F0
FU
• Emissão em ordem; Leitura e execução fora de ordem;
escrita fora de ordem, respeitando WAR
DAP Spr.‘98 ©UCB 6
Scoreboard - Sumário
• Limitações do scoreboard do CDC 6600
– Sem antecipação (primeiro escreve no registrador, depois lê) para
RAW
– Limitado a instruções num bloco básico (pequena janela)
– Número limitado de unidades funcionais (conflito estrutural)
– Espera pela dependência WAR para escrita
– Previne a dependência WAW na emissão
DAP Spr.‘98 ©UCB 7
Um outro Algoritmo para Escalação
Dinâmica: Algorítmo de Tomasulo
• Usado no IBM 360/91 por volta de 3 anos após CDC 6600
(1966)
• Alto Desempenho sem compiladores especiais
• Porquê estudar? Devido ao uso no Alpha 21264, HP
8000, MIPS 10000, Pentium II, PowerPC 604, …
DAP Spr.‘98 ©UCB 8
Algoritmo Tomasulo
• Controle & buffers distribuídos nas unidades funcionais (UFs)
– Buffers de UFs chamados estações de reserva (reservation
station- RS), contem operandos pendentes
3
2
1
SOMADOR FP3
SOMADOR FP2
SOMADOR FP1
DAP Spr.‘98 ©UCB 9
Algoritmo Tomasulo
• Operandos após serem processados pelas UFs são difundidos diretamente
para todas as RSs que esperam dados, pelo CDB (Common Data Bus)
(no scoreboard os resultados eram escritos nos registradores para depois
serem lidos)
• Loads e Stores tratados como UFs com RSs
• Instruções de inteiros podem ser executadas após desvios (branches)
UFs para Loads e Stores
DAP Spr.‘98 ©UCB 10
Renomeação de Registradores
Registradores são renomeados nas estações de reserva
Evita conflitos WAR, WAW
DIV.D
ADD.D
S.D
SUB.D
MUL.D
F0, F2, F4
F6, F0, F8
F6, 0(R1)
F8, F10, F14
F6, F10, F8
RENOMEAÇÃO:
DIV.D
ADD.D
S.D
SUB.D
MUL.D
F0, F2, F4
S, F0, F8
S, 0(R1)
T, F10, F14
F6, F10, T
DAP Spr.‘98 ©UCB 11
Organização de Tomasulo
DAP Spr.‘98 ©UCB 12
Componentes da Estação de Reserva
Op—operação na unidade (ex., add ou sub)
Vj, Vk—valores dos operandos fonte
– Os buffers de armazenamento (store) tem um campo do dado a ser
armazenado e um campo de endereço
– Os buffers de carga (load) tem apenas um campo de endereço
Qj, Qk— unidades funcionais/estação de reserva
produzindo os valores dos registradores fonte
– Os buffers de armazenamento tem somente Qi para indicar a unidade
funcional/estação de reserva produzindo o dado
Busy—indica se a estação de reserva está ocupada
Status de resultado do registrador — Indica qual
unidade funcional irá escrever em cada registrador.
DAP Spr.‘98 ©UCB 13
Os Três Estágios do Algoritmo de
Tomasulo
1.Emissão — a instrução da fila de instruções é emitida
com os nomes dos operandos renomeados, se tiver estação de reserva
disponível
2. Execução — realiza a execução da operação (EX)
se ambos os operandos estão prontos;
senão, aguarda o Bus de Dados Comum pelo resultado
3. Escrita do resultado — conclui a instrução (WB)
– escreve no Bus de Dados Comum para que todas as unidades à
espera possam ler o resultado:
Bus de Dados Normal: dado + destino (“go to” bus)
Bus de Dados Comum: dado + fonte (“come from” bus)
– 64 bits de dados + 4 bits de endereço fonte da Unidade Funcional
– marca a estação de reserva da instrução concluída como disponível
DAP Spr.‘98 ©UCB 14
Ex: Tomasulo Ciclo 0
Instruction status
Instruction
j
k
Issue
Execution
Wri te
complete
Result
Busy
LD
F6
34+
R2
Load1
No
LD
F2
45+
R3
Load2
No
MULTDF0
F2
F4
Load3
No
SUBD F8
F6
F2
DIVD
F0
F6
F8
F2
F10
ADDD F6
Reservation Stations
Time
Name
Busy Op
0 Add1
No
0 Add2
No
0 Add3
No
0 Mult1
No
0 Mult2
No
S1
S2
RS for j
RS for k
Vj
Vk
Qj
Qk
F2
F4
F6
F8
LD – 2 ciclos
SUBD – 2 ciclos
ADDD – 2 ciclos
MULT – 10 ciclos
DIVD – 40 ciclos
Address
Register result status
Clock
0
F0
F10
F12
...
F30
FU
DAP Spr.‘98 ©UCB 15
Ex: Tomasulo Ciclo 1
Instruction status
Instruction
j
k
Issue
1
Execution
Wri te
complete
Result
Busy
Address
Load1
No
Yes
34+R2
LD
F6
34+
R2
LD
F2
45+
R3
Load2
No
MULTDF0
F2
F4
Load3
No
SUBD F8
F6
F2
DIVD
F0
F6
F8
F2
F10
ADDD F6
Reservation Stations
Time
Name
Busy Op
0 Add1
No
0 Add2
No
Add3
No
0 Mult1
No
0 Mult2
No
S1
S2
RS for j
RS for k
Vj
Vk
Qj
Qk
F2
F4
F6
F8
Register result status
Clock
1
F0
FU
F10
F12
...
F30
Load1
DAP Spr.‘98 ©UCB 16
Ex: Tomasulo Ciclo 2
Instruction status
Instruction
j
k
Issue
Execution
Wri te
complete
Result
Busy
Address
LD
F6
34+
R2
1
Load1
Yes
34+R2
LD
F2
45+
R3
2
Load2
Yes
45+R3
MULTDF0
F2
F4
Load3
No
SUBD F8
F6
F2
DIVD
F0
F6
F8
F2
F10
ADDD F6
Reservation Stations
Time
Name
Busy Op
0 Add1
No
0 Add2
No
Add3
No
0 Mult1
No
0 Mult2
No
S1
S2
RS for j
RS for k
Vj
Vk
Qj
Qk
F2
F4
F6
F8
Register result status
Clock
2
F0
FU
Load2
F10
F12
...
F30
Load1
Nota: pode ter múltiplos loads em operação
DAP Spr.‘98 ©UCB 17
Ex: Tomasulo Ciclo 3
Instruction status
Instruction
j
k
Issue
Execution
Write
complete
Result
Address
Load1
Yes
34+R2
45+R3
LD
F6
34+
R2
1
LD
F2
45+
R3
2
Load2
Yes
MULTDF0
F2
F4
3
Load3
No
SUBD F8
F6
F2
DIVD
F0
F6
F8
F2
F10
ADDD F6
Reservation Stations
Time
Name
Busy Op
0 Add1
No
0 Add2
No
Add3
No
0 Mult1
Yes
0 Mult2
No
3
Busy
S1
S2
RS for j
RS for k
Vj
Vk
Qj
Qk
R(F4)
Load2
F4
F6
MULTD
Register result status
Clock
3
FU
F0
F2
Mult1
Load2
F8
F10
F12
...
F30
Load1
• Os nomes dos registradores são removidos (“renomeados”) nas
estações de reserva; MULT emitido
• Load1 completando: quem está esperando pelo Load1?DAP Spr.‘98 ©UCB 18
Ex: Tomasulo Ciclo 4
Instruction status
Instruction
j
k
Issue
Execution
Wri te
complete
Result
LD
F6
34+
R2
1
3
LD
F2
45+
R3
2
4
MULTDF0
F2
F4
3
SUBD F8
F6
F2
4
DIVD
F0
F6
F8
F2
F10
ADDD F6
Reservation Stations
Time
Busy
4
Load1
No
Load2
Yes
Load3
No
S1
S2
RS for j
RS for k
Busy Op
Vj
Vk
Qj
Qk
0 Add1
Yes
M(34+R2)
0 Add2
No
Add3
No
Name
0 Mult1
Yes
0 Mult2
No
SUBD
MULTD
Address
45+R3
Load2
R(F4)
Load2
F4
F6
F8
M(34+R2)
Add1
Register result status
Clock
4
FU
F0
F2
Mult1
Load2
F10
F12
...
F30
• Load2 completando: quem espera por F2?
DAP Spr.‘98 ©UCB 19
Ex: Tomasulo Ciclo 5
Instruction status
Instruction
j
k
Issue
Execution
Wri te
complete
Result
Busy
LD
F6
34+
R2
1
3
4
Load1
No
LD
F2
45+
R3
2
4
5
Load2
No
MULTDF0
F2
F4
3
Load3
No
SUBD F8
F6
F2
4
DIVD
F0
F6
5
F8
F2
F10
ADDD F6
Reservation Stations
Time
S1
S2
RS for j
RS for k
Busy Op
Vj
Vk
Qj
Qk
2 Add1
Yes
M(34+R2)
M(45+R3)
0 Add2
No
Add3
No
Name
SUBD
10 Mult1
Yes
MULTD M(45+R3)
R(F4)
0 Mult2
Yes
DIVD
M(34+R2)
Mult1
F4
F6
F8
F10
M(34+R2)
Add1
Mult2
Address
Register result status
Clock
5
FU
F0
F2
Mult1
M(45+R3)
F12
...
F30
DAP Spr.‘98 ©UCB 20
Ex: Tomasulo Ciclo 6
Instruction status
Instruction
j
k
Issue
Execution
Wri te
complete
Result
Busy
LD
F6
34+
R2
1
3
4
Load1
No
LD
F2
45+
R3
2
4
5
Load2
No
MULTDF0
F2
F4
3
Load3
No
SUBD F8
F6
F2
4
DIVD
F0
F6
5
F8
F2
6
F10
ADDD F6
Reservation Stations
Time
S1
S2
RS for j
RS for k
Busy Op
Vj
Vk
Qj
Qk
1 Add1
Yes
SUBD
M(34+R2)
M(45+R3)
0 Add2
Yes
ADDD
M(45+R3)
Name
Add3
Address
Add1
No
9 Mult1
Yes
MULTD M(45+R3)
R(F4)
0 Mult2
Yes
DIVD
M(34+R2)
Mult1
F4
F6
F8
F10
Add2
Add1
Mult2
Register result status
Clock
6
•
FU
F0
F2
Mult1
M(45+R3)
Emite ADDD
F12
...
F30
DAP Spr.‘98 ©UCB 21
Ex: Tomasulo Ciclo 7
Instruction status
Instruction
j
k
Issue
Execution
Wri te
complete
Result
Busy
LD
F6
34+
R2
1
3
4
Load1
No
LD
F2
45+
R3
2
4
5
Load2
No
MULTDF0
F2
F4
3
Load3
No
SUBD F8
F6
F2
4
DIVD
F0
F6
5
F8
F2
6
F10
ADDD F6
Reservation Stations
Time
7
S1
S2
RS for j
RS for k
Busy Op
Vj
Vk
Qj
Qk
0 Add1
Yes
SUBD
M(34+R2)
M(45+R3)
0 Add2
Yes
ADDD
M(45+R3)
Name
Add3
Address
Add1
No
8 Mult1
Yes
MULTD M(45+R3)
R(F4)
0 Mult2
Yes
DIVD
M(34+R2)
Mult1
F4
F6
F8
F10
Add2
Add1
Mult2
Register result status
Clock
7
FU
F0
F2
Mult1
M(45+R3)
F12
...
F30
• Add1 completando: quem espera pelo resultado?
DAP Spr.‘98 ©UCB 22
Ex: Tomasulo Ciclo 8
Instruction status
Instruction
j
LD
F6
34+
LD
F2
45+
MULTDF0
F2
SUBD F8
F6
DIVD F10
F0
ADDD F6
F8
Reservation Stations
Time
Name
k
R2
R3
F4
F2
F6
F2
Issue
1
2
3
4
5
6
Busy Op
Execution
complete
3
4
Wri te
Result
4
5
7
Load1
Load2
Load3
Busy
No
No
No
Address
F12
8
S1
S2
RS for j
RS for k
Vj
Vk
Qj
Qk
M()-M()
M(45+R3)
0 Add1
No
2 Add2
Yes
0 Add3
No
7 Mult1
Yes
MULTD M(45+R3)
R(F4)
0 Mult2
Register result status
Yes
DIVD
M(34+R2)
Mult1
F4
F6
F8
F10
Add2
M()-M()
Mult2
Clock
8
FU
ADDD
F0
F2
Mult1
M(45+R3)
...
F30
DAP Spr.‘98 ©UCB 23
Ex: Tomasulo Ciclo 9
Instruction status
Instruction
j
k
Issue
Execution
Wri te
complete
Result
Busy
LD
F6
34+
R2
1
3
4
Load1
No
LD
F2
45+
R3
2
4
5
Load2
No
MULTDF0
F2
F4
3
Load3
No
SUBD F8
F6
F2
4
DIVD
F0
F6
5
F8
F2
6
F10
ADDD F6
Reservation Stations
Time
Name
Busy Op
7
8
S1
S2
RS for j
RS for k
Vj
Vk
Qj
Qk
M()–M()
M(45+R3)
0 Add1
No
1 Add2
Yes
0 Add3
No
6 Mult1
Yes
MULTD M(45+R3)
R(F4)
0 Mult2
Yes
DIVD
M(34+R2)
Mult1
F4
F6
F8
F10
Add2
M()–M()
Mult2
ADDD
Address
Register result status
Clock
9
FU
F0
F2
Mult1
M(45+R3)
F12
...
F30
DAP Spr.‘98 ©UCB 24
Ex: Tomasulo Ciclo 10
Instruction status
Instruction
j
k
Issue
Execution
Wri te
complete
Result
Busy
LD
F6
34+
R2
1
3
4
Load1
No
LD
F2
45+
R3
2
4
5
Load2
No
MULTDF0
F2
F4
3
Load3
No
SUBD F8
F6
F2
4
DIVD
F0
F6
5
F8
F2
6
F10
ADDD F6
Reservation Stations
Time
Name
Busy Op
7
8
10
S1
S2
RS for j
RS for k
Vj
Vk
Qj
Qk
M()–M()
M(45+R3)
0 Add1
No
0 Add2
Yes
0 Add3
No
5 Mult1
Yes
MULTD M(45+R3)
R(F4)
0 Mult2
Yes
DIVD
M(34+R2)
Mult1
F4
F6
F8
F10
Add2
M()–M()
Mult2
ADDD
Address
Register result status
Clock
10
FU
F0
F2
Mult1
M(45+R3)
F12
...
F30
• Add2 completando: quem espera pelo resultado?
DAP Spr.‘98 ©UCB 25
Ex: Tomasulo Ciclo 11
Instruction status
Instruction
j
LD
F6
34+
LD
F2
45+
MULTDF0
F2
SUBD F8
F6
DIVD F10
F0
ADDD F6
F8
Reservation Stations
Time
Name
k
R2
R3
F4
F2
F6
F2
Issue
1
2
3
4
5
6
Busy Op
Execution
complete
3
4
Wri te
Result
4
5
7
8
10
11
Load1
Load2
Load3
S1
S2
RS for j
RS for k
Vj
Vk
Qj
Qk
Busy
No
No
No
Address
F12
0 Add1
No
0 Add2
No
0 Add3
No
4 Mult1
Yes
MULTD M(45+R3)
R(F4)
0 Mult2
Register result status
Yes
DIVD
M(34+R2)
Mult1
F4
F6
F8
F10
(M-M)+M()
M()ŠM()
Mult2
Clock
11
•
FU
F0
F2
Mult1
M(45+R3)
Escreve resultado de ADDD
...
F30
DAP Spr.‘98 ©UCB 26
Ex: Tomasulo Ciclo 12
Instruction status
Instruction
j
k
Issue
Execution
Wri te
complete
Result
Busy
LD
F6
34+
R2
1
3
4
Load1
No
LD
F2
45+
R3
2
4
5
Load2
No
MULTDF0
F2
F4
3
Load3
No
SUBD F8
F6
F2
4
DIVD
F0
F6
5
F8
F2
6
F10
ADDD F6
Reservation Stations
Time
Name
Busy Op
6
7
10
11
S1
S2
RS for j
RS for k
Vj
Vk
Qj
Qk
0 Add1
No
0 Add2
No
0 Add3
No
3 Mult1
Yes
MULTD M(45+R3)
R(F4)
0 Mult2
Yes
DIVD
M(34+R2)
Mult1
F4
F6
F8
F10
(M-M)+M()
M()–M()
Mult2
Address
Register result status
Clock
12
FU
F0
F2
Mult1
M(45+R3)
• Todas as instruções rápidas já completadas
F12
...
F30
DAP Spr.‘98 ©UCB 27
Ex: Tomasulo Ciclo 13
Instruction status
Instruction
j
k
Issue
Execution
Wri te
complete
Result
Busy
LD
F6
34+
R2
1
3
4
Load1
No
LD
F2
45+
R3
2
4
5
Load2
No
MULTDF0
F2
F4
3
Load3
No
SUBD F8
F6
F2
4
DIVD
F0
F6
5
F8
F2
6
F10
ADDD F6
Reservation Stations
Time
Name
Busy Op
0 Add1
No
0 Add2
No
Add3
No
7
8
10
11
S1
S2
RS for j
RS for k
Vj
Vk
Qj
Qk
2 Mult1
Yes
MULTD M(45+R3)
R(F4)
0 Mult2
Yes
DIVD
M(34+R2)
Mult1
F4
F6
F8
F10
(M–M)+M()
M()–M()
Mult2
Address
Register result status
Clock
13
FU
F0
F2
Mult1
M(45+R3)
F12
...
F30
DAP Spr.‘98 ©UCB 28
Ex: Tomasulo Ciclo 14
Instruction status
Instruction
j
k
Issue
Execution
Wri te
complete
Result
Busy
LD
F6
34+
R2
1
3
4
Load1
No
LD
F2
45+
R3
2
4
5
Load2
No
MULTDF0
F2
F4
3
Load3
No
SUBD F8
F6
F2
4
DIVD
F0
F6
5
F8
F2
6
F10
ADDD F6
Reservation Stations
Time
Name
Busy Op
7
8
10
11
S1
S2
RS for j
RS for k
Vj
Vk
Qj
Qk
0 Add1
No
0 Add2
No
0 Add3
No
1 Mult1
Yes
MULTD M(45+R3)
R(F4)
0 Mult2
Yes
DIVD
M(34+R2)
Mult1
F4
F6
F8
F10
(M–M)+M()
M()–M()
Mult2
Address
Register result status
Clock
14
FU
F0
F2
Mult1
M(45+R3)
F12
...
F30
DAP Spr.‘98 ©UCB 29
Ex: Tomasulo Ciclo 15
Instruction status
Execution
Instruction j
k Issue complete
LD F6 34+ R2
1
3
LD F2 45+ R3
2
4
MULTD
F0 F2
F4
3
15
SUBD
F8 F6
F2
4
7
DIVDF10 F0
F6
5
ADDD
F6 F8
F2
6
10
Reservation Stations
S1
TimeNameBusyOp
Vj
0 Add1 No
0 Add2 No
Add3 No
0 Mult1 Yes MULTD
M(45+R3)
0 Mult2 Yes DIVD
Register result status
Write
Result
4
5
Clock
F4
15
F0
F2
FU Mult1 M(45+R3)
Busy Address
Load1 No
Load2 No
Load3 No
8
11
S2
Vk
RS for j
Qj
RS for k
Qk
R(F4)
M(34+R2) Mult1
F6
F8
F10 F12 ...
F30
(M–M)+M()M()–M()Mult2
• Mult1 completando: quem espera pelo resultado?
DAP Spr.‘98 ©UCB 30
Ex: Tomasulo Ciclo 16
Instruction status
Instruction j
k Issue
LD F6 34+ R2
1
LD F2 45+ R3
2
MULTD
F0 F2
F4
3
SUBD
F8 F6
F2
4
DIVDF10 F0
F6
5
ADDD
F6 F8
F2
6
Reservation Stations
TimeNameBusyOp
0 Add1 No
0 Add2 No
Add3 No
0 Mult1 No
40 Mult2 Yes DIVD
Register result status
Execution Write
complete Result
3
4
4
5
15
16
7
8
Clock
16
F0
10
Busy Address
Load1 No
Load2 No
Load3 No
11
S1
Vj
S2
Vk
M*F4
M(34+R2)
F2
F4
FU M*F4 M(45+R3)
• Falta apenas a divisão
RS for j
Qj
RS for k
Qk
F6
F8
F10 F12 ...
F30
(M–M)+M()M()–M()Mult2
DAP Spr.‘98 ©UCB 31
Ex: Tomasulo Ciclo 55
Instruction status
Instruction
j
k
Issue
Execution
Wri te
complete
Result
Busy
LD
F6
34+
R2
1
3
4
Load1
No
LD
F2
45+
R3
2
4
5
Load2
No
MULTDF0
F2
F4
3
15
16
Load3
No
SUBD F8
F6
F2
4
7
8
DIVD
F0
F6
5
F8
F2
6
10
11
F10
ADDD F6
Reservation Stations
Time
Name
S1
S2
RS for j
RS for k
Vj
Vk
Qj
Qk
DIVD
M*F4
M(34+R2)
F0
F2
F4
F6
F8
F10
M*F4
M(45+R3)
(M–M)+M()
M()–M()
Mult2
Busy Op
0 Add1
No
0 Add2
No
Add3
No
0 Mult1
No
1 Mult2
Yes
Address
Register result status
Clock
55
FU
F12
...
F30
DAP Spr.‘98 ©UCB 32
Ex: Tomasulo Ciclo 56
Instruction status
Instruction
j
k
Issue
Execution
Wri te
complete
Result
Busy
LD
F6
34+
R2
1
3
4
Load1
No
LD
F2
45+
R3
2
4
5
Load2
No
MULTDF0
F2
F4
3
15
16
Load3
No
SUBD F8
F6
F2
4
7
8
DIVD
F0
F6
5
56
F8
F2
6
10
F10
ADDD F6
Reservation Stations
Time
Name
0 Add1
No
0 Add2
No
Add3
No
0 Mult1
No
0 Mult2
Yes
11
S1
S2
RS for j
RS for k
Vj
Vk
Qj
Qk
DIVD
M*F4
M(34+R2)
F0
F2
F4
F6
F8
F10
M*F4
M(45+R3)
(M–M)+M()
M()–M()
Mult2
Busy Op
Address
Register result status
Clock
56
FU
F12
...
F30
• Mult 2 completando: quem espera pelo resultado?
DAP Spr.‘98 ©UCB 33
Ex: Tomasulo Ciclo 57
Instruction status
Instruction
j
k
Issue
Execution
Wri te
complete
Result
Busy
LD
F6
34+
R2
1
3
4
Load1
No
LD
F2
45+
R3
2
4
5
Load2
No
MULTDF0
F2
F4
3
15
16
Load3
No
SUBD F8
F6
F2
4
7
8
DIVD
F0
F6
5
56
57
F8
F2
6
10
11
F10
ADDD F6
Reservation Stations
Time
Name
S1
S2
RS for j
RS for k
Vj
Vk
Qj
Qk
F0
F2
F4
F6
F8
F10
M*F4
M(45+R3)
(M–M)+M()
M()–M()
M*F4/M
Busy Op
0 Add1
No
0 Add2
No
Add3
No
0 Mult1
No
0 Mult2
No
Address
Register result status
Clock
57
FU
F12
...
F30
• Emissão em ordem, execução e finalização fora de
ordem
DAP Spr.‘98 ©UCB 34
Comparação com Scoreboard Ciclo 62
Instruction status
Instruction
Read
j
k
Issue
Execution Wri te
operands complete Result
LD
F6
34+
R2
1
2
3
4
LD
F2
45+
R3
5
6
7
8
MULTDF0
F2
F4
6
9
19
20
SUBD F8
F6
F2
7
9
11
12
DIVD
F0
F6
8
21
61
62
F8
F2
13
14
16
22
F10
ADDD F6
Functional unit status
Time Name
Busy
Integer
No
Mult1
No
Mult2
No
Add
No
0 Divide
No
dest
S1
S2
FU for j
FU for k
Fj?
Fk?
Op
Fi
Fj
Fk
Qj
Qk
Rj
Rk
F2
F4
F6
F8
F10
F12
...
F30
Register result status
Clock
62
F0
FU
• Porque scoreboard é mais demorado?
DAP Spr.‘98 ©UCB 35
Tomasulo v. Scoreboard
(IBM 360/91 v. CDC 6600)
(6 load, 3 store, 3 +, 2 x/÷)
(1 load/store, 1 + , 2 x, 1 ÷)
tamanho da janela: 14 instruções
5 instruções
Sem emissão no conflito estrutural
idem
WAR: por renomeação
pára a escrita
WAW: por renomeação
pára a emissão
Difunde resultados de UFs write/read de registradores
Controle: estações de reserva
scoreboard
DAP Spr.‘98 ©UCB 36
Desvantagens do Tomasulo
• Complexidade
• Muitos armazenamentos associativos (Bus de
Dados Comum) a alta velocidade
• Desempenho limitado pelo Bus de Dados
Comum
DAP Spr.‘98 ©UCB 37
Exemplo de Loop em Tomasulo
Loop: LD
MULTD
SD
SUBI
BNEZ
F0
F4
F4
R1
R1
0
F0
0
R1
Loop
R1
F2
R1
#8
• Assumir que Multiplicação leva 4 clocks
• Assumir que o primeiro load leva 8 clocks (miss no cache), o
segundo load leva 4 clocks (hit no cache) e store leva 4
clocks.
• Para ser claro, serão mostrados clocks para SUBI e BNEZ
DAP Spr.‘98 ©UCB 38
Loop Ciclo 0
Execution Wri te
Instruction status
Instruction
k
j
iterati on
Issue
complete
Busy
Result
F0
0 R1
1
Load1
No
MULTDF4
F0 F2
1
Load2
No
SD
F4
0 R1
1
Load3
No
LD
F0
0 R1
2
Store1
No
MULTDF4
F0 F2
2
Store2
No
F4
0 R1
2
Store3
No
LD
SD
Reservation Stations
Time Name
Busy Op
S1
S2
RS for j RS for k
Vj
Vk
Qj
Qk
Address
Qi
Code:
F0
0 Add1
No
LD
0 Add2
No
MULTDF4
0 Add3
No
SD
F4
0 Mult1
No
SUBI
R1
0 Mult2
No
BNEZ R1
0 R1
F0
F2
0 R1
R1
#8
Loop
Register result status
Clock
0
F0
R1
80
F2
F4
F6
F8
F10 F12 ... F30
Qi
DAP Spr.‘98 ©UCB 39
Loop Ciclo 1
Instruction status
Instruction
LD
Execution Wri te
j
k
iterati on
F0
0 R1
1
MULTDF4
F0 F2
Issue
complete
Result
1
Busy
Load1
Yes
1
Load2
No
SD
F4
0 R1
1
Load3
No
LD
F0
0 R1
2
Store1
No
MULTDF4
F0 F2
2
Store2
No
0 R1
2
Store3
No
SD
F4
Reservation Stations
Time Name
Busy Op
S1
S2
RS for j
RS for k
Vj
Vk
Qj
Qk
Address
80
Qi
Code:
0 Add1
No
LD
F0
0 Add2
No
MULTDF4
0 Add3
No
SD
F4
0 Mult1
No
SUBI
R1
0 Mult2
No
BNEZ R1
0 R1
F0
F2
0 R1
R1
#8
Loop
Register result status
Clock
1
F0
R1
80
Qi
F2
F4
F6
F8
F10 F12 ... F30
Load1
DAP Spr.‘98 ©UCB 40
Loop Ciclo 2
Instruction status
Instruction
LD
Execution Wri te
j
k
iterati on
Issue
complete
Result
Busy
F0
0 R1
1
1
Load1
Yes
MULTDF4
F0 F2
1
2
Load2
No
SD
F4
0 R1
1
Load3
No
LD
F0
0 R1
2
Store1
No
MULTDF4
F0 F2
2
Store2
No
0 R1
2
Store3
No
SD
F4
Reservation Stations
Time Name
Busy Op
S1
S2
RS for j
RS for k
Vj
Vk
Qj
Qk
Address
80
Qi
Code:
0 Add1
No
LD
0 Add2
No
MULTDF4
0 Add3
No
SD
F4
0 Mult1
Yes
SUBI
R1
0 Mult2
No
MULTD
R(F2)
Load1
F0
BNEZ R1
0 R1
F0
F2
0 R1
R1
#8
Loop
Register result status
Clock
2
F0
R1
80
Qi
F2
Load1
F4
F6
F8
F10 F12 ... F30
Mult1
DAP Spr.‘98 ©UCB 41
Loop Ciclo 3
Instruction status
Instruction
LD
Execution Wri te
j
k
iterati on
Issue
complete
Result
Busy
F0
0 R1
1
1
Load1
Yes
MULTDF4
F0 F2
1
2
Load2
No
3
Load3
No
SD
F4
0 R1
1
LD
F0
0 R1
2
Store1
Yes
MULTDF4
F0 F2
2
Store2
No
0 R1
2
Store3
No
SD
F4
Reservation Stations
Time Name
Busy Op
S1
S2
RS for j
RS for k
Vj
Vk
Qj
Qk
Address
80
Qi
80
Code:
0 Add1
No
LD
0 Add2
No
MULTDF4
0 Add3
No
SD
F4
0 Mult1
Yes
SUBI
R1
0 Mult2
No
MULTD
R(F2)
Load1
Mult1
F0
BNEZ R1
0 R1
F0
F2
0 R1
R1
#8
Loop
Register result status
Clock
3
F0
R1
80
Qi
F2
Load1
F4
F6
F8
F10 F12 ... F30
Mult1
DAP Spr.‘98 ©UCB 42
Loop Ciclo 4
Instruction status
Instruction
LD
Execution Wri te
j
k
iterati on
Issue
complete
Result
Busy
F0
0 R1
1
1
Load1
Yes
MULTDF4
F0 F2
1
2
Load2
No
3
Load3
No
SD
F4
0 R1
1
LD
F0
0 R1
2
Store1
Yes
MULTDF4
F0 F2
2
Store2
No
0 R1
2
Store3
No
SD
F4
Reservation Stations
Time Name
Busy Op
S1
S2
RS for j
RS for k
Vj
Vk
Qj
Qk
Address
80
Qi
80
Code:
0 Add1
No
LD
0 Add2
No
MULTDF4
0 Add3
No
SD
F4
0 Mult1
Yes
SUBI
R1
0 Mult2
No
MULTD
R(F2)
Load1
Mult1
F0
BNEZ R1
0 R1
F0
F2
0 R1
R1
#8
Loop
Register result status
Clock
4
F0
R1
72
Qi
Execução de SUBI
F2
Load1
F4
F6
F8
F10 F12 ... F30
Mult1
DAP Spr.‘98 ©UCB 43
Loop Ciclo 5
Instruction status
Instruction
LD
Execution Wri te
j
k
iterati on
Issue
complete
Result
Busy
F0
0 R1
1
1
Load1
Yes
MULTDF4
F0 F2
1
2
Load2
No
3
Load3
No
SD
F4
0 R1
1
LD
F0
0 R1
2
Store1
Yes
MULTDF4
F0 F2
2
Store2
No
0 R1
2
Store3
No
SD
F4
Reservation Stations
Time Name
Busy Op
S1
S2
RS for j
RS for k
Vj
Vk
Qj
Qk
Address
80
Qi
80
Code:
0 Add1
No
LD
0 Add2
No
MULTDF4
0 Add3
No
SD
F4
0 Mult1
Yes
SUBI
R1
0 Mult2
No
MULTD
R(F2)
Load1
Mult1
F0
BNEZ R1
0 R1
F0
F2
0 R1
R1
#8
Loop
Register result status
Clock
5
F0
R1
72
Qi
Execução de BNEZ
F2
Load1
F4
F6
F8
F10 F12 ... F30
Mult1
DAP Spr.‘98 ©UCB 44
Loop Ciclo 6
Instruction status
Instruction
LD
Execution Wri te
j
k
iterati on
Issue
complete
Result
Busy
Address
F0
0 R1
1
1
Load1
Yes
80
MULTDF4
F0 F2
1
2
Load2
Yes
72
SD
F4
0 R1
1
3
Load3
No
LD
F0
0 R1
2
6
Store1
Yes
MULTDF4
F0 F2
2
Store2
No
0 R1
2
Store3
No
SD
F4
Reservation Stations
Time Name
Busy Op
S1
S2
RS for j
RS for k
Vj
Vk
Qj
Qk
Qi
80
Code:
0 Add1
No
LD
0 Add2
No
MULTDF4
0 Add3
No
SD
F4
0 Mult1
Yes
SUBI
R1
0 Mult2
No
MULTD
R(F2)
Load1
Mult1
F0
BNEZ R1
0 R1
F0
F2
0 R1
R1
#8
Loop
Register result status
Clock
6
F0
R1
72
Qi
F2
Load2
F4
F6
F8
F10 F12 ... F30
Mult1
• F0 não vê resultado de Load1
DAP Spr.‘98 ©UCB 45
Loop Ciclo 7
Instruction status
Instruction
LD
Execution Wri te
j
k
iterati on
Issue
complete
Result
Busy
Address
F0
0 R1
1
1
Load1
Yes
80
MULTDF4
F0 F2
1
2
Load2
Yes
72
SD
F4
0 R1
1
3
Load3
No
LD
F0
0 R1
2
6
Store1
Yes
MULTDF4
F0 F2
2
7
Store2
No
0 R1
2
Store3
No
SD
F4
Reservation Stations
Time Name
Busy Op
S1
S2
RS for j
RS for k
Vj
Vk
Qj
Qk
Qi
80
Mult1
Code:
0 Add1
No
LD
F0
0 Add2
No
MULTDF4
0 Add3
No
SD
F4
0 Mult1
Yes
MULTD
R(F2)
Load1
SUBI
R1
0 Mult2
Yes
MULTD
R(F2)
Load2
BNEZ R1
F4
F6
0 R1
F0
F2
0 R1
R1
#8
Loop
Register result status
Clock
7
F0
R1
72
Qi
F2
Load2
F8
F10 F12 ... F30
Mult2
DAP Spr.‘98 ©UCB 46
Loop Ciclo 8
Instruction status
Instruction
LD
Execution Wri te
j
k
iterati on
Issue
complete
Result
Busy
Address
F0
0 R1
1
1
Load1
Yes
80
MULTDF4
F0 F2
1
2
Load2
Yes
72
SD
F4
0 R1
1
3
Load3
No
LD
F0
0 R1
2
6
Store1
Yes
80
Mult1
MULTDF4
F0 F2
2
7
Store2
Yes
72
Mult2
0 R1
2
8
Store3
No
SD
F4
Reservation Stations
Time Name
Busy Op
S1
S2
RS for j
RS for k
Vj
Vk
Qj
Qk
Qi
Code:
0 Add1
No
LD
F0
0 Add2
No
MULTDF4
0 Add3
No
SD
F4
0 Mult1
Yes
MULTD
R(F2)
Load1
SUBI
R1
0 Mult2
Yes
MULTD
R(F2)
Load2
BNEZ R1
F4
F6
0 R1
F0
F2
0 R1
R1
#8
Loop
Register result status
Clock
8
F0
R1
72
Qi
F2
Load2
F8
F10 F12 ... F30
Mult2
DAP Spr.‘98 ©UCB 47
Loop Ciclo 9
Instruction status
Instruction
LD
Execution Wri te
j
k
iterati on
Issue
F0
0 R1
1
1
MULTDF4
F0 F2
1
complete
Result
9
Busy
Address
Load1
Yes
80
2
Load2
Yes
72
SD
F4
0 R1
1
3
Load3
No
LD
F0
0 R1
2
6
Store1
Yes
80
Mult1
MULTDF4
F0 F2
2
7
Store2
Yes
72
Mult2
0 R1
2
8
Store3
No
SD
F4
Reservation Stations
Time Name
Busy Op
S1
S2
RS for j
RS for k
Vj
Vk
Qj
Qk
Qi
Code:
0 Add1
No
LD
F0
0 Add2
No
MULTDF4
0 Add3
No
SD
F4
0 Mult1
Yes
MULTD
R(F2)
Load1
SUBI
R1
0 Mult2
Yes
MULTD
R(F2)
Load2
BNEZ R1
F4
F6
0 R1
F0
F2
0 R1
R1
#8
Loop
Register result status
Clock
9
F0
R1
64
Qi
F2
Load2
F8
F10 F12 ... F30
Mult2
• Load1 completando: quem espera o resultado?
DAP Spr.‘98 ©UCB 48
Loop Ciclo 10
Instruction status
Instruction
LD
Execution Wri te
j
k
iterati on
Issue
F0
0 R1
1
1
MULTDF4
F0 F2
1
complete
Result
9
10
Busy
Load1
No
2
Load2
Yes
Load3
No
Store1
Yes
80
Mult1
72
Mult2
SD
F4
0 R1
1
3
LD
F0
0 R1
2
6
MULTDF4
F0 F2
2
7
Store2
Yes
0 R1
2
8
Store3
No
SD
F4
Reservation Stations
Time Name
Busy Op
Address
10
S1
S2
RS for j
RS for k
Vj
Vk
Qj
Qk
72
Qi
Code:
0 Add1
No
LD
0 Add2
No
MULTDF4
0 Add3
No
SD
F4
4 Mult1
Yes
MULTD
SUBI
R1
0 Mult2
Yes
MULTD
M(80)
R(F2)
R(F2)
Load2
F4
F6
F0
BNEZ R1
0 R1
F0
F2
0 R1
R1
#8
Loop
Register result status
Clock
R1
10
64
F0
Qi
F2
Load2
F8
F10 F12 ... F30
Mult2
• Load2 completando: quem espera o resultado?DAP Spr.‘98 ©UCB 49
Loop Ciclo 11
Instruction status
Instruction
LD
Execution Wri te
j
k
iterati on
Issue
F0
0 R1
1
1
MULTDF4
F0 F2
1
complete
Result
9
10
Busy
Load1
No
2
Load2
No
Load3
Yes
64
Qi
Store1
Yes
80
Mult1
72
Mult2
SD
F4
0 R1
1
3
LD
F0
0 R1
2
6
MULTDF4
F0 F2
2
7
Store2
Yes
0 R1
2
8
Store3
No
SD
F4
Reservation Stations
Time Name
Busy Op
Address
10
11
S1
S2
RS for j
RS for k
Vj
Vk
Qj
Qk
Code:
0 Add1
No
LD
F0
0 Add2
No
MULTDF4
0 Add3
No
SD
F4
3 Mult1
Yes
MULTD
M(80)
R(F2)
SUBI
R1
4 Mult2
Yes
MULTD
M(72)
R(F2)
BNEZ R1
F0
F2
F4
0 R1
F0
F2
0 R1
R1
#8
Loop
Register result status
Clock
R1
11
64
Qi
Load3
F6
F8
F10 F12 ... F30
Mult2
DAP Spr.‘98 ©UCB 50
Loop Ciclo 12
Instruction status
Instruction
LD
Execution Wri te
j
k
iterati on
Issue
F0
0 R1
1
1
MULTDF4
F0 F2
1
complete
Result
9
10
Busy
Load1
No
2
Load2
No
Load3
Yes
64
Qi
Store1
Yes
80
Mult1
72
Mult2
SD
F4
0 R1
1
3
LD
F0
0 R1
2
6
MULTDF4
F0 F2
2
7
Store2
Yes
0 R1
2
8
Store3
No
SD
F4
Reservation Stations
Time Name
Busy Op
Address
10
11
S1
S2
RS for j
RS for k
Vj
Vk
Qj
Qk
Code:
0 Add1
No
LD
F0
0 Add2
No
MULTDF4
0 Add3
No
SD
F4
2 Mult1
Yes
MULTD
M(80)
R(F2)
SUBI
R1
3 Mult2
Yes
MULTD
M(72)
R(F2)
BNEZ R1
F0
F2
F4
0 R1
F0
F2
0 R1
R1
#8
Loop
Register result status
Clock
R1
12
64
Qi
Load3
F6
F8
F10 F12 ... F30
Mult2
DAP Spr.‘98 ©UCB 51
Loop Ciclo 13
Instruction status
Instruction
LD
Execution Wri te
j
k
iterati on
Issue
F0
0 R1
1
1
MULTDF4
F0 F2
1
complete
Result
9
10
Busy
Load1
No
2
Load2
No
Load3
Yes
64
Qi
Store1
Yes
80
Mult1
72
Mult2
SD
F4
0 R1
1
3
LD
F0
0 R1
2
6
MULTDF4
F0 F2
2
7
Store2
Yes
0 R1
2
8
Store3
No
SD
F4
Reservation Stations
Time Name
Busy Op
Address
10
11
S1
S2
RS for j
RS for k
Vj
Vk
Qj
Qk
Code:
0 Add1
No
LD
F0
0 Add2
No
MULTDF4
0 Add3
No
SD
F4
1 Mult1
Yes
MULTD
M(80)
R(F2)
SUBI
R1
2 Mult2
Yes
MULTD
M(72)
R(F2)
BNEZ R1
F0
F2
F4
0 R1
F0
F2
0 R1
R1
#8
Loop
Register result status
Clock
R1
13
64
Qi
Load3
F6
F8
F10 F12 ... F30
Mult2
DAP Spr.‘98 ©UCB 52
Loop Ciclo 14
Instruction status
Instruction
LD
Execution Wri te
j
k
iterati on
Issue
complete
F0
0 R1
1
1
9
MULTDF4
F0 F2
1
2
14
Result
10
Busy
Load1
No
Load2
No
Load3
Yes
64
Qi
Store1
Yes
80
Mult1
72
Mult2
SD
F4
0 R1
1
3
LD
F0
0 R1
2
6
MULTDF4
F0 F2
2
7
Store2
Yes
0 R1
2
8
Store3
No
SD
F4
Reservation Stations
Time Name
Busy Op
10
11
Address
S1
S2
RS for j
RS for k
Vj
Vk
Qj
Qk
Code:
0 Add1
No
LD
F0
0 Add2
No
MULTDF4
0 Add3
No
SD
F4
0 Mult1
Yes
MULTD
M(80)
R(F2)
SUBI
R1
1 Mult2
Yes
MULTD
M(72)
R(F2)
BNEZ R1
F0
F2
F4
0 R1
F0
F2
0 R1
R1
#8
Loop
Register result status
Clock
R1
14
64
Qi
Load3
F6
F8
F10 F12 ... F30
Mult2
DAP Spr.‘98 ©UCB 53
• Mult1 completando: quem espera pelo resultado?
Loop Ciclo 15
Instruction status
Instruction
LD
Execution Wri te
j
k
iterati on
Issue
complete
Result
Busy
Address
F0
0 R1
1
1
9
10
Load1
No
MULTDF4
F0 F2
1
2
14
15
Load2
No
Load3
Yes
64
Qi
Store1
Yes
80
M(80)*R(F2)
Store2
Yes
72
Mult2
Store3
No
SD
F4
0 R1
1
3
LD
F0
0 R1
2
6
10
MULTDF4
F0 F2
2
7
15
0 R1
2
8
SD
F4
Reservation Stations
Time Name
Busy Op
11
S1
S2
RS for j
RS for k
Vj
Vk
Qj
Qk
Code:
0 Add1
No
LD
0 Add2
No
MULTDF4
0 Add3
No
SD
F4
0 Mult1
No
SUBI
R1
0 Mult2
Yes
MULTD
M(72)
R(F2)
F0
F2
F4
F0
BNEZ R1
0 R1
F0
F2
0 R1
R1
#8
Loop
Register result status
Clock
R1
15
64
Qi
Load3
F6
F8
F10 F12 ... F30
Mult2
• Mult2 completando: quem espera o resultado? DAP Spr.‘98 ©UCB 54
Loop Ciclo 16
Instruction status
Instruction
LD
Execution Wri te
j
k
iterati on
Issue
complete
Result
Busy
Address
F0
0 R1
1
1
9
10
Load1
No
MULTDF4
F0 F2
1
2
14
15
Load2
No
Load3
Yes
64
Qi
SD
F4
0 R1
1
3
LD
F0
0 R1
2
6
10
11
Store1
Yes
80
M(80)*R(F2)
MULTDF4
F0 F2
2
7
15
16
Store2
Yes
72
M(72)*R(72)
0 R1
2
8
Store3
No
SD
F4
Reservation Stations
Time Name
Busy Op
S1
S2
RS for j
RS for k
Vj
Vk
Qj
Qk
Code:
0 Add1
No
LD
0 Add2
No
MULTDF4
0 Add3
No
SD
F4
0 Mult1
Yes
SUBI
R1
0 Mult2
No
MULTD
R(F2)
Load3
F0
BNEZ R1
0 R1
F0
F2
0 R1
R1
#8
Loop
Register result status
Clock
R1
16
64
F0
Qi
F2
Load3
F4
F6
F8
F10 F12 ... F30
Mult1
DAP Spr.‘98 ©UCB 55
Loop Ciclo 17
Instruction status
Instruction
LD
Execution Wri te
j
k
iterati on
Issue
complete
Result
Busy
Address
F0
0 R1
1
1
9
10
Load1
No
MULTDF4
F0 F2
1
2
14
15
Load2
No
Load3
Yes
64
Qi
SD
F4
0 R1
1
3
LD
F0
0 R1
2
6
10
11
Store1
Yes
80
M(80)*R(F2)
MULTDF4
F0 F2
2
7
15
16
Store2
Yes
72
M(72)*R(72)
0 R1
2
8
Store3
Yes
64
Mult1
SD
F4
Reservation Stations
Time Name
Busy Op
S1
S2
RS for j
RS for k
Vj
Vk
Qj
Qk
Code:
0 Add1
No
LD
0 Add2
No
MULTDF4
0 Add3
No
SD
F4
0 Mult1
Yes
SUBI
R1
0 Mult2
No
MULTD
R(F2)
Load3
F0
BNEZ R1
0 R1
F0
F2
0 R1
R1
#8
Loop
Register result status
Clock
R1
17
64
F0
Qi
F2
Load3
F4
F6
F8
F10 F12 ... F30
Mult1
DAP Spr.‘98 ©UCB 56
Loop Ciclo 18
Instruction status
Instruction
LD
Execution Wri te
j
k
iterati on
Issue
complete
Result
Busy
Address
F0
0 R1
1
1
9
10
Load1
No
MULTDF4
F0 F2
1
2
14
15
Load2
No
Load3
Yes
64
Qi
SD
F4
0 R1
1
3
18
LD
F0
0 R1
2
6
10
11
Store1
Yes
80
M(80)*R(F2)
MULTDF4
F0 F2
2
7
15
16
Store2
Yes
72
M(72)*R(72)
0 R1
2
8
Store3
Yes
64
Mult1
SD
F4
Reservation Stations
Time Name
Busy Op
S1
S2
RS for j
RS for k
Vj
Vk
Qj
Qk
Code:
0 Add1
No
LD
0 Add2
No
MULTDF4
0 Add3
No
SD
F4
0 Mult1
Yes
SUBI
R1
0 Mult2
No
MULTD
R(F2)
Load3
F0
BNEZ R1
0 R1
F0
F2
0 R1
R1
#8
Loop
Register result status
Clock
R1
18
56
F0
Qi
F2
Load3
F4
F6
F8
F10 F12 ... F30
Mult1
DAP Spr.‘98 ©UCB 57
Loop Ciclo 19
Instruction status
Instruction
LD
Execution Wri te
j
k
iterati on
Issue
complete
Result
Busy
F0
0 R1
1
1
9
10
Load1
No
MULTDF4
F0 F2
1
2
14
15
Load2
No
SD
F4
0 R1
1
3
18
19
Load3
Yes
LD
F0
0 R1
2
6
10
11
Store1
No
MULTDF4
F0 F2
2
7
15
16
Store2
0 R1
2
8
Store3
SD
F4
Reservation Stations
Time Name
Busy Op
S1
S2
RS for j
RS for k
Vj
Vk
Qj
Qk
Address
64
Qi
Yes
72
M(72)*R(72)
Yes
64
Mult1
Code:
0 Add1
No
LD
0 Add2
No
MULTDF4
0 Add3
No
SD
F4
0 Mult1
Yes
SUBI
R1
0 Mult2
No
MULTD
R(F2)
Load3
F0
BNEZ R1
0 R1
F0
F2
0 R1
R1
#8
Loop
Register result status
Clock
R1
19
56
F0
Qi
F2
Load3
F4
F6
F8
F10 F12 ... F30
Mult1
DAP Spr.‘98 ©UCB 58
Loop Ciclo 20
Instruction status
Instruction
LD
Execution Wri te
j
k
iterati on
Issue
complete
Result
Busy
F0
0 R1
1
1
9
10
Load1
No
MULTDF4
F0 F2
1
2
14
15
Load2
No
SD
F4
0 R1
1
3
18
19
Load3
Yes
LD
F0
0 R1
2
6
10
11
Store1
No
MULTDF4
F0 F2
2
7
15
16
Store2
0 R1
2
8
20
Store3
SD
F4
Reservation Stations
Time Name
Busy Op
S1
S2
RS for j
RS for k
Vj
Vk
Qj
Qk
Address
64
Qi
Yes
72
M(72)*R(72)
Yes
64
Mult1
Code:
0 Add1
No
LD
0 Add2
No
MULTDF4
0 Add3
No
SD
F4
0 Mult1
Yes
SUBI
R1
0 Mult2
No
MULTD
R(F2)
Load3
F0
BNEZ R1
0 R1
F0
F2
0 R1
R1
#8
Loop
Register result status
Clock
R1
20
56
F0
Qi
F2
Load3
F4
F6
F8
F10 F12 ... F30
Mult1
DAP Spr.‘98 ©UCB 59
Loop Ciclo 21
Instruction status
Instruction
LD
Execution Wri te
j
k
iterati on
Issue
complete
Result
Busy
F0
0 R1
1
1
9
10
Load1
No
MULTDF4
F0 F2
1
2
14
15
Load2
No
SD
F4
0 R1
1
3
18
19
Load3
Yes
LD
F0
0 R1
2
6
10
11
Store1
No
MULTDF4
F0 F2
2
7
15
16
Store2
No
0 R1
2
8
20
21
Store3
Yes
SD
F4
Reservation Stations
Time Name
Busy Op
S1
S2
RS for j
RS for k
Vj
Vk
Qj
Qk
Address
64
Qi
64
Mult1
Code:
0 Add1
No
LD
0 Add2
No
MULTDF4
0 Add3
No
SD
F4
0 Mult1
Yes
SUBI
R1
0 Mult2
No
MULTD
R(F2)
Load3
F0
BNEZ R1
0 R1
F0
F2
0 R1
R1
#8
Loop
Register result status
Clock
R1
21
56
F0
Qi
F2
Load3
F4
F6
F8
F10 F12 ... F30
Mult1
DAP Spr.‘98 ©UCB 60
Suporte de HW para mais Paralelismo
(emissão simultânea de mais de uma instrução)
• Buffer para resultados de
instruções antes da
conclusão: reorder buffer
Contem: 3 campos: instr, destino,
valor
• pode servir de fonte de operandos:
– fornece operandos executados
porém não concluídos para RS
– É possível não concluir instruções
especulativas, como de desvios
ou de exceções
– Na conclusão das instruções, os
resultados são escritos nos
registradores
– Instruções são concluídas em ordem
DAP Spr.‘98 ©UCB 61
Quatro Passos do Algoritmo de
Tomasulo Especulativo
1. Emissão — obtem instrução da fila de instruções
Se uma RS e um slot do reorder buffer livres, emite instrução e envia
operandos para RS se disponíveis nos registradores ou no reorder buffer.
O número do slot alocado do reorder buffer também é enviado para a RS.
2. Execução— execução da operação (EX)
Se ambos os operandos estiverem prontos executa, senão aguarda pelo
CDB pelo resultado
3. Escreve o resultado — termina a execução (WB)
Escreve no Bus de Dados Comum para todas as UFs em espera e no
reorder buffer; marca a RS como disponível.
4. Conclusão—atualiza o registrador com o resultado do reorder buffer
Quando instr. no topo do reorder buffer obtem o seu resultado, atualiza
registrador com o resultado (ou armazena na memória) e remove instr do
reorder buffer. Desvios errôneos limpam o reorder buffer
DAP Spr.‘98 ©UCB 62