Bài giảng Kiến trúc máy tính - Chương 4.2: Thiết kế bộ xử lý đường ống (Pipelined Processor Design)

Nội dung text: Bài giảng Kiến trúc máy tính - Chương 4.2: Thiết kế bộ xử lý đường ống (Pipelined Processor Design)

1. dce 2017 Chapter 4.2 Thiết kế bộ xử lý đường ống (Pipelined Processor Design) Computer Architecture – Chapter 4.2 ©Fall 2017, CSE 2
2. dce 2017 Ví dụ cơ chế đường ống  Dịch vụ giặt đồ: 3 bước 1. Giặt 2. Sấy 3. Gấp  Mỗi bước thực hiện trong 30 phút A B  Có 4 mẻ C D Computer Architecture – Chapter 4.2 ©Fall 2017, CSE 4
3. dce 2017 Áp dụng cơ chế đường ống 6 PM 7 8 9 PM 30 30 30 30 30 30 Time 30 30 30 30 30 30 A  Cần 3 tiếng cho 4 mẻ  Hiệu quả hơn 2 lần cho B 4 mẻ C  Thời gian xử lý một mẻ không đổi (90 phút) D Computer Architecture – Chapter 4.2 ©Fall 2017, CSE 6
4. dce 2017 Bộ xử lý MIPS theo cơ chế Pipeline  Gồm 5 công đoạn, mỗi công đoạn là một chu kỳ 1. IF: Instruction Fetch (nạp lệnh) 2. ID: Instruction Decode (giải mã lệnh) 3. EX: Execute (thực thi phép toán) 4. MEM: Memory access (truy xuất bộ nhớ dữ liệu) 5. WB: Write Back (ghi kết quả vào thanh ghi đích) Computer Architecture – Chapter 4.2 ©Fall 2017, CSE 8
5. dce 2017 So sánh (tiếp theo)  Tp = max(200, 150) = 200 ps IF Reg ALU MEM Reg 200 IF Reg ALU MEM Reg 200 IF Reg ALU MEM Reg 200 200 200 200 200  CPI cho bộ xử lý pipeline = 1  Xét trường hợp số lượng lệnh lớn  Speedup của bộ xử lý pipeline = 900 ps / 200 ps = 4.5  IC và CPI bằng nhau cho cả hai trường hợp  Speedup nhỏ hơn 5 (số công đoạn)  Do thời gian các công đoạn không cân bằng Computer Architecture – Chapter 4.2 ©Fall 2017, CSE 10
6. dce 2017 Datapath đơn chu kỳ  Hình bên dưới là datapath của bộ xử lý đơn chu kỳ  Thay đổi datapath như thế nào để trở thành pipelined? Trả lời: Thêm thanh ghi vào cuối những công đoạn IF = Instruction Fetch ID = Decode & EX = Execute MEM = Memory WB = Register Read Access Write Jump or Branch Target Address Back J Next Beq PC 30 Bne ALU result Imm26 Imm16 PCSrc +1 zero 32 Instruction Rs 5 Data Memory RA BusA 30 Memory 0 32 A 32 32 00 Registers Instruction Rt 5 L Address 0 32 RB BusB 0 U 1 Address 0 32 Data_out 1 PC Rd RW Data_in 1 BusW E 1 32 RegDst Reg clk Write Mem Mem Mem ExtOp ALUSrc ALUCtrl Read Write toReg Computer Architecture – Chapter 4.2 ©Fall 2017, CSE 12
7. dce 2017 Vấn đề với thanh ghi đích (RW)  Có vấn đề với địa chỉ thanh ghi đích?  Các giá trị RA, RB, RW trong công đoạn ID khác với công đoạn WB  Địa chỉ thanh ghi đích RW khi WB không phải là giá trị đúng cần ghi vào ID = Decode & IF = Instruction Fetch Register Read EX = Execute MEM = Memory Access NPC2 Next PC +1 Imm26 Back WBWrite = NPC ALU result 32 Imm Imm16 zero Instruction 32 Data Memory Rs 5 BusA A A Memory RA L 0 Instruction Address Rt 5 ALUout 32 0 RB E 1 U Data_out 1 Address BusB WBData Instruction 0 B 0 32 1 PC RW Data_in Register File Register 1 BusW 32 D Rd 32 clk Computer Architecture – Chapter 4.2 ©Fall 2017, CSE 14
8. dce 2017 Giảng đồ thực thi lệnh theo đường ống  Diễn tả quá trình thực thi lệnh theo chu kỳ xung nhịp  Lệnh được liệt kê theo thứ tự từ trên xuống  Xung nhịp theo thứ tự từ trái qua phải  Mô tả chi tiết công đoạn của từng lệnh, tài nguyên sử dụng theo chu kỳ xung nhịp Time (in cycles) CC1 CC2 CC3 CC4 CC5 CC6 CC7 CC8 lw $t6, 8($s5) IM Reg ALU DM Reg add $s1, $s2, $s3 IM Reg ALU DM Reg ori $s4, $t3, 7 IM Reg ALU DM Reg sub $t5, $s2, $t3 IM Reg ALU DM Reg Program Execution Order sw $s2, 10($t3) IM Reg ALU DM Computer Architecture – Chapter 4.2 ©Fall 2017, CSE 16
9. dce 2017 Tín hiệu điều khiển IF ID EX MEM WB J Next NPC2 Beq PC +1 Imm26 Bne NPC ALU result 32 Imm Imm16 zero PCSrc Instruction 32 Data Memory Rs 5 BusA A A Memory RA L 0 Instruction Address Rt 5 ALUout 32 0 RB E 1 U Data_out 1 Address BusB WBData Instruction Rd B 0 32 1 PC RW Data_in Register File Register BusW 32 D 32 0 Rd4 Rd3 1 Rd2 clk Reg Reg Ext ALU ALU Mem Mem Mem Dst Write Op Src Ctrl Read Write toReg Các tín hiệu điều khiển giống như bộ xử lý đơn chu kỳ Computer Architecture – Chapter 4.2 ©Fall 2017, CSE 18
10. dce 2017 Tiếp theo  Thực thi theo kiểu đường ống so với tuần tự  Datapath & Control theo kiểu đường ống  Rủi ro (Hazard) trong hiện thực đường ống  Rủi ro về dữ liệu và phương pháp xúc tiến sớm  Chờ trong lệnh “Load”, phát hiện rủi ro và khựng  Rủi ro về điều khiển Computer Architecture – Chapter 4.2 ©Fall 2017, CSE 20
11. dce 2017 Rủi ro về mặt điều khiển  Vấn đề  Tranh chấp sử dụng một khối chức năng bởi hai lệnh khác nhau vào cùng một chu kỳ xung nhịp  Ví dụ Structural Hazard  Ghi lại kết quả ALU trong công đoạn 4 Hai lệnh cùng ghi kết quả vào thanh  Đụng độ với ghi kết quả ô nhớ trong bộ thanh ghi công đoạn 5 lw $t6, 8($s5) IF ID EX MEM WB ori $t4, $s3, 7 IF ID EX WB sub $t5, $s2, $s3 IF ID EX WB Instructions sw $s2, 10($s3) IF ID EX MEM CC1 CC2 CC3 CC4 CC5 CC6 CC7 CC8 CC9 Time Computer Architecture – Chapter 4.2 ©Fall 2017, CSE 22
12. dce 2017 Rủi ro về mặt dữ liệu  Phụ thuộc dữ liệu giữa các lệnh tạo ra rủi ro loại này  Các lệnh phụ thuộc dữ liệu nằm kề với nhau  Read After Write – Rủi ro RAW  Cho 2 lệnh I và J, với I được thực thi trước lệnh J  Lệnh J cần (đọc) toán hạn được ghi bởi lệnh I  Gọi là một phụ thuộc dữ liệu I: add $s1, $s2, $s3 # $s1 is written J: sub $s4, $s1, $s3 # $s1 is read  Rủi ro xảy ra khi lệnh J đọc toán hạn $s1 trước khi lệnh I cập nhật lại giá trị mới nhất Computer Architecture – Chapter 4.2 ©Fall 2017, CSE 24
13. dce 2017 Giải pháp 1: Khựng quá trình pipeline Time (in cycles) CC1 CC2 CC3 CC4 CC5 CC6 CC7 CC8 CC9 value of $s2 10 10 10 10 10 20 20 20 20 sub $s2, $t1, $t3 IM Reg ALU DM Reg add $s4, $s2, $t5 IM Reg Reg Reg Reg ALU DM Reg stall stall stall Instruction Order or $s6, $t3, $s2 IM Reg ALU DM  Khựng (stall) 3 chu kỳ từ CC3 đến CC5  Các chu kỳ khựng làm trễ quá trình thực thi của lênh add & và quá trịnh nạp lệnh của lênh or  Lệnh add không thể đọc $s2 cho đến đầu chu kỳ CC6  Lệnh add giữ nguyên mã lệnh cho đến chu kỳ CC6  Thanh ghi PC không thay đổi cho đến đầu chu kỳ CC6 Computer Architecture – Chapter 4.2 ©Fall 2017, CSE 26
14. dce 2017 Hiện thực xúc tiến sớm (forwarding)  Thêm vào 2 bộ hợp kênh (mux) 4 ngõ vào cho thanh ghi A & B  Dữ liệu từ công đoạn ALU, MEM, và WB được nối ngược lại  Các tín hiệu điều khiển: ForwardA và ForwardB để điều khiển forwarding ForwardA Imm26 Imm16 Im26 32 32 ALU result 0 A Rs BusA 1 A Address RA 2 L U Result Rt 3 E 1 Data 0 RB BusB 0 Memory 0 32 1 32 32 Data_out 1 WData Register File Register Instruction B RW D BusW 2 Data_in 3 32 0 Rd2 Rd4 1 Rd3 Rd clk ForwardB Computer Architecture – Chapter 4.2 ©Fall 2017, CSE 28
15. dce 2017 Forwarding Example Instruction sequence: When sub instruction is fetched lw $t4, 4($t0) ori will be in the ALU stage ori $t7, $t1, 2 lw will be in the MEM stage sub $t3, $t4, $t7 ForwardA = 2 from MEM stage ForwardB = 1 from ALU stage sub $t3,$t4,$t7 ori $t7,$t1,2 lw $t4,4($t0) Imm26 Imm16 2 ext Imm 32 32 ALU result 0 A Rs BusA 1 A Address RA 2 L Rt 3 1 U Result Data 0 RB BusB 0 Memory 0 32 1 32 32 Data_out 1 WData Register File Register Instruction B RW D BusW 2 Data_in 3 32 0 Rd2 Rd3 1 Rd4 Rd 1 clk Computer Architecture – Chapter 4.2 ©Fall 2017, CSE 30
16. dce 2017 Hazard Detect and Forward Logic Imm26 Im26 E 32 32 ALU result 0 A Rs BusA 1 A Address RA 2 L Rt 3 1 U Result Data 0 RB BusB 0 Memory 0 32 Rd 1 32 32 Data_out 1 WData Register File Register B RW D Instruction BusW 2 Data_in 3 ALUCtrl 32 0 Rd2 Rd3 1 Rd4 clk RegDst ForwardB ForwardA Hazard Detect and Forward func RegWrite RegWrite RegWrite Op Main & ALU EX Control MEM WB Computer Architecture – Chapter 4.2 ©Fall 2017, CSE 32
17. dce 2017 Load Delay  Unfortunately, not all data hazards can be forwarded  Load has a delay that cannot be eliminated by forwarding  In the example shown below  The LW instruction does not read data until end of CC4  Cannot forward data to ADD at end of CC3 - NOT possible Time (cycles) CC1 CC2 CC3 CC4 CC5 CC6 CC7 CC8 However, load can lw $s2, 20($t1) IF Reg ALU DM Reg forward data to 2nd next and later add $s4, $s2, $t5 IF Reg ALU DM Reg instructions or $t6, $t3, $s2 IF Reg ALU DM Reg Program Program Order and $t7, $s2, $t4 IF Reg ALU DM Reg Computer Architecture – Chapter 4.2 ©Fall 2017, CSE 34
18. dce 2017 Stall the Pipeline for one Cycle  ADD instruction depends on LW stall at CC3  Allow Load instruction in ALU stage to proceed  Freeze PC and Instruction registers (NO instruction is fetched)  Introduce a bubble into the ALU stage (bubble is a NO-OP)  Load can forward data to next instruction after delaying it Time (cycles) CC1 CC2 CC3 CC4 CC5 CC6 CC7 CC8 lw $s2, 20($s1) IM Reg ALU DM Reg add $s4, $s2, $t5 IM stall bubble bubble bubble Reg ALU DM Reg Program Program Order or $t6, $s3, $s2 IM Reg ALU DM Reg Computer Architecture – Chapter 4.2 ©Fall 2017, CSE 36
19. dce 2017 Hazard Detect, Forward, and Stall Imm26 Im26 E 32 32 ALU result 0 A Rs BusA 1 A Address RA 2 L Rt 3 1 U Result Data 0 RB BusB 0 Memory PC 0 32 Rd 1 32 32 Data_out 1 WData Register File Register B RW D Instruction BusW 2 Data_in 3 32 0 Rd2 Rd3 1 Rd4 clk RegDst ForwardB ForwardA func Hazard Detect Disable PC Disable Forward, & Stall MemRead Stall RegWrite RegWrite Op Control Signals RegWrite Main & ALU 0 Control Bubble 1 EX = 0 MEM WB Computer Architecture – Chapter 4.2 ©Fall 2017, CSE 38
20. dce 2017 Name Dependence: Write After Read  Instruction J should write its result after it is read by I  Called anti-dependence by compiler writers I: sub $t4, $t1, $t3 # $t1 is read J: add $t1, $t2, $t3 # $t1 is written  Results from reuse of the name $t1  NOT a data hazard in the 5-stage pipeline because:  Reads are always in stage 2  Writes are always in stage 5, and  Instructions are processed in order  Anti-dependence can be eliminated by renaming  Use a different destination register for add (eg, $t5) Computer Architecture – Chapter 4.2 ©Fall 2017, CSE 40
21. dce 2017 Tiếp theo  Thực thi theo kiểu đường ống so với tuần tự  Datapath & Control theo kiểu đường ống  Rủi ro (Hazard) trong hiện thực đường ống  Rủi ro về dữ liệu và phương pháp xúc tiến sớm  Chờ trong lệnh “Load”, phát hiện rủi ro và khựng  Rủi ro về điều khiển Computer Architecture – Chapter 4.2 ©Fall 2017, CSE 42
22. dce 2017 2-Cycle Branch Delay  Control logic detects a Branch instruction in the 2nd Stage  ALU computes the Branch outcome in the 3rd Stage  Next1 and Next2 instructions will be fetched anyway  Convert Next1 and Next2 into bubbles if branch is taken cc1 cc2 cc3 cc4 cc5 cc6 cc7 Beq $t1,$t2,L1 IF Reg ALU Next1 IF Reg Bubble Bubble Bubble Next2 IF Bubble Bubble Bubble Bubble Branch L1: target instruction Target IF Reg ALU DM Addr Computer Architecture – Chapter 4.2 ©Fall 2017, CSE 44
23. dce 2017 Predict Branch NOT Taken  Branches can be predicted to be NOT taken  If branch outcome is NOT taken then  Next1 and Next2 instructions can be executed  Do not convert Next1 & Next2 into bubbles  No wasted cycles cc1 cc2 cc3 cc4 cc5 cc6 cc7 Beq $t1,$t2,L1 IF Reg ALU NOT Taken Next1 IF Reg ALU DM Reg Next2 IF Reg ALU DM Reg Computer Architecture – Chapter 4.2 ©Fall 2017, CSE 46
24. dce 2017 Reducing Branch Delay to 1 Cycle Longer Cycle Zero = +1 Next J Data forwarded PC Beq Bne then compared Reset Imm16 Im16 0 PCSrc 32 Instruction 1 Memory Rs 5 BusA A A RA 2 L Instruction 3 Rt 5 ALUout 0 BusB E 1 U Jump or Branch Target Branch or Jump RB Instruction 0 Address Rd 0 1 PC RW 1 Register File Register B BusW D Op 2 32 3 32 0 Rd3 1 Rd2 clk func Reg Reset signal converts Dst J, Beq, Bne next instruction after ALUCtrl Control Signals jump or taken branch Main & ALU 0 Control into a bubble Bubble = 0 1 EX MEM Computer Architecture – Chapter 4.2 ©Fall 2017, CSE 48