Microsoft PowerPoint - notes3-Simple-filled12

Size: px

Start display at page:

Download "Microsoft PowerPoint - notes3-Simple-filled12"

堪司
5 years ago
Views:

1 Generic Computer Organization CSE Computer Architecture I Lecture Notes 3: A Simple Computer: Simple12 And Design at Register Transfer Level Stored Program Machine (vonneumann Model) Instructions are represented as numbers Programs in memory are read or written just as normal data Memory Register Data Path Program Memory Control Logic (Interprets the ISA) X. Sharon Hu Department of Computer Science and Engineering Clock Program Counter The notes are developed based on the effort of all those who have taught CSE321 before. X.S. Hu 3-1 X.S. Hu 3-2 Typical Instruction Execution Memory Organization I-Fetch DECODE EA Fetch the next Instruction Decide what is to be done Compute the address of any operands HARVARD ARCHITECTURE PRINCETON ARCHITECTURE D-FETCH EXECUTE Fetch the data Perform computation Instruction Memory CPU Data Memory CPU Instruction and Data Memory WRITEBACK Store the results ENDOP Clean up (increment PC) X.S. Hu 3-3 X.S. Hu 3-4 1

2 Simple12: A Minimal Computer Simple12 Instruction Format Start Control Datapath PC A Address(8) DataIn(12) DataOut(12) RAM PC (Program Counter): holds the 8-bit address of the current instruction A (Accumulator): holds 12 bits of data Opcode (4) Address (8) Opcode: Operation Code Specifies the action to be taken by the machine Address: The operand s address Read (1) Write (1) X.S. Hu 3-5 X.S. Hu 3-6 Simple12 ISA OPCODE Mnemonic RTL (What does the instruction do) 0000 JMP X PC <- X 0001 JN X if A<0 then PC <-X else PC++ 00 JZ X if A=0 then PC <-X else PC reserved 00 LOAD X A <- M(X), PC++ 01 STORE X M(X) <- A, PC++ 01 reserved 0111 reserved 00 AND X A <- A and M(X), PC++ 01 OR X A <- A or M(X), PC++ ADD X A <- A + M(X), PC++ 11 SUB X A <- A - M(X), PC++ 10 reserved 11 reserved 11 reserved 1111 reserved A Simple12 Assembly Program Problem: Given three memory locations (X, Y, and Z), use the Simple12 to find the maximum of (X, Y) and place it in Z PROGRAM 0 LOAD X 1 SUB Y 2 JN B1 3 LOAD X 4 JMP SAVE 5 B1: LOAD Y 6 SAVE: STORE Z X.S. Hu 3-7 X.S. Hu 3-8 2

3 Program Execution (1) Program Execution (2) PROGRAM VALUE IN A PROGRAM VALUE IN A 0 LOAD X 1 SUB Y 5 2 JN B1 5 (not taken) 3 LOAD X 4 JMP SAVE (taken) 5 B1: LOAD Y 6 SAVE: STORE Z X: Y: 5 Z: n/a 0 LOAD X 1 SUB Y - 5 = 5 2 JN B1 3 LOAD X 4 JMP SAVE 5 B1: LOAD Y 6 SAVE: STORE Z X: Y: 5 Z: n/a X.S. Hu 3-9 X.S. Hu 3- Program Execution (3) Program Execution (4) PROGRAM VALUE IN A PROGRAM VALUE IN A 0 LOAD X 1 SUB Y 2 JN B1 5 3 LOAD X 4 JMP SAVE 5 B1: LOAD Y 6 SAVE: STORE Z X: Y: 5 Z: n/a 0 LOAD X 1 SUB Y 2 JN B1 3 LOAD X 4 JMP SAVE 5 B1: LOAD Y 6 SAVE: STORE Z X: Y: 5 Z: n/a X.S. Hu 3-11 X.S. Hu

