CS4100：计算机结构

1、CS4100: 計算機結構Designing a Multicycle Processor,國立清華大學資訊工程學系 九十五學年度第一學期 Adapted from class notes of D. Patterson and W. Dally Copyright 1998, 2000 UCB,Multicycle Design-1,Outline,Designing a processor Building the datapath A single-cycle implementation A multicycle implementation Microprogramming: sim

2、plifying control (Appendix C.4) Exceptions,Multicycle Design-2,Recap: A Single-Cycle Processor,CPI=1,Multicycle Design-3,PC,Inst Memory,mux,ALU,Data Mem,mux,PC,Reg File,Inst Memory,mux,ALU,mux,PC,Inst Memory,mux,ALU,Data Mem,PC,Inst Memory,cmp,mux,Reg File,Reg File,Reg File,Arithmetic memory needs r

3、ead signal PC and A to one ALU input; four sources to another input,Fig. 5.27,Multicycle Design-10,Adding Branch/Jump,Three sources to PC Two PC write signals,Fig. 5.28,Multicycle Design-11,Outline,Designing a processor Building the datapath A single-cycle implementation A multicycle implementation

4、Multicycle datapath Multicycle execution steps Multicycle control (Appendix C.3) Microprogramming: simplifying control (Appendix C.4) Exceptions,Multicycle Design-12,Instruction Fetch Instruction Decode and Register Fetch Execution, Memory Address Computation, or Branch Completion Memory Access or R

5、-type Instruction Completion Memory Read Completion (Write-back)INSTRUCTIONS TAKE FROM 3 - 5 CYCLES!,Five Execution Steps,Multicycle Design-13,Step 1: Instruction Fetch,Use PC to get instruction and put it in the Instruction Register (IR) Increment the PC by 4 and put the result back in the PC Can b

6、e described succinctly using RTL (Register-Transfer Language)IR = MemoryPC;PC = PC + 4;Can we figure out the values of the control signals?What is the advantage of updating the PC now?,Multicycle Design-14,Step 2: Instruction Decode and Register Fetch,Read registers rs and rt in case needed Compute

7、the branch address in case the instruction is a branch RTL:A = RegIR25-21;B = RegIR20-16;ALUOut=PC+(sign-ext(IR15-0)2); We arent setting any control lines based on the instruction type yet(we are busy decoding it in control logic),Multicycle Design-15,ALU is performing one of three functions, based

8、on instruction type: Memory Reference:ALUOut = A + sign-extend(IR15-0); R-type:ALUOut = A op B; Branch:if (A=B) PC = ALUOut;,Step 3: Execution,Multicycle Design-16,Loads and stores access memoryMDR = MemoryALUOut;orMemoryALUOut = B; R-type instructions finishRegIR15-11 = ALUOut;The write actually ta

9、kes place at the end of the cycle on the edge,Step 4: R-type or Memory-access,Multicycle Design-17,Loads write to register RegIR20-16= MDR; What about all the other instructions?,Step 5: Write-back,Multicycle Design-18,Summary of the Steps,Fig. 5.30,Multicycle Design-19,Cycle 1 of add,IR = MemoryPC;

10、PC = PC + 4;,Multicycle Design-20,Cycle 2 of add,A=RegIR25-21; B=RegIR20-16; ALUOut=PC+(sign-ext(IR15-0)2);,Multicycle Design-21,Cycle 3 of add,ALUOut = A op B;,Multicycle Design-22,Cycle 4 of add,RegIR15-11 = ALUOut;,Multicycle Design-23,How many cycles will it take to execute this code? lw $t2, 0(

11、$t3)lw $t3, 4($t3)beq $t2, $t3, Labeladd $t5, $t2, $t3sw $t5, 8($t3)Label:. What is going on during the 8th cycle of execution? In what cycle does the actual addition of $t2 and $t3 takes place?,Simple Question,assume not,Multicycle Design-24,Outline,Designing a processor Building the datapath A sin

12、gle-cycle implementation A multicycle implementation Multicycle datapath Multicycle execution steps Multicycle control (Appendix C.3) Microprogramming: simplifying control (Appendix C.4) Exceptions,Multicycle Design-25,Implementing the Control,Value of control signals is dependent upon: what instruc

13、tion is being executed which step is being performed Control must specify both the signals to be set in any step and the next step in the sequence Control specification Use a finite state machine (graphically) Use microprogramming Implementation can be derived from the specification and use gates, R

14、OM, or PLA,Multicycle Design-26,Several possible initial representations, sequence control and logic representation, and control implementation = all may be determined indep.Initial Rep. Finite State Diagram Microprogram Sequencing Explicit Next State Microprogram Control Function Counter + Dispatch

