处理器设计：如何实现MIPS 的简单规律性

1 . ECE4680 Computer Organization and Architecture Designing a Single Cycle Datapath Processor Design: How to Implement MIPS Simplicity favors regularity ECE4680 Datapath.1 2003-3-19 The Big Picture: Where are We Now? °The Five Classic Components of a Computer Processor Input Control Memory Datapath Output °Today’s Topic: Datapath Design • What is data? • What is datapath? ECE4680 Datapath.2 2003-3-19 

2 . The Big Picture: The Performance Perspective °Performance of a machine was determined by: • Instruction count • Clock cycle time • Clock cycles per instruction °Processor design (datapath and control) will determine: • Clock cycle time • Clock cycles per instruction °In the next two lectures: • Single cycle processor: - Advantage: One clock cycle per instruction - Disadvantage: long cycle time ECE4680 Datapath.3 2003-3-19 The MIPS Instruction Formats °All MIPS instructions are 32 bits long. The three instruction formats: 31 26 21 16 11 6 0 • R-type op rs rt rd shamt funct 6 bits 5 bits 5 bits 5 bits 5 bits 6 bits 31 26 21 16 0 • I-type op rs rt immediate 6 bits 5 bits 5 bits 16 bits • J-type 31 26 0 op target address 6 bits 26 bits °The different fields are: • op: operation of the instruction • rs, rt, rd: the source and destination register specifiers • shamt: shift amount • funct: selects the variant of the operation in the “op” field • address / immediate: address offset or immediate value • target address: target address of the jump instruction ECE4680 Datapath.4 2003-3-19 

3 . The MIPS Subset 31 26 21 16 11 6 0 °ADD and subtract op rs rt rd shamt funct • add rd, rs, rt 6 bits 5 bits 5 bits 5 bits 5 bits 6 bits • sub rd, rs, rt 31 26 21 16 0 °OR Immediate: op rs rt immediate • ori rt, rs, imm16 6 bits 5 bits 5 bits 16 bits °LOAD and STORE • lw rt, rs, imm16 • sw rt, rs, imm16 °BRANCH: • beq rs, rt, imm16 °JUMP: 31 26 0 • j target op target address 6 bits 26 bits ECE4680 Datapath.5 2003-3-19 An Abstract View of the Implementation Two types of functional units –Operational element that operate on data (combinational) –State element that contain data (sequential) •Generic Implementation: Clk PC –use PC to supply instruction address –get the instruction from memory Instruction Address –read registers –use the instruction to decide exactly what to do Ideal Instruction bus •All instructions use the ALU after reading the registers Instruction Memory Rd Rs Rt Imm – Why? memory-reference? arithmetic? control flow? 5 5 5 16 Data Rw Ra Rb 32 Address 32 32 Ideal DataOut ALU 32 32-bit Data Registers Data Memory Clk In Clk 32 Next step: to fill in the details: more units, more connections, and control unit ECE4680 Datapath.6 2003-3-19 

4 . State Elements ° Unclocked vs. Clocked ° Clocks used in synchronous logic • when should an element that contains state be updated? falling edge cycle time rising edge ECE4680 Datapath.7 2003-3-19 An unclocked state element ° The set-reset latch • output depends on present inputs and also on past inputs R Q __ Q S ECE4680 Datapath.8 2003-3-19 