Program Execution (6) PROGRAM 0 LOAD X 1 SUB Y 2 JN B1 3 LOAD X 4 JMP SAVE 5 B1: LOAD Y 6 SAVE: STORE Z X: Y: 5 Z: VALUE IN A X.S. Hu 3-13 Another Example Simple12 Program ; A program to see if each : item in array contains a ; particular element ; while (A[i]!

DATA Mask 1 L1: LOAD A0 JZ Done AND Mask JZ B1 LOAD One JMP L2 B1: LOAD Zero L2: ST

4 Program Execution (6) PROGRAM 0 LOAD X 1 SUB Y 2 JN B1 3 LOAD X 4 JMP SAVE 5 B1: LOAD Y 6 SAVE: STORE Z X: Y: 5 Z: VALUE IN A X.S. Hu 3-13 Another Example Simple12 Program ; A program to see if each : item in array contains a ; particular element ; while (A[i]!= 0) ; if ( A[i] & Mask!=0) ; A[i] = 1; ; else ; A[i] = 0; ; i++; ; Data declarations!.data A0 3.DATA A1 5.DATA A2 3.DATA A3 8.DATA A4 19.DATA A5 0.DATA Zero 0.DATA One 1.DATA Mask 1 L1: LOAD A0 JZ Done AND Mask JZ B1 LOAD One JMP L2 B1: LOAD Zero L2: STORE A0 Done: LOAD ADD STORE LOAD ADD STORE JMP.END L1 One L1 L2 One L2 L1 X.S. Hu 3-14 Registers Register Transfer Operations CLK D Latch CLK Q Clocked Latch: State changes when Q the clock is asserted and the inputs change. D CLK D Register Before Clock Combinatorial Logic After Clock Register CLK Flip-Flop Q Flip-Flop: state changes only on the rising clock edge. D Q Register: an array of flip-flops Register Combinatorial Logic Register X.S. Hu 3-15 X.S. Hu

5 Register Transfer Language Register Transfer Language (RTL): describes the internal operation of the system in terms of a sequence of register reads, combinatorial logic, and register writes. Defines operations in terms of data flow and associated control mechanisms Can be relatively high level Forms the basis of most hardware description languages Example Register Transfer Operations A XOR C C <= A xor B B 1 A + A <= A + 1 X.S. Hu 3-17 X.S. Hu 3-18 RTL Assignments Functions and Operators Register transfer operations are expressed as: D <= S D (destination) gets S (source) c d S + CLK D load c CLK Z load s0 and x if (c) then D <= S if (s0 and x) then Z <= c+d C D S P Y <= A B n n... MUX n Y A when s=0 else B when s=1 else... n Bit-vectors used as both operands and results Examples: Decode(X) Add(X,Y) F(Q) Similar to switch/case construct in C X.S. Hu 3-19 X.S. Hu

6 Parallel Assignments LOAD A B A <= B, B<= A Question: if A=11 and B=00 initially, what are their values after one clock cycle? Sequencing Constructs Each line of code is executed after the line before: step1: A <= X; step2: B <= Y; step3: C <= A+B; Operations may occur in parallel: step1: A <= X, B<=Y; step2: C <= A+B; Goto Statement Acceptable: step1: A <= X, B <= Y; step2: C <= A + B, if A[0] = 1 goto step1; X.S. Hu 3-21 X.S. Hu 3-22 RTL Notation Summarized Sequencing SYMBOL DESCRIPTION EXAMPLE Names/Letters Registers A, B, foo <= Transfer into ( gets ) A <= B : (colon) indicates a control state s0: <statement>, (comma) parallel microoperations A<=B,C<=D +, - Arithmetic Operations A<=B+1 &,, overline logic operators (bitwise) A<=A&B <<,>> shift operators A<=B<<1 if, then, else conditional if (c=0) then F<= 1 else F<= 0 goto branch goto s0 S0 S1 S2 S3 Microinst Microinst Microinst N>=0 Microinst N<0 Algorithm execution is controlled by sequencing states Each state has an associated microinstruction Several parallel microoperations may occur in each state implemented as register transfers Conditional branching More excercise X.S. Hu 3-23 X.S. Hu

7 Microcoding AKA: Microprogramming Instructions are expressed as a series of microinstructions that express each time-step of the operation. microinstructions are composed of micro-operations Only one microinstruction executes at a time Each microinstruction executes its set of microoperations in parallel Microinstructions Microoperations } Microprogram Simple12 ISA OPCODE Mnemonic RTL 0000 JMP X PC <- X 0001 JN X if A<0 then PC <-X else PC++ 00 JZ X if A=0 then PC <-X else PC reserved 00 LOAD X A <- M(X), PC++ 01 STORE X M(X) <- A, PC++ 01 reserved 0111 reserved 00 AND X A <- A and M(X), PC++ 01 OR X A <- A or M(X), PC++ ADD X A <- A + M(X), PC++ 11 SUB X A <- A - M(X), PC++ 10 reserved 11 reserved 11 reserved 1111 reserved X.S. Hu 3-25 X.S. Hu 3-26 Simple12 Simple12: External Interfaces PC (Program Counter): holds the 8-bit address of the current instruction A (Accumulator): holds 12 bits of data VISIBLE REGISTERS PC (Program Counter): holds the 8-bit address of the current instruction A (Accumulator): holds 12 bits of data INVISIBLE REGISTERS MAR (Mem. Access Reg): places the address for a memory access onto the address bus. MDR (Mem. Data Reg.): transfers data to/from memory X.S. Hu 3-27 X.S. Hu