15、 ROMs Logic Rep. Logic Equations Truth Tables Implementation PLA ROM,Controller Design: An Overview,“hardwired control”,“microprogrammed control”,Multicycle Design-27,Finite state machines: a set of states and next state (set by current state and input) output (set by current state and possibly inpu

16、t) We will use a Moore Machine (output based only on the current state),Review: Finite State Machines,Multicycle Design-28,Control State,Next State Logic,Output Logic,inputs (conditions),outputs (control points),State X,Register Transfer Control Points,Depends on Input,State specifies control points

17、 for RT Transfer at exiting state (same falling edge) One state takes one cycle,Our Control Model,Multicycle Design-29,Summary of the Steps,Fig. 5.30,Control Specification for Multicycle,IR = MEMPC PC = PC + 4,A = Rrs B = Rrt S = PC+sx(Imm16)|00,PC = IR .,R-type,S = A op B,Rrd = S,S = A + sx(Imm16),

18、Rrt = M,M = MEMS,lw/sw,If zero PC = S,jump,beq,Instruction fetch,Decode/register fetch,Execute,Memory access,Memory read,MEMS = B,lw,sw,Multicycle Design-31,Organization of Multicycle Processor,Fig. 5.28,Multicycle Design-32,Control Signals,Signal nameEffect when deassertedEffect when assertedALUSrc

19、A1st ALU operand = PC1st ALU operand = RegrsRegWriteNoneReg file is written MemtoRegReg. data input = ALUReg. write data input = MDR RegDstReg. write dest. no. = rtReg. write dest. no. = rdMemReadNoneMemory at address is readMemWriteNoneMemory at address is written IorDMemory address = PCMemory addr

20、ess = ALUoutIRWriteNoneIR = MemoryPCWriteNonePC = PCSourcePCWriteCondNoneIf zero then PC = PCSource Signal nameValueEffect ALUOp00ALU adds 01ALU subtracts 10ALU operates according to func codeALUSrcB002nd ALU input = B 012nd ALU input = 4 102nd ALU input = sign extended IR15-0 112nd ALU input = sign

21、 ext., shift left 2 IR15-0PCSource00PC = ALU (PC + 4) 01PC = ALUout (branch target address) 10PC = PC+431-28 : IR25-0 2,Single Bit Control,Multiple Bit Control,Fig. 5.29,Multicycle Design-33,Mapping RT to Control Signals,Instruction fetch and decode portion of every instruction is identical:,Fig. 5.

22、32,A = Rrs B = Rrt S = PC+ sx(Imm16)|00,IR = MEMPC PC = PC + 4,Multicycle Design-34,Mapping RT to Control Signals,FSM for controllingmemory referenceinstructions:,Fig. 5.33,Complete FSM,Fig. 5.38,State number assignment,Multicycle Design-36,input output op SDatapath control NS 000000 000010010100000

23、0100 0001 000000 0001000000000011000 0110 000000 0010000000000010100 xxxx 000000 1010 000000 1111 000001 0000 000010 0000 100101000000100 0001 000010 0001 000000000011000 1001 000000 0010 000000000010100 xxxx,Truth Table,Multicycle Design-37,From FSM to Truth Table,Please reference the logic equatio

24、ns in Fig. C.3.3 and the truth table in Fig. C.3.6,OutputEquation PCWritestate0 + state9 PCWriteCondstate8 IorDstate3 + state5 NextState0state4 + state5 + state7 + state8 +state9 NextState1state0 NextState2state1 (op = lw) + (op = sw) NextState3state2 (op = lw) .,OutputCurrent states 0 1 2 3 4 5 6 7

25、 8 9 PCWrite1 0 0 0 0 0 0 0 0 1 PCWriteCond0 0 0 0 0 0 0 0 1 0 IorD0 0 0 1 0 1 0 0 0 0 ,Multicycle Design-38,state,6,4,11,next state,op,zero,control points,state,op,cond,next state,control points,Truth Table,datapath state,Control signals,Designing FSM Controller,Multicycle Design-39,The Control Uni

26、t,Fig. C.3.2,Sequence Control,Multicycle Design-40,PLA Implementation,Fig. C.3.9,Sequence Control,Multicycle Design-41,Need a ROM of 10-bit address, 20-bit word (16-bit datapath control, 4-bit next state) Address ROM content op SDatapath control NS 000000 0000100101000000100 000000 00010000000000110

