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

Nội dung text: 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

1. Dẫn nhập  Các yếu tố xác định hiệu xuất Bộ Xử lý  Số lệnh (Instruction Count)  Xác định bởi “Kiến trúc tập lệnh” ISA và Trình biên dịch  Số chu kỳ cho mỗi lệnh và thời gian chu kỳ đ/hồ  Xác định bằng phần cứng CPU  Đề cập 2 mô hình thực hiện MIPS  Phiên bản đơn giản  Phiên bản thực (cơ chế đường ống)  Nhóm các lệnh đơn giản, nhưng đặc trưng:  Truy cập bộ nhớ: lw, sw  Số học/luận lý: add, sub, and, or, slt  Nhảy, rẽ nhánh (chuyển điều khiển): beq, j BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 2
2. Lược đồ thực hiện (CPU) BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 4
3. Bộ phận Điều khiển BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 6
4. Ví dụ: các phần tử tổ hợp BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 8
5. Phần tử tuần tự (tt.)  Thanh ghi với tín hiệu đ/khiển write  Chỉ cập nhật theo cạnh xung khi mức điều khiển write ở mức 1  Sử dụng trong trường hợp lưu cho chu kỳ sau Clk D Q Write Write D Clk Q BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 10
6. Xây dựng lộ trình dữ liệu  Lộ trình xử lý Datapath  Các phần tử chức năng xử lý dữ liệu và địa chỉ trong CPU  Registers, ALUs, mux’s, memories,  Lộ trình sẽ được xây dựng từng bước từ thấp đến cao (đơn giản đến chi tiết)  Chi tiết và cụ thế hóa từng phần, bắt đầu từ Nạp lệnh (Instruction Fetch) BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 12
7. Lệnh dạng R (R-Format)  Đọc 2 toán hạng là thanh ghi  Thực hiện phép Số học/Luận lý  Ghi kết quả vào thanh ghi BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 14
8. Lệnh rẽ nhánh  Đọc toán hạng (thanh ghi)  So sánh toán hạng  Sử dụng ALU, subtract and check Zero  Tính toán địa chỉ đích  Mở rộng 16 sang 32 bit có dấu (địa chỉ)  Dịch trái 2 vị trí (1 word = 4 bytes)  Cộng PC=PC + 4  Đã được tính tự động khi nạp lệnh BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 16
9. Tổng hợp các phần tử  Lệnh được thực hiện trong 1 chu kỳ xung Clock  Mỗi bộ phận chỉ có thể thực hiện 1 chức năng tại mỗi thời điểm  Vì vậy, phải tách biệt giữa bộ nhớ lệnh và bộ nhớ dữ liệu  Multiplexer được sử dụng tại những nơi mà nguồn dữ liệu khác nhau ứng với lệnh khác nhau BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 18
10. Lộ trình toàn phần BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 20
11. Bộ điều khiển tín hiệu ALU (tt.)  Giả sử 2-bit ALUOp từ opcode của lệnh  Tín hiệu đ/khiển ALU từ mạch tổ hợp như sau: opcode ALUOp Operation funct ALU function ALU control lw 00 load word XXXXXX add 0010 sw 00 store word XXXXXX add 0010 beq 01 branch equal XXXXXX subtract 0110 R-type 10 add 100000 add 0010 subtract 100010 subtract 0110 AND 100100 AND 0000 OR 100101 OR 0001 set-on-less-than 101010 set-on-less-than 0111 BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 22
12. Lộ trình với tín hiệu đ/khiển BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 24
13. Lệnh nạp (Load) BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 26
14. Thực hiện lệnh Jumps Jump 2 address 31:26 25:0  Jump sử dụng địa chỉ trong 1 từ (word)  Cập nhật PC bằng cách tổng hợp từ  4 bits cao của thanh ghi cũ PC  26-bit jump address  00  Yêu cầu thêm các tín hiệu đ/khiển giải mã từ opcode BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 28
15. Vấn đề hiệu xuất  Trễ tối đa sẽ xác định độ dài chu kỳ đồng hồ  Lộ trình dài nhất: lệnh load  Instruction memory register file ALU data memory register file  Không khả thi nếu thay đổi chu kỳ xung theo lệnh khác nhau  Phá vỡ nguyên tắc thiết kế  Cái gì phổ biến nhất thực hiện nhanh nhất  Chúng ta sẽ cải thiện hiệu xuất theo cơ chế ống BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 30
16. Cơ chế ống trong MIPS  Mỗi lệnh: 5 công đoạn (mỗi bước/công đoạn), đó là 1. IF: Nạp lệnh (Inst. Fetch) từ bộ nhớ 2. ID: Giải mã (Inst. Decode) & đọc th/ghi 3. EX: Thực thi (Ex.) hay tính địa chỉ 4. MEM: Truy cập bộ nhớ 5. WB: Cất kết trở lại th/ghi BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 32
17. Hiệu suất ống (tt.) BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 34
18. Cơ chế ống với MIPS ISA  MIPS ISA được thiết kế với cơ chế ống  Tất cả các lệnh 32-bits  Dễ dàng nạp & giải mã trong 1 chu kỳ  Khác với x86: 1- đến 17-bytes/lệnh  Lệnh ít dạng và có quy tắc  Giải mã & đọc th/ghi trong 1 chu kỳ  Địa chỉ trong lệnh Load/store  Có thể tính trong công đoạn 3, truy cập bộ nhớ trong công đoạn 4  Các toán hạng bộ nhớ truy cập trong 1 cùng 1 chu kỳ BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 36
19. Rủi ro về cấu trúc EX Đọc dữ liệu từ lw IF ID MEM WB Bộ nhớ EX Inst 1 IF ID MEM WB EX Inst 2 IF ID MEM WB Nạp lệnh bị EX Inst 3 ngưng do xung IF ID MEM WB đột truy cập bộ nhớ tại chu kỳ EX IF ID MEM WB Inst 4 này BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 38
20. Rủi ro về dữ liệu  Kết quả truy xuất dữ liệu thuộc lệnh trước ảnh đến lệnh sau  add $s0, $t0, $t1 sub $t2, $s0, $t3 BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 40
21. Rủi ro dữ liệu khi dùng Load  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 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 42
22. Rủi ro về điều khiển  Rẽ nhánh thay đổi lộ trình thực hiện  Nạp lệnh kế phụ thuộc vào kết quả của điều kiện rẽ nhánh  Với cơ chế ống: khó xác định đúng  Thực hiện trong công đoạn giải mã lệnh  Trong cơ chế ống của MIPS  Giá trị các thanh ghi được so sánh & tính ra địa chỉ đích  Sử dụng thêm phần cứng để thực hiện trong bước giải mã lệnh BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 44
23. Tiên đoán khi có rẽ nhánh  Đối với ống dài: có thể xác định sớm  Sự “khựng lại” giảm hiệu xuất  Tiên đoán trước  50:50 “Khựng lại”  Trong cơ chế ống MIPS  Có thể tiên đóan  Tự động lấy lệnh kế BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 46
24. Giải pháp tiên đoán thực tế  Tiên đoán tĩnh (Static branch prediction)  Dựa trên hành vi rẽ nhánh thường xảy ra  Ví dụ: Vòng lặp với phát biểu if  Tiên đoán sẽ là rẽ nhánh quay lại (backward branches)  Tiên đoán rẽ nhánh xuôi (forward) không xuất hiện  Tiên đoán động (Dynamic branch prediction)  Bộ phận phần cứng sẽ đo đạc hành vi xảy ra  Ví du: lưu lại lịch sử mỗi rẽ nhánh  Giả thiết tương lai từ việc đo đạc  Nếu không đúng, cập nhật lại lịch sử, chấp nhận sự “khựng lại” BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 48
25. Lộ trình MIP theo bước (ống) MEM: rủi ro điều khiển Dòng từ phải qua trái WB: Rủi ro: Dũ rủi ro liệu, điều dữ BK khiển liệu TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 50
26. Hoạt động trong ống  Các lệnh sẽ được thực hiện theo luồng trong lộ trình dữ liệu ống (theo từng chu kỳ)  Biểu diễn theo chu kỳ đơn  Thể hiện lệnh/chu kỳ đồng hồ  Tô đậm các tài nguyên sử dụng  Ngược với biểu diễn theo đa chu kỳ  Biểu đồ tác vụ theo thời gian  Chúng ta sẽ quan sát quá trình thực hiện từng bước với lệnh load & store BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 52
27. Bước Giả mã lệnh (Load, Store, ) BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 54
28. Bước truy cập bộ nhớ (Load) BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 56
29. Lộ trình đúng (Load) BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 58
30. Bước ghi MEM (Store) BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 60
31. Biểu đồ ống đa bước (chu kỳ) . “Multiple-Clock-Cycle” 62 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính
32. Biểu đồ ống đơn bước  “Single-Clock-Cycle”  Trạng thái của ống trong 1 chu kỳ BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 64
33. Điều khiển cơ chế ống (tt.)  Tín hiệu điều khiển xác lập từ lệnh:  thực hiện đơn bước BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 66
34. Rủi ro dữ liệu khi thực hiện lệnh ALU  Quan sát đoạn code sau: sub $2, $1,$3 and $12,$2,$5 or $13,$6,$2 add $14,$2,$2 sw $15,100($2)  Ta có thể áp dụng phương pháp forwarding để giải quyết rủi ro  Làm thế nào để xác định khi nào BK forwarding? TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 68
35. Phát hiện yêu cầu Forward  Chuyển Chỉ số thanh ghi theo đường ống  Ví dụ: ID/EX.RegisterRs = Chỉ số của Rs trong thanh ghi ống giai đoạn ID/EX  Chỉ số thanh ghi toán hạng (ALU) trong công đoạn thực hiện (EX) lệnh sẽ là  ID/EX.RegisterRs, ID/EX.RegisterRt  Rủi ro dữ liệu xuất hiện khi: Xúc tiến sớm 1a. EX/MEM.RegisterRd = ID/EX.RegisterRs từ th/ghi EX/MEM 1b. EX/MEM.RegisterRd = ID/EX.RegisterRt Xúc tiến sớm 2a. MEM/WB.RegisterRd = ID/EX.RegisterRs từ th/ghi 2b. MEM/WB.RegisterRd = ID/EX.RegisterRt MEM/WB BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 70
36. Lộ trình xúc tiến sớm BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 72
37. Rủi ro dữ liệu đúp  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 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 74
38. Lộ trình với Forwarding BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 76
39. Phát hiện rủi ro do lệnh Load  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 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 78
40. Stall/Bubble in the Pipeline Stall inserted here BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 80
41. Lộ trình dữ liệu với bộ phát hiện rủi ro BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 82
42. Rủi ro điều khiển (rẽ nhánh)  Nếu rẽ nhánh được xác định trong bước MEM Flush these instructions (Set control values to 0) BK PC TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 84
43. Ví dụ: Rẽ nhánh xảy ra BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 86
44. Rủi ro dữ liệu với rẽ nhánh  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) add $1, $2, $3 IF ID EX MEM WB add $4, $5, $6 IF ID EX MEM WB IF ID EX MEM WB beq $1, $4, target IF ID EX MEM WB  Giải quyết bằng xúc tiếp sớm BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 88
45. Rủi ro dữ liệu với rẽ nhánh (tt.)  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” lw $1, addr IF ID EX MEM WB beq stalled IF ID beq stalled ID beq $1, $0, target ID EX MEM WB BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 90
46. 1-Bit Predictor: Shortcoming  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 BK iteration of inner loop next time around TP.HCM 25-Aug-16 Faculty of Computer Science & Engineering 92
47. Calculating the Branch Target  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 25-Aug-16 Faculty of Computer Science & Engineering 94
48. Xử lý ngoại lệ  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 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 96
49. Công việc xử lý ngoại lệ  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 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 98
50. Cơ chế ống với ngoại lệ BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 100
51. Ví dụ: ngoại lệ  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 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 102
52. Ví dụ: Ngoại lệ (tt.) BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 104
53. Imprecise Exceptions  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 25-Aug-16 Faculty of Computer Science & Engineering 106
54. Multiple Issue  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 25-Aug-16 Faculty of Computer Science & Engineering 108
55. Compiler/Hardware Speculation  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 25-Aug-16 Faculty of Computer Science & Engineering 110
56. Static Multiple Issue  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 25-Aug-16 Faculty of Computer Science & Engineering 112
57. MIPS with Static Dual Issue  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 25-Aug-16 Faculty of Computer Science & Engineering 114
58. Hazards in the Dual-Issue MIPS  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 25-Aug-16 Faculty of Computer Science & Engineering 116
59. Loop Unrolling  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 25-Aug-16 Faculty of Computer Science & Engineering 118
60. Dynamic Multiple Issue  “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 25-Aug-16 Faculty of Computer Science & Engineering 120
61. Dynamically Scheduled CPU Preserves dependencies Hold pending operands Results also sent to any waiting reservation stations Reorders buffer for register writes Can supply operands for BK issued instructions TP.HCM 122 25-Aug-16 Faculty of Computer Science & Engineering
62. Speculation  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 25-Aug-16 Faculty of Computer Science & Engineering 124
63. Does Multiple Issue Work?  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 25-Aug-16 Faculty of Computer Science & Engineering 126
64. Tổng kết  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 BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 128