Chisel logo

Module 2.3: Control Flow

Prev: Combinational Logic
Next: Sequential Logic

Motivation

Up until now there has been a strong correspondence between software and hardware in Chisel. In control flow there will be a greater divergence between the way we think about the two. This module introduces control flow both in the generator software and in the hardware. What happens if you reconnect to a Chisel wire? How can you make a mux with more than two inputs? The answers to these questions and more can be yours by completing this module.

Setup

In [ ]:
val path = System.getProperty("user.dir") + "/source/load-ivy.sc"
interp.load.module(ammonite.ops.Path(java.nio.file.FileSystems.getDefault().getPath(path)))
In [ ]:
import chisel3._
import chisel3.util._
import chisel3.iotesters.{ChiselFlatSpec, Driver, PeekPokeTester}

Last Connect Semantics

**Example: Reassignment**
As seen earlier, Chisel allows you to connect components using the := operator. For various reasons it is possible to issue multiple connect statements to the same component. When this happens, the last statement wins.

In [ ]:
class LastConnect extends Module {
  val io = IO(new Bundle {
    val in = Input(UInt(4.W))
    val out = Output(UInt(4.W))
  })
  io.out := 1.U
  io.out := 2.U
  io.out := 3.U
  io.out := 4.U
}

// Chisel Code: Declare a new tester for modules
class LastConnectTester(c: LastConnect) extends PeekPokeTester(c) {
  expect(c.io.out, 4)  // Assert that the output correctly has 4
}

//  Test LastConnect
val works = Driver(() => new LastConnect) {
  c => new LastConnectTester(c)
}
assert(works)        // Scala Code: if works == false, will throw an error
println("SUCCESS!!") // Scala Code: if we get here, our tests passed!

when, elsewhen, and otherwise

Chisel's primary implementation of conditional logic is the when, elsewhen, and otherwise constructs. This generally looks like

when(someBooleanCondition) {
  // things to do when true
}.elsewhen(someOtherBooleanCondition) {
  // things to do on this condition
}.otherwise {
  // things to do if none of th boolean conditions are true
}

They must appear in the above order, though either of the latter may be omitted. There can be as many elsewhen clauses as desired. Any section that is true terminates the construct. Actions taken in the bodies of the the three can be complex blocks and may contain nested when and allies. Unlike Scala if, values are not returned by the blocks associated with when. One cannot say

val result = when(squareIt) { x * x }.otherwise { x }

This will not work. We will discuss the solution to this in the Wires section.

**Example: Chisel Conditionals**
Below is an example Module using the when construct.

In [ ]:
// Max3 returns the max of its 3 arguments
class Max3 extends Module {
  val io = IO(new Bundle {
    val in1 = Input(UInt(16.W))
    val in2 = Input(UInt(16.W))
    val in3 = Input(UInt(16.W))
    val out = Output(UInt(16.W))
  })
    
  when(io.in1 >= io.in2 && io.in1 >= io.in3) {
    io.out := io.in1  
  }.elsewhen(io.in2 >= io.in3) {
    io.out := io.in2 
  }.otherwise {
    io.out := io.in3
  }
}

// verify that the max of the three inputs is correct
class Max3Tester(c: Max3) extends PeekPokeTester(c) {
  poke(c.io.in1, 6)
  poke(c.io.in2, 4)  
  poke(c.io.in3, 2)  
  expect(c.io.out, 6)  // input 1 should be biggest
  poke(c.io.in2, 7)  
  expect(c.io.out, 7)  // now input 2 is
  poke(c.io.in3, 11)  
  expect(c.io.out, 11) // and now input 3
  poke(c.io.in3, 3)  
  expect(c.io.out, 7)  // show that decreasing an input works as well
  poke(c.io.in1, 9)
  poke(c.io.in2, 9)
  poke(c.io.in3, 6)
  expect(c.io.out, 9)  // still get max with tie
}

// Test Max3
val works = Driver(() => new Max3) {
  c => new Max3Tester(c)
}
assert(works)        // Scala Code: if works == false, will throw an error
println("SUCCESS!!") // Scala Code: if we get here, our tests passed!

