Sequential Machine Datapath Control Flow Design

Explore the hardware implementation of control flow instructions for a sequential machine, including executing jumps, calls, and returns. Dive into the stages of computation involved in handling branching, fetching instructions, updating program counters, and managing stack pointers.

• Datapath Design
• Control Flow Instructions
• Sequential Machine
• Hardware Implementation
• Computation Stages

cris_il Follow

Uploaded on Oct 05, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. Systems I Datapath Design II Topics Control flow instructions Hardware for sequential machine (SEQ)

2. Executing Jumps jXX Dest 7 fn Dest Not taken fall thru: XX XX target: XX XX Taken Fetch Memory Read 5 bytes Increment PC by 5 Do nothing Write back Do nothing Decode Do nothing PC Update Set PC to Dest if branch taken or to incremented PC if not branch Execute Determine whether to take branch based on jump condition and condition codes 2

3. Stage Computation: Jumps jXX Dest icode:ifun M1[PC] Read instruction byte Fetch valC valP M4[PC+1] PC+5 Read destination address Fall through address Decode Execute Bch Cond(CC,ifun) Take branch? Memory Write back PC update PC Bch ? valC : valP Update PC Compute both addresses Choose based on setting of condition codes and branch condition 3

4. Executing call call Dest 8 0 Dest return: XX XX target: XX XX Fetch Memory Read 5 bytes Increment PC by 5 Write incremented PC to new value of stack pointer Write back Update stack pointer Decode Read stack pointer PC Update Set PC to Dest Execute Decrement stack pointer by 4 4

5. Stage Computation: call call Dest icode:ifun M1[PC] Read instruction byte Fetch valC valP M4[PC+1] PC+5 Read destination address Compute return point Decode valB valE R[%esp] valB + 4 Read stack pointer Decrement stack pointer Execute M4[valE] R[%esp] valP valE Memory Write Write return value on stack Update stack pointer back PC update PC valC Set PC to destination Use ALU to decrement stack pointer Store incremented PC 5

6. Executing ret 9 0 ret return: XX XX Fetch Memory Read 1 byte Read return address from old stack pointer Decode Write back Update stack pointer Read stack pointer Execute PC Update Set PC to return address Increment stack pointer by 4 6

7. Stage Computation: ret ret icode:ifun M1[PC] Read instruction byte Fetch valA valB valE R[%esp] R[%esp] valB + 4 Read operand stack pointer Read operand stack pointer Increment stack pointer Decode Execute valM R[%esp] M4[valA] valE Memory Write Read return address Update stack pointer back PC update PC valM Set PC to return address Use ALU to increment stack pointer Read return address from memory 7

8. Computation Steps OPl rA, rB icode:ifun rA:rB M1[PC+1] M1[PC] icode,ifun rA,rB valC valP valA, srcA valB, srcB valE Cond code valM dstE dstM PC Read instruction byte Read register byte [Read constant word] Compute next PC Read operand A Read operand B Perform ALU operation Set condition code register [Memory read/write] Write back ALU result [Write back memory result] Update PC Fetch valP valA valB valE Set CC PC+2 R[rA] R[rB] valB OP valA Decode Execute Memory Write R[rB] valE back PC update PC valP All instructions follow same general pattern Differ in what gets computed on each step 8

9. Computation Steps call Dest icode:ifun M1[PC] icode,ifun rA,rB valC valP valA, srcA valB, srcB valE Cond code valM dstE dstM PC Read instruction byte [Read register byte] Read constant word Compute next PC [Read operand A] Read operand B Perform ALU operation [Set condition code reg.] [Memory read/write] [Write back ALU result] Write back memory result Update PC Fetch valC valP M4[PC+1] PC+5 Decode valB valE R[%esp] valB + 4 Execute M4[valE] R[%esp] valP valE Memory Write back PC update PC valC All instructions follow same general pattern Differ in what gets computed on each step 9

10. Computed Values Fetch Execute icode ifun rA rB valC valP Instruction code Instruction function Instr. Register A Instr. Register B Instruction constant Incremented PC valE Bch ALU result Branch flag Memory valM Value from memory Decode srcA srcB dstE dstM valA valB Register ID A Register ID B Destination Register E Destination Register M Register value A Register value B 10

