3.2_collections.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a name=\"top\"></a><img src=\"images/chisel_1024.png\" alt=\"Chisel logo\" style=\"width:480px;\" />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Module 3.2: Generators: Collections\n",
    "**Prev: [Generators: Parameters](3.1_parameters.ipynb)**<br>\n",
    "**Next: [Interlude: Chisel Standard Library](3.2_interlude.ipynb)**\n",
    "\n",
    "\n",
    "## Motivation\n",
    "Generators will frequently have to deal with variable numbers of objects, whether they are IOs, modules, or test vectors.\n",
    "Collections are important building blocks for dealing with situations like this.\n",
    "This module will introduce Scala collections and how to use them with Chisel generators.\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": "markdown",
   "metadata": {},
   "source": [
    "Note we add a new import here because `mutable.ArrayBuffer` lives in `scala.collections`."
   ]
  },
  {
   "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\n",
    "import scala.collection._"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "# Generators and Collections<a name=\"generators-and-collections\"></a> \n",
    "In this section, we will focus on the concept of *generators* and the use of Scala collections as a tool to implement them.\n",
    "Instead of looking at Chisel code as an *instance* of a circuit, i.e. a description of a particular circuit, \n",
    "we will instead consider it to be a generator of a circuit.\n",
    "\n",
    "We will start by considering the FIR filter from previous exercises.  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class My4ElementFir(b0: Int, b1: Int, b2: Int, b3: Int) extends Module {\n",
    "  val io = IO(new Bundle {\n",
    "    val in = Input(UInt(8.W))\n",
    "    val out = Output(UInt(8.W))\n",
    "  })\n",
    "\n",
    "  val x_n1 = RegNext(io.in, 0.U)\n",
    "  val x_n2 = RegNext(x_n1, 0.U)\n",
    "  val x_n3 = RegNext(x_n2, 0.U)\n",
    "  io.out := io.in * b0.U(8.W) + x_n1 * b1.U(8.W) +\n",
    "    x_n2 * b2.U(8.W) + x_n3 * b3.U(8.W)\n",
    "}\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This circuit is a simple case of a generator because it can generate versions of this 4-tap filter with\n",
    "different coefficients.  But what if we want the circuit to have more taps?  We are going to do this in several steps.\n",
    "\n",
    "- Build a software *Golden Model* of a tap configurable FIR.\n",
    "- Redesign our test to use this model, and confirm that it works.\n",
    "- Refactor our My4ElementFir to allow an configurable number of taps.\n",
    "- Test the new circuit using our new test harness.\n",
    "\n",
    "<span style=\"color:blue\">**Example: FIR Golden Model**</span><br><a name=\"fir-golden-model\"></a> \n",
    "Below is a Scala software implementation of a FIR circuit.  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "/**\n",
    "  * A naive implementation of an FIR filter with an arbitrary number of taps.\n",
    "  */\n",
    "class ScalaFirFilter(taps: Seq[Int]) {\n",
    "  var pseudoRegisters = List.fill(taps.length)(0)\n",
    "\n",
    "  def poke(value: Int): Int = {\n",
    "    pseudoRegisters = value :: pseudoRegisters.take(taps.length - 1)\n",
    "    var accumulator = 0\n",
    "    for(i <- taps.indices) {\n",
    "      accumulator += taps(i) * pseudoRegisters(i)\n",
    "    }\n",
    "    accumulator\n",
    "  }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Seq\n",
    "Note that `taps` has become a `Seq[Int]` which means that the user of the class can pass an arbitrarily-long sequence of `Int`s when constructing the class.\n",
    "### Registers\n",
    "With `  var pseudoRegisters = List.fill(taps.length)(0)` we create a `List` that will hold values from previous cycles.  `List` was chosen because its syntax of adding an element to the head and removing the last element is very simple. Just about any member of the scala collections family could be used.  We are also initializing this list to contain all zeros.\n",
    "### Poke\n",
    "Our class adds a poke function/method that emulates putting a new input into the filter and cycling the clock.\n",
    "### Updating the registers\n",
    "The line `pseudoRegisters = value :: pseudoRegisters.take(taps.length - 1)` first uses the `take` method of list to keep the all but the last element of the list, then uses the `::` list concatentation operator to add `value` to the head of the reduced version of the list.\n",
    "### Computing the output\n",
    "A simple for loop with an accumulator sums each element of the list times its corresponding tap coefficient. The line with just `accumulator` returns that value as the function result.\n",
    "## Adapting our previous test for testing our golden model\n",
    "We will now use our previous work to confirm that our golden model works.  A bit of editing magic takes our previous tests harness and morphs it into..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "val filter = new ScalaFirFilter(Seq(1, 1, 1, 1))\n",
    "\n",
    "var out = 0\n",
    "\n",
    "out = filter.poke(1)\n",
    "println(s\"out = $out\")\n",
    "assert(out == 1)  // 1, 0, 0, 0\n",
    "\n",
    "out = filter.poke(4)\n",
    "assert(out == 5)  // 4, 1, 0, 0\n",
    "println(s\"out = $out\")\n",
    "\n",
    "out = filter.poke(3)\n",
    "assert(out == 8)  // 3, 4, 1, 0\n",
    "println(s\"out = $out\")\n",
    "\n",
    "out = filter.poke(2)\n",
    "assert(out == 10)  // 2, 3, 4, 1\n",
    "println(s\"out = $out\")\n",
    "\n",
    "out = filter.poke(7)\n",
    "assert(out == 16)  // 7, 2, 3, 4\n",
    "println(s\"out = $out\")\n",
    "\n",
    "out = filter.poke(0)\n",
    "assert(out == 12)  // 0, 7, 2, 3\n",
    "println(s\"out = $out\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Executing the previous block demonstrates that our software model returns the same results as My4ElementFir did.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Test circuit using the golden model.<a name=\"use-golden-model-as-test\"></a> \n",
    "Now that we are reasonably confident about our golden model, we re-write our test to compare the circuit outputs with the output of the golden model, instead of using laboriously hand-crafted examples.\n",
    "What follows is a quick first pass to do it."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "val goldenModel = new ScalaFirFilter(Seq(1, 1, 1, 1))\n",
    "\n",
    "test(new My4ElementFir(1, 1, 1, 1)) { c =>\n",
    "    for(i <- 0 until 100) {\n",
    "        val input = scala.util.Random.nextInt(8)\n",
    "\n",
    "        val goldenModelResult = goldenModel.poke(input)\n",
    "\n",
    "        c.io.in.poke(input.U)\n",
    "\n",
    "        c.io.out.expect(goldenModelResult.U, s\"i $i, input $input, gm $goldenModelResult, ${c.io.out.peek().litValue}\")\n",
    "\n",
    "        c.clock.step(1)\n",
    "    }\n",
    "\n",
    "}\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Our test runs for 100 cycles, and checks that the two different methods, hardware and software, are in sync at each step.\n",
    "\n",
    "### Things to watch out for\n",
    "(i.e., mistakes we actually committed while writing this.)\n",
    "\n",
    "1. Getting the step in the right place. Software and hardware execute differently; it's easy to get this wrong.\n",
    "1. This test is weak because it is very sensitive to how the IOs and registers are sized. Implementing a software golden model that observes wrapping behavior at arbitrary data bit widths can be complicated.  Here we just make sure that we only pass in values that fit."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<span style=\"color:blue\">**Example: Parameterized FIR Generator**</span><br><a name=\"fir-golden-model\"></a> \n",
    "Below we have created a new Filter class, `MyManyElementsFilter` that takes a `Seq` of constants to use for taps.  This list can be any number of elements.\n",
    "For good measure a `bitWidth` has been added that allows us to control the sizes of numbers that can be handled by our circuit.\n",
    "In response the variable length we have had to refactor the creation of registers and how they are connected.\n",
    "The methodology used below uses a simple subset of the available library of collection functions.\n",
    "Later sections show how to more succinctly express the behavior in a way that also makes what is happening clearer."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class MyManyElementFir(consts: Seq[Int], bitWidth: Int) extends Module {\n",
    "  val io = IO(new Bundle {\n",
    "    val in = Input(UInt(bitWidth.W))\n",
    "    val out = Output(UInt(bitWidth.W))\n",
    "  })\n",
    "\n",
    "  val regs = mutable.ArrayBuffer[UInt]()\n",
    "  for(i <- 0 until consts.length) {\n",
    "      if(i == 0) regs += io.in\n",
    "      else       regs += RegNext(regs(i - 1), 0.U)\n",
    "  }\n",
    "  \n",
    "  val muls = mutable.ArrayBuffer[UInt]()\n",
    "  for(i <- 0 until consts.length) {\n",
    "      muls += regs(i) * consts(i).U\n",
    "  }\n",
    "\n",
    "  val scan = mutable.ArrayBuffer[UInt]()\n",
    "  for(i <- 0 until consts.length) {\n",
    "      if(i == 0) scan += muls(i)\n",
    "      else scan += muls(i) + scan(i - 1)\n",
    "  }\n",
    "\n",
    "  io.out := scan.last\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### How we did it\n",
    "There are three parallel sections starting at lines 7, 13, and 18.\n",
    "We are using a Scala collection type called `ArrayBuffer`.\n",
    "`ArrayBuffer` allows you to append elements using the `+=` operator (also insert and delete, but we don't need this).\n",
    "First, we create an ArrayBuffer `regs` whose elements will be `UInt`s.\n",
    "Then iterate over the taps, adding the input as the first element followed by creating registers using RegNext which connect the input of the register to the previous element (`regs(i-1)`) and initializes it to unsigned zero (`0.U`).\n",
    "These registers will hold the previous values of inputs as they are needed.\n",
    "\n",
    "Next, we create another ArrayBuffer `muls` of `UInt`s.\n",
    "Each element of muls will be a node whose i-th element is the product of the `regs(i)` and `const(i)`.\n",
    "\n",
    "Note the use of the `scan.last` method.\n",
    "It takes the last element of a collection, and is a more elegant alternative to `regs(i - 1)` used during the `regs` construction."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Does it behave the same as `My4ElementFir`?\n",
    "A good first test of our new version is to see if it can pass the test we just applied to the\n",
    "`My4ElementFir`.\n",
    "We create an instance of `MyManyElementFir` and run even more data through it."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "val goldenModel = new ScalaFirFilter(Seq(1, 1, 1, 1))\n",
    "\n",
    "test(new MyManyElementFir(Seq(1, 1, 1, 1), 8)) { c =>\n",
    "    for(i <- 0 until 100) {\n",
    "      val input = scala.util.Random.nextInt(8)\n",
    "\n",
    "      val goldenModelResult = goldenModel.poke(input)\n",
    "\n",
    "      c.io.in.poke(input.U)\n",
    "\n",
    "      c.io.out.expect(goldenModelResult.U, s\"i $i, input $input, gm $goldenModelResult, ${c.io.out.peek().litValue}\")\n",
    "\n",
    "      c.clock.step(1)\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Now let's test a bunch of different sized FIR filters\n",
    "We create some helper functions: `r` which gets a random number; `runOneTest` which creates a golden model and a hardware simulation of a filter for a particular set of taps, and then runs at least twice the number of taps worth of data through the filter."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "/** a convenience method to get a random integer\n",
    "  */\n",
    "def r(): Int = {\n",
    "  scala.util.Random.nextInt(1024)\n",
    "}\n",
    "\n",
    "/**\n",
    "  * run a test comparing software and hardware filters\n",
    "  * run for at least twice as many samples as taps\n",
    "  */\n",
    "def runOneTest(taps: Seq[Int]) {\n",
    "    val goldenModel = new ScalaFirFilter(taps)\n",
    "\n",
    "    test(new MyManyElementFir(taps, 32)) { c =>\n",
    "        for(i <- 0 until 2 * taps.length) {\n",
    "            val input = r()\n",
    "\n",
    "            val goldenModelResult = goldenModel.poke(input)\n",
    "\n",
    "            c.io.in.poke(input.U)\n",
    "\n",
    "            c.io.out.expect(goldenModelResult.U, s\"i $i, input $input, gm $goldenModelResult, ${c.io.out.peek().litValue}\")\n",
    "\n",
    "            c.clock.step(1)\n",
    "        }\n",
    "    }\n",
    "}\n",
    "\n",
    "for(tapSize <- 2 until 100 by 10) {\n",
    "    val taps = Seq.fill(tapSize)(r())  // create a sequence of random coefficients\n",
    "\n",
    "    runOneTest(taps)\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Just for fun, let's make a bigger one\n",
    "The following will run a single test on a 500 tap\n",
    "FIR filter.  It can take a minute or so to run.\n",
    "(Hint: Watch for the Scala ● to change to Scala ○ on the Toolbar when the execution completes.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "runOneTest(Seq.fill(500)(r()))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "# Hardware Collections\n",
    "\n",
    "<span style=\"color:blue\">**Example: Add run-time configurable taps to our FIR**</span><br>\n",
    "The following code adds an additional `consts` vector to the IO of our FIR generator which allows the coefficients to be changed externally after circuit generation.\n",
    "This is done with the Chisel collection type `Vec`.\n",
    "`Vec` supports many of the scala collection methods but it can only contain Chisel hardware elements.\n",
    "`Vec` should only be used in situations where ordinary Scala collections won't work.  \n",
    "Basically this is in one of two situations.\n",
    "1. You need a collection of elements in a Bundle, typically a Bundle that will be used as IO.\n",
    "1. You need to access the collection via an index that is part of the hardware (think Register File).\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class MyManyDynamicElementVecFir(length: Int) extends Module {\n",
    "  val io = IO(new Bundle {\n",
    "    val in = Input(UInt(8.W))\n",
    "    val out = Output(UInt(8.W))\n",
    "    val consts = Input(Vec(length, UInt(8.W)))\n",
    "  })\n",
    "\n",
    "  // Reference solution\n",
    "  val regs = RegInit(VecInit(Seq.fill(length - 1)(0.U(8.W))))\n",
    "  for(i <- 0 until length - 1) {\n",
    "      if(i == 0) regs(i) := io.in\n",
    "      else       regs(i) := regs(i - 1)\n",
    "  }\n",
    "  \n",
    "  val muls = Wire(Vec(length, UInt(8.W)))\n",
    "  for(i <- 0 until length) {\n",
    "      if(i == 0) muls(i) := io.in * io.consts(i)\n",
    "      else       muls(i) := regs(i - 1) * io.consts(i)\n",
    "  }\n",
    "\n",
    "  val scan = Wire(Vec(length, UInt(8.W)))\n",
    "  for(i <- 0 until length) {\n",
    "      if(i == 0) scan(i) := muls(i)\n",
    "      else scan(i) := muls(i) + scan(i - 1)\n",
    "  }\n",
    "\n",
    "  io.out := scan(length - 1)\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "val goldenModel = new ScalaFirFilter(Seq(1, 1, 1, 1))\n",
    "\n",
    "test(new MyManyDynamicElementVecFir(4)) { c =>\n",
    "    c.io.consts(0).poke(1.U)\n",
    "    c.io.consts(1).poke(1.U)\n",
    "    c.io.consts(2).poke(1.U)\n",
    "    c.io.consts(3).poke(1.U)\n",
    "    for(i <- 0 until 100) {\n",
    "        val input = scala.util.Random.nextInt(8)\n",
    "\n",
    "        val goldenModelResult = goldenModel.poke(input)\n",
    "\n",
    "        c.io.in.poke(input.U)\n",
    "\n",
    "        c.io.out.expect(goldenModelResult.U, s\"i $i, input $input, gm $goldenModelResult, ${c.io.out.peek().litValue}\")\n",
    "\n",
    "        c.clock.step(1)\n",
    "    }\n",
    "}\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<span style=\"color:red\">**Exercise: 32-bit RISC-V Processor**</span><br><a name=\"fir-golden-model\"></a>\n",
    "\n",
    "A [register file](https://en.wikipedia.org/wiki/Register_file) is an important building block for making a processor.\n",
    "A register file is an array of registers that can be read from or written to via a number of read or write ports.\n",
    "Each port consists of an address and data field.\n",
    "\n",
    "The [RISC-V instruction set architecture](https://riscv.org/specifications/) defines several variants, the simplest of which is called RV32I.\n",
    "RV32I has a size-32 array of 32-bit registers.\n",
    "**The register at index 0 (the first register) is always zero when you read from it, regardless of what you write to it** (it's often useful to have 0 handy).\n",
    "\n",
    "Implement a register file for RV32I with a single write port and a paramterized number of read ports.\n",
    "Writes will only be performed when `wen` (write enable) is asserted."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class RegisterFile(readPorts: Int) extends Module {\n",
    "    require(readPorts >= 0)\n",
    "    val io = IO(new Bundle {\n",
    "        val wen   = Input(Bool())\n",
    "        val waddr = Input(UInt(5.W))\n",
    "        val wdata = Input(UInt(32.W))\n",
    "        val raddr = Input(Vec(readPorts, UInt(5.W)))\n",
    "        val rdata = Output(Vec(readPorts, UInt(32.W)))\n",
    "    })\n",
    "    \n",
    "    // A Register of a vector of UInts\n",
    "    val reg = RegInit(VecInit(Seq.fill(32)(0.U(32.W))))\n",
    "    \n",
    "    ???\n",
    "\n",
    "    \n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test(new RegisterFile(2) ) { c =>\n",
    "  def readExpect(addr: Int, value: Int, port: Int = 0): Unit = {\n",
    "    c.io.raddr(port).poke(addr.U)\n",
    "    c.io.rdata(port).expect(value.U)\n",
    "  }\n",
    "  def write(addr: Int, value: Int): Unit = {\n",
    "    c.io.wen.poke(true.B)\n",
    "    c.io.wdata.poke(value.U)\n",
    "    c.io.waddr.poke(addr.U)\n",
    "    c.clock.step(1)\n",
    "    c.io.wen.poke(false.B)\n",
    "  }\n",
    "  // everything should be 0 on init\n",
    "  for (i <- 0 until 32) {\n",
    "    readExpect(i, 0, port = 0)\n",
    "    readExpect(i, 0, port = 1)\n",
    "  }\n",
    "\n",
    "  // write 5 * addr + 3\n",
    "  for (i <- 0 until 32) {\n",
    "    write(i, 5 * i + 3)\n",
    "  }\n",
    "\n",
    "  // check that the writes worked\n",
    "  for (i <- 0 until 32) {\n",
    "    readExpect(i, if (i == 0) 0 else 5 * i + 3, port = i % 2)\n",
    "  }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div id=\"container\"><section id=\"accordion\"><div>\n",
    "<input type=\"checkbox\" id=\"check-1\" />\n",
    "<label for=\"check-1\"><strong>Solution</strong></label>\n",
    "<article>\n",
    "<pre style=\"background-color:#f7f7f7\">\n",
    "    when (io.wen) {\n",
    "        reg(io.waddr) := io.wdata\n",
    "    }\n",
    "    for (i &lt;- 0 until readPorts) {\n",
    "        when (io.raddr(i) === 0.U) {\n",
    "            io.rdata(i) := 0.U\n",
    "        } .otherwise {\n",
    "            io.rdata(i) := reg(io.raddr(i))\n",
    "        }\n",
    "    }\n",
    "\n",
    "</pre></article></div></section></div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "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
}