8 Memory Read/Write Typical Instruction Execution MAR holds the address, MDR holds the value The control signals memory read (mem_read) and memory write (mem_write) must be set appropriately MEMORY READ: MAR <= address, mem_read <= 1 MEMORY WRITE: MAR <= address, MDR <= value, mem_write <= 1 I-Fetch DECODE EA D-FETCH EXECUTE WRITEBACK ENDOP Fetch the next Instruction Decide what is to be done Compute the address of any operands Fetch the data Perform computation Store the results Clean up (increment PC) X.S. Hu 3-29 X.S. Hu 3-30 Simple12 Instruction Execution ALU Operations PC <= 0 Start=1 Fetch 12-bit Instruction Start=0 op X, take the form: A <= A op Mem[X] Fetch 12-bit Instruction 2 cycles IFetch MAR <= PC { mem_read <= 1 7 Cycles Decode Instruction Compute Operand s Address Microinstructions Decode Instruction Compute Operand s Address Decode Examine MDR(11:8) MAR <= MDR(7:0) Fetch 12-bit Operand Compute New Value Save Results Compute New PC NOTE: Not all instructions require that all microinstructions be executed. Fetch 12-bit Operand Compute New Value Save Results Compute New PC } mem_read <= 1 A <= A op MDR PC <= PC + 1 X.S. Hu 3-31 X.S. Hu

9 LOAD/STORE Operations LOAD X: A <= Mem[X] STORE X Mem[X] <= A MAR <= PC mem_read <= 1 Examine MDR(11:8) Jump Operations JMP X JN X JZ X Unconditional if A[11]=1 if A=0 MAR <= PC mem_read <= 1 MAR <= MDR mem_read <= 1 A <= MDR LOAD STORE MAR <= MDR MDR <= A mem_write <= 1 Examine MDR(11:8) Branch Failed Branch Successful PC <= PC + 1 PC <= MDR(7:0) PC <= PC + 1 PC <= PC + 1 How many cycles? How many cycles for each instruction? X.S. Hu 3-33 X.S. Hu 3-34 Required Datapath Operations Example Program Execution ALU Instructions AND, OR, ADD, SUB PC Increment LOAD/STORE Instructions Register Transfers Only PC Increment JUMP Instructions Check A[11] and A=0 n_flag z_flag Only Register Transfers EXAMPLE: Choose the max of two numbers. 00h: LOAD X (30h) 01h: SUB Y (31h) 02h: JN B1 (06h) 03h: LOAD X (30h) 04h: JMP SAVE (07h) 06h: B1: LOAD Y (31h) 07h: SAVE: STORE Z (32h)... 30h: X: 7 31h: Y: 32h: Z: n/a CYCLE* PC A MAR MDR MEM OP 1 00h h h Read M[0] 3 00h h h - 30h 430h h - 30h 007h Read M[30h] 6 00h 007h 30h 007h h 007h 30h 007h h 007h 01h 007h h 007h 01h B31h Read M[01h] 01h 007h 01h B31h h 007h 31h B31h h 007h 31h 00Ah Read M[31h] 13 01h FFDh 31h 00Ah h FFDh 31h 00Ah - * End of each cycle X.S. Hu 3-35 X.S. Hu