11. newPC SEQ Hardware New PC PC Key valM data out read Blue boxes: predesigned hardware blocks E.g., memories, ALU Data Data memory memory Mem. control Memory write Addr Data Bch valE Gray boxes: control logic Describe in HCL ALU fun. ALU ALU Execute CC CC ALU A ALU B White ovals: labels for signals Thick lines: 32-bit word values Thin lines: 4-8 bit values Dotted lines: 1-bit values valA valB dstE dstM srcA srcB dstE dstM srcA srcB Decode A A B B M M Register Register Register Register file file file file E E Write back icode ifun rA rB valC valP Instruction PC PC Instruction memory memory Fetch increment increment PC 11

12. Summary Today Control flow instructions Hardware for sequential machine (SEQ) Next time Control logic for instruction execution Timing and clocking 12

13. Systems I Datapath Design III Topics Control logic for instruction execution Timing and clocking 13

14. Fetch Logic icode ifun rA rB valC valP Need valC Instr valid PC PC increment increment Need regids Split Split Align Align Byte 0 Bytes 1-5 Instruction Instruction memory memory Predefined Blocks PC: Register containing PC Instruction memory: Read 6 bytes (PC to PC+5) Split: Divide instruction byte into icode and ifun Align: Get fields for rA, rB, and valC PC 14

15. Fetch Logic icode ifun rA rB valC valP Need valC Instr valid PC PC increment increment Need regids Split Split Align Align Byte 0 Bytes 1-5 Instruction Instruction memory memory PC Control Logic Instr. Valid: Is this instruction valid? Need regids: Does this instruction have a register byte? Need valC: Does this instruction have a constant word? 15

16. Fetch Control Logic in HCL icode ifun Split Byte 0 Instruction memory # Determine instruction code int icode = [ imem_error: INOP; 1: imem_icode; ]; imem_error PC # Determine instruction function int ifun = [ imem_error: FNONE; 1: imem_ifun; ]; 16

17. nop nop nop 0 0 0 0 0 0 0 0 Fetch Control Logic halt halt halt 1 1 1 1 0 0 0 0 rrmovl rA, rB rrmovl rA, rB rrmovl rA, rB rA rB rA rB rA rB rA rB 2 2 2 2 0 0 0 0 irmovl V, rB irmovl V, rB irmovl V, rB rB rB rB rB V V V 3 3 3 3 0 0 0 0 8 8 8 8 rmmovl rA, D(rB) rmmovl rA, D(rB) rmmovl rA, D(rB) rA rB rA rB rA rB rA rB D D D 4 4 4 4 0 0 0 0 mrmovl D(rB), rA mrmovl D(rB), rA mrmovl D(rB), rA rA rB rA rB rA rB rA rB D D D 5 5 5 5 0 0 0 0 OPl rA, rB OPl rA, rB OPl rA, rB fn rA rB fn rA rB fn fn rA rB rA rB 6 6 6 6 jXX Dest jXX Dest jXX Dest fn fn fn fn Dest Dest Dest 7 7 7 7 call Dest call Dest call Dest Dest Dest Dest 8 8 8 8 0 0 0 0 ret ret ret 9 9 9 9 0 0 0 0 pushl rA pushl rA pushl rA rA rA rA rA A A A A 0 0 0 0 8 8 8 8 popl rA popl rA popl rA rA rA rA rA B B B B 0 0 0 0 8 8 8 8 bool need_regids = icode in { IRRMOVL, IOPL, IPUSHL, IPOPL, IIRMOVL, IRMMOVL, IMRMOVL }; bool instr_valid = icode in { INOP, IHALT, IRRMOVL, IIRMOVL, IRMMOVL, IMRMOVL, IOPL, IJXX, ICALL, IRET, IPUSHL, IPOPL }; 17

18. Decode Logic valA valB valM valE Register File Read ports A, B Write ports E, M Addresses are register IDs or 8 (no access) A B M Register Register file file dstM E dstE srcA srcB dstE dstM srcA srcB Control Logic srcA, srcB: read port addresses dstA, dstB: write port addresses icode rA rB 18