The Wire Construct

Let's return to the note above describing the limitation that when does not return a value. The Chisel Wire construct is one of the ways around this. Wire defines a circuit component that can appear on the right hand side or left hand side of a connect := operator.

**Example: 4-Input Sort with Wires**
To illustrate this let's make a small combinational sorter that sorts its four numeric inputs into its four numeric outputs. To make things clearer, consider the following graph. Data follows the red lines at each step when the left value is less than the right, and follows the black lines, which swap the values, when the left is greater than the right. Sort4 The diagram shows a series of cells whose names begin with row, we will use Wires to construct these as where results of a particular copy or swap are placed. The code for this is quite verbose, but you'll see ways of shrinking it later.

In [ ]:
/** Sort4 sorts its 4 inputs to its 4 outputs */
class Sort4 extends Module {
  val io = IO(new Bundle {
    val in0 = Input(UInt(16.W))
    val in1 = Input(UInt(16.W))
    val in2 = Input(UInt(16.W))
    val in3 = Input(UInt(16.W))
    val out0 = Output(UInt(16.W))
    val out1 = Output(UInt(16.W))
    val out2 = Output(UInt(16.W))
    val out3 = Output(UInt(16.W))
  })

  val row10 = Wire(UInt(16.W))
  val row11 = Wire(UInt(16.W))
  val row12 = Wire(UInt(16.W))
  val row13 = Wire(UInt(16.W))

  when(io.in0 < io.in1) {
    row10 := io.in0            // preserve first two elements
    row11 := io.in1
  }.otherwise {
    row10 := io.in1            // swap first two elements
    row11 := io.in0
  }

  when(io.in2 < io.in3) {
    row12 := io.in2            // preserve last two elements
    row13 := io.in3
  }.otherwise {
    row12 := io.in3            // swap last two elements
    row13 := io.in2
  }

  val row21 = Wire(UInt(16.W))
  val row22 = Wire(UInt(16.W))

  when(row11 < row12) {
    row21 := row11            // preserve middle 2 elements
    row22 := row12
  }.otherwise {
    row21 := row12            // swap middle two elements
    row22 := row11
  }

  val row20 = Wire(UInt(16.W))
  val row23 = Wire(UInt(16.W))
  when(row10 < row13) {
    row20 := row10            // preserve middle 2 elements
    row23 := row13
  }.otherwise {
    row20 := row13            // swap middle two elements
    row23 := row10
  }

  when(row20 < row21) {
    io.out0 := row20            // preserve first two elements
    io.out1 := row21
  }.otherwise {
    io.out0 := row21            // swap first two elements
    io.out1 := row20
  }

  when(row22 < row23) {
    io.out2 := row22            // preserve first two elements
    io.out3 := row23
  }.otherwise {
    io.out2 := row23            // swap first two elements
    io.out3 := row22
  }
}

// verify the inputs are sorted
class Sort4Tester(c: Sort4) extends PeekPokeTester(c) {
  poke(c.io.in0, 3)
  poke(c.io.in1, 6)
  poke(c.io.in2, 9)
  poke(c.io.in3, 12)
  expect(c.io.out0, 3)
  expect(c.io.out1, 6)
  expect(c.io.out2, 9)
  expect(c.io.out3, 12)

  poke(c.io.in0, 13)
  poke(c.io.in1, 4)
  poke(c.io.in2, 6)
  poke(c.io.in3, 1)
  expect(c.io.out0, 1)
  expect(c.io.out1, 4)
  expect(c.io.out2, 6)
  expect(c.io.out3, 13)
    
  poke(c.io.in0, 13)
  poke(c.io.in1, 6)
  poke(c.io.in2, 4)
  poke(c.io.in3, 1)
  expect(c.io.out0, 1)
  expect(c.io.out1, 4)
  expect(c.io.out2, 6)
  expect(c.io.out3, 13)
}

// Here's the tester
val works = iotesters.Driver(() => new Sort4) {
c => new Sort4Tester(c)
}
assert(works) // Scala Code: if works == false, will throw an error
println("SUCCESS!!") // Scala Code: if we get here, our tests passed!

