EECS150Section 10Controller ImplementationsFall 2001EECS150 - Fall 2001 1-2Implement of Processor FSMsClassical Finite State Machine DesignDivide and Conquer Approach: Time-State Method Partition FSM into multiple communicating FSMsExploit MSI Functionality: Jump Counters Counters, Multiplexers, DecodersMicroprogramming: ROM-based methods Direct encoding of next states and outputsEECS150 - Fall 2001 1-3Processor / Memory InterfaceProblem:The processor and memory often do not share the same clock.Solution:Use appropriate handshakingEECS150 - Fall 2001 1-4Moore Note 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 → MBREECS150 - Fall 2001 1-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 ValidEECS150 - Fall 2001 1-6Processor Signal FLowEECS150 - Fall 2001 1-7Moore Machine Diagram16 states, 4 bit state registerNext State Logic: 9 Inputs, 4 OutputsOutput Logic: 4 Inputs, 18 OutputsThese can be implemented via ROMor 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 EECS150 - Fall 2001 1-8Moore Machine State TableReset Wait IR<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 (0010) 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)0 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 → PC{{{{EECS150 - Fall 2001 1-9State Transition TableObservations: 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 stateSome outputs always asserted in a groupROM-based implementations cannot take advantage of don't caresHowever, ROM-based implementation can skip state assignment stepEECS150 - Fall 2001 1-10SynchronizerCircuitry atInputs andOutputsSynchronizerCircuitry atInputs andOutputsOutput LogicOutput LogicOutput LogicDDDDSTATE STATE STATEQQQAAA'A'Qƒƒ'ƒƒƒ'ASynchronous Mealy MachinesStandard Mealy Machine has asynchronous outputsThese change in response to input changes, independent of clockRevise Mealy Machine design so outputs change only on clock edgesOne approach: non-overlapping clocksEECS150 - Fall 2001 1-11Synchronous Mealy MachinesCase I: Synchronizers at Inputs and OutputsA asserted in Cycle 0, ƒ becomes asserted after 2 cycle delay!This is clearly overkill!cycle 0cycle 1 cycle 2CLKAA'ƒƒ'S0S1S2A/ƒEECS150 - Fall 2001 1-12Synchronous Mealy MachineCase II: Synchronizers on InputsA asserted in Cycle 0, ƒ follows in next cycleSame as using delayed signal (A') in Cycle 1!cycle 0cycle 1 cycle 2CLKAA'ƒS0S1A/ƒS0S1A'/ƒEECS150 - Fall 2001 1-13Synchronous Mealy MachinesCase III: Synchronized OutputsA asserted during Cycle 0, ƒ' asserted in next cycleEffect of ƒ delayed one cyclecycle 0cycle 1 cycle 2CLKAƒƒ'S0S1A/ƒEECS150 - Fall 2001 1-14Synchronous Mealy MachinesImplications for Processor FSM Already DerivedConsider inputs: Reset, Wait, IR<15:14>, AC<15>Latter two already come from registers, and are sync'dto clockPossible to load IR with new instruction in one state & perform multiway branch on opcode in next stateBest solution for Reset and Wait: synchronized inputsPlace D flipflops between these external signals and thecontrol inputs to the processor FSMSync'd versions of Reset and Wait delayed by one clock cycleEECS150 - Fall 2001 1-15Time State Divide and ConquerOverview Classical Approach: Monolithic Implementations Alternative "Divide & Conquer" Approach:Decompose FSM into several simpler communicatingFSMsTime 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)EECS150 - Fall 2001 1-16Time State (Divide & Conquer)Time State FSMMost instructions follow same basic sequenceDiffer only in detailed execution sequenceTime State FSM can be parameterized byopcode and AC statesInstruction State:stored in IR<15:14>Condition State:stored in AC<15>T0T1T2T3T4T5T6T7Wait/Wait/Wait/Wait/Wait/Wait/BRN • AC 0/(LD + ST + ADD) • Wait/BRN + (ST • Wait)/(LD + ADD) • WaitIR=11=10=01=00LD STADD BRNAC<15>=0AC<15>=1AC 0AC < 0≥≥EECS150 - Fall 2001 1-17Time State (Divide & Conquer)Generation of Microoperations0 →PC: ResetPC + 1 →PC: T0PC →MAR: T0MAR →Memory Address Bus: T2 + T6 • (LD + ST + ADD)Memory Data Bus →MBR: T2 + T6 • (LD + ADD)MBR →Memory Data Bus: T6 • STMBR →IR: T4MBR →AC: T7 • LDAC →MBR: T5 • STAC + MBR →AC: T7 • ADDIR<13:0> →MAR: T5 • (LD + ST + ADD)IR<13:0> →PC:
View Full Document
Unlocking...