MC542 Organização de Computadores Teoria e Prática

MC542 4.1

2007

Prof. Paulo Cesar Centoducatte

[email protected]

www.ic.unicamp.br/~ducatte

MC542

Organização de ComputadoresTeoria e Prática

MC542 4.2

MC542

Arquitetura de Computadores

Micro-Arquitetura Pipeline

“DDCA” - (Capítulo 7)

“COD” - (Capítulo )

MC542 4.3

Micro-Arquitetura Pipeline Sumário

• Introdução– Execução Pepiline

• MIPS Pepilinig– 5 estágios– MIPS Pipelined– Execução de Instruções no MIPS Pipeline– DataPath Single-Cycle e Pipelining– Controle do Pepiline

• Limites de Pipelining– Hazards

» Estrutura» Dado» Controle

• Como Tratar os Hazards de Dados

MC542 4.4

Pipelining - Conceito

• Exemplo: Lavanderia

• 4 trouxas para serem lavadas

– Lavar: 30 minutos

– Secar: 40 minutos

– Passar: 20 minutos

A B C D

MC542 4.5

Lavanderia Seqüencial

• Lavanderia seqüencial: 6 horas para lavar 4 trouxas• Se for usado pipelining, quanto tempo?

A

B

C

D

30 40 2030 40 2030 40 2030 40 20

6 7 8 9 10 11 Horas

Ordem

Tarefas

Tempo

MC542 4.6

Lavanderia Pipelined

• Lavanderia Pipelined: 3.5 horas para 4 trouxas

A

B

C

D

6 7 8 9 10 11 Horas

Tempo

30 40 40 40 40 20

Ordem

Tarefas

MC542 4.7

Pipelining

• O Pipelining não ajuda na latência de uma tarefa, ajuda no throughput de toda a carga de trabalho

• O período do Pipeline é limitado pelo estágio mais lento

• Múltiplas tarefas simultâneas

• Speedup potencial = Número de estágios

• Estágios não balanceados reduzem o speedup

• O Tempo de “preenchimento” e de “esvaziamento“ reduzem o speedup

A

B

C

D

6 7 8 9

Task

Order

Time

30 40 40 40 40 20

MC542 4.8

CPU Pipeline

• Executam bilhões de instruções: throughput

• Características desejáveis em um conjunto de instruções (ISA) para pipelining?

– Instruções de tamanho variável vs. Todas instruções do mesmo tamanho?

–Operandos em memória em qq operação vs. operandos em memória somente para loads e stores?

–Formato das instruções irregular vs. formato regular das instruções (ié. Operandos nos mesmos lugares)?

MC542 4.9

Um RISC Típico

• Formato de instruções de 32-bit (3 formatos)

• Acesso à memória somente via instruções load/store

• 32 GPR de 32-bits (R0 contém zero)• Instruções aritméticas: 3-address, reg-reg,

registradores no mesmo lugar• Modo de endereçamento simples para

load/store (base + displacement)

– Sem indireção

• Condições simples para o branch• Delayed branch SPARC, MIPS, HP PA-Risc, DEC Alpha, IBM PowerPC,

CDC 6600, CDC 7600, Cray-1, Cray-2, Cray-3

MC542 4.10

Exemplo: MIPS (Localização dos regs)

Op

31 26 01516202125

Rs1 Rd immediate

Op

31 26 025

Op

31 26 01516202125

Rs1 Rs2

target

Rd Opx

Register-Register

561011

Register-Immediate

Op

31 26 01516202125

Rs1 Rs2 immediate

Branch

Jump / Call

MC542 4.11

Processador MIPS Pipelined

• Paralelismo Temporal

• Divide o processador single-cycle em 5 estágios:

– Fetch– Decode– Execute– Memory– Writeback

• Adicinar registradores de pipeline entre os estágios

MC542 4.12


Time (ps)Instr

FetchInstruction

DecodeRead Reg

ExecuteALU

MemoryRead / Write

WriteReg

1

2

0 100 200 300 400 500 600 700 800 900 1100 1200 1300 1400 1500 1600 1700 1800 19001000

Instr

1

2

3

FetchInstruction

DecodeRead Reg

ExecuteALU

MemoryRead / Write

WriteReg

FetchInstruction

DecodeRead Reg

ExecuteALU

MemoryRead/Write

WriteReg