Here's a more exhaustive tester using some Scala List features. You'll see more List functions in later modules.

In [ ]:
// verify the all possible ordering of 4 numbers are sorted
class BetterSort4Tester(c: Sort4) extends PeekPokeTester(c) {
  List(1, 2, 3, 4).permutations.foreach { case i0 :: i1 :: i2 :: i3 :: Nil =>
    println(s"Sorting $i0 $i1 $i2 $i3")
    poke(c.io.in0, i0)
    poke(c.io.in1, i1)
    poke(c.io.in2, i2)
    poke(c.io.in3, i3)
    expect(c.io.out0, 1)
    expect(c.io.out1, 2)
    expect(c.io.out2, 3)
    expect(c.io.out3, 4)
  }
}

// Here's the tester
val works = iotesters.Driver(() => new Sort4) {
c => new BetterSort4Tester(c)
}
assert(works) // Scala Code: if works == false, will throw an error
println("SUCCESS!!") // Scala Code: if we get here, our tests passed!

Exercises

**Exercise: Polynomial Circuit**
Build a Module that will compute the values of these polynomials.

  • $x^2 - 2x + 1$
  • $2x^2 + 6x + 3$
  • $4x^2 - 10x -5$

A selector input will determine which polynomial to calculate. Use Wires so that the $x^2$ computation appears only once in the module and so that there is a single connection to the output.

First let's use test-driven development and write a model using Scala. Complete these function defintions to pass the assertions below. It's not an exhaustive check, but rather a sanity check.

In [ ]:
def poly0(x: Int): Int = ???
def poly1(x: Int): Int = ???
def poly2(x: Int): Int = ???

assert(poly0(0) == 1)
assert(poly1(0) == 3)
assert(poly2(0) == -5)

assert(poly0(1) == 0)
assert(poly1(1) == 11)
assert(poly2(1) == -11)
def poly0(x: Int): Int = x*x - 2*x + 1
def poly1(x: Int): Int = 2*x*x + 6*x + 3
def poly2(x: Int): Int = 4*x*x - 10*x - 5

To make it even easier let's make a function that works like our desired hardware module. Use Scala if statements to select the polynomial based on the select input.

In [ ]:
def poly(select: Int, x: Int): Int = {
  ???
}

assert(poly(1, 0) == 3)
assert(poly(1, 1) == 11)
assert(poly(2, 1) == -11)
def poly(select: Int, x: Int): Int = {
  if(select == 0) {
    poly0(x)
  }
  else if(select == 1) {
    poly1(x)
  }
  else {
    poly2(x)
  }
}

Looks like the values are correct. So now use the following template to implement your circuit.

In [ ]:
// compute the polynomial
class Polynomial extends Module {
  val io = IO(new Bundle {
    val select = Input(UInt(2.W))
    val x = Input(SInt(32.W))
    val fOfX = Output(SInt(32.W))
  })
    
  val result = Wire(SInt(32.W))  
  val square = Wire(SInt(32.W))  
  
  ???

  io.fOfX := result  
}

// verify that the computation is correct
class PolynomialTester(c: Polynomial) extends PeekPokeTester(c) {
  for(x <- 0 to 20) {
    for(select <- 0 to 2) {
      poke(c.io.select, select)
      poke(c.io.x, x)
      expect(c.io.fOfX, poly(select, x))
    }
  }
}

// Test Polynomial
val works = Driver(() => new Polynomial) {
  c => new PolynomialTester(c)
}
assert(works)        // Scala Code: if works == false, will throw an error
println("SUCCESS!!") // Scala Code: if we get here, our tests passed!
  square := io.x * io.x
  when(io.select === 0.U) {
    result := (square - (2.S * io.x)) + 1.S
  }.elsewhen(io.select === 1.U) {
    result := (2.S * square) + (6.S * io.x) + 3.S
  }.otherwise {
    result := (4.S * square) - (10.S * io.x) - 5.S
  }

**Exercise: Finite State Machine**
Using Karnaugh maps to optimize the logic for state machines is tedious and solved by synthesis tools. It also produces unintuitive and unreadable code. So we'll write a more sensible one using Chisel control flow and last connect semantics.

