Bài giảng Kiến trúc máy tính - Chương 4: Bộ xử lý lộ trình dữ liệu - điều khiển - Nguyễn Thanh Sơn
Tóm tắt Bài giảng Kiến trúc máy tính - Chương 4: Bộ xử lý lộ trình dữ liệu - điều khiển - Nguyễn Thanh Sơn: ... TP.HCM Rủi ro dữ liệu khi dùng Load 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 42 Forwarding không phải lúc nào cũng giải quyết sự “khựng lại” trong ống Nếu cần kết quả là lệnh truy xuất bộ nhớ cho lệnh kế Không thể lùi lại! BK TP.HCM Khắc phục 25-Aug-16 Khoa Khoa học ...tiến sớm BK TP.HCM Điều kiện xúc tiến sớm xét lại 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 75 MEM hazard if (MEM/WB.RegWrite and (MEM/WB.RegisterRd ≠ 0) and not (EX/MEM.RegWrite and (EX/MEM.RegisterRd ≠ 0) and (EX/MEM.RegisterRd = ID/EX.RegisterRs)) and (MEM/WB.RegisterRd.../ghi EPC Chuyển điều khiển ch/trình xử lý tràn Tương tự cho việc rẽ nhánh với địa chỉ tiên đoán: sử dụng lại phần cứng BK TP.HCM Cơ chế ống với ngoại lệ 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 100 BK TP.HCM Exception Properties 25-Aug-16 Faculty of Computer Science & En...
Rt 2a. MEM/WB.RegisterRd = ID/EX.RegisterRs 2b. MEM/WB.RegisterRd = ID/EX.RegisterRt Xúc tiến sớm từ th/ghi EX/MEM Xúc tiến sớm từ th/ghi MEM/WB BK TP.HCM Phát hiện yêu cầu Forward (tt.) 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 71 Nhưng chỉ với trường hợp lệnh cần xúc tiến sớm có ghi ra thanh ghi, đó là EX/MEM.RegWrite, MEM/WB.RegWrite Và thanh ghi Rd không phải là th/ghi $zero EX/MEM.RegisterRd ≠ 0, MEM/WB.RegisterRd ≠ 0 BK TP.HCM Lộ trình xúc tiến sớm 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 72 BK TP.HCM Các điều kiện xúc tiến sớm 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 73 EX hazard if (EX/MEM.RegWrite and (EX/MEM.RegisterRd ≠ 0) and (EX/MEM.RegisterRd = ID/EX.RegisterRs)) ForwardA = 10 if (EX/MEM.RegWrite and (EX/MEM.RegisterRd ≠ 0) and (EX/MEM.RegisterRd = ID/EX.RegisterRt)) ForwardB = 10 MEM hazard if (MEM/WB.RegWrite and (MEM/WB.RegisterRd ≠ 0) and (MEM/WB.RegisterRd = ID/EX.RegisterRs)) ForwardA = 01 if (MEM/WB.RegWrite and (MEM/WB.RegisterRd ≠ 0) and (MEM/WB.RegisterRd = ID/EX.RegisterRt)) ForwardB = 01 BK TP.HCM Rủi ro dữ liệu đúp 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 74 Quan sát 3 lệnh dưới đây (Cộng dồn các phần tử của 1 dãy – Vector): add $1,$1,$2 add $1,$1,$3 add $1,$1,$4 Xảy ra 2 loại Hazards: Ex và MEM Dùng kết quả mới nhất của $1 Xét lại điều kiện để xúc tiến sớm BK TP.HCM Điều kiện xúc tiến sớm xét lại 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 75 MEM hazard if (MEM/WB.RegWrite and (MEM/WB.RegisterRd ≠ 0) and not (EX/MEM.RegWrite and (EX/MEM.RegisterRd ≠ 0) and (EX/MEM.RegisterRd = ID/EX.RegisterRs)) and (MEM/WB.RegisterRd = ID/EX.RegisterRs)) ForwardA = 01 if (MEM/WB.RegWrite and (MEM/WB.RegisterRd ≠ 0) and not (EX/MEM.RegWrite and (EX/MEM.RegisterRd ≠ 0) and (EX/MEM.RegisterRd = ID/EX.RegisterRt)) and (MEM/WB.RegisterRd = ID/EX.RegisterRt)) ForwardB = 01 BK TP.HCM Lộ trình với Forwarding 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 76 BK TP.HCM Rủi ro dữ liệu với lệnh Load 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 77 Phải “khựng lại” 1 bước BK TP.HCM Phát hiện rủi ro do lệnh Load 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 78 Kiểm tra lệnh trong giai đoạn giải mã (ID) Thanh ghi toán hạng của lệnh (inputs of ALU): IF/ID.RegisterRs, IF/ID.RegisterRt Rủi ro khi thực hiện Load nếu ID/EX.MemRead and ((ID/EX.RegisterRt = IF/ID.RegisterRs) or (ID/EX.RegisterRt = IF/ID.RegisterRt)) Nếu phát hiện, thì khựng lại và “nop” BK TP.HCM Làm “Khựng lại” ? 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 79 Giữ các giá trị điều khiển thanh ghi trong bước ID/EX bằng 0 EX, MEM & WB thực hiện nop (no-op) Không cập nhật PC & IF/ID register Sử dụng lại bước giải mã lệnh Nạp lệnh tiếp theo lần nữa 1-cyc đủ để đọc dữ liệu từ MEM đối với lw Can subsequently forward to EX stage BK TP.HCM Stall/Bubble in the Pipeline 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 80 Stall inserted here BK TP.HCM Stall/Bubble in the Pipeline 25-Aug-16 Faculty of Computer Science & Engineering 81 Or, more accurately BK TP.HCM Lộ trình dữ liệu với bộ phát hiện rủi ro 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 82 BK TP.HCM Sự “khựng lại” & Hiệu suất 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 83 Sự “Khựng lại” làm giảm hiệu suất Nhưng cần thiết để cho kết quả đúng Biên dịch có thể sắp xếp lại trật tự các lệnh sao cho rủi ro và sự “ khựng lại” không xảy ra Yêu cầu thông tin về cấu trúc thực hiện trong ống BK TP.HCM Rủi ro điều khiển (rẽ nhánh) 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 84 Nếu rẽ nhánh được xác định trong bước MEM PC Flush these instructions (Set control values to 0) BK TP.HCM Giảm độ trễ do thực hiện rẽ nhánh 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 85 Xác định sớm bằng phần cứng ở giai đoạn ID Bộ cộng địa chỉ đích (Target address adder) Bộ so sánh thanh ghi (Register comparator) Ví dụ: Giả thiết rẽ nhánh (branch taken) 36: sub $10, $4, $8 40: beq $1, $3, 7 44: and $12, $2, $5 48: or $13, $2, $6 52: add $14, $4, $2 56: slt $15, $6, $7 ... 72: lw $4, 50($7) BK TP.HCM Ví dụ: Rẽ nhánh xảy ra 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 86 BK TP.HCM Ví dụ: Rẽ nhánh xảy ra (tt.) 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 87 BK TP.HCM Rủi ro dữ liệu với rẽ nhánh 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 88 Nếu 1 th/ghi của lệnh so sánh là kết quả của 1 lệnh ALU trước đó (2 hay 3 lệnh) IF ID EX MEM WB IF ID EX MEM WB IF ID EX MEM WB IF ID EX MEM WB add $4, $5, $6 add $1, $2, $3 beq $1, $4, target Giải quyết bằng xúc tiếp sớm BK TP.HCM Rủi ro dữ liệu với rẽ nhánh (tt.) 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 89 Nếu 1 th/ghi của lệnh so sánh là kết quả của lệnh ALU ngay trước đó hoặc lệnh Load trước đó 2 lệnh Cần 1 bước “khựng lại” beq stalled IF ID EX MEM WB IF ID EX MEM WB IF ID ID EX MEM WB add $4, $5, $6 lw $1, addr beq $1, $4, target BK TP.HCM Rủi ro dữ liệu với rẽ nhánh (tt.) 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 90 Nếu 1 th/ghi của lệnh so sánh là kết quả của lệnh Load ngay trước đó Cần 2 bước “Khựng lại” beq stalled IF ID EX MEM WB IF ID ID ID EX MEM WB beq stalled lw $1, addr beq $1, $0, target BK TP.HCM Tiên đoán động rẽ nhánh 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 91 Ở những ống có nhiều bước, rủi ro điều khiển sẽ làm giảm hiệu xuất đáng kể Sử dụng phương pháp tiên đoán động Bộ đệm tiên đoán (Bảng lưu lịch sử quá khứ rẽ nhánh) Đánh dấu chỉ số các địa chỉ rẽ nhánh Cất kết quả rẽ nhánh (rẽ/không rẽ=tiếp tục) Thực hiện rẽ nhánh bằng cách Kiểm tra bảng lưu: cùng mong đợi Bắt đầu quy trình nạp (from fall-through or target) Nếu sai, Xóa lưu ông, cập nhật tiên đoán BK TP.HCM 1-Bit Predictor: Shortcoming 25-Aug-16 Faculty of Computer Science & Engineering 92 Inner loop branches mispredicted twice! outer: inner: beq , , inner beq , , outer Mispredict as taken on last iteration of inner loop Then mispredict as not taken on first iteration of inner loop next time around BK TP.HCM 2-Bit Predictor 25-Aug-16 Faculty of Computer Science & Engineering 93 Only change prediction on two successive mispredictions BK TP.HCM Calculating the Branch Target 25-Aug-16 Faculty of Computer Science & Engineering 94 Even with predictor, still need to calculate the target address 1-cycle penalty for a taken branch Branch target buffer Cache of target addresses Indexed by PC when instruction fetched If hit and instruction is branch predicted taken, can fetch target immediately BK TP.HCM Ngoại lệ & Ngắt quãng 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 95 Một sự kiện không mong đợi xảy ra làm cho thay đổi lộ trình thực hiện chương trình ISA khác nhau sử dụng theo cách khác nhau Ngoại lệ Xuất hiện khi CPU thực hiện Ví dụ: mã lệnh sai, tràn, lệnh gọi Ngắt quãng Bởi thiết bị ngoại vi Giải quyết mà không làm ảnh hưởng đến hiệu năng vấn đề khó BK TP.HCM Xử lý ngoại lệ 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 96 Trong MIP, ngoại lệ được quản lý bởi Bộ xử lý (kết hợp) điều khiển khiển hệ thống (CP0) Cất PC của lệnh gây ra ngoại lệ (hoặc ngắt) MIPS: Exception Program Counter (EPC) Cất dấu hiệu vấn đề sinh ra ngoại lệ MIPS: Thanh ghi nguyên nhân Giả sử 1-bit 0: opcode không tồn tại, 1: tràn Nhảy đến chương trình xử lý ngoại lệ: tại địa chỉ 8000 00180 BK TP.HCM Phương thức xử lý ngoại lệ khác 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 97 Bảng (Vectored Interrupts) Địa chỉ mỗi phần tử bảng xác định lý do ngoại lệ Ví dụ: Lệnh không tốn tại: C000 0000 Tràn: C000 0020 : C000 0040 Lệnh xử lý ngoại lệ sẽ là Giải quyết trực tiếp với ngắt Hoặc nhảy đến c/trình xử lý BK TP.HCM Công việc xử lý ngoại lệ 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 98 Xác định nguyên nhân và chuyển đến c/trình xử lý tương ứng Xác định các việc phải giải quyết Nếu phải tiếp tục sau khi xử lý Giải quyết vấn đề Sử dụng EPC để trở về c/trình cũ Nếu không Kết thúc c/trình Báo lỗi, sử dụng EPC, nguyên nhân, etc. BK TP.HCM Ngoại lệ trong cơ chế ống 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 99 Một dạng khác thuộc rủi ro điều khiển Giả sử tràn lệnh add trong bước EX add $1, $2, $1 Tránh thay đổi giá trị $1 Hoàn chỉnh lệnh trước đó Xóa bỏ lệnh add và các lệnh sau Gán nguyên nhân và giá trị t/ghi EPC Chuyển điều khiển ch/trình xử lý tràn Tương tự cho việc rẽ nhánh với địa chỉ tiên đoán: sử dụng lại phần cứng BK TP.HCM Cơ chế ống với ngoại lệ 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 100 BK TP.HCM Exception Properties 25-Aug-16 Faculty of Computer Science & Engineering 101 Restartable exceptions Pipeline can flush the instruction Handler executes, then returns to the instruction Refetched and executed from scratch PC saved in EPC register Identifies causing instruction Actually PC + 4 is saved Handler must adjust BK TP.HCM Ví dụ: ngoại lệ 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 102 Ngoại lệ xảy ra tại lệnh add trong đoạn code: 40 sub $11, $2, $4 44 and $12, $2, $5 48 or $13, $2, $6 4C add $1, $2, $1 50 slt $15, $6, $7 54 lw $16, 50($7) Xử lý ngoại lệ 80000180 sw $25, 1000($0) 80000184 sw $26, 1004($0) BK TP.HCM Ví dụ: Ngoại lệ 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 103 BK TP.HCM Ví dụ: Ngoại lệ (tt.) 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 104 BK TP.HCM Đa ngoại lệ 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 105 Nhiều lệnh thực thi phủ lấp nhau trong ống Dẫn đến xuất hiện ngoại lệ cùng lúc Phương án đơn giản: Giải quyết ngoại lệ xảy ra đầu tiên Xóa các lệnh kế tiếp “Precise” exceptions Ống phức tạp Nhiều lệnh trong cùng 1 chu kỳ Không còn khả năng hoàn tất Giải quyết ngoại lệ một cách chính xác: khó BK TP.HCM Imprecise Exceptions 25-Aug-16 Faculty of Computer Science & Engineering 106 Just stop pipeline and save state Including exception cause(s) Let the handler work out Which instruction(s) had exceptions Which to complete or flush May require “manual” completion Simplifies hardware, but more complex handler software Not feasible for complex multiple-issue out-of-order pipelines BK TP.HCM Instruction-Level Parallelism (ILP) 25-Aug-16 Faculty of Computer Science & Engineering 107 Pipelining: executing multiple instructions in parallel To increase ILP Deeper pipeline Less work per stage shorter clock cycle Multiple issue Replicate pipeline stages multiple pipelines Start multiple instructions per clock cycle CPI < 1, so use Instructions Per Cycle (IPC) E.g., 4GHz 4-way multiple-issue 16 BIPS, peak CPI = 0.25, peak IPC = 4 But dependencies reduce this in practice BK TP.HCM Multiple Issue 25-Aug-16 Faculty of Computer Science & Engineering 108 Static multiple issue Compiler groups instructions to be issued together Packages them into “issue slots” Compiler detects and avoids hazards Dynamic multiple issue CPU examines instruction stream and chooses instructions to issue each cycle Compiler can help by reordering instructions CPU resolves hazards using advanced techniques at runtime BK TP.HCM Speculation 25-Aug-16 Faculty of Computer Science & Engineering 109 “Guess” what to do with an instruction Start operation as soon as possible Check whether guess was right If so, complete the operation If not, roll-back and do the right thing Common to static and dynamic multiple issue Examples Speculate on branch outcome Roll back if path taken is different Speculate on load Roll back if location is updated BK TP.HCM Compiler/Hardware Speculation 25-Aug-16 Faculty of Computer Science & Engineering 110 Compiler can reorder instructions e.g., move load before branch Can include “fix-up” instructions to recover from incorrect guess Hardware can look ahead for instructions to execute Buffer results until it determines they are actually needed Flush buffers on incorrect speculation BK TP.HCM Speculation and Exceptions 25-Aug-16 Faculty of Computer Science & Engineering 111 What if exception occurs on a speculatively executed instruction? e.g., speculative load before null-pointer check Static speculation Can add ISA support for deferring exceptions Dynamic speculation Can buffer exceptions until instruction completion (which may not occur) BK TP.HCM Static Multiple Issue 25-Aug-16 Faculty of Computer Science & Engineering 112 Compiler groups instructions into “issue packets” Group of instructions that can be issued on a single cycle Determined by pipeline resources required Think of an issue packet as a very long instruction Specifies multiple concurrent operations Very Long Instruction Word (VLIW) BK TP.HCM Scheduling Static Multiple Issue 25-Aug-16 Faculty of Computer Science & Engineering 113 Compiler must remove some/all hazards Reorder instructions into issue packets No dependencies with a packet Possibly some dependencies between packets Varies between ISAs; compiler must know! Pad with nop if necessary BK TP.HCM MIPS with Static Dual Issue 25-Aug-16 Faculty of Computer Science & Engineering 114 Two-issue packets One ALU/branch instruction One load/store instruction 64-bit aligned ALU/branch, then load/store Pad an unused instruction with nop Address Instruction type Pipeline Stages n ALU/branch IF ID EX MEM WB n + 4 Load/store IF ID EX MEM WB n + 8 ALU/branch IF ID EX MEM WB n + 12 Load/store IF ID EX MEM WB n + 16 ALU/branch IF ID EX MEM WB n + 20 Load/store IF ID EX MEM WB BK TP.HCM MIPS with Static Dual Issue 25-Aug-16 Faculty of Computer Science & Engineering 115 BK TP.HCM Hazards in the Dual-Issue MIPS 25-Aug-16 Faculty of Computer Science & Engineering 116 More instructions executing in parallel EX data hazard Forwarding avoided stalls with single-issue Now can’t use ALU result in load/store in same packet add $t0, $s0, $s1 load $s2, 0($t0) Split into two packets, effectively a stall Load-use hazard Still one cycle use latency, but now two instructions More aggressive scheduling required BK TP.HCM Scheduling Example 25-Aug-16 Faculty of Computer Science & Engineering 117 Schedule this for dual-issue MIPS Loop: lw $t0, 0($s1) # $t0=array element addu $t0, $t0, $s2 # add scalar in $s2 sw $t0, 0($s1) # store result addi $s1, $s1,–4 # decrement pointer bne $s1, $zero, Loop # branch $s1!=0 ALU/branch Load/store cycle Loop: nop lw $t0, 0($s1) 1 addi $s1, $s1,–4 nop 2 addu $t0, $t0, $s2 nop 3 bne $s1, $zero, Loop sw $t0, 4($s1) 4 IPC = 5/4 = 1.25 (c.f. peak IPC = 2) BK TP.HCM Loop Unrolling 25-Aug-16 Faculty of Computer Science & Engineering 118 Replicate loop body to expose more parallelism Reduces loop-control overhead Use different registers per replication Called “register renaming” Avoid loop-carried “anti-dependencies” Store followed by a load of the same register Aka “name dependence” Reuse of a register name BK TP.HCM Loop Unrolling Example 25-Aug-16 Faculty of Computer Science & Engineering 119 IPC = 14/8 = 1.75 Closer to 2, but at cost of registers and code size BK TP.HCM Dynamic Multiple Issue 25-Aug-16 Faculty of Computer Science & Engineering 120 “Superscalar” processors CPU decides whether to issue 0, 1, 2, each cycle Avoiding structural and data hazards Avoids the need for compiler scheduling Though it may still help Code semantics ensured by the CPU BK TP.HCM Dynamic Pipeline Scheduling 25-Aug-16 Faculty of Computer Science & Engineering 121 Allow the CPU to execute instructions out of order to avoid stalls But commit result to registers in order Example lw $t0, 20($s2) addu $t1, $t0, $t2 sub $s4, $s4, $t3 slti $t5, $s4, 20 Can start sub while addu is waiting for lw BK TP.HCM Dynamically Scheduled CPU 25-Aug-16 Faculty of Computer Science & Engineering 122 Reorders buffer for register writes Can supply operands for issued instructions Results also sent to any waiting reservation stations Hold pending operands Preserves dependencies BK TP.HCM Register Renaming 25-Aug-16 Faculty of Computer Science & Engineering 123 Reservation stations and reorder buffer effectively provide register renaming On instruction issue to reservation station If operand is available in register file or reorder buffer Copied to reservation station No longer required in the register; can be overwritten If operand is not yet available It will be provided to the reservation station by a function unit Register update may not be required BK TP.HCM Speculation 25-Aug-16 Faculty of Computer Science & Engineering 124 Predict branch and continue issuing Don’t commit until branch outcome determined Load speculation Avoid load and cache miss delay Predict the effective address Predict loaded value Load before completing outstanding stores Bypass stored values to load unit Don’t commit load until speculation cleared BK TP.HCM Why Do Dynamic Scheduling? 25-Aug-16 Faculty of Computer Science & Engineering 125 Why not just let the compiler schedule code? Not all stalls are predicable e.g., cache misses Can’t always schedule around branches Branch outcome is dynamically determined Different implementations of an ISA have different latencies and hazards BK TP.HCM Does Multiple Issue Work? 25-Aug-16 Faculty of Computer Science & Engineering 126 Yes, but not as much as we’d like Programs have real dependencies that limit ILP Some dependencies are hard to eliminate e.g., pointer aliasing Some parallelism is hard to expose Limited window size during instruction issue Memory delays and limited bandwidth Hard to keep pipelines full Speculation can help if done well BK TP.HCM Tiết kiệm năng lượng 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 127 Complexity of dynamic scheduling and speculations requires power Multiple simpler cores may be better Microprocessor Year Clock Rate Pipeline Stages Issue width Out-of-order/ Speculation Cores Power i486 1989 25MHz 5 1 No 1 5W Pentium 1993 66MHz 5 2 No 1 10W Pentium Pro 1997 200MHz 10 3 Yes 1 29W P4 Willamette 2001 2000MHz 22 3 Yes 1 75W P4 Prescott 2004 3600MHz 31 3 Yes 1 103W Core 2006 2930MHz 14 4 Yes 2 75W UltraSparc III 2003 1950MHz 14 4 No 1 90W UltraSparc T1 2005 1200MHz 6 1 No 8 70W BK TP.HCM Tổng kết 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 128 ISA influences design of datapath and control Datapath and control influence design of ISA Pipelining improves instruction throughput using parallelism More instructions completed per second Latency for each instruction not reduced Rủi ro: cấu trúc, dữ liệu, điều khiển Multiple issue and dynamic scheduling (ILP) Dependencies limit achievable parallelism Complexity leads to the power wall
File đính kèm:
- bai_giang_kien_truc_may_tinh_chuong_4_bo_xu_ly_lo_trinh_du_l.pdf