FetchInstruction

DecodeRead Reg

ExecuteALU

MemoryRead/Write

WriteReg

FetchInstruction

DecodeRead Reg

ExecuteALU

MemoryRead/Write

WriteReg

Single-Cycle

Pipelined

MC542 4.13


SignImm

CLK

A RD

InstructionMemory

+

4

A1

A3

WD3

RD2

RD1WE3

A2

CLK

Sign Extend

RegisterFile

0

1

0

1

A RD

DataMemory

WD

WE0

1

PC0

1PC' Instr

25:21

20:16

15:0

5:0

SrcB

20:16

15:11

<<2

+

ALUResult ReadData

WriteData

SrcA

PCPlus4

PCBranch

WriteReg4:0

Result

31:26

RegDst

Branch

MemWrite

MemtoReg

ALUSrc

RegWrite

Op

Funct

ControlUnit

Zero

PCSrc

CLK

ALUControl2:0

AL

U0

1

25:0 <<2

27:0 31:28

PCJump

Jump

MIPS single-cycle

MC542 4.14


MemoryAccess

Write

Back

InstructionFetch

Instr. DecodeReg. Fetch

ExecuteAddr. Calc

LMD

ALU

MU

X

Mem

ory

Reg File

MU

XM

UX

Data

Mem

ory

MU

X

SignExtend

4

Ad

der Zero?

Next SEQ PC

Addre

ss

Next PC

WB Data

Inst

RD

RS1

RS2

Imm

MC542 4.15


• Abstração da execução Pipeline

Time (cycles)

lw $s2, 40($0) RF 40

$0RF

$s2+ DM

RF $t2

$t1RF

$s3+ DM

RF $s5

$s1RF

$s4- DM

RF $t6

$t5RF

$s5& DM

RF 20

$s1RF

$s6+ DM

RF $t4

$t3RF

$s7| DM

add $s3, $t1, $t2

sub $s4, $s1, $s5

and $s5, $t5, $t6

sw $s6, 20($s1)

or $s7, $t3, $t4

1 2 3 4 5 6 7 8 9 10

add

IM

IM

IM

IM

IM

IM lw

sub

and

sw

or

MC542 4.16


• DataPath Single-Cycle e Pipelining

SignImmE

CLK

A RD

InstructionMemory

+

4

A1

A3

WD3

RD2

RD1WE3

A2

CLK

Sign Extend

RegisterFile

0

1

0

1

A RD

DataMemory

WD

WE0

1

PCF0

1

PC' InstrD25:21

20:16

15:0

SrcBE

20:16

15:11

RtE

RdE

<<2+

ALUOutM

ALUOutW

ReadDataW

WriteDataE WriteDataM

SrcAE

PCPlus4D

PCBranchM

ResultW

PCPlus4EPCPlus4F

ZeroM

CLK CLK

AL

U

WriteRegE4:0

CLK

CLK

CLK

SignImm

CLK

A RD

InstructionMemory

+

4

A1

A3

WD3

RD2

RD1WE3

A2

CLK

Sign Extend

RegisterFile

0

1

0

1

A RD

DataMemory

WD

WE0

1

PC0

1PC' Instr

25:21

20:16

15:0

SrcB

20:16

15:11

<<2

+

ALUResult ReadData

WriteData

SrcA

PCPlus4

PCBranch

WriteReg4:0

Result

Zero

CLK

AL

U

Fetch Decode Execute Memory Writeback

MC542 4.17


MemoryAccess

Write

Back

InstructionFetch


ExecuteAddr. Calc

ALU

Mem

ory

Reg File

MU

XM

UX

Data

Mem

ory

MU

X

SignExtend

Zero?

IF/ID

ID/E

X

MEM

/WB

EX

/MEM

4

Ad

der

Next SEQ PC Next SEQ PC

RD RD RD WB

Data

Next PC

Addre

ss

RS1

RS2

Imm

MU

X

MC542 4.18


SignImmE

CLK

A RD

InstructionMemory

+

4

A1

A3

WD3

RD2

RD1WE3

A2

CLK

Sign Extend

RegisterFile

0

1

0

1

A RD

DataMemory

WD

WE0

1

PCF0

1

PC' InstrD25:21

20:16

15:0

SrcBE

20:16

15:11

RtE

RdE

<<2

+

ALUOutM