19. A Source OPl rA, rB valA R[rA] Decode Read operand A rmmovl rA, D(rB) valA R[rA] Decode Read operand A popl rA valA R[%esp] Decode Read stack pointer jXX Dest Decode No operand call Dest Decode No operand ret valA R[%esp] Decode Read stack pointer int srcA = [ ]; icode in { IRRMOVL, IRMMOVL, IOPL, IPUSHL } : rA; icode in { IPOPL, IRET } : RESP; 1 : RNONE; # Don't need register 19

20. E Destination OPl rA, rB R[rB] valE Write-back Write back result rmmovl rA, D(rB) Write-back None popl rA R[%esp] valE Write-back Update stack pointer jXX Dest Write-back None call Dest R[%esp] valE Write-back Update stack pointer ret R[%esp] valE Write-back Update stack pointer int dstE = [ ]; icode in { IRRMOVL, IIRMOVL, IOPL} : rB; icode in { IPUSHL, IPOPL, ICALL, IRET } : RESP; 1 : RNONE; # Don't need register 20

21. Execute Logic Units ALU Implements 4 required functions Generates condition code values Bch valE CC bcond bcond Register with 3 condition code bits ALU fun. ALU ALU CC CC bcond Computes branch flag Set CC ALU A ALU B Control Logic Set CC: Should condition code register be loaded? ALU A: Input A to ALU ALU B: Input B to ALU ALU fun: What function should ALU compute? icode ifun valC valA valB 21

22. ALU A Input OPl rA, rB valE valB OP valA Execute Perform ALU operation rmmovl rA, D(rB) valE valB + valC Execute Compute effective address popl rA valE valB + 4 Execute Increment stack pointer jXX Dest Execute No operation call Dest valE valB + 4 Execute Decrement stack pointer ret valE valB + 4 Execute Increment stack pointer int aluA = [ ]; icode in { IRRMOVL, IOPL } : valA; icode in { IIRMOVL, IRMMOVL, IMRMOVL } : valC; icode in { ICALL, IPUSHL } : -4; icode in { IRET, IPOPL } : 4; # Other instructions don't need ALU 22

23. ALU Operation OPl rA, rB valE valB OP valA Execute Perform ALU operation rmmovl rA, D(rB) valE valB + valC Execute Compute effective address popl rA valE valB + 4 Execute Increment stack pointer jXX Dest Execute No operation call Dest valE valB + 4 Execute Decrement stack pointer ret valE valB + 4 Execute Increment stack pointer int alufun = [ ]; icode == IOPL : ifun; 1 : ALUADD; 23

24. Memory Logic Memory Reads or writes memory word valM data out Mem. read read Data Data memory memory Control Logic Mem. read: should word be read? Mem. write: should word be written? Mem. addr.: Select address Mem. data.: Select data Mem. write write data in Mem addr Mem data icode valE valA valP 24

25. Instruction Status Stat Control Logic stat: What is instruction status? valM stat dmem_error data out Mem. read read instr_valid Data memory imem_error Mem. write write data in Mem. addr Mem. data icode valE valA valP ## Determine instruction status int Stat = [ imem_error || dmem_error : SADR; !instr_valid: SINS; icode == IHALT : SHLT; 1 : SAOK; ]; 25