5 . Latches and Flip-flops ° Output is equal to the stored value inside the element (don't need to ask for permission to look at the value) ° Change of state (value) is based on the clock ° Latches: whenever the inputs change, and the clock is asserted ° Flip-flop: state changes only on a clock edge (edge-triggered methodology) "logically true", — could mean electrically low A clocking methodology defines when signals can be read and written — wouldn't want to read a signal at the same time it was being written ECE4680 Datapath.9 2003-3-19 D-latch and D flip-flop Two inputs: • the data value to be stored (D) • the clock signal (C) indicating when to read & store D • Output changes when C is high C D Q C _ Q D Q Output changes only on the clock edge D D Q D Q Q D D latch latch _ _ D C C Q Q C C Q ECE4680 Datapath.10 2003-3-19 

6 . Clocking Methodology (Appendix B.7) Clk Setup Hold Setup Hold Don’t Care . . . . . . . . . . . . °All storage elements are clocked by the same clock edge • Edge-trigged: all stored values are updated on a clock edge °Cycle Time = Latch Prop + Longest Delay Path + Setup + Clock Skew °(Latch Prop + Shortest Delay Path - Clock Skew) > Hold Time ECE4680 Datapath.11 2003-3-19 An Abstract View of the Critical Path °Register file and ideal memory: • The CLK input is a factor ONLY during write operation • During read operation, behave as combinational logic: - Address valid => Output valid after “access time.” Clk Critical Path (Load Operation) = PC PC’s prop time + Instruction Address Instruction Memory’s Access Time + Register File’s Access Time + ALU to Perform a 32-bit Add + Ideal Instruction bus Data Memory Access Time + Instruction Setup Time for Register File Write + Memory Rd Rs Rt Imm 5 5 5 16 Clock Skew Data Rw Ra Rb 32 Address 32 32 Ideal DataOut ALU 32 32-bit Data Registers Data Memory Clk In Clk 32 ECE4680 Datapath.12 2003-3-19 

7 . The Steps of Designing a Processor °Instruction Set Architecture => Register Transfer Language °Register Transfer Language (RTL) => • Datapath components • Datapath interconnect °Datapath components => Control signals °Control signals => Control logic po nent Element < com ECE4680 Datapath.13 2003-3-19 What is RTL: The ADD Instruction Register Transfer Language °add rd, rs, rt • mem[PC] Fetch the instruction from memory • R[rd] R[rs] + R[rt] The ADD operation • PC PC + 4 Calculate the next instruction’s address ECE4680 Datapath.14 2003-3-19 

8 . What is RTL: The Load Instruction °lw rt, rs, imm16 • mem[PC] Fetch the instruction from memory • Addr R[rs] + SignExt(imm16) Calculate the memory address • R[rt] Mem[Addr] Load the data into the register • PC PC + 4 Calculate the next instruction’s address ECE4680 Datapath.15 2003-3-19 Combinational Logic Elements CarryIn °Adder A 32 Adder Sum 32 B Carry 32 °MUX (p.B-9,B-19) °Decoder Select out0 A out1 Decoder 32 MUX out2 Y 3 32 B out7 32 °ALU OP A 32 In which cases do we ALU Result need an adder, ALU, 32 MUX or Decoder? B Zero 32 ECE4680 Datapath.16 2003-3-19 

9 . Storage Element: Register (p.B22-B25) °Register Write Enable • Similar to the D Flip Flop except Data In Data Out - N-bit input and output - Write Enable input N N • Write Enable: - 0: Data Out will not change Clk - 1: Data Out will become Data In • Array of logical elements(see register file on next 2 slides) l is set to 1. the W rite Enable signa ck tick ONLY if The content is updated at the clo ECE4680 Datapath.17 2003-3-19 Storage Element: Register File RW RA RB °Register File consists of 32 registers: Write Enable 5 5 5 • Two 32-bit output busses: busA busA and busB busW 32 32-bit 32 • One 32-bit input bus: busW 32 Registers Clk busB °Register is selected by: 32 • RA selects the register to put on busA • RB selects the register to put on busB • RW selects the register to be written via busW when Write Enable is 1 °Clock input (CLK) • The CLK input is a factor ONLY during write operation • During read operation, behaves as a combinational logic block: - RA or RB valid => busA or busB valid after “access time.” ECE4680 Datapath.18 2003-3-19 

10 . Storage Element: Register File -- Detailed diagram RW RA RB Write Enable 5 5 5 busA busW 32 32-bit 32 32 Registers Write Enable RA RB Clk busB 32 C 0 Register 0 1 D 32-to-1 C RW Decoder Register 1 30 D M 31 U busA C Register 30 X D C Register 31 busW D Clk M U busB X ECE4680 Datapath.19 2003-3-19 Storage Element: Idealized Memory Write Enable Address °Memory (idealized) • One input bus: Data In Data In DataOut • One output bus: Data Out 32 32 Clk °Memory word is selected by: • Address selects the word to put on Data Out • Write Enable = 1: address selects the memory memory word to be written via the Data In bus °Clock input (CLK) • The CLK input is a factor ONLY during write operation • During read operation, behaves as a combinational logic block: - Address valid => Data Out valid after “access time.” ECE4680 Datapath.20 2003-3-19 

11 . Overview of the Instruction Fetch Unit (Fig. 5.5) °The common RTL operations • Fetch the Instruction: mem[PC] • Update the program counter: - Sequential Code: PC <- PC + 4 - Branch and Jump PC <- “something else” Clk PC Next Address Logic Address Instruction Word Instruction Memory 32 ECE4680 Datapath.21 2003-3-19 RTL: The ADD Instruction 31 26 21 16 11 6 0 op rs rt rd shamt funct 6 bits 5 bits 5 bits 5 bits 5 bits 6 bits °add rd, rs, rt • mem[PC] Fetch the instruction from memory • R[rd] R[rs] + R[rt] The actual operation • PC PC + 4 Calculate the next instruction’s address ECE4680 Datapath.22 2003-3-19 

12 . RTL: The Subtract Instruction 31 26 21 16 11 6 0 op rs rt rd shamt funct 6 bits 5 bits 5 bits 5 bits 5 bits 6 bits °sub rd, rs, rt • mem[PC] Fetch the instruction from memory • R[rd] R[rs] - R[rt] The actual operation • PC PC + 4 Calculate the next instruction’s address ECE4680 Datapath.23 2003-3-19 Datapath for Register-Register Operations °R[rd] <- R[rs] op R[rt] Example: add rd, rs, rt • Ra, Rb, and Rw comes from instruction’s rs, rt, and rd fields • ALUctr and RegWr: control logic after decoding the instruction 31 26 21 16 11 6 0 op rs rt rd shamt funct 6 bits 5 bits 5 bits 5 bits 5 bits 6 bits Rd Rs Rt RegWr 5 5 ALUctr 5 busA Rw Ra Rb busW 32 ALU 32 32-bit Result 32 Registers 32 Clk busB 32 ECE4680 Datapath.24 2003-3-19 

13 . Register-Register Timing Clk Clk-to-Q PC Old Value New Value Instruction Memory Access Time Rs, Rt, Rd, Old Value New Value Op, Func Delay through Control Logic ALUctr Old Value New Value RegWr Old Value New Value Register File Access Time busA, B Old Value New Value ALU Delay busW Old Value New Value Rd Rs Rt RegWr 5 5 ALUctr Register Write 5 Occurs Here busA Rw Ra Rb busW 32 ALU 32 32-bit Result 32 Registers 32 Clk busB 32 ECE4680 Datapath.25 2003-3-19 RTL: The OR Immediate Instruction 31 26 21 16 0 op rs rt immediate 6 bits 5 bits 5 bits 16 bits °ori rt, rs, imm16 • mem[PC] Fetch the instruction from memory • R[rt] R[rs] or ZeroExt(imm16) The OR operation • PC PC + 4 Calculate the next instruction’s address 31 16 15 0 0000000000000000 immediate 16 bits 16 bits ECE4680 Datapath.26 2003-3-19 

14 . Datapath for Logical Operations with Immediate °R[rt] <- R[rs] op ZeroExt[imm16]] Example: ori rt, rs, imm16 31 26 21 16 0 op rs rt immediate 6 bits 5 bits 5 bits 16 bits Newly added parts are in blue color. Rd Rt RegDst Mux Don’t Care Rs (Rt) ALUctr RegWr 5 5 5 busA Rw Ra Rb busW 32 Result 32 32-bit ALU 32 Registers 32 Clk busB Mux 32 ZeroExt imm16 16 32 ALUSrc ECE4680 Datapath.27 2003-3-19 RTL: The Load Instruction 31 26 21 16 0 op rs rt immediate °lw rt, rs, imm16 6 bits 5 bits 5 bits 16 bits • mem[PC] Fetch the instruction from memory • Addr R[rs] + SignExt(imm16) Calculate the memory address R[rt] Mem[Addr] Load the data into the register • PC PC + 4 Calculate the next instruction’s address 31 16 15 0 0000000000000000 0 immediate 16 bits 16 bits 31 16 15 0 1111111111111111 1 immediate 16 bits 16 bits ECE4680 Datapath.28 2003-3-19 