ALUOutW

ReadDataW


SrcAE

PCPlus4D

PCBranchM

WriteRegM4:0

ResultW

PCPlus4EPCPlus4F

ZeroM

CLK CLK

WriteRegW4:0

AL

U

WriteRegE4:0

CLK

CLK

CLK

Fetch Decode Execute Memory Writeback

MC542 4.19


• Controle do Pepiline

SignImmE

CLK

A RD

InstructionMemory

+

4

A1

A3

WD3

RD2

RD1WE3

A2

CLK

Sign Extend

RegisterFile

0

1

0

1

A RD

DataMemory

WD

WE0

1

PCF0

1PC' InstrD

25:21

20:16

15:0

5:0

SrcBE

20:16

15:11

RtE

RdE

<<2

+

ALUOutM

ALUOutW

ReadDataW


SrcAE

PCPlus4D

PCBranchM

WriteRegM4:0

ResultW

PCPlus4EPCPlus4F

31:26

RegDstD

BranchD

MemWriteD

MemtoRegD

ALUControlD

ALUSrcD

RegWriteD

Op

Funct

ControlUnit

ZeroM

PCSrcM

CLK CLK CLK

CLK CLK

WriteRegW4:0

ALUControlE2:0

AL

U

RegWriteE RegWriteM RegWriteW

MemtoRegE MemtoRegM MemtoRegW

MemWriteE MemWriteM

BranchE BranchM

RegDstE

ALUSrcE

WriteRegE4:0

MC542 4.20

Limites de Pipelining

• Hazards: impedem que a próxima instrução seja executada no ciclo de clock “previsto” para ela

– Structural hazards: O HW não suporta uma dada combinação de instruções

– Data hazards: Uma Instrução depende do resultado da instrução anterior que ainda está no pipeline

– Control hazards: Causado pelo delay entre o fetching de uma instrução e a decisão sobre a mudança do fluxo de execução (branches e jumps).

MC542 4.21

Memória Única (D/I) - Structural Hazards

Instr.

Order

Time (clock cycles)

Load

Instr 1

Instr 2

Instr 3

Instr 4

Reg

ALU

DMemIfetch Reg

Reg

ALU

DMemIfetch Reg

Reg

ALU

DMemIfetch Reg

Reg

ALU

DMemIfetch Reg

Cycle 1Cycle 2 Cycle 3Cycle 4 Cycle 6Cycle 7Cycle 5

Reg

ALU

DMemIfetch Reg

MC542 4.22

Memória Única (D/I) - Structural Hazards

Instr.

Order

Time (clock cycles)

Load

Instr 1

Instr 2

Stall

Instr 3

Reg

ALU

DMemIfetch Reg

Reg

ALU

DMemIfetch Reg

Reg

ALU

DMemIfetch Reg

Cycle 1Cycle 2 Cycle 3Cycle 4 Cycle 6Cycle 7Cycle 5

Reg

ALU

DMemIfetch Reg

Bubble Bubble Bubble BubbleBubble

MC542 4.23

• Read After Write (RAW)

InstrJ lê o operando antes da InstrI escreve-lo

– Causada por uma “Dependência” (nomenclatura de compiladores).

Data Hazards

I: add r1,r2,r3J: sub r4,r1,r3

MC542 4.24

Instr.

Order

add r1,r2,r3

sub r4,r1,r3

and r6,r1,r7

or r8,r1,r9

xor r10,r1,r11

Reg

ALU

DMemIfetch Reg

Reg

ALU

DMemIfetch Reg

Reg

ALU

DMemIfetch Reg

Reg

ALU

DMemIfetch Reg

Reg

ALU

DMemIfetch Reg

Data Hazard em R1

Time (clock cycles)

IF ID/RF EX MEM WB

MC542 4.25

• Write After Read (WAR) InstrJ escreve o operando antes que a InstrI o leia

• Chamada “anti-dependência” (nomenclatura de compiladores). Devido ao reuso do nome “r1”.

• Não ocorre no pipeline do MIPS:

– Todas instruções usam 5 estágios, e– Leituras são no estágio 2, e– Escritas são no estágio 5

I: sub r4,r1,r3 J: add r1,r2,r3K: mul r6,r1,r7

Data Hazards

MC542 4.26

Data Hazards

• Write After Write (WAW) InstrJ escreve o operando antes que a InstrI o escreva.