26. Memory Address OPl rA, rB Memory No operation rmmovl rA, D(rB) M4[valE] valA Memory Write value to memory popl rA valM M4[valA] Memory Read from stack jXX Dest Memory No operation call Dest M4[valE] valP Memory Write return value on stack ret valM M4[valA] Memory Read return address int mem_addr = [ icode in { IRMMOVL, IPUSHL, ICALL, IMRMOVL } : valE; icode in { IPOPL, IRET } : valA; # Other instructions don't need address ]; 26

27. Memory Read OPl rA, rB Memory No operation rmmovl rA, D(rB) M4[valE] valA Memory Write value to memory popl rA valM M4[valA] Memory Read from stack jXX Dest Memory No operation call Dest M4[valE] valP Memory Write return value on stack ret valM M4[valA] Memory Read return address bool mem_read = icode in { IMRMOVL, IPOPL, IRET }; 27

28. PC Update Logic PC New PC Select next value of PC New PC icode Bch valC valM valP 28

29. PC Update OPl rA, rB PC valP PC update Update PC rmmovl rA, D(rB) PC valP PC update Update PC popl rA PC valP PC update Update PC jXX Dest PC Bch ? valC : valP PC update Update PC call Dest PC valC PC update Set PC to destination ret PC valM PC update Set PC to return address int new_pc = [ ]; icode == ICALL : valC; icode == IJXX && Bch : valC; icode == IRET : valM; 1 : valP; 29

30. SEQ Operation State PC register Cond. Code register Data memory Register file All updated as clock rises Read Read Write Write Combinational Logic Data Data memory memory CC CC Read Ports Write Ports Combinational Logic ALU Control logic Memory reads Instruction memory Register file Data memory Register Register file file PC 0x00c 30

31. SEQ Operation #2 Cycle 1 Cycle 2 Cycle 3 Cycle 4 Clock Cycle 1: 0x000: irmovl $0x100,%ebx # %ebx <-- 0x100 Cycle 2: 0x006: irmovl $0x200,%edx # %edx <-- 0x200 Cycle 3: 0x00c: addl %edx,%ebx # %ebx <-- 0x300 CC <-- 000 Cycle 4: 0x00e: je dest # Not taken Read Read Write Write state set according to second irmovl instruction combinational logic starting to react to state changes Combinational Logic Data Data memory memory CC CC 100 100 Read Ports Write Ports Register file Register file %ebx = 0x100 %ebx = 0x100 PC 0x00c 31

32. SEQ Operation #3 Cycle 1 Cycle 2 Cycle 3 Cycle 4 Clock Cycle 1: 0x000: irmovl $0x100,%ebx # %ebx <-- 0x100 Cycle 2: 0x006: irmovl $0x200,%edx # %edx <-- 0x200 Cycle 3: 0x00c: addl %edx,%ebx # %ebx <-- 0x300 CC <-- 000 Cycle 4: 0x00e: je dest # Not taken Read Read Write Write state set according to second irmovl instruction combinational logic generates results for addl instruction Combinational Logic Data Data memory memory CC CC 100 100 Read Ports Write Ports 000 Register file Register file %ebx = 0x100 %ebx = 0x100 0x00e PC 0x00c 32

33. SEQ Operation #4 Cycle 1 Cycle 2 Cycle 3 Cycle 4 Clock Cycle 1: 0x000: irmovl $0x100,%ebx # %ebx <-- 0x100 Cycle 2: 0x006: irmovl $0x200,%edx # %edx <-- 0x200 Cycle 3: 0x00c: addl %edx,%ebx # %ebx <-- 0x300 CC <-- 000 Cycle 4: 0x00e: je dest # Not taken Read Read Write Write state set according to addl instruction combinational logic starting to react to state changes Combinational Logic Data Data memory memory CC CC 000 000 Read Ports Write Ports Register file Register file %ebx = 0x300 %ebx = 0x300 PC 0x00e 33

34. SEQ Operation #5 Cycle 1 Cycle 2 Cycle 3 Cycle 4 Clock Cycle 1: 0x000: irmovl $0x100,%ebx # %ebx <-- 0x100 Cycle 2: 0x006: irmovl $0x200,%edx # %edx <-- 0x200 Cycle 3: 0x00c: addl %edx,%ebx # %ebx <-- 0x300 CC <-- 000 Cycle 4: 0x00e: je dest # Not taken Read Read Write Write state set according to addl instruction combinational logic generates results for je instruction Combinational Logic Logic Combinational Data Data Data Data memory memory memory memory CC CC CC CC 000 000 000 000 Read Read Ports Ports Write Ports Ports Write Register file file file Register Register Register file %ebx = 0x300 %ebx = 0x300 %ebx = 0x300 %ebx = 0x300 0x013 0x013 PC PC 0x00e 0x00e 34

35. SEQ Summary Implementation Express every instruction as series of simple steps Follow same general flow for each instruction type Assemble registers, memories, predesigned combinational blocks Connect with control logic Limitations Too slow to be practical In one cycle, must propagate through instruction memory, register file, ALU, and data memory Would need to run clock very slowly Hardware units only active for fraction of clock cycle 35