10 Potential Improvements Cannot use opcode in the subsequent cycle as it is in MDR Solution: Add an Instruction Register (IR) Loaded from the memory bits 11-8 at the same time as MDR A cycle is wasted in each instruction moving PC to MAR Solution: update PC and MAR simultaneously The only writes to memory come from A Solution: tie A to DataOut and save a cycle for MDR <= A Most instructions require PC <= PC+1 Solution: use more hardware Many microinstructions are the same (or very similar) regardless of opcode Solution: group common states together Revised Microprogram RTL Stopped: IFetch: EAGen: OpAccess: Execute: If start=1 then (MAR <= 0, PC<=0, goto IFetch) else goto Stopped read_mem <= 1, MDR <= DataIn, MAR<=PC+1, PC<=PC+1, IR<=DataIn(11:8), goto EAGen if (IR=JMP) or (IR=JN and A(11)=1) or (IR=JZ and A=0) then MAR <= MDR(7:0), PC<=MDR(7:0) goto IFetch else if (IR=JN) or (IR=JZ) then goto IFetch else MAR <= MDR(7:0), goto OpAccess MAR <= PC, if IR=LOAD or IR(3:2)= /* i.e., an ALU operation */ then (Read <= 1, MDR<=DataIn, goto Execute) else (Write <= 1, DataOut <= A, goto IFetch) /* a STORE */ if (IR=LOAD) then A <= MDR, goto IFetch else if (IR=AND) then A <= A and MDR, goto IFetch else if (IR=OR) then A <= A or MDR, goto IFetch else if (IR=ADD) then A <= A + MDR, goto IFetch else if (IR=SUB) then A <= A - MDR, goto IFetch NOTE: if Read and Write are not explicitly specified, they are 0 X.S. Hu 3-37 X.S. Hu 3-38 Revised State Machine A First-Cut Datapath Stopped Start IFetch EAGen OpAccess Execute ~Start Jumps Store INSTRUCTION CYCLES JMP 2 JN 2 JZ 2 LOAD 4 STORE 3 AND 4 OR 4 ADD 4 SUB 4 Required Microoperations: PC <= 0 MDR <= DataIn, IR <= DataIn, PC<= PC +1 MAR <= MDR(7:0), PC<=MDR(7:0) MAR <= PC A <= MDR A <= A + MDR A <= A - MDR A <= A and MDR A <= A or MDR R(11) Negative Zero B A M U X PC AND 0 0/1 MAR IR MDR A Address DataIn DataOut X.S. Hu 3-39 X.S. Hu 3-40

11 Control Signals Cin Binv Zero Resulting Control Points: Load Signals for each register ALU Controls (4 bits) b-invert, carry-in, op1, op0 MUX1: select PC, MDR, or 0 AND: Select 0 or A bmux LoadPC R(11) Negative B A M U X PC AND 0 agate MAR IR MDR (0/1) A FuncSel (Op0 and Op1) Address DataIn DataOut LoadMAR LoadIR LoadMDR LoadA ALU Control Definitions Binv Cin op1 op0 ACTION A and B A and ~B A or B A or ~B A + B A + B A -B A -B + 1 ALU also has a zero flag. X.S. Hu 3-41 X.S. Hu 3-42 Moore and Mealy Machines Moore and Mealy Machines Microinstructions will be issued to the data path using a state machine Two possibilities: Moore Machine: the outputs of the state machine depend only on the current state Mealy Machine: the outputs of the state machine depend on the current state and the values of the inputs Moore Machine Inputs Curr ent State Next State Function (comb. logic) Mealy Machine Inputs Curr ent State Next State Function (comb. logic) Output Function (combinational logic) Output Output Function (combinational logic) Output X.S. Hu 3-43 X.S. Hu