• Chamada “dependência de saída” (nomenclatura de compiladores). Devido ao reuso do nome “r1”.

• Não ocorre no pipeline do MIPS:

– Todas Instruções são de 5 estágios, e– Escritas são sempre no 5 estágio – (WAR e WAW ocorrem em pipelines mais sofisticados)

I: sub r1,r4,r3 J: add r1,r2,r3K: mul r6,r1,r7

MC542 4.27

Como Tratar os Data Hazards

• Inserir instruções nops no código

• Rearranjar o código em tempo de compilação

• Stall o processador em tempo de execução (run-time)

• Forward data

MC542 4.28

Data Hazards – Solução por SW

• Compilador reconhece o data hazard e troca a ordem

das instruções (quando possível)

• Compilador reconhece o data hazard e adiciona nops

Exemplo:

sub R2, R1, R3 ; reg R2 escrito por sub

nop ; no operation

nop

and R12, R2, R5 ; resultado do sub disponível

or R13, R6, R2

add R14, R2, R2

sw 100 (R2), R15

MC542 4.29

Data Hazard Control: Stalls

• Hazard ocorre quando a instr. Lê (no estágio ID) um reg que será escrito, por uma instr. anterior (no estágio EX, MEM, WB)

• Solução: Detectar o hazard e parar a instrução no pipeline até o hazard ser resolvido

• Detectar o hazard pela comparação do campo read no IF/ID pipeline register com o campo write dos outros pipeline registers (ID/EX, EX/MEM, MEM/WB)

• Adicionar bubble no pipeline– Preservar o PC e o IF/ID pipeline register

MC542 4.30


• Data Forwarding

Time (cycles)

add $s0, $s2, $s3 RF $s3

$s2RF

$s0+ DM

RF $s1

$s0RF

$t0& DM

RF $s0

$s4RF

$t1| DM

RF $s5

$s0RF

$t2- DM

and $t0, $s0, $s1

or $t1, $s4, $s0

sub $t2, $s0, $s5

1 2 3 4 5 6 7 8

and

IM

IM

IM

IMadd

or

sub

MC542 4.31


• Data Forwarding

Time (cycles)

add $s0, $s2, $s3 RF $s3

$s2RF

$s0+ DM

RF $s1

$s0RF

$t0& DM

RF $s0

$s4RF

$t1| DM

RF $s5

$s0RF

$t2- DM

and $t0, $s0, $s1

or $t1, $s4, $s0

sub $t2, $s0, $s5

1 2 3 4 5 6 7 8

and

IM

IM

IM

IMadd

or

sub

MC542 4.32


• HW para forwarding

MEM

/WR

ID/E

X

EX

/MEM

DataMemory

ALU

mux

mux

Registe

rs

NextPC

Immediate

mux

MC542 4.33


• HW para forwarding

SignImmE

CLK

A RD

InstructionMemory

+

4

A1

A3

WD3

RD2

RD1WE3

A2

CLK

SignExtend

RegisterFile

0

1

0

1

A RD

DataMemory

WD

WE

1

0

PCF0

1PC' InstrD

25:21

20:16

15:0

5:0

SrcBE

25:21

15:11

RsE

RdE

<<2

+

ALUOutM

ALUOutW

ReadDataW


SrcAE

PCPlus4D

PCBranchM

WriteRegM4:0

ResultW

PCPlus4F

31:26

RegDstD

BranchD

MemWriteD

MemtoRegD

ALUControlD2:0

ALUSrcD

RegWriteD

Op

Funct

ControlUnit

PCSrcM

CLK CLK CLK

CLK CLK

WriteRegW4:0

ALUControlE2:0

AL

U



MemWriteE MemWriteM

RegDstE

ALUSrcE

WriteRegE4:0

000110

000110

SignImmD

For

wa

rdA

E

For

wa

rdB

E

20:16RtE

RsD

RdD

RtD

Reg

Wri

teM

Reg

Wri

teW

Hazard Unit

PCPlus4E

BranchE BranchM

ZeroM

MC542 4.34


• Forward para o estágio Execute a partir de:– Memory stage ou– Writeback stage

• Lógica de Forwarding para ForwardAE:

if ((rsE != 0) AND (rsE == WriteRegM) AND RegWriteM) then ForwardAE = 10else if ((rsE != 0) AND (rsE == WriteRegW) AND RegWriteW) then ForwardAE = 01else ForwardAE = 00

