{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "\"Chisel" ] }, { "cell_type": "markdown", "metadata": { "collapsed": true }, "source": [ "# Module 2.3: Control Flow\n", "**Prev: [Combinational Logic](2.2_comb_logic.ipynb)**
\n", "**Next: [Sequential Logic](2.4_sequential_logic.ipynb)**\n", "\n", "## Motivation\n", "Up until now there has been a strong correspondence between software and hardware in Chisel.\n", "In control flow there will be a greater divergence between the way we think about the two.\n", "This module introduces control flow both in the generator software and in the hardware.\n", "What happens if you reconnect to a Chisel wire?\n", "How can you make a mux with more than two inputs?\n", "The answers to these questions and more can be yours by completing this module.\n", "\n", "## Setup" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "val path = System.getProperty(\"user.dir\") + \"/source/load-ivy.sc\"\n", "interp.load.module(ammonite.ops.Path(java.nio.file.FileSystems.getDefault().getPath(path)))" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "import chisel3._\n", "import chisel3.util._\n", "import chisel3.tester._\n", "import chisel3.tester.RawTester.test" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "---\n", "# Last Connect Semantics\n", "\n", "**Example: Reassignment**
\n", "As seen earlier, Chisel allows you to connect components using the `:=` operator.\n", "For various reasons it is possible to issue multiple connect statements to the same component.\n", "When this happens, the last statement wins." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "class LastConnect extends Module {\n", " val io = IO(new Bundle {\n", " val in = Input(UInt(4.W))\n", " val out = Output(UInt(4.W))\n", " })\n", " io.out := 1.U\n", " io.out := 2.U\n", " io.out := 3.U\n", " io.out := 4.U\n", "}\n", "\n", "// Test LastConnect\n", "test(new LastConnect) { c => c.io.out.expect(4.U) } // Assert that the output correctly has 4\n", "println(\"SUCCESS!!\") // Scala Code: if we get here, our tests passed!" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "---\n", "# `when`, `elsewhen`, and `otherwise`\n", "Chisel's primary implementation of conditional logic is the `when`, `elsewhen`, and `otherwise` constructs. \n", "This generally looks like\n", "```scala\n", "when(someBooleanCondition) {\n", " // things to do when true\n", "}.elsewhen(someOtherBooleanCondition) {\n", " // things to do on this condition\n", "}.otherwise {\n", " // things to do if none of th boolean conditions are true\n", "}\n", "```\n", "They must appear in the above order, though either of the latter may be omitted.\n", "There can be as many elsewhen clauses as desired.\n", "Any section that is true terminates the construct.\n", "Actions taken in the bodies of the the three can be complex blocks and may contain nested\n", "`when` and allies.\n", "**Unlike** Scala `if`, values are not returned by the blocks associated with `when`.\n", "One cannot say\n", "```scala\n", "val result = when(squareIt) { x * x }.otherwise { x }\n", "```\n", "This will **not** work. We will discuss the solution to this in the *Wires* section.\n", "\n", "**Example: Chisel Conditionals**
\n", "Below is an example `Module` using the `when` construct." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "// Max3 returns the max of its 3 arguments\n", "class Max3 extends Module {\n", " val io = IO(new Bundle {\n", " val in1 = Input(UInt(16.W))\n", " val in2 = Input(UInt(16.W))\n", " val in3 = Input(UInt(16.W))\n", " val out = Output(UInt(16.W))\n", " })\n", " \n", " when(io.in1 >= io.in2 && io.in1 >= io.in3) {\n", " io.out := io.in1 \n", " }.elsewhen(io.in2 >= io.in3) {\n", " io.out := io.in2 \n", " }.otherwise {\n", " io.out := io.in3\n", " }\n", "}\n", "\n", "// Test Max3\n", "test(new Max3) { c =>\n", " // verify that the max of the three inputs is correct\n", " c.io.in1.poke(6.U)\n", " c.io.in2.poke(4.U)\n", " c.io.in3.poke(2.U)\n", " c.io.out.expect(6.U) // input 1 should be biggest\n", " c.io.in2.poke(7.U)\n", " c.io.out.expect(7.U) // now input 2 is\n", " c.io.in3.poke(11.U)\n", " c.io.out.expect(11.U) // and now input 3\n", " c.io.in3.poke(3.U)\n", " c.io.out.expect(7.U) // show that decreasing an input works as well\n", " c.io.in1.poke(9.U)\n", " c.io.in2.poke(9.U)\n", " c.io.in3.poke(6.U)\n", " c.io.out.expect(9.U) // still get max with tie\n", "}\n", "\n", "println(\"SUCCESS!!\") // Scala Code: if we get here, our tests passed!" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "---\n", "# The `Wire` Construct\n", "Let's return to the note above describing the limitation that `when` does not return a value.\n", "The Chisel `Wire` construct is one of the ways around this.\n", "`Wire` defines a circuit component that can appear on the right hand side or left hand side of\n", "a connect `:=` operator.\n", "\n", "**Example: 4-Input Sort with Wires**
\n", "To illustrate this let's make a small combinational sorter that sorts its four numeric inputs into\n", "its four numeric outputs. To make things clearer, consider the following graph. Data follows the red lines\n", "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.\n", "![Sort4](images/Sorter4.png)\n", "The diagram shows a series of cells whose names begin with *row*, we will use `Wire`s 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." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "scrolled": true }, "outputs": [], "source": [ "/** Sort4 sorts its 4 inputs to its 4 outputs */\n", "class Sort4 extends Module {\n", " val io = IO(new Bundle {\n", " val in0 = Input(UInt(16.W))\n", " val in1 = Input(UInt(16.W))\n", " val in2 = Input(UInt(16.W))\n", " val in3 = Input(UInt(16.W))\n", " val out0 = Output(UInt(16.W))\n", " val out1 = Output(UInt(16.W))\n", " val out2 = Output(UInt(16.W))\n", " val out3 = Output(UInt(16.W))\n", " })\n", "\n", " val row10 = Wire(UInt(16.W))\n", " val row11 = Wire(UInt(16.W))\n", " val row12 = Wire(UInt(16.W))\n", " val row13 = Wire(UInt(16.W))\n", "\n", " when(io.in0 < io.in1) {\n", " row10 := io.in0 // preserve first two elements\n", " row11 := io.in1\n", " }.otherwise {\n", " row10 := io.in1 // swap first two elements\n", " row11 := io.in0\n", " }\n", "\n", " when(io.in2 < io.in3) {\n", " row12 := io.in2 // preserve last two elements\n", " row13 := io.in3\n", " }.otherwise {\n", " row12 := io.in3 // swap last two elements\n", " row13 := io.in2\n", " }\n", "\n", " val row21 = Wire(UInt(16.W))\n", " val row22 = Wire(UInt(16.W))\n", "\n", " when(row11 < row12) {\n", " row21 := row11 // preserve middle 2 elements\n", " row22 := row12\n", " }.otherwise {\n", " row21 := row12 // swap middle two elements\n", " row22 := row11\n", " }\n", "\n", " val row20 = Wire(UInt(16.W))\n", " val row23 = Wire(UInt(16.W))\n", " when(row10 < row13) {\n", " row20 := row10 // preserve middle 2 elements\n", " row23 := row13\n", " }.otherwise {\n", " row20 := row13 // swap middle two elements\n", " row23 := row10\n", " }\n", "\n", " when(row20 < row21) {\n", " io.out0 := row20 // preserve first two elements\n", " io.out1 := row21\n", " }.otherwise {\n", " io.out0 := row21 // swap first two elements\n", " io.out1 := row20\n", " }\n", "\n", " when(row22 < row23) {\n", " io.out2 := row22 // preserve first two elements\n", " io.out3 := row23\n", " }.otherwise {\n", " io.out2 := row23 // swap first two elements\n", " io.out3 := row22\n", " }\n", "}\n", "\n", "\n", "// Here's the tester\n", "test(new Sort4) { c =>\n", " // verify the inputs are sorted\n", " c.io.in0.poke(3.U)\n", " c.io.in1.poke(6.U)\n", " c.io.in2.poke(9.U)\n", " c.io.in3.poke(12.U)\n", " c.io.out0.expect(3.U)\n", " c.io.out1.expect(6.U)\n", " c.io.out2.expect(9.U)\n", " c.io.out3.expect(12.U)\n", "\n", " c.io.in0.poke(13.U)\n", " c.io.in1.poke(4.U)\n", " c.io.in2.poke(6.U)\n", " c.io.in3.poke(1.U)\n", " c.io.out0.expect(1.U)\n", " c.io.out1.expect(4.U)\n", " c.io.out2.expect(6.U)\n", " c.io.out3.expect(13.U)\n", "\n", " c.io.in0.poke(13.U)\n", " c.io.in1.poke(6.U)\n", " c.io.in2.poke(4.U)\n", " c.io.in3.poke(1.U)\n", " c.io.out0.expect(1.U)\n", " c.io.out1.expect(4.U)\n", " c.io.out2.expect(6.U)\n", " c.io.out3.expect(13.U)\n", "}\n", "println(\"SUCCESS!!\") // Scala Code: if we get here, our tests passed!\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Here's a more exhaustive tester using some Scala `List` features. You'll see more `List` functions in later modules." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "// Here's the tester\n", "test(new Sort4) { c =>\n", " // verify the all possible ordering of 4 numbers are sorted\n", " List(1, 2, 3, 4).permutations.foreach { case i0 :: i1 :: i2 :: i3 :: Nil =>\n", " println(s\"Sorting $i0 $i1 $i2 $i3\")\n", " c.io.in0.poke(i0.U)\n", " c.io.in1.poke(i1.U)\n", " c.io.in2.poke(i2.U)\n", " c.io.in3.poke(i3.U)\n", " c.io.out0.expect(1.U)\n", " c.io.out1.expect(2.U)\n", " c.io.out2.expect(3.U)\n", " c.io.out3.expect(4.U)\n", " }\n", "}\n", "println(\"SUCCESS!!\") // Scala Code: if we get here, our tests passed!" ] }, { "cell_type": "markdown", "metadata": { "collapsed": true }, "source": [ "---\n", "# Exercises\n", "\n", "**Exercise: Polynomial Circuit**
\n", "Build a `Module` that will compute the values of these polynomials.\n", "- $x^2 - 2x + 1$\n", "- $2x^2 + 6x + 3$\n", "- $4x^2 - 10x -5$\n", "\n", "A selector input will determine which polynomial to calculate. Use `Wire`s so that the $x^2$ computation appears only once in the module and so that there is a single connection to the output.\n", "\n", "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." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def poly0(x: Int): Int = ???\n", "def poly1(x: Int): Int = ???\n", "def poly2(x: Int): Int = ???\n", "\n", "assert(poly0(0) == 1)\n", "assert(poly1(0) == 3)\n", "assert(poly2(0) == -5)\n", "\n", "assert(poly0(1) == 0)\n", "assert(poly1(1) == 11)\n", "assert(poly2(1) == -11)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
\n", "\n", "\n", "
\n", "
\n",
    "def poly0(x: Int): Int = x*x - 2*x + 1\n",
    "def poly1(x: Int): Int = 2*x*x + 6*x + 3\n",
    "def poly2(x: Int): Int = 4*x*x - 10*x - 5\n",
    "
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "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." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def poly(select: Int, x: Int): Int = {\n", " ???\n", "}\n", "\n", "assert(poly(1, 0) == 3)\n", "assert(poly(1, 1) == 11)\n", "assert(poly(2, 1) == -11)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
\n", "\n", "\n", "
\n", "
\n",
    "def poly(select: Int, x: Int): Int = {\n",
    "  if(select == 0) {\n",
    "    poly0(x)\n",
    "  }\n",
    "  else if(select == 1) {\n",
    "    poly1(x)\n",
    "  }\n",
    "  else {\n",
    "    poly2(x)\n",
    "  }\n",
    "}\n",
    "
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Looks like the values are correct. So now use the following template to implement your circuit." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "// compute the polynomial\n", "class Polynomial extends Module {\n", " val io = IO(new Bundle {\n", " val select = Input(UInt(2.W))\n", " val x = Input(SInt(32.W))\n", " val fOfX = Output(SInt(32.W))\n", " })\n", " \n", " val result = Wire(SInt(32.W)) \n", " val square = Wire(SInt(32.W)) \n", " \n", " ???\n", "\n", " io.fOfX := result \n", "}\n", "\n", "// Test Polynomial\n", "test(new Polynomial) { c =>\n", " for(x <- 0 to 20) {\n", " for(select <- 0 to 2) {\n", " c.io.select.poke(select.U)\n", " c.io.x.poke(x.S)\n", " c.io.fOfX.expect(poly(select, x).S)\n", " }\n", " }\n", "}\n", "println(\"SUCCESS!!\") // Scala Code: if we get here, our tests passed!" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
\n", "\n", "\n", "
\n", "
\n",
    "  square := io.x * io.x\n",
    "  when(io.select === 0.U) {\n",
    "    result := (square - (2.S * io.x)) + 1.S\n",
    "  }.elsewhen(io.select === 1.U) {\n",
    "    result := (2.S * square) + (6.S * io.x) + 3.S\n",
    "  }.otherwise {\n",
    "    result := (4.S * square) - (10.S * io.x) - 5.S\n",
    "  }\n",
    "
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Exercise: Finite State Machine**
\n", "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.\n", "\n", "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.\n", "\n", "\n", "\n", "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\")`." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "// state map\n", "def states = Map(\"idle\" -> 0, \"coding\" -> 1, \"writing\" -> 2, \"grad\" -> 3)\n", "\n", "// life is full of question marks\n", "def gradLife (state: Int, coffee: Boolean, idea: Boolean, pressure: Boolean): Int = {\n", " var nextState = states(\"idle\")\n", " ???\n", " nextState\n", "}\n", "\n", "// some sanity checks\n", "(0 until states.size).foreach{ state => assert(gradLife(state, false, false, false) == states(\"idle\")) }\n", "assert(gradLife(states(\"writing\"), true, false, true) == states(\"writing\"))\n", "assert(gradLife(states(\"idle\"), true, true, true) == states(\"coding\"))\n", "assert(gradLife(states(\"idle\"), false, true, true) == states(\"idle\"))\n", "assert(gradLife(states(\"grad\"), false, false, false) == states(\"idle\"))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
\n", "\n", "\n", "
\n", "
\n",
    "  if (state == states(\"idle\")) {\n",
    "    if      (coffee) { nextState = states(\"coding\") }\n",
    "    else if (idea) { nextState = states(\"idle\") }\n",
    "    else if (pressure) { nextState = states(\"writing\") }\n",
    "  } else if (state == states(\"coding\")) {\n",
    "    if      (coffee) { nextState = states(\"coding\") } \n",
    "    else if (idea || pressure) { nextState = states(\"writing\") }\n",
    "  } else if (state == states(\"writing\")) {\n",
    "    if      (coffee || idea) { nextState = states(\"writing\") }\n",
    "    else if (pressure) { nextState = states(\"grad\") }\n",
    "  }\n",
    "
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "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!" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "// life gets hard-er\n", "class GradLife extends Module {\n", " val io = IO(new Bundle {\n", " val state = Input(UInt(2.W))\n", " val coffee = Input(Bool())\n", " val idea = Input(Bool())\n", " val pressure = Input(Bool())\n", " val nextState = Output(UInt(2.W))\n", " })\n", " \n", " val idle :: coding :: writing :: grad :: Nil = Enum(4)\n", " \n", " ???\n", "}\n", "\n", "\n", "// Test\n", "test(new GradLife) { c =>\n", " // verify that the hardware matches the golden model\n", " for (state <- 0 to 3) {\n", " for (coffee <- List(true, false)) {\n", " for (idea <- List(true, false)) {\n", " for (pressure <- List(true, false)) {\n", " c.io.state.poke(state.U)\n", " c.io.coffee.poke(coffee.B)\n", " c.io.idea.poke(idea.B)\n", " c.io.pressure.poke(pressure.B)\n", " c.io.nextState.expect(gradLife(state, coffee, idea, pressure).U)\n", " }\n", " }\n", " }\n", " }\n", "}\n", "println(\"SUCCESS!!\") // Scala Code: if we get here, our tests passed!" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
\n", "\n", "\n", "
\n", "
\n",
    "  io.nextState := idle\n",
    "  when (io.state === idle) {\n",
    "    when      (io.coffee) { io.nextState := coding } \n",
    "    .elsewhen (io.idea) { io.nextState := idle }\n",
    "    .elsewhen (io.pressure) { io.nextState := writing }\n",
    "  } .elsewhen (io.state === coding) {\n",
    "    when      (io.coffee) { io.nextState := coding } \n",
    "    .elsewhen (io.idea || io.pressure) { io.nextState := writing }\n",
    "  } .elsewhen (io.state === writing) {\n",
    "    when      (io.coffee || io.idea) { io.nextState := writing }\n",
    "    .elsewhen (io.pressure) { io.nextState := grad }\n",
    "  }\n",
    "
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": true }, "source": [ "---\n", "# You're done!\n", "\n", "[Return to the top.](#top)" ] } ], "metadata": { "kernelspec": { "display_name": "Scala", "language": "scala", "name": "scala" }, "language_info": { "codemirror_mode": "text/x-scala", "file_extension": ".scala", "mimetype": "text/x-scala", "name": "scala", "nbconvert_exporter": "script", "version": "2.12.10" } }, "nbformat": 4, "nbformat_minor": 2 }