›
›

Bài giảng Kiến trúc máy tính - Chương 3: Bộ xử lý - Nguyễn Đức Minh

pdf 77 trang hapham 3080
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 3: Bộ xử lý - Nguyễn Đức Minh", để 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_3_bo_xu_ly_nguyen_duc_mi.pdf

Nội dung text: Bài giảng Kiến trúc máy tính - Chương 3: Bộ xử lý - Nguyễn Đức Minh

  1. KIẾN TRÚC MÁY TÍNH ET4270 TS. Nguyễn Đức Minh [Adapted from Computer Organization and Design, 4th Edition, Patterson & Hennessy, © 2008, MK] [Adapted from Computer Architecture lecture slides, Mary Jane Irwin, © 2008, PennState University]
  2. Tổ chức lớp Số tín chỉ 3 (3-1-1-6) Giảng viên TS. Nguyễn Đức Minh Văn phòng C9-401 Email minhnd1@gmail,com Website • Username: ca.fet.hut@gmail.com • Pass: dungkhoiminh Sách Computer Org and Design, 3rd Ed., Patterson &Hennessy, ©2007 Digital Design and Computer Architecture, David Money Harris Thí nghiệm 3 bài Bài tập Theo chương, đề bài xem trên trang web Giới thiệu 2 HUST-FET, 13/03/2011
  3. Điểm số Điều kiện thi Lab Bài thi giữa kỳ 30% Bài tập 20% (Tối đa 100 điểm) Tiến trình 10% Tối đa: 100 điểm, Bắt đầu: 50 điểm Tích lũy, trừ qua trả lời câu hỏi trên lớp và đóng góp tổ chức lớp Bài thi cuối kỳ 70% Giới thiệu 3 HUST-FET, 13/03/2011
  4. Lịch học  Thời gian:  Từ 14h00 đến 17h20  Lý thuyết: 11 buổi x 135 phút / 1 buổi  Bài tập: 4 buổi x 135 phút / 1 buổi  Thay đổi lịch (nghỉ, học bù) sẽ được thông báo trên website trước 2 ngày Giới thiệu 4 HUST-FET, 13/03/2011
  5. Kết luận chương 2  Dữ liệu và chỉ thị cho máy tính được biểu diễn bằng các chuỗi bit. Giá trị của dữ liệu, ý nghĩa của chỉ thị máy được quy định trong phương pháp mã hóa.  Thiết kế kiến trúc tập lệnh:  Kích thước và kiểu dữ liệu  Phép toán: loại nào được hỗ trợ  Định dạng và mã hóa chỉ thị: Chỉ thị được giải mã thế nào?  Vị trí toán hạng và kết quả  Số lượng toán hạng?  Giá trị toán hạng được lưu ở đâu?  Kết quả được lưu ở vị trí nào?  Các toán hạng bộ nhớ được định vị thế nào?  Kiến trúc tập lệnh MIPS(RISC) được thiết kế dựa trên 4 nguyên tắc cơ bản.  Bộ cộng trừ nhân chia được triển khai bằng các phần tử logic hay bằng thuật toán. Chương 3. Bộ xử lý - Processor 5 HUST-FET, 13/03/2011
  6. Nguyên tắc thiết kế MIPS (RISC)  Tính đơn giản quan trọng hơn tính quy tắc(Simplicity favors regularity)  Chỉ thị kích thước cố định (32 bit)  Ít định dạng chỉ thị (3 loại định dạng)  Mã lệnh ở vị trí cố định (6 bit đầu)  Nhỏ hơn thì nhanh hơn  Số chỉ thị giới hạn  Số thanh ghi giới hạn  Số chế độ địa chỉ giới hạn  Tăng tốc các trường hợp thông dụng  Các toán hạng số học lấy từ thanh ghi (máy tính dựa trên cơ chế load- store)  Các chỉ thị có thể chứa toán hạng trực tiếp  Thiết kế tốt đòi hỏi sự thỏa hiệp  3 loại định dạng chỉ thị Chương 3. Bộ xử lý - Processor 6 HUST-FET, 13/03/2011
  7. Nội dung Đường dữ liệu bộ xử lý MIPS Đơn xung nhịp Đa xung nhịp Hiệu năng Kỹ thuật đường ống Nguyên tắc hoạt động Hiệu năng Xung đột trong đường ống 7 HUST-FET, 13/03/2011
  8. Bộ xử lý: Đường dữ liệu và điều khiển  Triển khai các lệnh  Lệnh truy cập bộ nhớ: lw, sw Instruction Fetch  Lệnh số học và logic: add, sub, and, or, slt  Lệnh điều khiển dòng chương trình: beq, j Instruction Decode  Triển khai các pha hoạt động Operand  Dùng thanh ghi PC để lưu địa chỉ lệnh Fetch Đọc lệnh từ bộ nhớ, và cập nhật giá trị PC  Giải mã lệnh và đọc các thanh ghi Execute  Thực hiện lệnh Result  Lưu kết quả Fetch Store PC = PC+4 Next Exec, Decode Instruction Store 8 HUST-FET, 13/03/2011
  9. Thiết kế đồng bộ theo đồng hồ  Mạch đồng bộ theo đồng hồ: thời điểm dữ liệu trong 1 phần tử trạng thái là hợp lệ và ổn định được quy định bởi xung đồng hồ  Phần tử trạng thái - phần tử nhớ - VD. thanh ghi, FF  Kích hoạt theo sườn – các trạng thái thay đối khi có xườn xung  Hoạt động thông thường:  đọc nội dung của phần tử trạng thái -> tính giá trị bằng logic tổ hợp -> ghi kết quả vào phần tử trạng thái State Combinational State element logic element 1 2 clock one clock cycle  Các phần tử trạng thái được ghi ở tất cả các chu kỳ đồng hồ. Nếu không: cần tín hiệu điều khiển việc ghi 9 HUST-FET, 13/03/2011
  10. Nạp lệnh  Đọc lệnh tại địa chỉ (lưu trong) PC từ bộ nhớ lệnh (eng. Instruction Memory)  Cập nhật giá trị PC tới địa chỉ của lệnh kế tiếp clock Add 4 Fetch PC = PC+4 Instruction Memory Exec, PC Read Instruction Decode Store Address  PC được cập nhật ở mọi chu kỳ không cần tín hiệu điều khiển ghi PC.  Đọc từ bộ nhớ lệnh được thực hiện bằng logic tổ hợp 10 HUST-FET, 13/03/2011
  11. Giải mã lệnh  Chuyển các bit thuộc trường mã lệnh và trường mã chức năng tới khối điều khiển Control Fetch Unit PC = PC+4 Exec, Read Addr 1 Decode Store Register Read Data 1 Instruction Read Addr 2 File Write Addr Read Data 2 Write Data  Đọc 2 giá trị toán hạng nguồn từ tệp thanh ghi - Chỉ số các thanh ghi nằm trong lệnh 11 HUST-FET, 13/03/2011
  12. Thực hiện lệnh loại R  Lệnh định dạng R (add, sub, slt, and, or) 31 25 20 15 10 5 0 R-type: op rs rt rd shamt funct  Thực hiện phép toán (mã hóa bới op và funct) trên giá trị toạn hạng trong rs và rt  Ghi kết quả vào tệp thanh ghi (tại vị trí rd) RegWrite ALU control Read Addr 1 Fetch Register Read Data 1 PC = PC+4 Instruction Read Addr 2 overflow File ALU zero Write Addr Exec Decode Read Data 2 Write Data  Tệp thanh ghi không được ghi ở mọi chu kỳ cần tín hiệu điều khiển ghi riêng biệt. 12 HUST-FET, 13/03/2011
  13. Thực hiện lệnh đọc ghi bộ nhớ  Tính địa chỉ bộ nhớ bằng cách cộng thanh ghi cơ sở (đọc từ tệp thanh ghi khi giải mã lệnh) với giá trị offset  ghi (sw) giá trị (được đọc từ tệp thanh ghi khi giải mã lệnh) vào bộ nhớ dữ liệu  đọc (lw) giá trị từ bộ nhớ dữ liệu vào tệp thanh ghi RegWrite ALU control MemWrite overflow Read Addr 1 zero Register Read Address Data 1 Instruction Read Addr 2 Data File ALU Memory Read Data Write Addr Read Data 2 Write Data Write Data Sign MemRead Extend 13 HUST-FET, 13/03/2011
  14. Thực hiện lệnh rẽ nhánh có điều kiện  so sánh toán hạng đọc từ tệp thanh ghi khi giải mã  tính địa chỉ đích bằng cách cộng giá trị PC (sau khi cập nhât) với trường offset 16 bit đã được mở rộng dấu. Add Branch target 4 Add Shift address left 2 ALU control PC Read Addr 1 zero (to branch Register Read control logic) Data 1 Instruction Read Addr 2 File ALU Write Addr Read Data 2 Write Data Sign 16 Extend 32 14 HUST-FET, 13/03/2011
  15. Thực hiện lệnh nhảy không điều kiện  Thay 28 bit thấp của PC bằng 26 bít thấp của lệnh được nạp và 2 bít 0 Add 4 4 Jump Instruction Shift address Memory left 2 28 Read PC Instruction Address 26 15 HUST-FET, 13/03/2011
  16. Đường dữ liệu  Ghép các phần của đường dữ liệu thêm các đường tín hiệu điều khiển và bộ ghép (multiplexors)  Thiết kế đơn xung nhịp – các pha thực hiện: nạp, giải mã and thực hiện, ghi của mỗi lệnh trong một chu kỳ đồng hồ  Các tài nguyên phần cứng của đường dữ liệu không thể tái sử dụng cho cùng 1 lệnh, một số tài nguyên phải nhân đôi (VD., bộ nhớ lệnh và dữ liệu riêng biệt, một vài bộ cộng)  bộ ghép được dùng ở đầu vào của các tài nguyên dùng chung và được điều khiển bằng tín hiệu điều khiển  Chu kỳ đồng hồ: xác định bằng độ dài đường dữ liệu dài nhất 16 HUST-FET, 13/03/2011
  17. Đường dữ liệu: Phần nạp, thực hiện lệnh R, lw,sw Add RegWrite ALUSrc ALU control MemWrite MemtoReg 4 ovf zero Instruction Read Addr 1 Register Read Address Memory Data 1 Read Addr 2 Data PC Read Instruction File Read Data Address ALU Memory Write Addr Read Data 2 Write Data Write Data MemRead Sign 16 Extend 32 Các tín hiệu điều khiển bộ ghép: lựa chọn đầu vào cho các khối chức năng được tính bằng khối điều khiển từ trường mã lệnh (opcode) và trường chức năng lệnh (funct) 17 HUST-FET, 13/03/2011
  18. Bộ xử lý đơn xung nhịp (1) – Lệnh R 0 Add Add 1 4 Shift left 2 PCSrc ALUOp Branch MemRead Instr[31-26] Control MemtoReg Unit MemWrite ALUSrc RegWrite RegDst ovf Instr[25-21] Instruction Read Addr 1 Register Read Address Memory Instr[20-16] Data 1 zero Read Addr 2 Data Read File PC Instr[31-0] 0 ALU Memory Read Data 1 Address Write Addr 1 Read 0 Data 2 Write Data 0 Instr[15 Write Data -11] 1 Instr[15-0] Sign ALU Extend 16 32 control Instr[5-0] 18 HUST-FET, 13/03/2011
  19. BXL đơn xung nhịp (3) – Lệnh lw, sw 0 Add Add 1 4 Shift left 2 PCSrc ALUOp Branch MemRead Instr[31-26] Control MemtoReg Unit MemWrite ALUSrc RegWrite RegDst ovf Instr[25-21] Instruction Read Addr 1 Register Read Address Memory Instr[20-16] Data 1 zero Read Addr 2 Data Read File PC Instr[31-0] 0 ALU Memory Read Data 1 Address Write Addr 1 Read 0 Data 2 Write Data 0 Instr[15 Write Data -11] 1 Instr[15-0] Sign ALU Extend 16 32 control Instr[5-0] 19 HUST-FET, 13/03/2011
  20. BXL đơn xung nhịp (4) – Lệnh rẽ nhánh 0 Add Add 1 4 Shift left 2 PCSrc ALUOp Branch MemRead Instr[31-26] Control MemtoReg Unit MemWrite ALUSrc RegWrite RegDst ovf Instr[25-21] Instruction Read Addr 1 Register Read Address Memory Instr[20-16] Data 1 zero Read Addr 2 Data Read File PC Instr[31-0] 0 ALU Memory Read Data 1 Address Write Addr 1 Read 0 Data 2 Write Data 0 Instr[15 Write Data -11] 1 Instr[15-0] Sign ALU Extend 16 32 control Instr[5-0] 20 HUST-FET, 13/03/2011
  21. BXL đơn xung nhịp – Thêm lệnh nhảy Instr[25-0] Shift 1 28 32 26 left 2 PC+4[31-28] 0 Add 0 Add 1 4 Shift Jump left 2 PCSrc ALUOp Branch MemRead Instr[31-26] Control MemtoReg Unit MemWrite ALUSrc RegWrite RegDst ovf Instr[25-21] Read Addr 1 Instruction Read Address Memory Register Instr[20-16] Read Addr 2 Data 1 zero Data Read File PC Instr[31-0] 0 ALU Memory Read Data 1 Address Write Addr 1 Read 0 Data 2 Write Data 0 Instr[15 Write Data -11] 1 Instr[15-0] Sign ALU 16 Extend 32 control Instr[5-0] 21 HUST-FET, 13/03/2011
  22. Tính chu ky đồng hồ Tc – Đường dài nhất  Tính chu kỳ đồng hồ trong trường hợp bỏ qua trễ ở bộ ghép, khối điều khiển, khối mở rộng dấu, khối đọc PC, khối dịch 2, dây dẫn, thời gian thiết lập và giữ. Cho biết độ trễ:  Truy cập bộ nhớ lệnh và bộ nhớ dữ liệu (200 ps)  Khối số học logic và bộ cộng (200 ps)  Truy cập tệp thanh ghi (đọc hoặc ghi) (100 ps) Instr. I Mem Reg Rd ALU Op D Mem Reg Wr Total R- type load store beq jump 22 HUST-FET, 13/03/2011
  23. Ví dụ 3.1 – Hiệu năng thiết kế đơn xung nhịp Độ trễ logic khi P Not Truy cập lệnh 2 ns ALU-type C used Đọc thanh ghi 1 ns Hoạt động ALU 2 ns Truy cập bộ nhớ DL 2 ns P Load C Ghi thanh ghi 1 ns Tổng 8 ns Tốc độ đồng hồ = P Not Store C used Các loại lệnh: R-type 44% 6 ns P Not Not Not Load 24% 8 ns Branch used (and jr) C used used Store 12% 7 ns Branch 18% 5 ns Not Not Not Jump 2% 3 ns Jump P Not used used used (except C used Trung bình  jr & jal) 23 HUST-FET, 13/03/2011
  24. Thiết kế đơn xung nhịp – Ưu nhược điểm  Sử dụng chu kỳ đồng hồ không hiệu quả – chu kỳ đồng hồ được đặt theo lệnh chậm nhất  Vấn đề đặc biệt của các lệnh phức tạp như lệnh nhân dấu phẩy động Cycle 1 Cycle 2 Clk lw sw Waste  Tốn diện tích thiết kế vì cần nhân đôi một số khối chức năng (VD. bộ cộng) vì chúng không thể được chia sẻ trong cùng 1 chu kỳ đồng hồ Nhưng  Đơn giản và dễ hiểu 24 HUST-FET, 13/03/2011
  25. So sánh đánh giá thiết kế đơn xung nhịp Instruction access 2 ns Đồng hồ tốc độ 125 MHz là bình thường Register read 1 ns ALU operation 2 ns Data cache access 2 ns Register write 1 ns Total 8 ns Single-cycle clock = 125 MHz So sánh với các bộ xử lý trên thị trường: Không tồi nếu so sánh độ trễ thực hiện 1 lệnh Một bộ xử lý 2.5 GHz với 20 giai đoạn pipeline có độ trễ khoảng: 0.4 ns/cycle 20 cycles = 8 ns Lưu lượng của bộ xử lý có pipeline tốt hơn rất nhiều: Tốt hơn tới 20 lần với các bộ xử lý phát hành đơn lệnh Tốt hơn tới 100 lần với các bộ xử lý phát hành đa lệnh 25 HUST-FET, 13/03/2011
  26. Thiết kế đa xung nhịp  Chia lệnh thành các pha thực hiện: IF, ID, EX, MEM, WB. Mỗi pha thực hiện trong 1 chu kỳ xung nhịp  Các ưu điểm o Thời gian thực hiện (= số pha) của mỗi lệnh được điều chỉnh tùy thuộc độ phức tạp của lệnh o Các khối chức năng được chia sẻ giữa các pha khác nhau của lệnh do một khối chức năng cụ thể không cần trong toàn bộ các pha thực hiện của lệnh Clock Time needed Time allotted Instr 1 Instr 2 Instr 3 Instr 4 Clock Time Time needed saved 3 cycles 5 cycles 3 cycles 4 cycles Time allotted Instr 1 Instr 2 Instr 3 Instr 4 26 HUST-FET, 13/03/2011
  27. Ví dụ 3.2 – Hiệu năng thiết kế đa xung nhịp Các loại lệnh sử dụng số chu kỳ khác nhau P Not ALU-type C used R-type 44% 4 cycles Load 24% 5 cycles Store 12% 4 cycles P Load C Branch 18% 3 cycles Jump 2% 3 cycles P Not Đóng góp vào số chu kỳ Store C used trung bình cần cho một lệnh: R-type P Not Not Not Branch used (and jr) C used used Load Store Branch Not Not Not Jump P Not used used used Jump (except C used ___ jr & jal) CPI trung bình  27 HUST-FET, 13/03/2011
  28. So sánh đánh giá thiết kế đa xung nhịp Đồng hồ tốc độ 500MHz tốt hơn 125MHz của Cycle time = 2 ns bộ xử lý một xung nhịp, nhưng vẫn là Clock rate = 500 MHz bình thường. R-type 44% 4 cycles Load 24% 5 cycles So sánh với các bộ xử lý trên thị trường: Store 12% 4 cycles Branch 18% 3 cycles Không tồi nếu so sánh độ trễ thực hiện 1 lệnh Jump 2% 3 cycles Một bộ xử lý 2.5 GHz với 20 giai đoạn pipeline có độ trễ khoảng: 0.4 ns/cycle 20 cycles = 8 ns Contribution to CPI R-type 0.44 4 = 1.76 Lưu lượng của bộ xử lý có pipeline tốt hơn rất nhiều: Load 0.24 5 = 1.20 Tốt hơn tới 20 lần với các bộ xử lý Store 0.12 4 = 0.48 phát hành đơn lệnh Branch 0.18 3 = 0.54 Jump 0.02 3 = 0.06 Tốt hơn tới 100 lần với các bộ xử lý ___ Average CPI  4.04 phát hành đa lệnh 28 HUST-FET, 13/03/2011
  29. Thiết kế đơn xung nhịp Clock rate = 125 MHz Incr PC Next addr CPI = 1 (125 MIPS) jta Next PC ALUOvfl (PC) PC rs (rs) Ovfl rt ALU Data Data Instr inst Reg out addr Data out 0 ALU 0 cache rd 1 file cache 1 2 2 31 (rt) Func Data 0 32 in / SE / 1 imm 16 op fn Register input RegDst ALUSrc DataRead RegInSrc Br&Jump RegWrite ALUFunc DataWrite 29 HUST-FET, 13/03/2011
  30. Thiết kế đa xung nhịp Clock rate = 500 MHz CPI  4 ( 125 MIPS) 26 30 / / 0 4 MSBs SysCallAddr 1 30 ALUZero Inst Reg jta x Reg x Mux ALUOvfl Address rs (rs) 0 PC rt Zero z Reg 4 1 Ovfl 0 0 rd 1 1 0 2 Reg Cache 31 ALU 2 1 file y Mux 3 0 (rt) 4 0 Func Data 1 1 2 2 ALU out 4 3 Data Reg imm 16 32 y Reg / SE / op fn Inst Data MemWrite RegInSrc ALUSrcX ALUFunc PCSrc PCWrite MemRead IRWrite RegDst RegWrite ALUSrcY JumpAddr 30 HUST-FET, 13/03/2011
  31. Đường ống (Eng. pipeline): Kết hợp ưu điểm Pipelined: Clock rate = 500 MHz CPI  1 Single-cycle: Multicycle: Clock rate = 125 MHz Clock rate = 500 MHz CPI = 1 CPI  4 31 HUST-FET, 13/03/2011
  32. Dây chuyền sản xuất trong nhà máy 32 HUST-FET, 13/03/2011
  33. Tăng hiệu năng (tốc độ) bằng cách nào?  Bắt đầu nạp và thực hiện lệnh tiếp theo trước khi lệnh hiện tại kết thúc: • Kỹ thuật đường ống – được áp dụng trong hầu hết các bộ xử lý hiện đại • Trong điều kiện lý tưởng với số lượng lệnh lớn, đường ống giúp tăng tốc độ bằng số giai đoạn đường ống. Đường ống 5 giai đoạn sẽ nhanh hơn gần 5 lần vì Tc tăng gấp 5. Tcpu I CPI Tc  Nạp (và thực hiên) nhiều lệnh cùng một lúc  Xử lý superscalar 33 HUST-FET, 13/03/2011
  34. 5 giai đoạn đường ống của lệnh lw Cycle 1 Cycle 2 Cycle 3 Cycle 4 Cycle 5 lw IFetch Dec Exec Mem WB  IFetch: Nạp lệnh và cập nhập giá trị PC  IDec: Đọc thanh ghi và giải mã lệnh  EXec: Thực hiện lệnh R; tính địa chỉ bộ nhớ  MEM: Đọc/ghi bộ nhớ dữ liệu  WB: Ghi kết quả vào tệp thanh ghi 34 HUST-FET, 13/03/2011
  35. Đường ống trong MIPS  Bắt đầu lệnh tiếp theo trước khi lệnh hiện tại kết thúc  cải thiện thông lượng – tổng số công việc hoàn thành trong 1 khoảng thời gian  độ trễ lệnh (thời gian thực hiện, thời gian đáp ứng – thời gian từ lúc bắt đầu đến lúc kết thúc lệnh) không được giảm Cycle 1 Cycle 2 Cycle 3 Cycle 4 Cycle 5 Cycle 6 Cycle 7 Cycle 8 lw IFetch Dec Exec Mem WB sw IFetch Dec Exec Mem WB R-type IFetch Dec Exec Mem WB  chu kỳ đồng hồ (thời gian 1 giai đoạn đường ống) quyết định bởi giai đoạn chậm nhất  một số giai đoạn không dùng toàn bộ chu kỳ đồng hồ (VD., WB)  một số lệnh, có các giai đoạn là chu kỳ lãng phí (nghĩa là, không thực hiện gì trong chu kỳ đó với lệnh đó) 35 HUST-FET, 13/03/2011
  36. Ví dụ 3.3 – Pipeline vs. Đơn xung nhịp Triển khai đơn xung nhịp (Tc = 800 ps): Cycle 1 Cycle 2 Clk lw sw Waste Triển khai pipeline (Tc = 200 ps): 400 ps lw IFetch Dec Exec Mem WB sw IFetch Dec Exec Mem WB R-type IFetch Dec Exec Mem WB  Để hoàn thành 1 lệnh trong trường hợp pipeline cần 1000 ps (So với 800 ps trong trường hợp đơn xung nhịp). Tại sao?  Để thực hiên 1.000.000 lệnh “adds” cần thời gian bao lâu? 36 HUST-FET, 13/03/2011
  37. Kỹ thuật đường ống cho MIPS(RISC) ISA  Dễ triển khai:  Các lệnh có cùng độ dài (32 bits) Có thể nạp lệnh trong giai đoạn 1st và giải mã lệnh trong giai đoạn 2nd  Ít định dạng lệnh (ba). Các định dạng lệnh có tính đối xứng - Có thể đọc thanh ghi ở giai đoạn 2nd  Chỉ truy cập bộ nhớ bằng lệnh lw và sw - Có thể tính địa chỉ bộ nhớ ở giai đoạn EX (thực hiện lệnh)  Mỗi lệnh chỉ ghi lớn nhất 1 kết quả (làm thay đổi trạng thái máy) ở 2 giai đoạn cuối (MEM or WB)  Toán hạng được sắp xếp trong bộ nhớ sao cho 1 lệnh dịch chuyển dữ liệu chỉ cần 1 lần truy cập bộ nhớ. 37 HUST-FET, 13/03/2011
  38. Đường dữ liệu MIPS pipeline  Thanh ghi trạng thái giữa các giai đoạn thực hiện lệnh để phân cách IF:IFetch ID:Dec EX:Execute MEM: WB: MemAccess WriteBack IF/ID ID/EX EX/MEM Add 4 Shift Add MEM/WB left 2 Instruction Read Addr 1 Register Read Data Memory Read Addr 2Data 1 Memory Read File Read PC Address ALU Address Write Addr Read Data Data 2 Write Data Write Data Sign 16 Extend 32 System Clock 38 HUST-FET, 13/03/2011
  39. Điều khiển MIPS pipeline  Các tín hiệu điều khiển được xác định trong giai đoạn giải mã và được lưu trong các thanh ghi trạng thái giữa các giai đoạn pipeline PCSrc ID/EX EX/MEM Control IF/ID Add Branch MEM/WB Add 4 RegWrite Shift left 2 Instruction Read Addr 1 Register Read Data Memory Read Addr 2Data 1 Memory MemtoReg ALUSrc Read File Read PC Address Write Addr ALU Address Read Data Data 2 Write Data Write Data ALU cntrl Sign MemRead Extend 16 32 ALUOp RegDst 39 HUST-FET, 13/03/2011
  40. Mô tả hoạt động pipeline ALU IM Reg DM Reg  Đo hiệu năng: Cần bao nhiêu chu kỳ đề thực hiện đoạn mã?  Phân tích hoạt động: ALU làm gì ở chu kỳ 4?  Cải tiến: Có xảy ra hazard không? Tại sao? Dùng cách nào để khắc phục? 40 HUST-FET, 13/03/2011
  41. Hiệu năng pipeline Time (clock cycles) ALU Khi pipeline I Inst 0 IM Reg DM Reg đầy, 1 lệnh n được hoàn s ALU thành trong t Inst 1 IM Reg DM Reg 1 chu kỳ r. CPI = 1 ALU O Inst 2 IM Reg DM Reg r d ALU e Inst 3 IM Reg DM Reg r ALU Inst 4 IM Reg DM Reg Thời gian điền đầy pipeline 41 HUST-FET, 13/03/2011
  42. Xung đột Pipeline  Xung đột cấu trúc: yêu cầu sử dụng cùng một tài nguyên cho 2 lệnh khác nhau tại cùng 1 thời điểm  Xung đột dữ liệu: yêu cầu sử dụng dữ liệu trước khi nó sẵn sàng Các toán hạng nguồn của 1 lệnh được tạo ra bởi lệnh phía trước vẫn đang nằm trong pipeline  Xung đột điều khiển: yêu cầu quyết định điều khiển dòng chương trình trước khi điều kiện rẽ nhánh và giá trị PC mới được tính toán Các lệnh rẽ nhánh, nhảy và ngắt  Giải quyết xung đột bằng cách chờ đợi  Khối điều khiển pipeline cần phát hiện xung đột  Và hành động để giải quyết xung đột 42 HUST-FET, 13/03/2011
  43. Bộ nhớ đơn: Xung đột cấu trúc Time (clock cycles) ALU Đọc dữ liệu từ bộ I lw Mem Reg Mem Reg nhớ n s ALU t Inst 1 Mem Reg Mem Reg r. ALU O Inst 2 Mem Reg Mem Reg r d ALU e Inst 3 Mem Reg Mem Reg r ALU Inst 4 Đọc lệnh từ bộ nhớ Mem Reg Mem Reg  Sửa: Bộ nhớ dữ liệu và lệnh riêng rẽ(I$ and D$) 43 HUST-FET, 13/03/2011
  44. Xung đột cấu trúc khi truy cập tệp thanh ghi ALU Sửa xung đột truy I add $1, IM Reg DM Reg cập tệp thanh ghhi n bằng cách đọc s ALU trong nửa đầu chu t Inst 1 IM Reg DM Reg kỳ và ghi trong nửa r. sau chu kỳ ALU O Inst 2 IM Reg DM Reg r d ALU e add $2,$1, IM Reg DM Reg r Sườn đồng hồ điều Sườn đồng hồ điều khiển ghi khiển đọc 44 HUST-FET, 13/03/2011
  45. Sử dụng thanh ghi: Xung đột dữ liệu  Phụ thuộc dữ liệu ngược theo thời gian gây ra xung đột ALU I add $1, IM Reg DM Reg n s ALU t sub $4,$1,$5 IM Reg DM Reg r. ALU O and $6,$1,$7 IM Reg DM Reg r d ALU e or $8,$1,$9 IM Reg DM Reg r ALU xor $4,$1,$5 IM Reg DM Reg  Xung đột đọc trước khi ghi (Read before write) 45 HUST-FET, 13/03/2011
  46. Sử dụng thanh ghi: Xung đột dữ liệu  Phụ thuộc dữ liệu ngược theo thời gian gây ra xung đột ALU I add $1, IM Reg DM Reg n s ALU t sub $4,$1,$5 IM Reg DM Reg r. ALU O and $6,$1,$7 IM Reg DM Reg r d ALU e or $8,$1,$9 IM Reg DM Reg r ALU xor $4,$1,$5 IM Reg DM Reg  Xung đột đọc trước khi ghi (Read before write) 46 HUST-FET, 13/03/2011
  47. Đọc từ bộ nhớ: Gây xung đột dữ liệu  Dependencies backward in time cause hazards ALU IM DM Reg I lw $1,4($2) Reg n s ALU t sub $4,$1,$5 IM Reg DM Reg r. ALU O and $6,$1,$7 IM Reg DM Reg r d ALU e or $8,$1,$9 IM Reg DM Reg r ALU xor $4,$1,$5 IM Reg DM Reg  Load-use data hazard 47 HUST-FET, 13/03/2011
  48. Xung đột điều khiển  Dependencies backward in time cause hazards ALU I beq IM Reg DM Reg n s ALU t lw IM Reg DM Reg r. ALU O Inst 3 IM Reg DM Reg r d ALU e Inst 4 IM Reg DM Reg r 48 HUST-FET, 13/03/2011
  49. Các cấu trúc pipeline khác  Phép toán nhân (chậm) gấp 2 lần?  Làm đồng hồ chậm đi 2 lần hoặc  thực hiện trong 2 chu kỳ đồng hồ (vì không cần sử dụng giai đoạn DM) MUL ALU IM Reg DM Reg  Truy cập bộ nhớ dữ liệu chậm hơn bộ nhớ lệnh 2 lần?  Làm đồng hồ chậm đi 2 lần hoặc  thực hiện việc đọc trong 2 chu kỳ (và giữ nguyên chu kỳ đồng hồ) ALU IM Reg DM1 DM2 Reg 49 HUST-FET, 13/03/2011
  50. Tóm tắt 1  Các bộ xử lý hiện đại đều dùng kỹ thuật pipeline  Pipelining không làm giảm độ trễ của 1 nhiệm vụ đơn lẻ, nó giúp tăng thông lượng của toàn bộ  Tăng tốc tiềm năng: CPI = 1 và đồng hồ nhanh, Tc nhỏ  Tốc độ đồng hồ bị hạn chế bởi giai đoạn pipeline chậm nhất  Các giai đoạn pipeline không cân bằng làm giảm hiệu suất  Thời gian “làm đầy” pipeline và thời gian “làm trống” pipeline ảnh hưởng đến độ tăng tốc khi pipeline sâu (nhiều giai đoạn) và đoạn mã ngắn  Cần phát hiện và giải quyết xung đột  Dừng ảnh hưởng xấu tới CPI (làm CPI lớn hơn giá trị lý tưởng 1) 50 HUST-FET, 13/03/2011
  51. Xung đột dữ liệu  Xung đột dữ liệu đọc trước ghi Value of $1 10 10 10 10 10/-20 -20 -20 -20 -20 ALU add $1, IM Reg DM Reg ALU sub $4,$1,$5 IM Reg DM Reg ALU and $6,$1,$7 IM Reg DM Reg ALU or $8,$1,$9 IM Reg DM Reg ALU xor $4,$1,$5 IM Reg DM Reg 51 HUST-FET, 13/03/2011
  52. Giải quyết xung đột: Tạm dừng Có thể giải ALU quyết xung đột add $1, IM Reg DM Reg I dữ liệu bằng n dừng chờ– stall s – ảnh hưởng t stall r. tới CPI O stall r d ALU e sub $4,$1,$5 IM Reg DM Reg r ALU and $6,$1,$7 IM Reg DM Reg 52 HUST-FET, 13/03/2011
  53. Giải quyết xung đột: Chuyển tiếp dữ liệu Giải quyết xung ALU đột dữ liệu bằng add $1, IM Reg DM Reg I chuyển tiếp kết n quả ngay khi s ALU chúng sẵn sàng t sub $4,$1,$5 IM Reg DM Reg r. tới nơi cần O ALU r and $6,$1,$7 IM Reg DM Reg d e ALU r or $8,$1,$9 IM Reg DM Reg ALU xor $4,$1,$5 IM Reg DM Reg 53 HUST-FET, 13/03/2011
  54. Chuyển tiếp dữ liệu  Lấy kết quả ở thời điểm nó xuất hiện sớm nhất trong bất kỳ thanh ghi pipeline nào, và chuyển tiếp nó đến khối chức năng (VD. ALU) mà cần kết quả tại chu kỳ đồng hồ đó  Với khối chức năng ALU: đầu vào có thể từ bất kỳ thanh ghi pipeline nào chứ không cần từ ID/EX bằng cách  thêm bộ chọn vào trước đầu vào của ALU  nối dữ liệu ghi Rd ở EX/MEM hoặc MEM/WB tới một trong 2 hoăc cả 2 thanh ghi pipeline Rs và Rt thuộc giai đoạn EX.  thêm phần điều khiển phần cứng để điều khiển bộ chọn  Các khối chức năng khác cũng cần được thêm tương tự (VD. DM)  Với chuyển tiếp có thể đạt được CPI = 1 ngay khi có sự phụ thuộc dữ liệu 54 HUST-FET, 13/03/2011
  55. Minh họa triển khai chuyển tiếp ALU I add $1, IM Reg DM Reg n s ALU t sub $4,$1,$5 IM Reg DM Reg r. O ALU r and $6,$7,$1 IM Reg DM Reg d e r EX forwarding MEM forwarding 55 HUST-FET, 13/03/2011
  56. Xung đột dữ liệu khi chuyển tiếp  Một loại xung đột dữ liệu xuất hiện khi chuyển tiếp: Xung đột giữa kết quả của lệnh đang ở giai đoạn WB và lệnh đang ở giai đoạn MEM – kết quả nào cần được chuyển tiếp? I ALU add $1,$1,$2 IM Reg DM Reg n s t r. ALU add $1,$1,$3 IM Reg DM Reg O r ALU d add $1,$1,$4 IM Reg DM Reg e r 56 HUST-FET, 13/03/2011
  57. Xung đột dữ liệu khi có lệnh lw ALU IM Reg DM Reg I lw $1,4($2) n ALU s IM Reg DM Reg t sub $4,$1,$5 r. ALU IM Reg DM Reg O and $6,$1,$7 r ALU d IM Reg DM Reg e or $8,$1,$9 r ALU xor $4,$1,$5 IM Reg DM Reg ALU IM Reg DM 57 HUST-FET, 13/03/2011
  58. Xung đột điều khiển  Khi địa chỉ các lệnh không tuần tự (i.e., PC = PC + 4); xuất hiện khi có các lệnh thay đổi dòng chương trình  Lệnh rẽ nhánh không điều kiện (j, jal, jr)  Lệnh rẽ nhánh có điều kiện (beq, bne)  Ngắt, Exceptions  Giải pháp  Tạm dừng (ảnh hưởng CPI)  Tín toán điều kiện rẽ nhánh càng sớm càng tốt trong giai đoạn pipeline giảm số chu kỳ phải dừng  Rẽ nhánh chậm (Delayed branches - Cần hỗ trợ của trình dịch)  Dự đoán và hy vọng điều tốt nhất!  Xung đột điều khiển ít xảy ra, nhưng không có giải pháp giải quyết hiệu quả như chuyển tiếp đối với xung đột dữ liệu 58 HUST-FET, 13/03/2011
  59. Lệnh nhảy: Cần một chu kỳ dừng  Lệnh nhảy không được giải mã cho đến giai đoạn ID, cần một lệnh xóa (flush)  Để xóa, đặt trường mã lệnh của thanh ghi pipeline IF/ID bằng 0 (làm nó trở thành 1 lệnh noop) ALU Giải quyết I j IM Reg DM Reg n xung đột s lệnh nhảy t ALU bằng cách flush IM Reg DM Reg r. chờ – flush ALU O j target IM Reg DM Reg r d e r  Lệnh nhảy rất ít xuất hiện – chỉ chiếm 3% số lệnh trong SPECint 59 HUST-FET, 13/03/2011
  60. Xung đột điều khiển lệnh rẽ nhánh ALU I beq IM Reg DM Reg n s ALU t lw IM Reg DM Reg r. ALU O Inst 3 IM Reg DM Reg r d ALU e Inst 4 IM Reg DM Reg r 60 HUST-FET, 13/03/2011
  61. Giải quyết xung đột điều khiển lệnh rẽ nhánh ALU Giải quyết I beq IM Reg DM Reg xung đột n bằng chờ– s ALU flush – t flush IM Reg DM Reg nhưng ảnh r. ALU hưởng CPI IM Reg DM Reg O flush r ALU d IM Reg DM Reg e flush r ALU beq target IM Reg DM Reg ALU IM Reg DM Inst 3 61 HUST-FET, 13/03/2011
  62. Giải quyết xung đột điều khiển lệnh rẽ nhánh  Tính toán điều kiện rẽ nhánh càng sớm càng tốt, tức là trong giai đoạn giải mã chỉ cần 1 chu kỳ chờ ALU IM DM Reg Fix branch I beq Reg n hazard by waiting – s ALU t flush IM Reg DM Reg flush r. ALU O IM Reg DM Reg r beq target d ALU e IM Reg DM r Inst 3 62 HUST-FET, 13/03/2011
  63. Rẽ nhánh chậm  Nếu phần cứng cho rẽ nhánh nằm ở giai đoạn ID, ta có thể loại bỏ các chu kỳ chờ rẽ nhánh bằng cách sử dụng rẽ nhánh chậm (delayed branches) – luôn thực hiện lệnh theo sau lệnh lệnh rẽ nhánh – rẽ nhánh có tác dụng sau lệnh kế tiếp nó  Trình dịch MIPS compiler chuyển 1 lệnh an toàn (không bị ảnh hưởng bởi lệnh rẽ nhánh) tới sau lệnh rẽ nhánh (vào khe trễ). Vì vậy sẽ dấu được sự rẽ nhánh chậm  Với pipeline sâu (nhiều giai đoạn), trễ rẽ nhánh tăng cần nhiều lệnh được chèn vào sau lệnh rẽ nhánh  Rẽ nhánh chậm đang được thay thế bởi các phương pháp khác tốn kém hơn nhưng mềm dẻo (động) hơn như dự đoán rẽ nhánh  Sự phát triển của IC cho phép có bộ dự đoán rẽ nhánh ít tốn kém hơn 63 HUST-FET, 13/03/2011
  64. Sắp xếp lệnh trong rẽ nhánh chậm A. Từ trước lệnh rẽ nhánh B. Từ đích lệnh rẽ nhánh C. Từ nhánh sai add $1,$2,$3 sub $4,$5,$6 add $1,$2,$3 if $2=0 then if $1=0 then delay slot delay slot add $1,$2,$3 if $1=0 then delay slot sub $4,$5,$6 becomes becomes becomes add $1,$2,$3 if $2=0 then if $1=0 then add $1,$2,$3 sub $4,$5,$6 add $1,$2,$3 if $1=0 then sub $4,$5,$6  TH A là lựa chọn tốt nhất, điền được khe trễ và giảm I  TH B và C, lệnh sub cần sao lại, tăng I  TH B và C, phải đảm bảo thực hiện lệnh sub không ảnh hưởng khi không rẽ nhánh 64 HUST-FET, 13/03/2011
  65. Dự đoán rẽ nhánh tĩnh  Giải quyết xung đột rẽ nhánh bằng cách giả sử 1 hướng rẽ nhánh và tiếp tục không cần chờ tính toán kết quả rẽ nhánh thực sự. 1. Đoán không rẽ nhánh – luôn giả sử lệnh không rẽ nhánh, tiếp tục nạp các lệnh kế tiếp, chỉ khi có rẽ nhánh thì cần dừng pipeline  Nếu rẽ nhánh, xóa các lệnh sau rẽ nhánh (sớm ở trong pipeline) - trong giai đoạn IF, ID, và EX nếu bộ tính rẽ nhánh ở MEM – ba dừng - trong giai đoạn IF và ID nếu bộ tính rẽ nhánh ở EX – hai dừng - trong giai đoạn IF nếu bộ tính rẽ nhánh ở ID – môt dừng  Đảm bảo rằng các lệnh bị xóa không ảnh hưởng tới trạng thái máy.  Khởi tạo lại pipeline ở đích lệnh rẽ nhánh 65 HUST-FET, 13/03/2011
  66. Xóa khi dự đoán sai ALU IM Reg DM Reg I 4 beq $1,$2,2 n s ALU IM Reg DM Reg t 8 sub $4,$1,$5 r. O r d e r 66 HUST-FET, 13/03/2011
  67. Xóa khi dự đoán sai (Đoán không rẽ nhánh) ALU IM Reg DM Reg I 4 beq $1,$2,2 n s ALU IM Reg DM Reg t 8 flushsub $4,$1,$5 r. ALU IM Reg DM Reg O 16 and $6,$1,$7 r d ALU e 20 or r8,$1,$9 IM Reg DM Reg r  Để xóa, đặt trường mã lệnh của thanh ghi pipeline IF/ID bằng 0 (làm nó trở thành 1 lệnh noop) 67 HUST-FET, 13/03/2011
  68. Dự đoán rẽ nhánh  Giải quyết xung đột bằng cách giả thiết kết quả rẽ nhánh và tiếp tục 2. Đoán có rẽ nhánh – dữ đoán luôn luôn có rẽ nhánh  Đoán có rẽ nhánh luôn cần 1 chu kỳ dừng (nếu phần cứng tính rẽ nhánh ở giai đoạn ID)  Cần phương pháp đọc trước (vào bộ đệm) lệnh ở địa chỉ đích??  Vì thiệt hại do rẽ nhánh đang tăng lên (với các pipeline sâu), mô hình dự đoán rẽ nhánh tĩnh sẽ ảnh hưởng tới hiệu năng. Với nhiều phần cứng hơn, có thể thử dự đoán hoạt động rẽ nhánh động lúc chương trình được thực hiện 3. Dự đoán rẽ nhánh động – đoán rẽ nhánh lúc chạy dựa trên các thông tin chạy (run-time information) 68 HUST-FET, 13/03/2011
  69. Dự đoán rẽ nhánh động bằng 1 bit  Bô dự đoán 1 bít sẽ sai 2 lần nếu đoán không rẽ nhánh:  Giá sử predict_bit = 0 lúc bắt đầu (chỉ ra không rẽ nhánh) lệnh rẽ nhánh điều khiển ở cuối vòng lặp Loop: 1st loop instr 2nd loop instr 1. Lần thực hiện vòng lặp 1, bộ dự đoán sai . cho lệnh rẽ nhánh vì nó dẫn quay lại đầu . vòng lặp; cần đảo bít rẽ nhánh (predict_bit . = 1) last loop instr bne $1,$2,Loop 2. Khi nào vẫn còn rẽ nhánh (vẫn lặp), dự fall out instr đoán đúng 3. Khi thoát khỏi vòng lặp, bộ dự đoán sẽ sai 1 lần nữa vì lần này sẽ không rẽ nhánh mà ra ngoài vòng lặp; đảo bit rẽ nhánh (predict_bit = 0)  Nếu lặp 10 lần ta sẽ có tỉ lệ rẽ nhánh đúng là 80%. Nếu dùng lệnh rẽ nhánh beq thì đúng 90% 69 HUST-FET, 13/03/2011
  70. Dự đoán rẽ nhánh động bằng 2 bit  Cơ chế dùng 2 bit cho độ chính xác 90% vì chỉ khi dự đoán sai 2 lần thì bit dự đoán mới thay đổi Loop: 1st loop instr 2nd loop instr . Taken . Not taken . Predict Predict last loop instr Taken Taken bne $1,$2,Loop Taken fall out instr Taken Not taken Not taken Predict Predict Not Taken Not Taken Taken Not taken 70 HUST-FET, 13/03/2011
  71. Exceptions  Exceptions (ngắt - interrupts) có thể coi là 1 dạng xung đột dữ liệu. Exception xuất hiện từ:  Tràn khi thực hiện lệnh số học  Lệnh không được định nghĩa  Yêu cầu từ thiết bị vào ra  Yêu cầu dịch vụ hệ điều hành (VD. lỗi trang, lỗi TLB)  Lỗi chức năng phần cứng  Pipeline cần phải: • dừng thực hiện lệnh lỗi, • để tất cả các lệnh trước đó hoàn thành, • xóa các lệnh sau đó, • đặt thanh ghi chỉ ra nguyên nhân exception, • lưu lại địa chỉ lệnh lỗi, • nhảy đến địa chỉ định trước (địa chỉ của hàm xử lý exception)  Phần mềm (OS) sẽ xử lý tiếp exception. 71 HUST-FET, 13/03/2011
  72. Hai loại exceptions  Ngắt – không đồng bộ với sự thực hiện chương trình  gây ra bởi sự kiện bên ngoài  có thể được xử lý giữa các lệnh, nên để các lệnh đang có trong pipeline hoàn thành trước khi chuyển điều khiển cho hàm xử lý ngắt của OS.  đơn giản là dừng và tiếp tục chương trình người dùng  Bẫy (Exception) – đồng bộ với sự thực hiện chương trình  gây ra bởi sự kiện bên trong  hàm xử lý bẫy cần sửa chữa điều kiện cho đúng lệnh bị bẫy, nên phải dừng lệnh lỗi trong trong pipeline và chuyển điều khiển cho hàm xử lý bẫy của OS  lệnh lỗi có thể tiếp tục chương trình có thể bị kết thúc hoặc được tiếp tục 72 HUST-FET, 13/03/2011
  73. Exception có thể xuất hiện ở đâu trong pipeline ALU IM Reg DM Reg Stage(s)? Synchronous?  Tràn số học  Lệnh không định nghĩa  Lỗi TLB hoặc trang  Yêu cầu dịch vụ I/O  Lỗi phần cứng 73 HUST-FET, 13/03/2011
  74. Exception có thể xuất hiện ở đâu trong pipeline ALU IM Reg DM Reg Stage(s)? Synchronous?  Tràn số học EX yes  Lệnh không định nghĩa ID yes  Lỗi TLB hoặc trang IF, MEM yes  Yêu cầu dịch vụ I/O any no  Lỗi phần cứng any no  Chú ý rằng nhiều exception có thể xuất hiện đồng thời trong một chu kỳ đồng hồ 74 HUST-FET, 13/03/2011
  75. Nhiều exception đồng thời ALU I Inst 0 IM Reg DM Reg n s ALU t Inst 1 IM Reg DM Reg r. ALU O Inst 2 IM Reg DM Reg r d ALU e Inst 3 IM Reg DM Reg r ALU Inst 4 IM Reg DM Reg  Lệnh sớm nhất sẽ bị ngắt đầu tiên 75 HUST-FET, 13/03/2011
  76. Nhiều exception đồng thời ALU I Inst 0 IM Reg DM Reg n D$ page fault s ALU t Inst 1 IM Reg DM Reg r. arithmetic overflow ALU O Inst 2 IM Reg DM Reg r d undefinedALU instruction e Inst 3 IM Reg DM Reg r ALU Inst 4 IM Reg DM Reg I$ page fault  Lệnh sớm nhất sẽ bị ngắt đầu tiên 76 HUST-FET, 13/03/2011
  77. Tổng kết  Tất cả các bộ xử lý hiện đại đều dùng pipeline để tăng hiệu suất (CPI=1 và đồng hồ nhanh - fc lớn)  Tốc độ đồng hồ pipeline bị giới hạn bởi giai đoạn pipeline chậm nhất – thiết kế pipeline cân bằng là rất quan trọng  Cần phát hiện và giải quyết xung đột trong pipeline  Xung cấu trúc – giải quyết: thiết kế pipeline đúng  Xung đột dữ liệu - Dừng (ảnh hưởng CPI) - Chuyển tiếp (cần phần cứng hỗ trợ)  Xung đột điều khiển – đặt phần cứng quyết định rẽ nhánh lên các trạng thái đầu trong pipeline - Dừng (ảnh hưởng CPI) - Rẽ nhánh chậm (cần hỗ trợ của trình dịch) - Dự đoán rẽ nhánh tĩnh và động (cần phần cứng hỗ trợ)  Xử lý ngắt trong pipeline phức tạp 77 HUST-FET, 13/03/2011