• Lógica de Forwarding para ForwardBE similar, trocando rsE com rtE, e ForwardAE com ForwardBE

MC542 4.35


• Data Hazard com Forwarding

Time (clock cycles)

Instr.

Order

lw r1, 0(r2)

sub r4,r1,r6

and r6,r1,r7

or r8,r1,r9

Reg

ALU

DMemIfetch Reg

Reg

ALU

DMemIfetch Reg

Reg ALU

DMemIfetch Reg

Reg

ALU

DMemIfetch Reg

MC542 4.36


• Data Hazard com Forwarding

Time (clock cycles)

or r8,r1,r9

Instr.

Order

lw r1, 0(r2)

sub r4,r1,r6

and r6,r1,r7

Reg

ALU

DMemIfetch Reg

RegIfetch

ALU

DMem RegBubble

Ifetch

ALU

DMem RegBubble Reg

Ifetch

ALU

DMemBubble Reg

MC542 4.37


• Hardware para Stall

SignImmE

CLK

A RD

InstructionMemory

+

4

A1

A3

WD3

RD2

RD1WE3

A2

CLK

SignExtend

RegisterFile

0

1

0

1

A RD

DataMemory

WD

WE

1

0

PCF0

1PC' InstrD

25:21

20:16

15:0

5:0

SrcBE

25:21

15:11

RsE

RdE

<<2

+

ALUOutM

ALUOutW

ReadDataW


SrcAE

PCPlus4D

PCBranchM

WriteRegM4:0

ResultW

PCPlus4F

31:26

RegDstD

BranchD

MemWriteD

MemtoRegD

ALUControlD2:0

ALUSrcD

RegWriteD

Op

Funct

ControlUnit

PCSrcM

CLK CLK CLK

CLK CLK

WriteRegW4:0

ALUControlE2:0

ALU



MemWriteE MemWriteM

RegDstE

ALUSrcE

WriteRegE4:0

000110

000110

SignImmD

Sta

llF

Sta

llD

For

war

dAE

For

war

dBE

20:16RtE

RsD

RdD

RtD

Reg

Writ

eM

Reg

Writ

eW

Mem

toR

egE

Hazard Unit

Flu

shE

PCPlus4E

BranchE BranchM

ZeroM

EN

EN

CLR

MC542 4.38


• Lógica para Stall:

lwstall = ((rsD == rtE) OR (rtD == rtE)) AND MemtoRegE

StallF = StallD = FlushE = lwstall

MC542 4.39


• Load Hazards - Software Scheduling

Código para (a, b, c, d ,e, f na memória).

a = b + c;

d = e – f;

Slow_code:

LW Rb,b

LW Rc,c

ADD Ra,Rb,Rc

SW a,Ra

LW Re,e

LW Rf,f

SUB Rd,Re,Rf

SW d,Rd

Fast_code:LW Rb,bLW Rc,cLW Re,e ADD Ra,Rb,RcLW Rf,fSW a,Ra SUB Rd,Re,RfSW d,Rd

MC542 4.40


Control Hazard• beq: o branch não é determinado até o 4 estágio do

pipeline• Definições:

– Branch delay slot(s): Instruções buscadas antes do branch ser determinado

– Misprediction penalty: número de instruções flushed quando o branch é taken

• Várias estratégias são usadas para lidar com control hazards:

– Stall o pipeline– Rearranjar o código e por instruções “úteis” no(s) branch

delay slot(s)– Reduzir o misprediction penalty (determinar o branch mais

cedo no pipeline)– Flush pipeline quando o branch é taken

MC542 4.41


10: beq r1,r3,36

14: and r2,r3,r5

18: or r6,r1,r7

22: add r8,r1,r9

36: xor r10,r1,r11

Reg ALU

DMemIfetch Reg

Reg ALU

DMemIfetch Reg

Reg ALU

DMemIfetch Reg

Reg

ALU

DMemIfetch Reg

Reg ALU

DMemIfetch Reg

MC542 4.42


MemoryAccess

Write

Back

InstructionFetch


ExecuteAddr. Calc

ALU

Mem

ory

Reg File

MU

XM

UX

Data

Mem

ory

MU

X

SignExtend

Zero?

IF/ID