27、00 000000 0010000000000010100 000000 1010 000000 1111 000001 0000 000010 0000 100101000000100 000010 0001 000000000011000 000000 0010 000000000010100,ROM Implementation,0001,Multicycle Design-42,Address ROM content op SDatapath control NS 000000 0000100101000000100 0001 000000 0001000000000011000 01

28、10 000000 0010000000000010100 xxxx 000000 1010 000000 1111 000001 0000 000010 0000 100101000000100 0001 000010 0001 000000000011000 1001 000000 0010 000000000010100 xxxx,ROM Implementation(Truth Table),Rather wasteful, since for lots of entries, outputs are same or are dont-care Could break up into

29、two smaller ROMs (Fig. C.3.7, C.3.8),Multicycle Design-43,ROM vs PLA,ROM: use two smaller ROMs (Fig. C.3.7, C.3.8) 4 state bits give the 16 outputs, 24x16 bits of ROM 10 bits (op + state) give 4 next state bits, 210 x 4 bits of ROM Total = 4.3K bits of ROM (compared to 210 x 20 bits of single ROM im

30、plementation) PLA is much smaller can share product terms only need entries that produce an active output can take into account dont-cares Size is (#inputs #product-terms) + (#outputs #product-terms) For this example = (10 x17)+(20 x17) = 460 PLA cells PLA cells usually about the size of a ROM cell

31、(slightly bigger),Complete FSM,Fig. 5.38,State number assignment,Multicycle Design-45,Use Counter for Sequence Control,Fig. C.4.1,No Next-State Lines,Multicycle Design-46,Address Select Unit,AddrCtl Value: 0Set state to 0 1Dispatch ROM 1 2Dispatch ROM 2 3Use incrementedstate,Fig. C.4.2,Control Conte

32、nts,Fig. C.4.3, C.4.4,Multicycle Design-48,Outline,Designing a processor Building the datapath A single-cycle implementation A multicycle implementation Multicycle datapath Multicycle execution steps Multicycle control Microprogramming: simplifying control (Appendix C.4) Exceptions,Multicycle Design

33、-49,Several possible initial representations, sequence control and logic representation, and control implementation = all may be determined indep.Initial Rep. Finite State Diagram Microprogram Sequencing Explicit Next State Microprogram Control Function Counter + Dispatch ROMs Logic Rep. Logic Equat

34、ions Truth Tables Implementation PLA ROM,Controller Design: An Overview,“hardwired control”,“microprogrammed control”,Multicycle Design-50,Control is the hard part of processor design Datapath is fairly regular and well-organized Memory is highly regular Control is irregular and global But, the stat

35、e diagrams that define the controller for an instruction set processor are highly structured Use this structure toconstruct a simple“microsequencer” Control reduces toprogramming thissimple device = microprogramming,sequencer control,datapath control,micro-PC,sequencer,microinstruction,Microprogram,

36、. control signals,Multicycle Design-51,Microinstruction,Control signals : Think of the set of control signals that must be asserted in a state as an instruction Executing a microinstruction has the effect of asserting the control signal specified by the microinstruction Sequencing What microinstruct

37、ion should be executed next ? Execute sequentially (next state unconditionally) Branch (next state also depends on inputs) A microprogram is a sequence of microinstructions executing a program flow chart (finite state machine),Multicycle Design-52,1) Start with a list of control signals 2) Group sig

38、nals together that make sense (vs. random): called fields 3) Places fields in some logical order (e.g., ALU operation B = Regrt; Write ALURegrd = ALUout Write MDRRegrt = MDR MemoryRead PCIR (MDR) = memPCRead ALUMDR = memALUoutWrite ALUmemALUout = BPC writeALUPC = ALU outputALUout-cond.IF ALU zero th

39、en PC = ALUoutjump addr.PC = PCSourceSequencingSeqGo to sequential microinstructionFetchGo to the first microinstructionDispatch 1Dispatch using ROM1 Dispatch 2Dispatch using ROM2,Control Signals,Multicycle Design-56,The Microprogram,Multicycle Design-57,The Controller,Fig. C.4.6,Multicycle Design-5

40、8,The Dispatch ROMs,Fig. C.5.2,Rformat1,JUMP1,BEQ1,Mem1,Mem1,LW2,SW2,Multicycle Design-59,Our Plan: Using ROM,Multicycle Design-60,Main Memory,execution unit,control memory,CPU,ADD SUB AND,DATA,. . .,User program plus Data this can change!,AND microsequence e.g., Fetch Calc Operand Addr Fetch Operan

41、d(s) Calculate Save Answer(s),one of these is mapped into one of these,Microinstruction Interpretation,Multicycle Design-61,Microprogramming Using ROM : Pros and Cons,Ease of design Flexibility Each to adapt to changes in organization, timing, technology Can make changes late in design cycle, or eve

42、n in the field Generality Implement multiple inst. sets on same machine Can tailor instruction set to application Can implement very powerful instruction sets (just more control memory) Compatibility Many organizations, same instruction set Costly to implement and Slow,Multicycle Design-62,5) Microi

