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
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.tester._
import chisel3.tester.RawTester.test
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
}
// Test LastConnect
test(new LastConnect) { c => c.io.out.expect(4.U) } // Assert that the output correctly has 4
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
}
}
// Test Max3
test(new Max3) { c =>
// verify that the max of the three inputs is correct
c.io.in1.poke(6.U)
c.io.in2.poke(4.U)
c.io.in3.poke(2.U)
c.io.out.expect(6.U) // input 1 should be biggest
c.io.in2.poke(7.U)
c.io.out.expect(7.U) // now input 2 is
c.io.in3.poke(11.U)
c.io.out.expect(11.U) // and now input 3
c.io.in3.poke(3.U)
c.io.out.expect(7.U) // show that decreasing an input works as well
c.io.in1.poke(9.U)
c.io.in2.poke(9.U)
c.io.in3.poke(6.U)
c.io.out.expect(9.U) // still get max with tie
}
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.
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
}
}
// Here's the tester
test(new Sort4) { c =>
// verify the inputs are sorted
c.io.in0.poke(3.U)
c.io.in1.poke(6.U)
c.io.in2.poke(9.U)
c.io.in3.poke(12.U)
c.io.out0.expect(3.U)
c.io.out1.expect(6.U)
c.io.out2.expect(9.U)
c.io.out3.expect(12.U)
c.io.in0.poke(13.U)
c.io.in1.poke(4.U)
c.io.in2.poke(6.U)
c.io.in3.poke(1.U)
c.io.out0.expect(1.U)
c.io.out1.expect(4.U)
c.io.out2.expect(6.U)
c.io.out3.expect(13.U)
c.io.in0.poke(13.U)
c.io.in1.poke(6.U)
c.io.in2.poke(4.U)
c.io.in3.poke(1.U)
c.io.out0.expect(1.U)
c.io.out1.expect(4.U)
c.io.out2.expect(6.U)
c.io.out3.expect(13.U)
}
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 [ ]:
// Here's the tester
test(new Sort4) { c =>
// verify the all possible ordering of 4 numbers are sorted
List(1, 2, 3, 4).permutations.foreach { case i0 :: i1 :: i2 :: i3 :: Nil =>
println(s"Sorting $i0 $i1 $i2 $i3")
c.io.in0.poke(i0.U)
c.io.in1.poke(i1.U)
c.io.in2.poke(i2.U)
c.io.in3.poke(i3.U)
c.io.out0.expect(1.U)
c.io.out1.expect(2.U)
c.io.out2.expect(3.U)
c.io.out3.expect(4.U)
}
}
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)
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
}
// Test Polynomial
test(new Polynomial) { c =>
for(x <- 0 to 20) {
for(select <- 0 to 2) {
c.io.select.poke(select.U)
c.io.x.poke(x.S)
c.io.fOfX.expect(poly(select, x).S)
}
}
}
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)
???
}
// Test
test(new GradLife) { c =>
// verify that the hardware matches the golden model
for (state <- 0 to 3) {
for (coffee <- List(true, false)) {
for (idea <- List(true, false)) {
for (pressure <- List(true, false)) {
c.io.state.poke(state.U)
c.io.coffee.poke(coffee.B)
c.io.idea.poke(idea.B)
c.io.pressure.poke(pressure.B)
c.io.nextState.expect(gradLife(state, coffee, idea, pressure).U)
}
}
}
}
}
println("SUCCESS!!") // Scala Code: if we get here, our tests passed!
io.nextState := idle
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 }
}