ID/E

X

MEM

/WB

EX

/MEM

4

Ad

der

Next SEQ PC Next SEQ PC

RD RD RD WB

Data

Next PC

Addre

ss

RS1

RS2

Imm

MU

X

MC542 4.43


Exemplo: Impacto do Branch Stall no Desempenho

• Se CPI = 1, 30% branches, 3-cycle stall

CPI = 1.9!

• Solução para minimizar os efeitos:

– Determinar branch taken ou não o mais cedo, e– Calcular o endereço alvo do branch logo

• MIPS branch: testa se regs = ou

• Solução MIPS:– Zero test no estágio ID/RF– Adder para calcular o novo PC no estágio ID/RF– 1 clock cycle penalty por branch versus 3

MC542 4.44


Ad

der

IF/ID

MemoryAccess

Write

Back

InstructionFetch


ExecuteAddr. Calc

ALU

Mem

ory

Reg File

MU

X

Data

Mem

ory

MU

X

SignExtend

=

MEM

/WB

EX

/MEM

4

Ad

der

Next SEQ PC

RD RD RD WB

Data

Next PC

Addre

ss

RS1

RS2

ImmM

UX

ID/E

X

MC542 4.45


EqualD

SignImmE

CLK

A RD

InstructionMemory

+

4

A1

A3

WD3

RD2

RD1WE3

A2

CLK

SignExtend

RegisterFile

0

1

0

1

A RD

DataMemory

WD

WE

1

0

PCF0

1PC' InstrD

25:21

20:16

15:0

5:0

SrcBE

25:21

15:11

RsE

RdE

<<2

+

ALUOutM

ALUOutW

ReadDataW


SrcAE

PCPlus4D

PCBranchD

WriteRegM4:0

ResultW

PCPlus4F

31:26

RegDstD

BranchD

MemWriteD

MemtoRegD

ALUControlD2:0

ALUSrcD

RegWriteD

Op

Funct

ControlUnit

PCSrcD

CLK CLK CLK

CLK CLK

WriteRegW4:0

ALUControlE2:0

ALU



MemWriteE MemWriteM

RegDstE

ALUSrcE

WriteRegE4:0

000110

000110

=

SignImmD

Sta

llF

Sta

llD

For

war

dAE

For

war

dBE

20:16RtE

RsD

RdE

RtD

Reg

Writ

eM

Reg

Writ

eW

Mem

toR

egE

Hazard Unit

Flu

shE

EN

EN

CLR

CLR

MC542 4.46


Time (cycles)

beq $t1, $t2, 40 RF $t2

$t1RF- DM

RF $s1

$s0RF& DMand $t0, $s0, $s1

or $t1, $s4, $s0

sub $t2, $s0, $s5

1 2 3 4 5 6 7 8

andIM

IMlw20

24

28

2C

30

...

...

9

Flushthis

instruction

64 slt $t3, $s2, $s3 RF $s3

$s2RF

$t3slt DMIM

slt

MC542 4.47


Alternativas para Branch Hazard

#1: Stall até a decisão se o branch será tomado ou não

#2: Predict Branch Not Taken– Executar a próxima instrução – “Invalidar” as instruções no pipeline se branch é tamado– Vantagem: retarda a atualização do pipeline– 47% dos branches no MIPS não são tomados, em média– PC+4 já está computado, use-o para pegar a próxima

instrução

#3: Predict Branch Taken– 53% dos branches do MIPS são tomados, em média– “branch target address” no MIPS ainda não foi calculado

» 1 cycle branch penalty» Em outras máquinas esse penalty pode não ocorrer

MC542 4.48


Alternativas para Branch Hazard

#4: Delayed Branch– Define-se que o branch será tamado APÓS a uma

dada quantidade de instruções

branch instructionsequential successor1

sequential successor2

........sequential successorn

branch target if taken

– 1 slot delay permite a decisão e o calculo do “branch target address” no pipeline de 5 estágios

– MIPS usa está solução

Branch delay de tamanho n (n delay slots)

MC542 4.49


Delayed Branch

• Qual instrução usar para preencher o branch delay slot?

– Antes do branch

– Do target address ( avaliada somente se branch taken)

– Após ao branch (somente avaliada se branch not taken)

MC542 4.50


MC542 4.51


• Compilador: single branch delay slot:

– Preenche +/- 60% dos branch delay slots

– +/- 80% das instruções executadas no branch delay slots são utéis à computação

– +/- 50% (60% x 80%) dos slots preenchidos são utéis

MC542 4.52

Processador MIPS PipelinedTratando data e control hazards

EqualD

SignImmE

CLK

A RD

InstructionMemory

+

4

A1

A3

WD3

RD2

RD1WE3

A2

CLK

SignExtend

RegisterFile

0

1

0

1

A RD

DataMemory

WD

WE

1

0

PCF0

1PC' InstrD

25:21

20:16

15:0

5:0

SrcBE

25:21

15:11

RsE

RdE

<<2

+

ALUOutM

ALUOutW

ReadDataW


SrcAE

PCPlus4D

PCBranchD

WriteRegM4:0

ResultW

PCPlus4F

31:26

RegDstD

BranchD

MemWriteD

MemtoRegD

ALUControlD2:0

ALUSrcD

RegWriteD

Op

Funct

ControlUnit

PCSrcD

CLK CLK CLK

CLK CLK

WriteRegW4:0

ALUControlE2:0

AL

U



MemWriteE MemWriteM

RegDstE

ALUSrcE

WriteRegE4:0

000110

000110

0

1

0

1

=

SignImmD

Sta

llF

Sta

llD

For

wa

rdA

E

For

wa

rdB

E

For

wa

rdA

D

For

wa

rdB

D

20:16RtE

RsD

RdD

RtD

Reg

Wri

teE

Reg

Wri

teM

Reg

Wri

teW

Me

mto

Reg

E

Bra

nch

D

Hazard Unit

Flu

shE

EN

EN

CL

R

CL

R

MC542 4.53


Control Forwarding e Stalling Hardware

• Lógica de Forwarding:ForwardAD = (rsD !=0) AND (rsD == WriteRegM) AND RegWriteMForwardBD = (rtD !=0) AND (rtD == WriteRegM) AND RegWriteM

• Lógica de Stalling:branchstall = BranchD AND RegWriteE AND (WriteRegE == rsD

OR WriteRegE == rtD) OR BranchD AND MemtoRegM AND (WriteRegM ==

rsD OR WriteRegM == rtD)

StallF = StallD = FlushE = lwstall OR branchstall

MC542 4.54


Desempenho do MIPS PipelinedIdeal: CPI = 1, IPC = 1

Porém devido aos stall (causados por loads e branches)

SPECINT2000 benchmark: 25% loads10% stores 11% branches2% jumps52% R-type

Suponha que:40% dos loads são usados pela próxima instrução25% dos branches são mispredicted

Qual o CPI médio?Average CPI = (0.25)(1.4) + (0.1)(1) + (0.11)(1.25) + (0.02)

(2) + (0.52)(1) = 1.15

MC542 4.55


Desempenho do MIPS Pipelined

• Pipelined processor critical path: Tc = max {

tpcq + tmem + tsetup

2(tRFread + tmux + teq + tAND + tmux + tsetup )

tpcq + tmux + tmux + tALU + tsetup

tpcq + tmemwrite + tsetup

2(tpcq + tmux + tRFwrite) }

MC542 4.56


Exemplo de DesempenhoElement Parameter Delay (ps)

Register clock-to-Q tpcq_PC30

Register setup tsetup20

Multiplexer tmux25

ALU tALU200

Memory read tmem250

Register file read tRFread150

Register file setup tRFsetup20

Equality comparator teq40

AND gate tAND15

Memory write Tmemwrite220

Register file write tRFwrite100 ps

Tc = 2(tRFread + tmux + teq + tAND + tmux + tsetup )

= 2[150 + 25 + 40 + 15 + 25 + 20] ps = 550 ps

MC542 4.57


Exemplo de Desempenho

• Para um programa que executa 100 bilhões de instruções em um processaddor MIPs pipelined,

• CPI = 1.15

• Tc = 550 ps

Execution Time = (# instructions) × CPI × Tc

= (100 × 109)(1.15)(550 × 10-12)

= 63 seconds

MC542 4.58


Exemplo de Desempenho

Processor

Execution Time(seconds)

Speedup(single-cycle is baseline)

Single-cycle

95 1

Multicycle 133 0.71

Pipelined 63 1.51

Documents

MC542 Organização de Computadores Teoria e Prática