Overview презентация

Overview Alternative controller FSM implementation approaches based on: classical Moore and Mealy machines jump counters microprogramming (ROM) based approaches branch sequencers horizontal microcode vertical microcode

Alternative Ways to Implement Processor FSMs "Random Logic" based on Moore and Mealy Design Classical Finite State Machine Design Divide and Conquer Approach: Time-State Method Partition FSM into multiple communicating FSMs Exploit MSI Components: Jump Counters Counters, Multiplexors, Decoders Microprogramming: ROM-based methods Direct encoding of next states and outputs

Random Logic Perhaps poor choice of terms for "classical" FSMs Contrast with structured logic: PAL/PLA, PGA, ROM Could just as easily construct Moore and Mealy machines with these components

Moore Machine State Diagram

Memory-Register Interface Timing

Moore Machine Diagram

Moore Machine State Table Reset Wait IR<15> IR<14> AC<15> Current State Next State Register Transfer Ops 1 X X X X X RES (0000) 0 X X X X RES (0000) IF0 (0001) 0 PC 0 X X X X IF0 (0001) IF1 (0001) PC  MAR, PC + 1  PC 0 0 X X X IF1 (0010) IF1 (0010) 0 1 X X X IF1 (0010) IF2 (0011) 0 1 X X X IF2 (0011) IF2 (0011) MAR  Mem, Read, 0 0 X X X IF2 (0011) IF3 (0100) Request, Mem  MBR 0 0 X X X IF3 (0100) IF3 (0100) MBR  IR 0 1 X X X IF3 (0100) OD (0101) 0 X 0 0 X OD (0101) LD0 (0110) 0 X 0 1 X OD (0101) ST0 (1001) 0 X 1 0 X OD (0101) AD0 (1011) 0 X 1 1 X OD (0101) BR0 (1110)

Moore Machine State Table Reset Wait IR<15> IR<14> AC<15> Current State Next State Register Transfer Ops 0 X X X X LD0 (0110) LD1 (0111) IR  MAR 0 1 X X X LD1 (0111) LD1 (0111) MAR  Mem, Read, 0 0 X X X LD1 (0111) LD2 (1000) Request, Mem  MBR 0 X X X X LD2 (1000) IF0 (0001) MBR  AC 0 X X X X ST0 (1001) ST1 (1010) IR  MAR, AC  MBR 0 1 X X X ST1 (1010) ST1 (1010) MAR  Mem, Write, 0 0 X X X ST1 (1010) IF0 (0001) Request, MBR  Mem 0 X X X X AD0 (1011) AD1 (1100) IR  MAR 0 1 X X X AD1 (1100) AD1 (1100) MAR  Mem, Read, 0 0 X X X AD1 (1100) AD2 (1101) Request, Mem  MBR 0 X X X X AD2 (1101) IF0 (0001) MBR + AC  AC 0 X X X 0 BR0 (1110) IF0 (0001) 0 X X X 1 BR0 (1110) BR1 (1111) 0 X X X X BR1 (1111) IF0 (0001) IR  PC

Moore Machine State Transition Table Observations: Extensive use of Don't Cares Inputs used only in a small number of state e.g., AC<15> examined only in BR0 state IR<15:14> examined only in OD state Some outputs always asserted in a group ROM-based implementations cannot take advantage of don't cares However, ROM-based implementation can skip state assignment step

Moore Machine Implementation

Moore Machine Implementation

Synchronous Mealy Machines Standard Mealy Machine has asynchronous outputs These change in response to input changes, independent of clock Revise Mealy Machine design so outputs change only on clock edges One approach: non-overlapping clocks

Synchronous Mealy Machines

Synchronous Mealy Machine

Synchronous Mealy Machines

Synchronous Mealy Machines Implications for Processor FSM Already Derived Consider inputs: Reset, Wait, IR<15:14>, AC<15> Latter two already come from registers, and are sync'd to clock Possible to load IR with new instruction in one state & perform multiway branch on opcode in next state Best solution for Reset and Wait: synchronized inputs Place D flipflops between these external signals and the control inputs to the processor FSM Sync'd versions of Reset and Wait delayed by one clock cycle

Time State Divide and Conquer Overview Classical Approach: Monolithic Implementations Alternative "Divide & Conquer" Approach: Decompose FSM into several simpler communicating FSMs Time state FSM (e.g., IFetch, Decode, Execute) Instruction state FSM (e.g., LD, ST, ADD, BRN) Condition state FSM (e.g., AC < 0, AC  0)

Time State (Divide & Conquer)

Time State (Divide & Conquer)

Jump Counter

Jump Counters

Jump Counters

Jump Counters

Jump Counters

Jump Counters

Jump Counters

Jump Counter

Jump Counters

Branch Sequencers

Branch Sequencers

Branch Sequencer

