Bài giảng môn Kiến trúc máy tính - Chương 4: Bộ xử lý

t.)
  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
4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 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 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
 4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 90
 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
 4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 91
 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
 4/5/2019 Faculty of Computer Science & Engineering 92
 2-Bit Predictor
  Only change prediction on two 
 successive mispredictions
BK
TP.HCM
4/5/2019 Faculty of Computer Science & Engineering 93
 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
 4/5/2019 Faculty of Computer Science & Engineering 94
 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
 4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 95
 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
 4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 96
 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
 4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 97
 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
4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 98
 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
 4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 99
 Cơ chế ống với ngoại lệ
 BK
TP.HCM
 4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 100
 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
 4/5/2019 Faculty of Computer Science & Engineering 101
 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
4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 102
 Ví dụ: Ngoại lệ
 BK
TP.HCM
 4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 103
 Ví dụ: Ngoại lệ (tt.)
 BK
TP.HCM
 4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 104
 Đ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
4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 105
 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
 4/5/2019 Faculty of Computer Science & Engineering 106
 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
 4/5/2019 Faculty of Computer Science & Engineering 107
 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
4/5/2019 Faculty of Computer Science & Engineering 108
 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
 4/5/2019 Faculty of Computer Science & Engineering 109
 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
 4/5/2019 Faculty of Computer Science & Engineering 110
 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
 4/5/2019 Faculty of Computer Science & Engineering 111
 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
 4/5/2019 Faculty of Computer Science & Engineering 112
 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
 4/5/2019 Faculty of Computer Science & Engineering 113
 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
 4/5/2019 Faculty of Computer Science & Engineering 114
 MIPS with Static Dual Issue
 BK
TP.HCM
 4/5/2019 Faculty of Computer Science & Engineering 115
 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
4/5/2019 Faculty of Computer Science & Engineering 116
 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
 4/5/2019 Faculty of Computer Science & Engineering 117
 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
 4/5/2019 Faculty of Computer Science & Engineering 118
 Loop Unrolling Example
  IPC = 14/8 = 1.75
  Closer to 2, but at cost of registers and code size
 BK
TP.HCM
 4/5/2019 Faculty of Computer Science & Engineering 119
 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
4/5/2019 Faculty of Computer Science & Engineering 120
 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
 4/5/2019 Faculty of Computer Science & Engineering 121
 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
 Faculty of Computer Science & Engineering 122
 4/5/2019
 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
4/5/2019 Faculty of Computer Science & Engineering 123
 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
 4/5/2019 Faculty of Computer Science & Engineering 124
 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
4/5/2019 Faculty of Computer Science & Engineering 125
 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
 4/5/2019 Faculty of Computer Science & Engineering 126
 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
 4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 127
 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
 4/5/2019 Khoa Khoa học & Kỹ thuật Máy tính 128