Refactor of State Machines

(1)

Refactor of State Machines

Martin Schoeberl

Technical University of Denmark Embedded Systems Engineering

March 24, 2022

(2)

Outline

I Repeat functions and parameters

I Repeat finite-state machine with datapath I Factoring of finite-state machines

I Input processing I Reset input

(3)

Midterm Evaluation

I Do we need this?

I An anonymous Google form (no login required) I 15 minutes time during the break

I We will look into it after the break

(4)

Functions

I Circuits can be encapsulated in functions I Eachfunction callgenerates hardware I A function is defined withdefname I Similar to methods in Java

I Simple functions can be a single line

def adder( v1 : UInt , v2 : UInt ) = v1 + v2 val add1 = adder (a , b)

val add2 = adder (c , d)

(5)

More Function Examples

I Functions can also contain registers

def addSub( add : Bool , a: UInt , b: UInt ) = Mux (add , a + b , a - b)

val res = addSub ( cond , a , b)

def rising(d: Bool ) = d && ! RegNext (d) val edge = rising ( cond )

(6)

The Counter as a Function

I Longer functions in curly brackets I Last value is the return value

def counter(n: UInt ) = {

val cntReg = RegInit (0. U (8. W)) cntReg := cntReg + 1. U

when ( cntReg === n) { cntReg := 0. U }

cntReg }

(7)

Functional Abstraction

I Functions for repeated pieces of logic I May contain state

I Functions may returnhardware I More lightweight than aModule

(8)

Parameterization

class ParamChannel(n: Int ) extends Bundle { val data = Input ( UInt (n.W))

val ready = Output ( Bool () ) val valid = Input ( Bool () ) }

val ch32 = new ParamChannel (32)

I Bundles and modules can be parametrized I Pass a parameter in the constructor

(9)

A Module with a Parameter

class ParamAdder(n: Int ) extends Module { val io = IO (new Bundle {

val a = Input ( UInt (n.W)) val b = Input ( UInt (n.W)) val c = Output ( UInt (n.W)) })

io .c := io .a + io .b }

I Parameter can also be a Chisel type

(10)

Use the Parameter

val add8 = Module (new ParamAdder (8) ) val add16 = Module (new ParamAdder (16) )

I Can be used for the display multiplexing configuration I Different maximum value for the counter for the simulation

and for the FPGA

(11)

FSM with Datapath

I A type of computing machine

I Consists of a finite-state machine (FSM) and a datapath I The FSM is the master (the controller) of the datapath I The datapath has computing elements

I E.g., adder, incrementer, constants, multiplexers, ...

I The datapath has storage elements (registers) I E.g., sum of money payed, count of something, ...

(12)

FSM-Datapath Interaction

I The FSM controls the datapath I For example, add 2 to the sum I By controlling multiplexers

I For example, select how much to add I Not adding means selecting 0 to add I Which value goes where

I The FSM logic also depends on datapath output

I Is there enough money payed to release a can of soda?

I FSM and datapath interact

(13)

Popcount Example

I An FSMD that computes the popcount I Also called the Hamming weight I Compute the number of ‘1’s in a word I Input is the data word

I Output is the count

I Code available atPopCount.scala

(14)

Popcount Block Diagram

dinValid popCntValid

FSM

din popCnt

popCntReady dinReady

Datapath

(15)

Popcount Connection

I Inputdinand outputpopCount I Both connected to the datapath I We need some handshaking I For data input and for count

output

FSM

din popCnt

Datapath

(16)

Popcount Handshake

I We use a ready-valid handshake I When data is available valid is

asserted

I When the receiver can accept data ready is asserted

I Transfer takes place when both are asserted

FSM

din popCnt

Datapath

(17)

The FSM

Count Idle

Done

Valid

Finished Result read

I A Very Simple FSM

I Two transitions depend on input/output handshake I One transition on the datapath output

(18)

The Datapath

+ din shf

0 0

cnt count

(19)

Let’s Explore the Code

I InPopCount.scala

(20)

Usage of an FSMD

I Maybe the main part your vending machine is an FSMD?

(21)

Factoring FSMs

I Divide a big problem into several smaller problems I Splitting a FSM into two or more

I Simplify the design

I FSMs communicate via logic signals

I FSM provides input controls signals to another I FSM senses output from another

(22)

Specification Of a Light Flasher

I Inputs: start I Outputs: light I Operation:

I When in = 1, FSM goes through 5 sequences:

I On-Off-On-Off-On I Each On sequence (flash):

I out = 1 I 6 cycles long

I Each Off sequence (space):

I out = 0 I 4 cycles long

I After 5 sequences, FSM goes back tooffstate to wait for

(23)

Light Flasher State Diagram

I Example from Dally, Chapter 17

I Copyright figure, so show it from older slides

(24)

Specification Change

I We have a flat FSM with 27 states I 27is(state)statements I If we change the specification to

I 12 cycles for each flash I 4 flashes

I 7 cycles between flashes

I Complete change ofswitchstatement I Now 70isstatements!

I This does not scale

(25)

Factor Light Flasher

I Factor out counting on and off intervals I Into a timer

I Reduces 6 and 4 states sequences into two single states I Results in

I a master FSM and I a timer FSM I Simplifies FSMs

I Allows easier change of interval lengths

(26)

Factored Light Flasher

start

timerLoad

light Master FSM

Timer timerSelect timerDone

(27)

Timer Specification

I Two inputs

I timerLoadto load the down counter

I timerSelectto select between 6 and 4 cycles counting I Output