Example Processor FSM ROM ADDRESS ROM CONTENTS (Reset, Current State, a, b) Next State Register Transfer Operations RES 0 0000 X X 0001 (IF0) PC  MAR, PC + 1  PC IF0 0 0001 0 0 0001 (IF0) 0 0001 1 1 0010 (IF1) MAR  Mem, Read, Request IF1 0 0010 0 0 0011 (IF2) MAR  Mem, Read, Request 0 0010 1 1 0010 (IF1) Mem  MBR IF2 0 0011 0 0 0011 (IF2) 0 0011 1 1 0100 (OD) MBR  IR OD 0 0100 0 0 0101 (LD0) IR  MAR 0 0100 0 1 1000 (ST0) IR  MAR, AC  MBR 0 0100 1 0 1001 (AD0) IR  MAR 0 0100 1 1 1101 (BR0) IR  MAR

Example Processor FSM ROM ADDRESS ROM CONTENTS (Reset, Current State, a, b) Next State Register Transfer Operations LD0 0 0101 X X 0110 (LD1) MAR  Mem, Read, Request LD1 0 0110 0 0 0111 (LD2) Mem  MBR 0 0110 1 1 0110 (LD1) MAR  Mem, Read, Request LD2 0 0111 X X 0000 (RES) MBR  AC ST0 0 1000 X X 1001 (ST1) MAR  Mem, Write, Request, MBR  Mem ST1 0 1001 0 0 0000 (RES) 0 1001 1 1 1001 (ST1) MAR  Mem, Write, Request, MBR  Mem AD0 0 1010 X X 1011 (AD1) MAR  Mem, Read, Request AD1 0 1011 0 0 1100 (AD2) 0 1011 1 1 1011 (AD1) MAR  Mem, Read, Request AD2 0 1100 X X 0000 (RES) MBR + AC  AC BR0 0 1101 0 0 0000 (RES) 0 1101 1 1 0000 (RES) IR  PC

Branch Sequencers

Microprogramming

Microprogramming

Horizontal Microprogramming

Horizontal Microprogramming

Horizontal Microprogramming

Horizontal Microprogramming

Vertical Microprogramming More extensive encoding to reduce ROM word length Typically use multiple microword formats: Horizontal microcode -- next state + control bits in same word Separate formats for control outputs and "branch jumps" may require several microwords in a sequence to implement same function as single horizontal word In the extreme, very much like assembly language programming

Vertical Microprogramming

Vertical Microprogramming ROM ADDRESS SYMBOLIC CONTENTS BINARY CONTENTS 000000 RES RT PC  MAR, PC +1  PC 0 001 011 100 000001 IF0 RT MAR  M, Read 0 100 000 101 000010 BJ Wait=0, IF0 1 000 000 001 000011 IF1 RT MAR  M, M  MBR, Read 0 100 100 101 000100 BJ Wait=1, IF1 1 001 000 011 000101 IF2 RT MBR  IR 0 011 010 000 000110 BJ Wait=0, IF2 1 000 000 101 000111 RT IR  MAR 0 010 011 000 001000 OD BJ IR<15>=1, OD1 1 101 010 101 001001 BJ IR<14>=1, ST0 1 111 010 000 001010 LD0 RT MAR  M, Read 0 100 000 101 001011 LD1 RT MAR  M, M  MBR, Read 0 100 100 101 001100 BJ Wait=1, LD1 1 001 001 011 001101 LD2 RT MBR  AC 0 110 001 010 001110 BJ Wait=0, RES 1 000 000 000 001111 BJ Wait=1, RES 1 001 000 000

Vertical Microprogramming ROM ADDRESS SYMBOLIC CONTENTS BINARY CONTENTS 010000 ST0 RT AC  MBR 0 101 101 000 010001 RT MAR  M, MBR  M, Write 0 100 111 110 010010 ST1 RT MAR  M, MBR  M, Write 0 100 111 110 010011 BJ Wait=0, RES 1 000 000 000 010100 BJ Wait=1, ST1 1 001 010 010 010101 OD1 BJ IR<14>=1, BR0 1 111 011 101 010110 AD0 RT MAR  M, Read 0 100 000 101 010111 AD1 RT MAR  M, M  MBR, Read 0 100 100 101 011000 BJ Wait=1, AD1 1 001 010 111 011001 AD2 RT AC + MBR  AC 0 110 001 001 011010 BJ Wait=0, RES 1 000 000 000 011011 BJ Wait=1, RES 1 000 000 000 011100 BR0 BJ AC<15>=0, RES 1 010 000 000 011101 RT IR  PC 0 010 110 000 011110 BJ AC<15>=1, RES 1 011 000 000

Vertical Programming

Vertical Microprogramming

Vertical Microprogramming Writeable Control Store Part of control store addresses map into RAM Allows assembly language programmer to implement own instructions Extend "native" instruction set with application specific instructions Requires considerable sophistication to write microcode Not a popular approach with today's processors Make the native instruction set simple and fast Write "higher level" functions as assembly language sequences

Controller Implementation Summary Control Unit Organization Register transfer operation Classical Moore and Mealy machines Time State Approach Jump Counter Branch Sequencers Horizontal and Vertical Microprogramming