Pipeline

Pipeline

Lab. FICAn03.Sapt03

2/38

Motto:

3/38

Saga lui Pip Eline

• Pip Eline VS Vrăjitoarea– Dacă Pip reuşeşte să facă clătitele mai repede

decât vrăjitoarea, primeşte calul năzdrăvan

4/38

Cum lucrează vrăjitoarea?

Timpul

Colectat ingredientele

Făcut aluatul

Încălzit tigaia

Turnat aluatul

Întors clătita

Scos clătita

Încălzit tigaia

Turnat aluatul

Întors clătitaScos clătita

5/38

Cum lucrează Pip Eline?

Timpul


Făcut aluatul

Încălzit tigaia 1Turnat aluatul în tigaia 1

Încălzit tigaia 2

Întors clătita din tigaia 1Turnat aluatul în tigaia 2

Încălzit tigaia 3

Scos clătita din tigaia 1Întors clătita din tigaia 2Turnat aluatul în tigaia 3

Încălzit tigaia 4

Scos clătita din tigaia 3Întors clătita din tigaia 4Turnat aluatul în tigaia 1Încălzit tigaia 2


6/38

Cum ştim cine a câştigat?

• Timpul total– Timpul necesar până la terminarea apariţiei

tuturor ieşirilor

• Latenţa = L– Latency – Timpul necesar ca o intrare să apară la ieşire

• Capacitatea de trecere = T– Throughput– #outputs / time

7/38

Pentru a obţine N clătite

• Vrăjitoarea– Timp total = timp ingrediente + timp aluat +

N*(t încălzit + t turnat + t întors + t scos)– Excluzând timpul pentru ingrediente şi aluat

• L= t încălzit + t turnat + t întors + t scos• T = 1 / L

• Pip Eline– Timp total = timp ingrediente + timp aluat +

N/4*(t încălzit + t turnat + t întors + t scos)– Excluzând timpul pentru ingrediente şi aluat

• L = max (t încălzit, t turnat, t întors, t scos) * 4• T = 1 / L

8/38

Răsplata lui Pip.Eline

9/38

Limitări al metodei pipeline

• Există porţiuni

NEPARALELIZABILE

Timpul


Făcut aluatul

Încălzit tigaia 1Turnat aluatul în tigaia 1

Încălzit tigaia 2

Întors clătita din tigaia 1Turnat aluatul în tigaia 2

Încălzit tigaia 3

Scos clătita din tigaia 1Întors clătita din tigaia 2Turnat aluatul în tigaia 3

Încălzit tigaia 4


10/38

De analizat: speed-up şi cost

A

C

B

16 km

44 km

11/38

Speed-up & cost

A B C

4km/h

0 $

10km/h

10 $

50 km/h

40 $

250 km/h

150$

Timp Speed-up Cost

15h 1 0

8.4h 1.786 10

5.14h 2.92 40

4.176h 3.59 150

12/38

Legea lui Amdhal

13/38

Şi acum... Înapoi la circuite...

14/38

Unpipelined VS pipelined in combinational logic

Unpipelined• L of the circuit =

longest path from the input to the output

• T is 1 output / L

Pipelined • registers in-between

• Ideal registers • zero contamination and

propagation delay• zero setup and hold time

• register’s clock cycle = propagation delay of the slowest block.

15/38

Making a pipeline - rules of thumb

1. Put two dots on opposite sides of the circuit. Draw lines from one dot to another

2. Always put a register on the output

3. Isolate the slowest block with registers. Make this block the slowest stage for maximum throughput

4. Never cross a path twice with the same line. This helps ensure that each path has the same number of registers

5. Add a register every time a line crosses a wire.

• Sursa: A Student’s Guide to the Digital World by Margaret Chong

16/38

Exemplu

• Any configuration is valid as long as there are an equal number of registers on each path from input to output.

• Sursa: A Student’s Guide to the Digital World by Margaret Chong

17/38

MIPS

18/38

MIPS - pipeline

19/38

ALU instructions - schema

20/38

ALU instructions – schema + tabelul IF/ID.IR ← Mem[PC]; IF/ID.NPC,PC ← (if ((EX/MEM.opcode == branch) & EX/MEM.cond){EX/MEM.ALUOutput} else {PC+4});

ID/EX.A ← Regs[IF/ID.IR[rs]]; ID/EX.B ← Regs[IF/ID.IR[rt]];ID/EX.IR ← IF/ID.IR;

