mc542-A-07-2s07

Prévia do material em texto

MC542
Organização de Computadores
Teoria e Prática
MC542
7.1
2007
Prof. Paulo Cesar Centoducatte
ducatte@ic.unicamp.br
www.ic.unicamp.br/~ducatte
MC542
Arquitetura de Computadores
Exceções
Micro-Arquitetura Avançadas
MC542
7.2
“DDCA” - (Capítulo 7)
“COD” - (Capítulo #)
Sumário
• Exceções
• Micro-Arquiteturas Avançadas
– Deep Pipelining
– Branch Prediction
– Superscalar Processors
– Out of Order Processors
– Register Renaming
– SIMD
– Multithreading
MC542
7.3
– Multithreading
– Multiprocessors
Exceções
• Chamada de procedimento não “prevista” para 
tratamento de uma exceção
• Causado por:
– Hardware, também chamado de interrupção (keyboard, …)
– Software, também chamado de traps (instrução indefinida, …)
• Quando uma exceção ocorre, o processador (MIPS):
MC542
7.4
• Quando uma exceção ocorre, o processador (MIPS):
– Registra a causa da exceção (Cause register)
– Salta para a rotina de tratamento da exceção no endereço 
de instrução 0x80000180
– Retorna ao programa (EPC register)
Exemplo de Exceções
MC542
7.5
Registradores de Exceção
• Não faz parte do register file.
– Cause
» Registra a causa da exceção
» Coprocessor 0 register 13
– EPC (Exception PC)
» Registra o PC onde ocorreu a exceção
MC542
7.6
» Registra o PC onde ocorreu a exceção
» Coprocessor 0 register 14
• Move from Coprocessor 0
– mfc0 $t0, EPC
– Move o conteúdo de EPC para $t0
Causa de Exceções
Exception Cause
Hardware Interrupt 0x00000000
System Call 0x00000020
Breakpoint / Divide by 0 0x00000024
MC542
7.7
Undefined Instruction 0x00000028
Arithmetic Overflow 0x00000030
Modificar o MIPS multiciclos para tratar 
as duas últimas exceções.
1. O Processador salva a causa e o PC em Cause e EPC
2. Processador desvia para o exception handler
(0x80000180)
3. Exception handler:
– Salva os registradores na pilha
– Lê o registrador Cause
mfc0 Cause, $t0
MC542
7.8
mfc0 Cause, $t0
– Trata a exceção
– Restaura os registradores
– Retorna ao programa
mfc0 EPC, $k0
jr $k0
Exceções: passos 1 e 2 
CLK
WE3
CLK
0 SrcA
RegDst BranchMemWrite MemtoReg ALUSrcARegWrite
Zero
PCSrc1:0
CLK
ALUControl2:0
WE
CLK CLK
CLK
ALUSrcB1:0IRWriteIorD PCWrite
PCEn
CLK
EN
EPCWrite
CLK
EN
CauseWrite
0
1
IntCause
0x30
0x28
EPC
Cause
1. O Processador salva a causa e o PC em Cause e EPC
2. Processador desvia para 0x80000180
MC542
7.9
SignImm
A
RD
Instr / Data
Memory
A1
A3
WD3
RD2
RD1
WE3
A2
Sign Extend
Register
File
0
1
0
1PC
0
1
PC' Instr
25:21
20:16
15:0
SrcB20:16
15:11
<<2
ALUResult
SrcA
ALUOut
Zero
A
L
U
WD
WE
Adr
0
1
Data
CLK
A
B
00
01
10
11
4
CLK
ENEN
<<2
25:0 (jump)
31:28
27:0
PCJump
00
01
10
11
0x8000 0180
Overflow
Exceções: passo 3 (mfc0)
• mfc0 $t0, Cause 
Exception handler
op 00000 $t0 (8) Cause (13) 00000000000
mfc0
MC542
7.10
31:26 25:21 20:16 15:11 10:0
Exceções: passo 3 (mfc0)
CLK
A1 RD1
WE3
CLK
0
125:21
SrcA
RegDst BranchMemWrite MemtoReg
1:0
ALUSrcARegWrite
Zero
PCSrc
1:0
CLK
ALUControl
2:0
WE
CLK CLK
A CLK
ALUSrcB
1:0
IRWriteIorD PCWrite
PCEn
31:28
CLK
EN
EPCWrite
CLK
EN
CauseWrite
0
1
IntCause
0x30
0x28
EPC
Cause
...
01101
01110
...
15:11
C0
MC542
7.11
SignImm
A
RD
Instr / Data
Memory
A1
A3
WD3
RD2
RD1
WE3
A2
Sign Extend
Register
File
0
1
1PC
0
1
PC' Instr
25:21
20:16
15:0
SrcB20:16
15:11
<<2
ALUResult ALUOut
Zero
A
L
U
WD
WE
Adr
00
01
Data
CLK
A
B
00
01
10
11
4
CLK
ENEN
<<2
25:0 (jump)
31:28
27:0
PCJump
00
01
10
11
0x8000 0180
Overflow
10
Exceções: FSM de Controle
IorD = 0
AluSrcA = 0
ALUSrcB = 01
ALUOp = 00
PCSrc = 00
IRWrite
PCWrite
ALUSrcA = 0
ALUSrcB = 11
ALUOp = 00
Reset
S0: Fetch
S2: MemAdr
S1: Decode
S6: Execute
Op = LW
or
Op = SW
Op = R-type
Op = BEQ
Op = ADDI
PCSrc = 10
PCWrite
Op = J
S11: Jump
Op = others
PCSrc = 11
PCWrite
IntCause = 1
CauseWrite
EPCWrite
S12: Undefined
RegDst = 0
Memtoreg = 10
RegWrite
Op = mfc0
S14: MFC0
MC542
7.12
ALUSrcA = 1
ALUSrcB = 10
ALUOp = 00
IorD = 1
RegDst = 1
MemtoReg = 00
RegWrite
IorD = 1
MemWrite
ALUSrcA = 1
ALUSrcB = 00
ALUOp = 10
ALUSrcA = 1
ALUSrcB = 00
ALUOp = 01
PCSrc = 01
Branch
S2: MemAdr
S3: MemRead
S5: MemWrite
S6: Execute
S7: ALU
Writeback
S8: Branch
Op = SW
Op = LW
Op = SW
RegDst = 0
MemtoReg = 01
RegWrite
S4: Mem
Writeback
ALUSrcA = 1
ALUSrcB = 10
ALUOp = 00
RegDst = 0
MemtoReg = 00
RegWrite
S9: ADDI
Execute
S10: ADDI
Writeback
Overflow Overflow
S13:
Overflow
PCSrc = 11
PCWrite
IntCause = 0
CauseWrite
EPCWrite
Micro-Arquiteturas Avançadas
• Deep Pipelining
• Branch Prediction
• Superscalar Processors
• Out of Order Processors
• Register Renaming
• SIMD
MC542
7.13
• SIMD
• Multithreading
• Multiprocessors
Deep Pipelining
• Tipicamente 10 a 20 estágios
• O Número de estágios é limitado por:
– Pipeline hazards
– Sequencing overhead
– Cost
MC542
7.14
– Cost
Branch Prediction
• Processador pepilined Ideal: CPI = 1
• Branch misprediction aumenta o CPI
• Static branch prediction:
– Avalia a direção do branch (forward ou backward)
– se backward: predict taken
MC542
7.15
– se backward: predict taken
– Caso contrário: predict not taken
• Dynamic branch prediction:
– Mantém histórico dos últimos (centenas) branches em um 
branch target buffer (Branch History Table) que mantém:
» Destino do Branch
» E se o branch foi taken
Branch Prediction: Exemplo
add $s1, $0, $0 # sum = 0
add $s0, $0, $0 # i = 0
addi $t0, $0, 10 # $t0 = 10
for:
beq $t0, $t0, done # if i == 10, branch
add $s1, $s1, $s0 # sum = sum + i
MC542
7.16
addi $s0, $s0, 1 # increment i
j for
……
done:
1-Bit Branch Predictor
• Desempenho = ƒ(precisão, custo do misprediction)
• Branch History Table: Bits menos significativos do PC 
usados como índice de uma tabela de valores de 1 bit
– Informa se o branch foi tomado ou não na última vez
– Não há comparação do endereço (menos HW, mas pode não 
ser o branch correto)
0 1 2 3 4 5 6 7 8 9 A B C D E F Branch
MC542
7.17
0 1 1 0 0 1 1 1 0 0 0 0 0 1 0 1
0 1 2 3 4 5 6 7 8 9 A B C D E F
Addi $t0, $s0, 10
Beq $t0, $t0, 0xfff00002
Add $s1, $s1, $s0
0xaaa00028
Branch
History
Table
1-Bit Branch Prediction
• Quando descobre que errou, atualiza a entrada 
correta, elimina as instruções erradas do pipeline e 
recomeça o fetch de 0xfff00002
• Problema: em um loop, 1-bit BHT irá causar 
MC542
7.18
• Problema: em um loop, 1-bit BHT irá causar 
2 mispredictions (em média nos loops – na entrada e na 
saída):
– No fim do loop quando ele termina
– Na entrada do loop quando ele preve exit no lugar de looping
– Em um loop com 10 iterações
» somente 80% de precisão 
» mesmo que os Taken sejam 90% do tempo
2-Bit Branch Predictor
• Solução: esquema com 2-bit onde só há troca na 
previsão se houver duas misprediction:
T
T
Predict Taken Predict Taken
T
NT
NT
MC542
7.19
• Vermelho: not taken
• Verde: taken
• Adicionado uma Histerese (inércia) para tomar a 
decisão
T
NT
Predict Not 
Taken
Predict Not 
TakenT
NT
NT
Branch Predictor
Vários outros esquemas:
• Correlating Branches
• Execução Predicada
• Tournament Predictors
• Branch Target Buffer (BTB)
MC542
7.20
• Branch Target Buffer (BTB)
• Return Addresses stack
Superscalar
• Múltiplas copias do datapath executando múltiplas instruções
• Dependências dificultam o despacho (Issue) de múltiplas 
instruções por vez
CLK CLK CLK CLK
CLK
MC542
7.21
A
RD A1
A2
RD1A3
WD3
WD6
A4
A5
A6
RD4
RD2
RD5
Instruction
Memory
Register
File Data
Memory
A
L
U
s
PC
A1
A2
WD1
WD2
RD1
RD2
Superscalar: Exemplo
lw $t0, 40($s0)
add $t1, $s1, $s2
sub $t2, $s1, $s3 IPC Ideal: 2
and $t3, $s3, $s4 IPC: 2
or $t4, $s1, $s5
sw $s5, 80($s0)
1 2 3 4 5 6 7 8
MC542
7.22
Time (cycles)
RF
40
$s0
RF
$t0
+
DM
IM
lw
add
lw $t0, 40($s0)add $t1, $s1, $s2
sub $t2, $s1, $s3
and $t3, $s3, $s4
or $t4, $s1, $s5
sw $s5, 80($s0)
$t1
$s2
$s1
+
RF
$s3
$s1
RF
$t2
-
DM
IM
sub
and $t3
$s4
$s3
&
RF
$s5
$s1
RF
$t4
|
DM
IM
or
sw
80
$s0
+ $s5
Superscalar Exemplo com Dependências
lw $t0, 40($s0)
add $t1, $t0, $s1
sub $t0, $s2, $s3 IPC Ideal: 2
and $t2, $s4, $t0 IPC: 6/5 = 1.17
or $t3, $s5, $s6
sw $s7, 80($t3)
Time (cycles)
1 2 3 4 5 6 7 8 9
MC542
7.23
Stall
Time (cycles)
RF
40
$s0
RF
$t0
+
DM
IM
lw
lw $t0, 40($s0)
add $t1, $t0, $s1
sub $t0, $s2, $s3
and $t2, $s4, $t0
sw $s7, 80($t3)
RF
$s1
$t0
add
RF
$s1
$t0
RF
$t1
+
DM
RF
$t0
$s4
RF
$t2
&
DM
IM
and
IM
or
and
sub
|$s6
$s5
$t3
RF
80
$t3
RF
+
DM
sw
IM
$s7
$s3
$s2
$s3
$s2
-
$t0
or
or $t3, $s5, $s6
IM
Processador Out of Order
• Avaliar múltiplas instruções para despachar o máximo
possível por vez
• Executar instruções out of order se não tem dependências
• Dependências:
– RAW (read after write): one instruction writes, and later 
MC542
7.24
– RAW (read after write): one instruction writes, and later 
instruction reads a register
– WAR (write after read): one instruction reads, and a later 
instruction writes a register (also called an antidependence)
– WAW (write after write): one instruction writes, and a later 
instruction writes a register (also called an output dependence)
• Instruction level parallelism: número de instruções que
podem ser despachadas simultaneamente
Processador Out of Order
• Instruction level parallelism: número de instruções
que podem ser despachadas simultaneamente
• Scoreboard: tabela que mantém:
– Instruções esperando para serem despachadas e 
executadas
– Unidades funcionais disponíveis
MC542
7.25
– Unidades funcionais disponíveis
– Dependências
• Tomasulo:
– Instruções esperando para serem despachadas e 
executadas
– Unidades funcionais disponíveis
– Dependências
– Register Rename
Processador Out of Order: Exemplo
lw $t0, 40($s0)
add $t1, $t0, $s1
sub $t0, $s2, $s3 IPC Ideal: 2
and $t2, $s4, $t0 IPC: 6/4 = 1.5
or $t3, $s5, $s6
sw $s7, 80($t3)
Time (cycles)
1 2 3 4 5 6 7 8
MC542
7.26
RF
40
$s0
RF
$t0
+
DM
IM
lw
lw $t0, 40($s0)
add $t1, $t0, $s1
sub $t0, $s2, $s3
and $t2, $s4, $t0
sw $s7, 80($t3)
or
|$s6
$s5
$t3
RF
80
$t3
RF
+
DM
sw $s7
or $t3, $s5, $s6
IM
RF
$s1
$t0
RF
$t1
+
DM
IM
add
sub
-$s3
$s2
$t0
two cycle latency
between load and
use of $t0
RAW
WAR
RAW
RF
$t0
$s4
RF
&
DM
and
IM
$t2
RAW
Register Renaming
1 2 3 4 5 6 7
lw $t0, 40($s0)
add $t1, $t0, $s1
sub $t0, $s2, $s3 IPC Ideal: 2
and $t2, $s4, $t0 IPC: 6/3 = 2
or $t3, $s5, $s6
sw $s7, 80($t3)
MC542
7.27
Time (cycles)
RF
40
$s0
RF
$t0
+
DM
IM
lw
lw $t0, 40($s0)
add $t1, $t0, $s1
sub $r0, $s2, $s3
and $t2, $s4, $r0
sw $s7, 80($t3)
sub
-$s3
$s2
$r0
RF
$r0
$s4
RF
&
DM
and
$s7
or $t3, $s5, $s6
IM
RF
$s1
$t0
RF
$t1
+
DM
IM
add
sw
+80
$t3
RAW
$s6
$s5
|
or
2-cycle RAW
RAW
$t2
$t3
Algoritmo de Tomasulo
Exemplo
• Foco: Unidades de ponto-flutuante e load-store
• Cada estágio pode ter um número arbitrário de ciclos
• Múltiplas unidades funcionais
MC542
7.28
• Múltiplas unidades funcionais
• Diferentes instruções possuem tempos diferentes no
estágio EX
• Unidades disponíveis: load-store; mult e adder
Scheduling Dinâmico
Implementação - MIPS
IF ID MEM WB
EX
Inteira
M1 M2 M3 M4 M5 M6 M7
MC542
7.29
IF ID MEM WB
A1 A2 A3
DIV
A4
Estrutura Básica de uma Implementação do 
Algoritmo de Tomasulo (para o MIPS)
From Mem FP RegistersFP Op
Queue
Load Buffers
Store 
Buffers
Load1
Load2
Load3
Load4
Load5
Load6
MC542
7.30
FP addersFP adders
Add1
Add2
Add3
FP multipliersFP multipliers
Mult1
Mult2
Reservation 
Stations
Common Data Bus (CDB)
To Mem
Buffers
Reservation Station
Busy Op Vj Vk Qj Qk A
0/1
Load/Store
Imediato/Endereço Efetivo
MC542
7.31
Valores a serem calculados
0 – já foi calculado ou não usado
Valores já conhecidos
Operação
0/1
OBS.: Register File
Qi = N0. RS
OBS.: Terminologia do Screboard
Do CDC (ver apêndice A)
Reservation Station
Op: Operação a ser executada na unidade (e.g., + or –)
Vj, Vk: Valores dos operantos Fontes
– Store buffers tem campos V, resultados devem ser 
armazenados 
Qj, Qk: Reservation Stations produzirá os operandos 
correspondentes (valores a serem escritos)
– Qj,Qk = 0 => ready
– Store buffers tem somente Qi para RS producing result
MC542
7.32
– Store buffers tem somente Qi para RS producing result
Busy: Indica que a Reservation Station e sua FU estão 
ocupadas
A: Mantém informação sobre o end. de memória 
calculado para load ou store 
Register result status (campo Qi no register file) — Indica 
para cada registrador a unidade funcional (reservation 
station) que irá escreve-lo. Em branco se não há 
instruções pendentes que escreve no registrador. 
3 estágios do algoritmo de Tomasulo
1. Issue— pega a instrução na “FP Op Queue”
Se a reservation station está livre (não há hazard 
estrutural), 
issues instr & envia operandos (renames registers)
2.Execute —executa a operação sobre os operandos (EX)
MC542
7.33
2.Execute —executa a operação sobre os operandos (EX)
Se os dois operandos estão prontos executa a 
operação;
Se não, monitora o Common Data Bus (espera pelo 
cálculo do 
operando, essa espera resolve RAW)
(quando um operando está pronto -> reservation 
table)
3.Write result — termina a execução (WB)
3 estágios do algoritmo de Tomasulo
• data bus normal: dado + destino (“go to” bus)
• Common data bus: dado + source (“come from” bus)
– 64 bits de dados + 4 bits para endereço da 
Functional Unit 
MC542
7.34
Functional Unit 
– Escreve se há casamento com a Functional Unit 
(produz resultado)
– broadcast
SIMD
• Single Instruction Multiple Data (SIMD)
– Uma única instrução aplicada a múltiplos (pedaços de) 
dados 
– Aplicação Comum: computação gráfica
– Executa operações aritméticas curtas (também 
denominadas de packed arithmetic)
• Exemplo, quatro add de elementos de 8-bit
• ALU deve ser modificada para eliminar os carries entre 
os valores de 8-bit
MC542
7.35
• ALU deve ser modificada para eliminar os carries entre 
os valores de 8-bit
padd8 $s2, $s0, $s1
a0
0781516232432 Bit position
$s0a1a2a3
b0 $s1b1b2b3
a0 + b0 $s2a1 + b1a2 + b2a3 + b3
+
Técnicas Avançadas
• Multithreading
– Wordprocessor: thread para typing, spell checking, printing
MC542
7.36
• Multiprocessors
– Múltiplos processadores (cores) em um único chip
Multithreading: Algumas Definições
• Processo: programa executando em um computador
• Múltiplos processos podem estar em execução ao mesmo 
tempo: navegando na Web, ouvindo musica, escrevendo um 
artigo etc
• Thread: parte de um programa
• Cada processo possue múltiplas threads: em processador de 
texto tem threads para typing, spell checking, printing …
• Em um computador convencional:
MC542
7.37
• Em um computador convencional:
– Uma thread está em execução por vez
– Quando uma thread para (por exemplo, devido a um page fault):
» O estado da thread é guardado (registradores, ….)
» O estado da thread em espera é carregado no processador 
e inicia-se sua execução
» Chamado de context switching
– Para o usuário parece que todas as threads executam 
simultaneamente (existem outras condições que provocam 
mudança da thread em execução: acesso a disco, time-out, …)
Multithreading
• Múltiplas cópias de status da arquitetura (uma por thread)
• Múltiplas threads activas por vez:
– Quando uma thread para, outra inicia sua execução imediatamente 
(não é necessário armazenar e restaurar o status)
– Se uma thread não tem todas as unidades de execução necessárias, 
MC542
7.38
– Se uma thread não tem todas as unidades de execução necessárias, 
outra thread pode ser executada
• Não aumenta o ILP de uma única of thread, porém aumenta o 
throughput 
Multiprocessors
• Multiple processors (cores) com alguma forma de comunicação 
entre eles• Tipos de multiprocessamento:
– Symmetric multiprocessing (SMT): múltiplos cores com 
memória compartilhada
MC542
7.39
– Asymmetric multiprocessing: cores separados para diferentes 
tarefas (por examplo, DSP e CPU em um telefone celular)
– Clusters: cada core possue seu próprio sistema de memória
Outras Fontes para Leitura
• Patterson & Hennessy’s: Computer Architecture: A 
Quantitative Approach 3ª e 4ª Edições
• Conferências:
– www.cs.wisc.edu/~arch/www/
– ISCA (International Symposium on Computer Architecture)
MC542
7.40
– ISCA (International Symposium on Computer Architecture)
– HPCA (International Symposium on High Performance 
Computer Architecture)