OverviewAlternative Ways to Implement Processor FSMsRandom LogicMoore Machine State DiagramMemory-Register Interface TimingMoore Machine DiagramMoore Machine State TableSlide 8Moore Machine State Transition TableMoore Machine ImplementationSlide 11Synchronous Mealy MachinesSlide 13Synchronous Mealy MachineSlide 15Slide 16Time State Divide and ConquerTime State (Divide & Conquer)Slide 19Jump CounterJump CountersSlide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Branch SequencersSlide 30Branch SequencerExample Processor FSMSlide 33Slide 34MicroprogrammingSlide 36Horizontal MicroprogrammingSlide 38Slide 39Slide 40Vertical MicroprogrammingSlide 42Slide 43Slide 44Vertical ProgrammingSlide 46Slide 47Controller Implementation SummaryCS 150 - Spring 2001 - Controller Implementation - 1Overview•Alternative controller FSM implementation approaches based on:–classical Moore and Mealy machines–jump counters–microprogramming (ROM) based approaches–branch sequencers–horizontal microcode–vertical microcodeCS 150 - Spring 2001 - Controller Implementation - 2Alternative 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 Functionality: Jump Counters–Counters, Multiplexers, Decoders•Microprogramming: ROM-based methods–Direct encoding of next states and outputsCS 150 - Spring 2001 - Controller Implementation - 3Random 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 componentsCS 150 - Spring 2001 - Controller Implementation - 4Moore 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 2001 - Controller Implementation - 5Memory-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 2001 - Controller Implementation - 6Moore 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 ADDCS 150 - Spring 2001 - Controller Implementation - 7Moore Machine State TableResetWaitIR<15>IR<14>AC<15> Current StateNext StateRegister Transfer Ops1 XX XX XRES (0000)0 XX XXRES (0000)IF0 (0001) 0 PC0 XX XXIF0 (0001)IF1 (0001)PC MAR, PC + 1 PC0 0X XXIF1 (0010)IF1 (0010)0 1X XXIF1 (0010)IF2 (0011)0 1X XXIF2 (0011)IF2 (0011)MAR Mem, Read,0 0X XXIF2 (0011)IF3 (0100)Request, Mem MBR0 0X XXIF3 (0100)IF3 (0100)MBR IR0 1X XXIF3 (0100)OD (0101)0 X0 0XOD (0101)LD0 (0110)0 X0 1XOD (0101)ST0 (1001)0 X1 0XOD (0101)AD0 (1011)0 X1 1XOD (0101)BR0 (1110)CS 150 - Spring 2001 - Controller Implementation - 8ResetWaitIR<15>IR<14>AC<15> Current StateNext StateRegister Transfer Ops0 XX XXLD0 (0110)LD1 (0111)IR MAR0 1X XXLD1 (0111)LD1 (0111)MAR Mem, Read,0 0X XXLD1 (0111)LD2 (1000)Request, Mem MBR0 XX XXLD2 (1000)IF0 (0001)MBR AC0 XX XXST0 (1001)ST1 (1010)IR MAR, AC MBR0 1X XXST1 (1010)ST1 (1010)MAR Mem, Write,0 0X XXST1 (1010)IF0 (0001)Request, MBR Mem0 XX XXAD0 (1011)AD1 (1100)IR MAR0 1X XXAD1 (1100)AD1 (1100)MAR Mem, Read,0 0X XXAD1 (1100)AD2 (1101)Request, Mem MBR0 XX XXAD2 (1101)IF0 (0001)MBR + AC AC0 XX X0BR0 (1110)IF0 (0001)0 XX X1BR0 (1110)BR1 (1111)0 XX XXBR1 (1111)IF0 (0001)IR PCMoore Machine State TableCS 150 - Spring 2001 - Controller Implementation - 9Moore 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 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 stepCS 150 - Spring 2001 - Controller Implementation - 10Moore Machine ImplementationAssume PAL/PLA implementation styleFirst idea: run ESPRESSO with naive state assignment.i 9 .o 4.ilb reset wait ir15 ir14 ac15 q3 q2 q1 q0.ob p3 p2 p1 p0.p 261---- ---- 0000 0---- 0001 000100--- 0010 001001--- 0010 001101--- 0011 0011 00--- 0011 010000--- 0100 010001--- 0100 01010-00- 0101 01100-01- 0101 10010-10- 0101 10110-11- 0101 11100---- 0110 011101--- 0111 011100--- 0111 10000---- 1000 00010---- 1001 101001--- 1010 101000--- 1010 00010---- 1011 110001--- 1100 110000--- 1100 11010---- 1101 00010---0 1110 0001 0---1 1110 11110---- 1111 0001.e.i 9.o 4.ilb reset wait ir15 ir14 ac15 q3 q2 q1 q0.ob p3 p2 p1 p0.p 210-00-0101 01100-01-0101 10010-11-0101 11100-10-0101 101101---1010 101000---0111 100000----011 01000----1000 00010---11110 111001---011- 01000----0001 000101---01-0 00010----1001 10100----1011 110000---1--0 00010----1100 11000----0-10 00100-----110 00010----11-1 00010----01-0 010001---0-1- 0011.e21 product termsCompare with 512product terms in ROMimplementation!CS 150 - Spring 2001 - Controller Implementation - 11Moore Machine ImplementationNOVA assignment does betterNOVA State Assignment SUMMARYonehot_products = 22best_products = 18best_size = 414states[0]:IF0 Best code: 0000states[1]:IF1 Best code: 1011states[2]:IF2 Best code: 1111states[3]:IF3 Best code: 1101states[4]:OD Best code: 0001states[5]:LD0 Best code: 0010states[6]:LD1 Best
View Full Document
Unlocking...