15 . Datapath for Load Operations °R[rt] <- Mem[R[rs] + SignExt[imm16]] Example: lw rt, rs, imm16 31 26 21 16 0 op rs rt immediate 6 bits 5 bits 5 bits 16 bits Rd Rt RegDst Mux Don’t Care Rs (Rt) ALUctr RegWr 5 5 5 MemtoReg busA Rw Ra Rb busW 32 ALU 32 32-bit 32 Registers Mux 32 Clk busB MemWr 32 32 Mux WrEn Adr Extender Data In imm16 32 Data 16 32 Memory Clk ALUSrc ECE4680 Datapath.29 ExtOp 2003-3-19 RTL: The Store Instruction 31 26 21 16 0 op rs rt immediate 6 bits 5 bits 5 bits 16 bits °sw rt, rs, imm16 • mem[PC] Fetch the instruction from memory • Addr R[rs] + SignExt(imm16) Calculate the memory address • Mem[Addr] R[rt] Store the register into memory • PC PC + 4 Calculate the next instruction’s address ECE4680 Datapath.30 2003-3-19 

16 . Datapath for Store Operations °Mem[R[rs] + SignExt[imm16] <- R[rt]] Example: sw rt, rs, imm16 31 26 21 16 0 op rs rt immediate 6 bits 5 bits 5 bits 16 bits Rd Rt RegDst Mux Rs Rt ALUctr RegWr 5 5 5 MemWr MemtoReg busA Rw Ra Rb busW 32 ALU 32 32-bit 32 Registers Mux 32 Clk busB 32 32 Mux Data In WrEn Adr Extender 32 imm16 Data 32 16 Memory ALUSrc Clk ECE4680 Datapath.31 ExtOp 2003-3-19 RTL: The Branch Instruction 31 26 21 16 0 op rs rt immediate 6 bits 5 bits 5 bits 16 bits °beq rs, rt, imm16 • mem[PC] Fetch the instruction from memory • Cond R[rs] - R[rt] Calculate the branch condition • if (COND eq 0) Calculate the next instruction’s address - PC PC + 4 + ( SignExt(imm16) x 4 ) • else - PC PC + 4 ECE4680 Datapath.32 2003-3-19 