12 Mealy Design Problem Two Solutions EAGen if (IR=JMP) or (IR=JN and A(11)=1 or (IR=JZ and A=0) then MAR <= PC <= MDR(7:0) First: EAGen (IR=JN and A(11)=1) or (IR=JZ and A=0) BTaken MAR <=PC<=MDR(7:0) IR=JN or IR=JZ IFetch IR=JN or IR=JZ (not taken) IFetch ALU needed twice in the same cycle! Second: Add More Hardware (check the Z-flag outside the ALU) X.S. Hu 3-45 X.S. Hu 3-46 Revised Timing Simple12 Control Signal Table INSTRUCTION CYCLES JMP 2 JN not taken 2 taken 3 JZ not taken 2 taken 3 LOAD 4 STORE 3 AND 4 OR 4 ADD 4 SUB 4 Q Stopped IFetch EAGen Opnd Execute BTaken JMP JN JZ LD/ST ALUOP STORE IR n/a LOAD AND ADD SUB a r t S Neg n/a 01 Zero n/a Q* Opnd EAGen IFetch BTaken Execute Stopped A 0 L 1 C P 1 L 0 R A M 1 L 0 R D M 0 L 1 R I 01 L U L + AND OR ADD SUB n/a X U MDR b PC 0 e t a G 0 1 d a e 0 R 1 et ir 0 W X.S. Hu 3-47 X.S. Hu

13 Control Path Implementation Microprogrammed Control Unit Hardwired Microprogrammed A control unit with its binary control values stored as words in memory (ie, a ROM) Big Questions: How do we structure the microprogram? How do we sequence through microinstructions? What are the fields? Address (Control Inputs) Memory (ROM) Data (Control Outputs) X.S. Hu 3-49 X.S. Hu 3-50 Microprogram Structure Microinstruction Template Common States (IFetch, etc) Additional Long Sequences Up to 2 Micro- Instructions per OpCode Shared States Stopped, IFetch 16 Possible OpCodes OperandAccess and Execute sequences somewhat different for each Minimum 2 non-shared Microinstructions to be allocated Additional space available in table for growth Cond Sel 3 Addr Sel 1 Addr Next 6 A Load 1 PC Load 1 MAR Load 1 MDR Load 1 ALU 4 MUX b 2 Gate a 1 Rd 1 Wt 1 b-inv Cin OR ADD AND X.S. Hu 3-51 X.S. Hu

14 Condition Select Sample Microinstruction Branch Addr (6) Addr Select (1) MUX Q,IR Control Store ROM 1 => Loads Q with new address 0 => Increments Q to next address LD/EN M U X False True ~A(11) ~ALU=0 ~Start Condition Select: chooses how LD/EN is driven Cond Sel 0 Addr Sel 0 Addr Next A Load 0 PC Load 1 MAR Load 1 MDR Load 0 ALU 00 MUX b 0 Gate a 0 Rd 0 Wt0 Addr. Select: if Q LD/EN=1 (load Q) 0 => select next address bits from ROM 1 => construct address from control and IR bits Control Signals to Data Flow b-inv Cin OR ADD AND X.S. Hu 3-53 X.S. Hu 3-54 Sample Microinstruction (continued) EAGen for JN BTaken Cond Sel 001 Addr Sel 1 Next Addr Load A 0 Load PC 1 Load MAR 1 Load MDR 1 ALU 01 MUX b 11 a Gate 0 Rd 1 Wt0 Cond Sel Addr Sel Addr Next A Load PC Load MAR Load MDR Load ALU MUX b Gate a Rd Wt b-inv Cin AND OR ADD b-inv Cin OR ADD AND X.S. Hu 3-55 X.S. Hu

15 BTaken for JN EAGen for ADD BTaken 1 MAR PC MDR(7:0), goto IFetch ADD at 10 MAR MDR[7:0], goto OpAcc Cond Sel Addr Sel Next Addr Load A Load PC Load MAR Load MDR ALU MUX b a Gate Rd Wt Cond Sel Addr Sel Addr Next A Load PC Load MAR Load MDR Load ALU MUX b Gate a Rd Wt b-inv Cin AND OR ADD b-inv Cin OR ADD AND X.S. Hu 3-57 X.S. Hu 3-58 OpAcc for ADD Execute for ADD OpAcc for ADD at 11 MDR[7:0] DataIn, goto Execute Execute for ADD at 01 A MDR[7:0] + A, goto IFetch Cond Sel Addr Sel Next Addr Load A Load PC Load MAR Load MDR ALU MUX b a Gate Rd Wt Cond Sel Addr Sel Addr Next A Load PC Load MAR Load MDR Load ALU MUX b Gate a Rd Wt b-inv Cin AND OR ADD Any mistake? Yes, need MAR <- PC LoadMAR = 1, ALU = 00, bmux = 11, agate = 0 X.S. Hu 3-59 b-inv Cin OR ADD AND X.S. Hu

16 EAGen for LOAD OpAcc for LOAD LOAD at 00 MAR MDR[7:0], goto OpAcc OpAcc for LOAD at 01 MDR[7:0] DataIn, MAR PC, goto Execute Cond Sel Addr Sel Next Addr Load A Load PC Load MAR Load MDR ALU MUX b a Gate Rd Wt Cond Sel Addr Sel Next Addr Load A Load PC Load MAR Load MDR ALU MUX b a Gate Rd Wt b-inv Cin AND OR ADD b-inv Cin OR ADD AND X.S. Hu 3-61 X.S. Hu 3-62 Execute for LOAD Execute for LOAD at 00 A MDR[7:0], goto IFetch Cond Sel Addr Sel Next Addr Load A Load PC Load MAR Load MDR ALU MUX b a Gate Rd Wt b-inv Cin AND OR ADD X.S. Hu

Microsoft PowerPoint - CA_03 Chapter5 Part-II_multi _V1.ppt

Microsoft PowerPoint - CA_03 Chapter5 Part-II_multi _V1.ppt Chapter5-2 The Processor: Datapath and Control (Multi-cycle implementation) 臺大電機系吳安宇教授 V1. 03/27/2007 For 2007 DSD Course 臺大電機吳安宇教授 - 計算機結構 1 Outline 5.1 Introduction 5.2 Logic Design Conventions 5.3