I timerDoneis 1 when counter has completed the countdown I Remains asserted until counter reloaded

I Counter can be (re)loaded in any state I When not loaded it counts down to zero I Similar to the timer we looked at two weeks ago

(28)

The Timer FSM

val timerReg = RegInit (0. U) timerDone := timerReg === 0. U // Timer FSM ( down counter ) when (! timerDone ) {

timerReg := timerReg - 1. U }

when ( timerLoad ) { when ( timerSelect ) {

timerReg := 5. U } . otherwise {

timerReg := 3. U }

(29)

The Master FSM

I Show in IntelliJ

I Run test and show waveform

(30)

Result of Refactoring

I State of original flat FSM has been separated I The part of cycle counting in the counter I Part flash or space in master FSM

I Represent original 27 states in just two 6 states FSMs I

I BTW: the master FSM is a Mealy FSM

(31)

20’ Break

I Mid-term evaluation

I Will send the link per email and Slack (now) I We talk about the results after the break

(32)

Still Redundancy in FSM

I flash1,flash2, andflash3same function I space1andspace2same function

I Refactor number of remaining flashes I Master FSM states: off,flash, andspace

(33)

Factor out “flash number”

start

timerLoad

light Master FSM

Timer

timerSelect timerDone cntLoad

Counter cntDecr cntDone

(34)

Counter

val cntReg = RegInit (0. U) cntDone := cntReg === 0. U // Down counter FSM

when ( cntLoad ) { cntReg := 2. U }

when ( cntDecr ) { cntReg := cntReg - 1. U } I Loaded with 2 for 3 flashes

I Counts theremainingflashes

(35)

Code of Flasher2

I Show in IntelliJ

I Run test and show waveform

(36)

Benefits of Refactored Solution

I Master FSM has just three states: off,flash, andspace I Change of intervals or number of flashes needs no change

in the FSM

I Smaller components are easier to read and simpler to test individually

(37)

Usage in your VM

I Maybe factor out the edge detection for the button(s) I Use a timer for more advanced user interface

I Blinking LED on some error

I Write text as a banner in the 7-segment display I ...

(38)

Input Processing

I Input signals are not synchronous to the clock I May violate setup and hold time of a flip-flop I Can lead to metastability

I Signals need to besynchronized I Using two flip-flops

I Metastability cannot be avoided I Assumption is:

I First flip-flop may become metastable I But will resolve within the clock period

(39)

Input Synchronizer

Synchronous circuit

External world

btn btnSync

val btnSync = RegNext ( RegNext ( btn ))

(40)

Bouncing Buttons

I Buttons and switches need some time to transition between on and off

I May bounce between the two values

I Without processing we detect more than one event I Solution is to filter out bouncing

I Can be done electrically (R + C + Schmitt trigger) I That is why you have the extra PCB with the buttons I But we can also do this digitally

I Assume bouncing timet_bounce I Sample at a periodT >t_bounce I

(41)

Sampling for Debouncing

bouncing in

debounced A

debounced B

(42)

Sampling for Debouncing

val FAC = 100000000/100

val btnDebReg = Reg ( Bool () ) val cntReg = RegInit (0. U (32. W)) val tick = cntReg === (fac -1) .U cntReg := cntReg + 1. U

when ( tick ) { cntReg := 0. U

btnDebReg := btnSync }

I We already know how to do this!

(43)

Noisy Input Signal

I Sometimes input may be noisy I May contain spikes

I Filtering with majority voting

I Majority voting of the sampled input signal I However, this is seldom needed

I Not for the buttons you have

(44)

Majority Voting

en en en

din

Majority voting dout = (a & b) | (a & c) | (b & c)

a b c

tick

(45)

Majority Voting

val shiftReg = RegInit (0. U (3. W)) when ( tick ) {

// shift left and input in LSB

shiftReg := shiftReg (1 , 0) ## btnDebReg }

// Majority voting

val btnClean = ( shiftReg (2) & shiftReg (1) ) | ( shiftReg (2) & shiftReg (0) ) | ( shiftReg (1) &

shiftReg (0) )

(46)

Detecting the Press Event

I Edge detection

I You have seen this before

I Just to complete the input procssing

val risingEdge = btnClean & ! RegNext ( btnClean ) // Use the rising edge of the debounced and // filtered button to count up

val reg = RegInit (0. U (8. W)) when ( risingEdge ) {

reg := reg + 1. U }

(47)

Combine Input Processing with Functions

I Using small functions to abstract the processing I Debounce.scala

(48)

Reset is an Asynchronous Signal

I Needs a input synchronizer

I Usually hidden in Chisel, but easy to access I Do the reset synchronizer at the top level module class SyncReset extends Module {

val io = IO (new Bundle () { val value = Output ( UInt () ) })

val syncReset = RegNext ( RegNext ( reset )) val cnt = Module (new WhenCounter (5) ) cnt . reset := syncReset

(49)

Today’s Lab

I Driving your 7-segment decoder

I Use a counter to count from 0 to 15, driving your display I Use another counter to generate your timing

I We talked about this today I You clock on the board is 100 MHz

I The given tester does only generate a waveform, no testing I Use a different maximum count value for waveform

debugging

I Then synthesize it for the FPGA I Show a TA your working design I Lab 8

(50)

Summary

I Divide a bigger problem into smaller ones I Easier to design

I Easier to test

I Sometimes only feasible solution I Factoring state machines

I Separate state into multiple ‘orthogonal’ state variables I Each is simpler to handle (fewer states)

I “Factors out” repetitive sequences I Hierarchical structure