EX/MEM.IR ← ID/EX.IR;EX/MEM.ALUOutput←ID/EX.A func ID/EX.B;orEX/MEM.ALUOutput ←ID/EX.A op ID/EX.Imm;EX/MEM.cond ← 0;

MEM/WB.IR ← EX/MEM.IR;MEM/WB.ALUOutput ←EX/MEM.ALUOutput;

Regs[MEM/WB.IR[rd]] ←MEM/WB.ALUOutput;orRegs[MEM/WB.IR[rt]] ←MEM/WB.ALUOutput;

21/38

Load - schema

22/38

Load – schema + tabelul IF/ID.IR ← Mem[PC]; IF/ID.NPC,PC ← (if ((EX/MEM.opcode == branch) & EX/MEM.cond){EX/MEM.ALUOutput} else {PC+4});

ID/EX.A ← Regs[IF/ID.IR[rs]]; ID/EX.Imm ← sign extend(IF/ID.IR[immediate field]);ID/EX.IR ← IF/ID.IR;

EX/MEM.IR← ID/EX.IREX/MEM.ALUOutput ←ID/EX.A + ID/EX.Imm;EX/MEM.cond ← 0;

MEM/WB.IR ← EX/MEM.IR;MEM/WB.LMD ←Mem[EX/MEM.ALUOutput];

Regs[MEM/WB.IR[rt]] ←MEM/WB.LMD;

23/38

Store - schema

24/38

Store – schema + tabelul IF/ID.IR ← Mem[PC]; IF/ID.NPC,PC ← (if ((EX/MEM.opcode == branch) & EX/MEM.cond){EX/MEM.ALUOutput} else {PC+4});

ID/EX.A ← Regs[IF/ID.IR[rs]]; ID/EX.B ← Regs[IF/ID.IR[rt]];ID/EX.Imm ← sign extend(IF/ID.IR[immediate field]);ID/EX.IR ← IF/ID.IR;

EX/MEM.IR← ID/EX.IREX/MEM.ALUOutput ←ID/EX.A + ID/EX.Imm;EX/MEM.cond ← 0;EX/MEM.B← ID/EX.B;

MEM/WB.IR ← EX/MEM.IR;Mem[EX/MEM.ALUOutput] ←EX/MEM.B;

25/38

Branch - schema

NPC

26/38

Branch – schema + tabelul IF/ID.IR ← Mem[PC]; IF/ID.NPC,PC ← (if ((EX/MEM.opcode == branch) & EX/MEM.cond){EX/MEM.ALUOutput} else {PC+4});

ID/EX.A ← Regs[IF/ID.IR[rs]]; ID/EX.NPC ← IF/ID.NPCID/EX.Imm ← sign extend(IF/ID.IR[immediate field]);ID/EX.IR ← IF/ID.IR;

EX/MEM.ALUOutput ←ID/EX.NPC+ID/EX.Imm;EX/MEM.cond ←(ID/EX.A == 0);

NPC

27/38

And that’s MIPS pipeline schematics in a nutshell!

28/38

Moduri de notatie

• O instructiune:

• sau

• Mai multe instructiuni

29/38

Let’s complicate things!

30/38

Moduri de tratare branch-uri -1/5

• De ce e necesar?– Pentru ca branch-ul se intoarce cu adresa CORECTA de

start abia dupa ciclul de EX

31/38

Moduri de tratare branch-uri -2/5• Freeze & flush

1 2 3 4 5 6 7 8

Branch IF ID EX MEM WB

Next instruction

STALL STALL IF ID EX MEM WB

32/38


• Predict as untaken

cc1 cc2 cc3 cc4 cc5 cc6 cc7

Branch instruction

IF ID EX MEM WB

IF

next

instruction

Stall ID EX MEM WB If not taken

IF

branch

target

ID EX MEM If taken

33/38


• Predict as taken

cc1 cc2 cc3 cc4 cc5 cc6 cc7

Branch instruction

IF ID EX MEM WB

IF

branch

target

Stall ID EX MEM WB If taken

IF next

instruction

ID EX MEM If not taken

34/38


• Delayslot

35/38

Tricks & treats – 1/3

36/38


• Forwarding

37/38


• Bypassing

S.D F8, -8(R1)

38/38

Congratulations! You’ve made it!

Pipeline

Documents

Transcript of Pipeline