43、nstruction Encoding,Fig. C.4.5,Bits 7-13 can be encoded to 3 bits because there are only 7 patterns of the control word,Multicycle Design-63,Minimal vs. Maximal Encoding,Minimal (Horizontal ): + more control over the potential parallelism of operations in the datapath - uses up lots of control store

44、 Maximal (Vertical): + uses less number of control store - extra level of decoding may slow the machine down,Multicycle Design-64,Control is specified by a finite state diagram Specialized state-diagrams easily captured by microsequencer simple increment and “branch” fields datapath control fields C

45、ontrol can also be specified by microprogramming Control is more complicated with: complex instruction sets restricted datapaths Simple instruction set and powerful datapath = simple control could reduce hardware Or go for speed = many instructions at once!,Summary of Control,Multicycle Design-65,Ou

46、tline,Designing a processor Building the datapath A single-cycle implementation A multicycle implementation Multicycle datapath Multicycle execution steps Multicycle control Microprogramming: simplifying control Exceptions,Multicycle Design-66,Exceptions,User Program,System Exception Handler,Excepti

47、on,return from exception,Normal control flow: sequential, jumps, branches, calls, returns Exception = unprogrammed control transfer system takes action to handle the exception must record address of the offending instruction should know cause and transfer to proper handler if returns to user, must s

48、ave & restore user state,Multicycle Design-67,By providing two modes of execution (user/system), computer may manage itself OS is a special program that runs in the privileged system mode and has access to all of the resources of the computer Presents “virtual resources” to each user that are more c

49、onvenient than the physical resources files vs. disk sectors virtual memory vs. physical memory protects each user program from others Exceptions allow the system to take action in response to events that occur while user program is executing OS begins at the handler,User/System Modes,Multicycle Des

50、ign-68,Two Types of Exceptions,Interrupts: caused by external events and asynchronous to execution= may be handled between instructions simply suspend and resume user program Exceptions: caused by internal events and synchronous to execution, e.g., exceptional conditions (overflow), errors (parity),

51、 faults instruction may be retried or simulated and program continued or program may be aborted,Multicycle Design-69,MIPS Convention of Exceptions,MIPS convention: exception means any unexpected change in control flow, without distinguishing internal or external use interrupt only when the event is

52、externally caused Type of eventFrom where?MIPS terminologyI/O device requestExternalInterruptInvoke OS from user programInternalExceptionHardware malfunctionsEitherException orInterruptArithmetic overflow InternalExceptionUsing an undefined inst.InternalException,Multicycle Design-70,Precise Interru

53、pts,Precise: machine state is preserved as if program executed upto the offending inst. Same system code will work on different implementations of the architecture Position clearly established by IBM, and taken by MIPS Difficult in the presence of pipelining, out-ot-order execution, . Imprecise: sys

54、tem software has to figure out what is where and put it all back together Performance goals often lead designers to forsake precise interrupts system software developers, user, markets etc., usually wish they had not done this,Multicycle Design-71,Handling Exceptions in Our Design,Consider two types

55、 of exceptions:undefined instruction & arithmetic overflow Basic actions on exception: Save state: save the address of the offending instruction in the exception program counter (EPC) Transfer control to OS at some specified address= need to know the cause for the exception= then know the address of

56、 exception handler After service, OS can terminate the program or continue its execution, using EPC to return,Multicycle Design-72,Push it onto the stack Vax, 68k, 80 x86 Save it in special registers MIPS EPC, BadVaddr, Status, Cause Shadow Registers M88k Save state in a shadow of the internal pipel

57、ine registers,Saving State: General Approaches,Multicycle Design-73,iv_base,cause,handler entry code,Traditional approach: interrupt vector The cause of exception is a vectorgiving the address of the handler PC - MEM IV_base + cause | 00 68000, Vax, 80 x86, . . . RISC Handler Table PC - IV_base + cause | 0000 Saves state and jumps Sparc, PA, M88K, . . . MIPS approach: fixed entry use a status register (cause register)to hold a field to indicate the cause PC - EXC_addr,Addressing the Exception Handler,Multicycle Design-74,Datapath with Exceptio