Grad students pass through four states in their career: Idle, Coding, Writing, and Graduating. These states transition based off three inputs: Coffee, Ideas they come up with, and Pressure from their advisor to make progress. Once they Graduate, they return to the Idle state. The FSM diagram below shows these states and transitions. Any unlabelled transition (i.e. when there are no inputs) returns a grad student to the Idle state instead of staying in the current state. The input precedence is coffee > idea > pressure, so when in the Idle state and receiving both coffee and pressure, a graduate student will move to the Coding state.

First we'll construct a model to test against our hardware. Complete the following functional description of our state machine. It has four inputs. The output is the next state. The state map is provided for you. You can access it like states("grad").

In [ ]:
// state map
def states = Map("idle" -> 0, "coding" -> 1, "writing" -> 2, "grad" -> 3)

// life is full of question marks
def gradLife (state: Int, coffee: Boolean, idea: Boolean, pressure: Boolean): Int = {
  var nextState = states("idle")
  ???
  nextState
}

// some sanity checks
(0 until states.size).foreach{ state => assert(gradLife(state, false, false, false) == states("idle")) }
assert(gradLife(states("writing"), true, false, true) == states("writing"))
assert(gradLife(states("idle"), true, true, true) == states("coding"))
assert(gradLife(states("idle"), false, true, true) == states("idle"))
assert(gradLife(states("grad"), false, false, false) == states("idle"))
  if (state == states("idle")) {
    if      (coffee) { nextState = states("coding") }
    else if (idea) { nextState = states("idle") }
    else if (pressure) { nextState = states("writing") }
  } else if (state == states("coding")) {
    if      (coffee) { nextState = states("coding") } 
    else if (idea || pressure) { nextState = states("writing") }
  } else if (state == states("writing")) {
    if      (coffee || idea) { nextState = states("writing") }
    else if (pressure) { nextState = states("grad") }
  }

Since you haven't learned sequential logic yet, the current state is an input to the Module, and the next state is an output, as with the gradLife function earlier. Now implement the state machine in Chisel to pass the tester. Chisel provides a convenient state machine mapping function for us called Enum. To use these states, treat them like UInt literals. Remember that hardware equality is performed with the triple equals sign!

In [ ]:
// life gets hard-er
class GradLife extends Module {
  val io = IO(new Bundle {
    val state = Input(UInt(2.W))
    val coffee = Input(Bool())
    val idea = Input(Bool())
    val pressure = Input(Bool())
    val nextState = Output(UInt(2.W))
  })
    
  val idle :: coding :: writing :: grad :: Nil = Enum(4)
  
  io.nextState := idle
  ???
}

// verify that the hardware matches the golden model
class GradLifeSim(c: GradLife) extends PeekPokeTester(c) {
  for (state <- 0 to 3) {
    for (coffee <- List(true, false)) {
      for (idea <- List(true, false)) {
        for (pressure <- List(true, false)) {
          poke(c.io.state, state)
          poke(c.io.coffee, coffee)
          poke(c.io.idea, idea)
          poke(c.io.pressure, pressure)
          expect(c.io.nextState, gradLife(state, coffee, idea, pressure))
        }
      }
    }
  }
}

// Test
val works = Driver(() => new GradLife) {c => new GradLifeSim(c)}
assert(works)        // Scala Code: if works == false, will throw an error
println("SUCCESS!!") // Scala Code: if we get here, our tests passed!
  when (io.state === idle) {
    when      (io.coffee) { io.nextState := coding } 
    .elsewhen (io.idea) { io.nextState := idle }
    .elsewhen (io.pressure) { io.nextState := writing }
  } .elsewhen (io.state === coding) {
    when      (io.coffee) { io.nextState := coding } 
    .elsewhen (io.idea || io.pressure) { io.nextState := writing }
  } .elsewhen (io.state === writing) {
    when      (io.coffee || io.idea) { io.nextState := writing }
    .elsewhen (io.pressure) { io.nextState := grad }
  }

You're done!

Return to the top.