›
›

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

pdf 128 trang ngocly 5710
Download
Bạn đang xem 20 trang mẫu của tài liệu "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", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfbai_giang_kien_truc_may_tinh_chuong_4_bo_xu_ly_lo_trinh_du_l.pdf

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. Computer Architecture Computer Science & Engineering Chương 4 Bộ Xử lý Lộ trình dữ liệu – Điều khiển BK TP.HCM
  2. 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
  3. Các bước thực hiện lệnh  PC Bộ nhớ chứa lệnh, Nạp lệnh  Đọc nội dung thanh ghi (Register numbers[rs, rt, rd] register file)  Tùy thuộc vào loại lệnh mà  Sử dụng ALU để tính  Phép số học Kết quả  Xác định địa chỉ bộ nhớ (load/store)  Xác định địa chỉ rẽ nhánh  Truy cập dữ liệu bộ nhớ cho lệnh for load/store  PC  Địa chỉ lệnh kế or PC + 4 BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 3
  4. 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
  5. Bộ Multiplexer  Không thể nối dây trực tiếp lại với nhau  Sử dụng bộ multiplexers BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 5
  6. 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
  7. Nguyên lý thiết kế luận lý  Biểu diễn thông tin nhị phân  Áp mức thấp = 0, Áp mức cao = 1  Một đường dây cho mỗi bit  Dữ liệu gồm nhiều bit sẽ biểu diễn một tuyến nhiều đường dây  Phần tử tổ hợp  Thực hiện trên dữ liệu  Kết quả đầu ra = hàm(đầu vào)  Phần tử trạng tái (mạch tuần tự)  Lưu được dữ liệu BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 7
  8. 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
  9. Phần tử tuần tự  Thanh ghi: lưu dữ liệu trong bộ mạch  Sử dụng tín hiệu xung đồng hồ để xác định khi nào cập nhật giá trị lưu trữ  Kích cạnh: đầu ra cập nhật khi xung đồng hồ thay đổi từ 0 lên 1 Clk D Q D Clk Q BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 9
  10. 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
  11. Phương thức làm việc dựa trên xung đồng hồ (Clocking Methodology)  Mạch tổ hợp sẽ thay đổi giá trị dữ liệu trong chu kỳ đồng hồ  Giữa các cạnh của xung  Trạng thái của phần tử trước Đầu vào của phần tử sau (tức thời)  Độ trễ dài nhất quyết định độ dài chu kỳ BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 11
  12. 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
  13. Nạp lệnh (Inst. Fetch) BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 13
  14. 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
  15. Lệnh Load/Store  Đọc toán hạng thanh ghi  Tính địa chỉ của bộ nhớ (16-bit độ dời)  Sử dụng ALU, nhưng độ dời phát triển ra 32-bit có dấu  Nạp (Load): Đọc bộ nhớ & cập nhật thanh ghi  Cất (Store): Ghi giá trị (register) Bộ nhớ BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 15
  16. 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
  17. Lệnh rẽ nhánh Just re-routes wires Sign-bit wire BK replicated TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 17
  18. 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
  19. Lộ trình tổng hợp (R-Type/Load/Store) BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 19
  20. 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
  21. Bộ điều khiển tín hiệu ALU  ALU dùng trong những lệnh  Load/Store: F(unction) = add  Branch: F(unction) = subtract  R-type: F phụ thuộc vào hàm (funct) ALU control Function 0000 AND 0001 OR 0010 add 0110 subtract 0111 set-on-less-than 1100 NOR BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 21
  22. 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
  23. Bộ phận điều khiển chính  Các tín hiệu đ/khiển giải mã từ lệnh R-type 0 rs rt rd shamt funct 31:26 25:21 20:16 15:11 10:6 5:0 Load/ 35 or 43 rs rt address Store 31:26 25:21 20:16 15:0 Branch 4 rs rt address 31:26 25:21 20:16 15:0 opcode always read, write for sign-extend read except R-type and add for load and load BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 23
  24. 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
  25. Lệnh dạng R-Type BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 25
  26. Lệnh nạp (Load) BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 26
  27. Rẽ nhánh với đ/kiện (=) BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 27
  28. 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
  29. Lộ trình với lệnh Jumps BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 29
  30. 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
  31. Giới thiệu: Cơ chế ống  Ví dụ thực tế: Quy trình giặt đồ (các bước thực hiện phủ lấp)  Các bước thực hiện đồng thời: cải thiện HS  4 mẻ:  Tăng tốc = 8/3.5 = 2.3  Giặt không ngừng:  Tăng tốc = 2n/0.5n + 1.5 ≈ 4 = số bước/mẻ giặt BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 31
  32. 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
  33. Hiệu suất ống  Giả sử thời gian thực hiện cho các công đoạn  100ps để đọc hoặc ghi thanh ghi  200ps cho các công đoạn khác  So sánh lộ trình xử lý ống và chu kỳ đơn như bảng dưới đây: Lệnh Nạp lệnh Đọc ALU op Truy cập Ghi Tổng thời th/ghi bộ nhớ th/ghi gian lw 200ps 100 ps 200ps 200ps 100 ps 800ps sw 200ps 100 ps 200ps 200ps 700ps R-format 200ps 100 ps 200ps 100 ps 600ps beq 200ps 100 ps 200ps 500ps BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 33
  34. Hiệu suất ống (tt.) BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 34
  35. Tăng tốc của ống  Nếu công việc các công đoạn như nhau  Ví dụ: có cùng thời gian thực hiện  Time between instructionspipelined = Time between instructionsnonpipelined Number of stages  Nếu các công đoạn không đều nhau Độ tăng tốc sẽ ít hơn  Độ tăng tốc thể hiện hiệu suất (throughput) tăng  Vì thời gian thực thi cho mỗi lệnh không thay đổi (giảm) BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 35
  36. 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
  37. Rủi ro (Hazards) trong cơ chế ống  Có trường hợp: Lệnh kế tiếp không thể thực hiện trong chu kỳ kế Rủi ro. Tồn tại 3 loại rủi ro:  Rủi ro về cấu trúc (Structure Hazard)  Một tài nguyên được yêu cầu, nhưng bận  Rủi ro về dữ liệu  Đợi lệnh trước hoàn tất tác vụ đọc/ghi dữ  Rủi ro về điều khiển  Quyết định bước tiếp theo phụ thuộc vào BK lệnh trước đó TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 37
  38. 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
  39. Rủi ro về cấu trúc  Tranh chấp sử dụng tài nguyên  Trong MIPS, cơ chế ống với 1 loại bộ nhớ  Load/store yêu cầu đọc/ghi dữ liệu  Nạp lệnh sẽ bị “kẹt” trong chu kỳ đó  Trường hợp đó gọi là sự “khựng lại” hay “bong bóng” (bubble)  Vì vậy, trong cơ chế ống lộ trình xử lý lệnh cần tách 2 bộ nhớ riêng biệt (lệnh, data)  ít ra thì 2 vùng cache riêng BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 39
  40. 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
  41. Xúc tiến sớm (Forwarding)  Sử dụng ngay kết quả vừa tính toán xong của lệnh trước  Không cần đợi kết quả cất lại thanh ghi  Cần có thêm kết nối trong lộ trình BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 41
  42. 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
  43. Khắc phục  Sắp xếp lại code để tránh sử dụng kết quả của lệnh load trong lệnh kế  C code: A = B + E; C = B + F; lw $t1, 0($t0) lw $t1, 0($t0) lw $t2, 4($t0) lw $t2, 4($t0) stall add $t3, $t1, $t2 lw $t4, 8($t0) sw $t3, 12($t0) add $t3, $t1, $t2 lw $t4, 8($t0) sw $t3, 12($t0) stall add $t5, $t1, $t4 add $t5, $t1, $t4 sw $t5, 16($t0) sw $t5, 16($t0) BK 13 cycles 11 cycles TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 43
  44. 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
  45. Sự “khựng lại” trong rẽ nhánh  Đợi cho đến khi xác định được khi nào sẽ nạp lệnh kế. BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật máy tính 45
  46. 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
  47. Ví dụ: Tiên đoán 50:50 Prediction correct Prediction incorrect BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 47
  48. 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
  49. Tổng kết về Cơ chế ống  Cơ chế ống cải thiện hiệu suất thực hiện lệnh (throughput)  Thực hiện nhiều lệnh cùng lúc  Mỗi lệnh có thời gian thực thi không đổi  Vấn đề nảy sinh: rủi ro  Cấu trúc, dữ liệu , điều khiển  Thiết kế tập lệnh (theo nguyên tắc thiết kế) có thể làm phức tạp quá trình thực thi cơ chế ống BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 49
  50. 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
  51. Thanh ghi đệm giữa các bước  Cần có các thanh ghi đệm giữa các công đoạn (bước): lưu t/tin bước trước đó BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 51
  52. 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
  53. Bước Nạp lệnh (Load, Store, ) BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 53
  54. 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
  55. Bước thực hiện lệnh (Load) BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 55
  56. 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
  57. Bước ghi thanh ghi (Load) Wrong register number BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 57
  58. Lộ trình đúng (Load) BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 58
  59. Bước thực hiện (Store) BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 59
  60. Bước ghi MEM (Store) BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 60
  61. Bước ghi lên bộ nhớ (Store) BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 61
  62. 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
  63. Biểu đồ ống đa bước (tt.)  Cách biểu diễn truyền thống BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 63
  64. 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
  65. Điều khiển cơ chế ống (đã đơn giản) BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 65
  66. Đ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
  67. Điều khiển cơ chế ống BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 67
  68. 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
  69. Sự ràng buộc & Forwarding BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 69
  70. 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
  71. Phát hiện yêu cầu Forward (tt.)  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 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 71
  72. 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
  73. Các điều kiện xúc tiến sớm  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)) BK ForwardB = 01 TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 73
  74. 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
  75. Điều kiện xúc tiến sớm xét lại  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 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 75
  76. Lộ trình với Forwarding BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 76
  77. Rủi ro dữ liệu với lệnh Load Phải “khựng lại” 1 bước BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 77
  78. 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
  79. Làm “Khựng lại” ?  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 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 79
  80. 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
  81. Stall/Bubble in the Pipeline Or, more BK accurately TP.HCM 25-Aug-16 Faculty of Computer Science & Engineering 81
  82. 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
  83. Sự “khựng lại” & Hiệu suất  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 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 83
  84. 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
  85. Giảm độ trễ do thực hiện rẽ nhánh  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 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 85
  86. 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
  87. Ví dụ: Rẽ nhánh xảy ra (tt.) BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 87
  88. 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
  89. 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 ALU ngay trước đó hoặc lệnh Load trước đó 2 lệnh  Cần 1 bước “khựng lại” lw $1, addr IF ID EX MEM WB add $4, $5, $6 IF ID EX MEM WB beq stalled IF ID beq $1, $4, target ID EX MEM WB BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 89
  90. 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
  91. Tiên đoán động rẽ nhánh  Ở 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 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 91
  92. 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
  93. 2-Bit Predictor  Only change prediction on two successive mispredictions BK TP.HCM 25-Aug-16 Faculty of Computer Science & Engineering 93
  94. 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
  95. Ngoại lệ & Ngắt quãng  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 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 95
  96. 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
  97. Phương thức xử lý ngoại lệ khác  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 BK  Hoặc nhảy đến c/trình xử lý TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 97
  98. 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
  99. Ngoại lệ trong cơ chế ống  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ỉ BK tiên đoán: sử dụng lại phần cứng TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 99
  100. 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
  101. Exception Properties  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 25-Aug-16 Faculty of Computer Science & Engineering 101
  102. 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
  103. Ví dụ: Ngoại lệ BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 103
  104. Ví dụ: Ngoại lệ (tt.) BK TP.HCM 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 104
  105. Đa ngoại lệ  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 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 105
  106. 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
  107. Instruction-Level Parallelism (ILP)  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 25-Aug-16 Faculty of Computer Science & Engineering 107
  108. 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
  109. Speculation  “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  BK Roll back if location is updated TP.HCM 25-Aug-16 Faculty of Computer Science & Engineering 109
  110. 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
  111. Speculation and Exceptions  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 25-Aug-16 Faculty of Computer Science & Engineering 111
  112. 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
  113. Scheduling Static Multiple Issue  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 25-Aug-16 Faculty of Computer Science & Engineering 113
  114. 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
  115. MIPS with Static Dual Issue BK TP.HCM 25-Aug-16 Faculty of Computer Science & Engineering 115
  116. 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
  117. Scheduling Example  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 25-Aug-16 Faculty of Computer Science & Engineering 117
  118. 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
  119. Loop Unrolling Example  IPC = 14/8 = 1.75  Closer to 2, but at cost of registers and code size BK TP.HCM 25-Aug-16 Faculty of Computer Science & Engineering 119
  120. 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
  121. Dynamic Pipeline Scheduling  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 25-Aug-16 Faculty of Computer Science & Engineering 121
  122. 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
  123. Register Renaming  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 BK  Register update may not be required TP.HCM 25-Aug-16 Faculty of Computer Science & Engineering 123
  124. 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
  125. Why Do Dynamic Scheduling?  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 25-Aug-16 Faculty of Computer Science & Engineering 125
  126. 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
  127. Tiết kiệm năng lượng  Complexity of dynamic scheduling and speculations requires power  Multiple simpler cores may be better Microprocessor Year Clock Rate Pipeline Issue Out-of-order/ Cores Power Stages width Speculation 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 25-Aug-16 Khoa Khoa học & Kỹ thuật Máy tính 127
  128. 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