17 . Datapath for Branch Operations °beq rs, rt, imm16 We need to compare Rs and Rt! 31 26 21 16 0 op rs rt immediate 6 bits 5 bits 5 bits 16 bits Rd Rt Branch Clk PC RegDst Mux Rs Rt ALUctr imm16 RegWr 5 5 5 Next Address busA 16 Logic Rw Ra Rb busW 32 ALU 32 32-bit 32 Registers Clk busB Zero To Instruction Memory 32 Mux Extender imm16 32 16 ALUSrc ECE4680 Datapath.33 ExtOp 2003-3-19 Binary Arithmetic for the Next Address °In theory, the PC is a 32-bit byte address into the instruction memory: • Sequential operation: PC<31:0> = PC<31:0> + 4 • Branch operation: PC<31:0> = PC<31:0> + 4 + SignExt[Imm16] * 4 °The magic number “4” always comes up because: • The 32-bit PC is a byte address • And all our instructions are 4 bytes (32 bits) long °In other words: • The 2 LSBs of the 32-bit PC are always zeros • There is no reason to have hardware to keep the 2 LSBs °In practice, we can simplify the hardware by using a 30-bit PC<31:2>: • Sequential operation: PC<31:2> = PC<31:2> + 1 • Branch operation: PC<31:2> = PC<31:2> + 1 + SignExt[Imm16] • In either case: Instruction Memory Address = PC<31:2> concat “00” ECE4680 Datapath.34 2003-3-19 

18 . Next Address Logic: Expensive and Fast Solution °Using a 30-bit PC: • Sequential operation: PC<31:2> = PC<31:2> + 1 • Branch operation: PC<31:2> = PC<31:2> + 1 + SignExt[Imm16] • In either case: Instruction Memory Address = PC<31:2> concat “00” 30 Addr<31:2> 30 Addr<1:0> PC “00” Adder 30 0 Instruction 30 Mux Memory Adder “1” 1 32 Clk 30 SignExt imm16 30 Instruction<15:0> 16 Instruction<31:0> Branch Zero ECE4680 Datapath.35 2003-3-19 Next Address Logic: Cheap and Slow Solution °Why is this slow? • Cannot start the address add until Zero (output of ALU) is valid °Does it matter that this is slow in the overall scheme of things? • Probably not here. Critical path is the load operation. 30 Addr<31:2> PC 30 “1” Addr<1:0> “00” “0” Carry In Instruction 0 Adder Memory Mux Clk 30 SignExt 1 32 imm16 30 30 Instruction<15:0> 16 Instruction<31:0> Branch Zero ECE4680 Datapath.36 2003-3-19 

19 . RTL: The Jump Instruction 31 26 0 op target address 6 bits 26 bits °j target • mem[PC] Fetch the instruction from memory • PC<31:2> PC<31:28> concat target<25:0> Calculate the next instruction’s address ECE4680 Datapath.37 2003-3-19 Instruction Fetch Unit °j target • PC<31:2> PC<31:28> concat target<25:0> 30 Addr<31:2> PC<31:28> 30 Addr<1:0> “00” Target 4 1 Instruction Instruction<25:0> 30 Mux 26 Memory PC 30 0 Adder 0 32 30 Mux “1” Adder 1 Jump Instruction<31:0> Clk 30 SignExt imm16 30 16 Instruction<15:0> Branch Zero This is the whole design of Instruction Fetch Unit: 3 inputs: jump, Branch and Zero; 1 output: instruction word. ECE4680 Datapath.38 2003-3-19 

20 . Putting it All Together: A Single Cycle Datapath °We have everything except control signals (underline) Branch Instruction<31:0> <21:25> <16:20> <11:15> Instruction <0:15> Jump Fetch Unit Rd Rt RegDst Clk 1 Mux 0 Rs Rt Rt Rs Rd Imm16 RegWr 5 5 5 ALUctr busA Zero MemWr MemtoReg Rw Ra Rb busW 32 ALU 32 32-bit 32 0 Registers busB 0 32 Mux Clk Mux 32 32 WrEn Adr 1 Extender 1 Data In 32 imm16 Data 32 16 Memory Clk ALUSrc ExtOp ECE4680 Datapath.39 2003-3-19 Where to get more information? °To be continued ... ECE4680 Datapath.40 2003-3-19