CS 150 - Spring 2007 – Lec #14: Control Implementation - 1Controller Implementation--Part I• Alternative controller FSM implementationapproaches based on:– Classical Moore and Mealy machines– Time state: Divide and Counter– Jump counters– Microprogramming (ROM) based approaches» branch sequencers» horizontal microcode» vertical microcodeCS 150 - Spring 2007 – Lec #14: Control Implementation - 2INQ0Q1CLK100Cascading Edge-triggered Flip-Flops• Shift register– New value goes into first stage– While previous value of first stage goes into second stage– Consider setup/hold/propagation delays (prop must be > hold)CLKINQ0 Q1D Q D Q OUTCS 150 - Spring 2007 – Lec #14: Control Implementation - 3INQ0Q1CLK100Cascading Edge-triggered Flip-Flops• Shift register– New value goes into first stage– While previous value of first stage goes into second stage– Consider setup/hold/propagation delays (prop must be > hold)CLKINQ0 Q1D Q D Q OUTDelayClk1Clk1CS 150 - Spring 2007 – Lec #14: Control Implementation - 4original state: IN = 0, Q0 = 1, Q1 = 1due to skew, next state becomes: Q0 = 0, Q1 = 0, and not Q0 = 0, Q1 = 1CLK1 is a delayedversion of CLKInQ0Q1CLKCLK1100Clock Skew• The problem– Correct behavior assumes next state of all storage elementsdetermined by all storage elements at the same time– Difficult in high-performance systems because time for clock toarrive at flip-flop is comparable to delays through logic (and will soonbecome greater than logic delay)– Effect of skew on cascaded flip-flops:CS 150 - Spring 2007 – Lec #14: Control Implementation - 5Why Gating of Clocks is Bad!RegClkLDRegClkLDGOODBADDo NOT Mess With Clock Signals!gatedClKCS 150 - Spring 2007 – Lec #14: Control Implementation - 6Why Gating of Clocks is Bad!Do NOT Mess With Clock Signals!ClkLDgatedClkLD generated by FSMshortly after rising edge of CLKRunt pulse plays HAVOC with register internals!ClkLDngatedClkNASTY HACK: delay LD throughnegative edge triggered FF toensure that it won’t change duringnext positive edge event Clk skew PLUS LD delayed by half clock cycle …What is the effect on your register transfers?CS 150 - Spring 2007 – Lec #14: Control Implementation - 7Why Gating of Clocks is Bad!ClkResetRegCounterBADDo NOT Mess With Clock Signals!slowClKCS 150 - Spring 2007 – Lec #14: Control Implementation - 8Why Gating of Clocks is Bad!ClkResetRegCounterBetter!Do NOT Mess With Clock Signals!LDCS 150 - Spring 2007 – Lec #14: Control Implementation - 9Alternative Ways to ImplementProcessor 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 Logic Block Functionality: Jump Counters– Counters, Multiplexers, Decoders• Microprogramming: ROM-based methods– Direct encoding of next states and outputsCS 150 - Spring 2007 – Lec #14: Control Implementation - 10Random Logic• Perhaps poor choice of terms for "classical"FSMs• Contrast with structured logic: PLA, FPGA,ROM-based (latter used in microprogrammedcontrollers)• Could just as easily construct Moore and Mealymachines with these componentsCS 150 - Spring 2007 – Lec #14: Control Implementation - 11Moore MachineState DiagramNote capture of MBRin these states0 ! PCResetWait/Wait/Wait/Wait/Wait/Wait/=11=10=0=1BR0BR1IF3OD=00=01AD0ST0ST1 AD1Wait/Wait/AD2Wait/Wait/LD0LD1LD2Wait/Wait/PC ! MAR, PC + 1 ! PCMAR ! Mem, 1 ! Read/Write, 1 ! Request, Mem ! MBRMBR ! IRIR ! MAR IR ! MARIR ! PCMAR ! Mem, 1 ! Read/Write, 1 ! Request, Mem ! MBRMAR ! Mem, 0 ! Read/Write, 1 ! Request, MBR ! MemMAR ! Mem, 1 ! Read/Write, 1 ! Request, Mem ! MBRMBR ! ACMBR + AC ! ACIF2IF1IF0RESIR ! MAR, AC ! MBRCS 150 - Spring 2007 – Lec #14: Control Implementation - 12Memory-Register Interface TimingValid data latched on IF2 to IF3 transitionbecause data must be valid before Wait can go lowCLK WAIT Mem Bus Latch MBRIF1 IF2 IF2 IF2 IF3Invalid Data LatchedInvalid Data LatchedValid Data LatchedData ValidCS 150 - Spring 2007 – Lec #14: Control Implementation - 13Moore Machine Diagram16 states, 4 bit state registerNext State Logic: 9 Inputs, 4 OutputsOutput Logic: 4 Inputs, 18 OutputsThese can be implemented via ROM or PAL/PLANext State: 512 x 4 bit ROMOutput: 16 x 18 bit ROMNext State LogicClock StateReset Wait IR<15> IR<14> AC<15>Output LogicRead/Write Request 0 ! PC PC + 1 ! PC PC ! ABUS IR ! ABUS ABUS ! MAR ABUS ! PC MAR ! Memory Address Bus Memory Data Bus ! MBR MBR ! Memory Data Bus MBR ! MBUS MBUS ! IR MBUS ! ALU B MBUS ! AC RBUS ! AC RBUS ! MBR ALU ADD CS 150 - Spring 2007 – Lec #14: Control Implementation - 14Moore Machine State TableResetWaitIR<15> IR<14> AC<15>Current State Next State Register Transfer Ops1 X X X X X RES (0000)0 X X X X RES (0000) IF0 (0001) 0 ! PC0 X X X X IF0 (0001) IF1 (0001) PC ! MAR, PC + 1 ! PC0 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 ! MBR0 0 X X X IF3 (0100) IF3 (0100) MBR ! IR0 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)CS 150 - Spring 2007 – Lec #14: Control Implementation - 15ResetWait IR<15> IR<14> AC<15> Current State Next State Register Transfer Ops0 X X X X LD0 (0110) LD1 (0111) IR ! MAR0 1 X X X LD1 (0111) LD1 (0111) MAR ! Mem, Read,0 0 X X X LD1 (0111) LD2 (1000) Request, Mem ! MBR0 X X X X LD2 (1000) IF0 (0001) MBR ! AC0 X X X X ST0 (1001) ST1 (1010) IR ! MAR, AC ! MBR0 1 X X X ST1 (1010) ST1 (1010) MAR ! Mem, Write,0 0 X X X ST1 (1010) IF0 (0001) Request, MBR ! Mem0 X X X X AD0 (1011) AD1 (1100) IR ! MAR0 1 X X X AD1 (1100) AD1 (1100) MAR ! Mem, Read,0 0 X X X AD1 (1100) AD2 (1101) Request, Mem ! MBR0 X X X X AD2 (1101) IF0 (0001) MBR + AC ! AC0 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 ! PCMoore Machine State TableCS 150 - Spring 2007 – Lec #14: Control Implementation - 16Moore Machine State Transition Table• Observations:– Extensive use of Don't Cares– Inputs used only in a small number of statee.g., AC<15> examined only in BR0 stateIR<15:14> examined only in OD state• Some outputs always asserted in a group• ROM-based implementations cannot take advantage ofdon't cares• However, ROM-based implementation can skip stateassignment stepCS 150 - Spring
View Full Document
Unlocking...