Bus-level design

Customizing Scala collections

Now that we have data and control put into good use, let us approach the next issue in terms of design convenience. Namely, the transition from designing with individual wires that carry bits (that is, individual gates in our Scala simulation) to designing with buses of wires that carry words (that is, sequences of gates in our Scala simulation). Recall from Round 2: Bits and data that a word is the atomic unit by which a processor architecture manipulates data. The word length of the architecture is the number of bits in a word.

The necessity to design at the level of words is of course an excellent motivation to drill into the Scala collections framework, and in particular into the tools to manipulate sequences. If possible, we want our bus-level designs to be just as succinct as our gate-level designs. Indeed, recall that our goal for this round is to build a Boolean circuit that adds two 64-bit integers.

Let us start by recalling our gate-level design for selecting between two gates:

val r = (a && !s) || (b && s)

Here a and b were the data inputs (individual gates), and s was the control input (individual gate).

We want to upgrade the gate-selector to a bus-selector, that selects between two n-bit buses. Here we display a bus-selector that selects between two 4-bit buses, aa and bb, to produce the 4-bit bus rr as output.

The circuit diagram may look a bit daunting at first, but observe that this is in fact not the case. The same two-input selector is simply repeated four times, once for each pair of corresponding bits aa(i) and bb(i) in the two buses. In particular, the same control input s drives all four selectors.

To enter the realm of bus-level design, let us first try to work with the obvious abstraction, namely let us just work with an array of gates Array[Gate] whenever a bus is needed.

Say, let us transport the gate-level design into a design with two n-bit buses with n = 4. Let us build these buses out of input elements:

val n  = 4
val aa = new Array[Gate](n)
for i <- 0 until n do aa(i) = new InputElement()
val bb = new Array[Gate](n)
for i <- 0 until n do bb(i) = new InputElement()
val s  = new InputElement()

Here is a first attempt to build a two-bus selector that uses a for-loop over the bits of the bus:

val rr_attempt1 = new Array[Gate](n)
for i <- 0 until n do
  rr_attempt1(i) = (aa(i) && !s)||(bb(i) && s)
end for

This code will build precisely the circuit depicted above, so in principle we are done.

But again we should be more critical. Indeed, we are using a for-loop when far more succinct and idiomatic expressions exist for the task. Also the need to reserve new Array-objects looks cumbersome.

Here are three further attempts, throwing in some skill at using Scala collections and anonymous functions. (Do not worry if you cannot follow in detail what these one-liners do, we will get practice during later rounds.) Here we go:

val rr_attempt2 = (aa.map(_ && !s) zip bb.map(_ && s)).map((p,q) => p || q)

Here is another go:

val rr_attempt3 = (aa zip bb).map((a,b) => (a && !s) || (b && s))

And yet another:

val rr_attempt4 = (aa zip bb).map(x => (x._1 && !s) || (x._2 && s))

A quick Toggler session gives us a fair amount of confidence that all four solutions work (try this!):

val t = new Toggler()
t.watch("aa", aa)
t.watch("bb", bb)
t.watch("s", s)
t.watch("rr1", rr_attempt1)
t.watch("rr2", rr_attempt2)
t.watch("rr3", rr_attempt3)
t.watch("rr4", rr_attempt4)
t.go()

Several working solutions are a fair start, but we should not be happy, since the Scala code is far from succinct and readable.

So what is it that we would like? An appropriately apt solution would perhaps be:

val rr = (aa && !s)|(bb && s)

And while we are at it, perhaps the setup code could be also cleaned. If we place some routine setup code into aptly named companion objects, the entire two-bus selector gets built with:

val n  = 4
val aa = Bus.inputs(n)
val bb = Bus.inputs(n)
val s  = Gate.input()
val rr = (aa && !s)|(bb && s)

Incidentally, the bus-level design tools are already implemented in package tinylog. Just copy and paste what is above into your console after include tinylog.* to witness this.

The package tinylog is included with the exercises for this round. If you open it up you will see something like in the listing below. Understanding the entire code is not necessary at this point, but note that Bus extends Seq[Gate], that is, a bus is a sequence of Gate objects. This allows us to perform standard sequence operations, such as zip on Bus as well as the defined custom methods.

package tinylog
import scala.collection.{SpecificIterableFactory, StrictOptimizedSeqOps, mutable}
import collection.SeqOps

sealed class Bus(gates: Seq[Gate]) extends Seq[Gate]
    with SeqOps[Gate, Seq, Bus]
    with StrictOptimizedSeqOps[Gate, Seq, Bus]:

  // Mandatory implementation of `apply` in SeqOps
  def apply(idx: Int) = gates.apply(idx)

  /** Creates a new Bus from a set of indexes to this one.*/
  def apply(idxs: Seq[Int]) = new Bus(idxs.map(gates(_)))

  // Mandatory implementation of `length` and `iterator`
  def length = gates.length
  def iterator = gates.iterator

  /* Operations on Gates.*/

  /** Values of Gates.*/
  def values = gates.map(_.value)

  /** The number of gates (i) in this bus and (ii) recursively referenced by the ones in this bus. */
  def nofGates: Int =
    val counted = new mutable.HashSet[Gate]()
    gates.foldLeft(0)((result, gate) => result + gate.nofReferenced(counted))

  /**
   * For a bus aa and gate g, aa && g returns a new bus cc
   * of length aa.length such that cc(i) is aa(i) && g.
   */
  def &&(that: Gate) = new Bus(this.map(_ && that))

  /**
   * For a bus aa and gate g, aa || g returns a new bus cc
   * of length aa.length such that cc(i) is aa(i) || g.
   */
  def ||(that: Gate) = new Bus(this.map(_ || that))

  /**
   * Bitwise negation of the bus.
   * For a bus aa, ~aa is a new bus cc such that cc(i) is !aa(i).
   */
  def unary_~ = this.map(!_)

  /**
   * Bitwise AND of two busses.
   * For two busses aa and bb, aa & bb returns a new bus cc
   * of length aa.length such that cc(i) is aa(i) && bb(i).
   * The busses must be of the same length.
   */
  def &(that: Bus) =
    require(this.length == that.length, "Cannot take bitwise and of busses of different length")
    new Bus((this zip that).map(x => x._1 && x._2))

  /**
   * Bitwise OR of two busses.
   * For two busses aa and bb, aa | bb returns a new bus cc
   * of length aa.length such that cc(i) is aa(i) || bb(i).
   * The busses must be of the same length.
   */
  def |(that: Bus) =
    require(this.length == that.length, "Cannot take bitwise and of busses of different length")
    new Bus((this zip that).map(x => x._1 || x._2))
  /* Because Bus is a custom collection (based on Seq) with SeqOps trait
     we need to override a a few methods so that it can inherit all of the
     standard operations from the trait while still behaving as a Bus as
     much as possible.
     If you are interested, see the RNA exampe at 
     https://docs.scala-lang.org/overviews/core/custom-collections.html#final-version-of-rna-strands-class
   */

  // Mandatory overrides of `fromSpecific`, `newSpecificBuilder`,
  // and `empty`, from `IterableOps`
  override protected def fromSpecific(coll: IterableOnce[Gate]): Bus =
    Bus.fromSpecific(coll)

  override protected def newSpecificBuilder: mutable.Builder[Gate, Bus] =
    Bus.newBuilder

  override def empty: Bus = Bus.empty

  // Overloading of `appended`, `prepended`, `appendedAll`, `prependedAll`,
  // `map`, `flatMap` and `concat` to return a `Bus` when possible
  def concat(suffix: IterableOnce[Gate]): Bus =
    strictOptimizedConcat(suffix, newSpecificBuilder)

  @inline final def ++ (suffix: IterableOnce[Gate]): Bus = concat(suffix)

  def appended(base: Gate): Bus =
    (newSpecificBuilder ++= this += base).result()

  def appendedAll(suffix: Iterable[Gate]): Bus =
    strictOptimizedConcat(suffix, newSpecificBuilder)

  def prepended(base: Gate): Bus =
    (newSpecificBuilder += base ++= this).result()

  def prependedAll(prefix: Iterable[Gate]): Bus =
    (newSpecificBuilder ++= prefix ++= this).result()

  def map(f: Gate => Gate): Bus =
    strictOptimizedMap(newSpecificBuilder, f)

  def flatMap(f: Gate => IterableOnce[Gate]): Bus =
    strictOptimizedFlatMap(newSpecificBuilder, f)

  // The class name will by default be shown as 'Seq', we don't want that.
  override def className = "Bus"


object Bus extends SpecificIterableFactory[Gate, Bus]:

  def empty: Bus = new Bus(Seq.empty)

  def newBuilder: mutable.Builder[Gate,Bus] =
    mutable.ArrayBuffer.newBuilder[Gate]
    .mapResult(s=>new Bus(s.toSeq))

  def fromSpecific(it: IterableOnce[Gate]): Bus = it match
    case seq: Seq[Gate] => new Bus(seq)
    case _ => new Bus(it.iterator.toSeq)

  /** Returns a new bus with n InputElement gates */
  def inputs(n: Int) = new Bus((1 to n).map(x => Gate.input()))
  /** Returns a new bus of n False gates */
  def falses(n: Int) = new Bus((1 to n).map(x => Gate.False))
  /** Returns a new bus of n True gates */
  def trues(n: Int) = new Bus((1 to n).map(x => Gate.True))

What sets a Bus apart from a plain sequence of objects of type Gate is that there are custom methods (operator definitions) inside class Bus that enable succinct bus-level building:

def &&(that: Gate) = new Bus(this.map(_ && that))
def ||(that: Gate) = new Bus(this.map(_ || that))
def unary_~        = this.map(!_)
def &(that: Bus)   = new Bus((this zip that).map(x => x._1 && x._2))
def |(that: Bus)   = new Bus((this zip that).map(x => x._1 || x._2))

Let us take a more detailed look at these operators. (At this point it may be convenient to recall how we defined the gate-level operators in the previous section.)

First, let us look at the operators

def &&(that: Gate) = new Bus(this.map(_ && that))
def ||(that: Gate) = new Bus(this.map(_ || that))

Observe that the operators && and || are defined so that the left operand (this) is a Bus, and the right operand (that) is a Gate. In both cases the result is a new bus, consisting of AND and OR gates (depending on whether && or || was applied) such that the left input is a gate from the bus, and the right input is the right operand (the gate that). (The expression _ && that is a shorthand for the function z => z && that.) If you are familiar with vectors and scalars, this is the circuit-building analogue of operating on a vector with a scalar.

The following figure illustrates the bus that gets built when we execute the expression bb && g for a 4-gate bus bb and a gate g.

Let us proceed to the next operator:

def unary_~        = this.map(!_)

The operator ~ builds, one entry of its operand (this) at a time, a NOT-gate that takes input from the entry (the gate of the bus), and returns a bus consisting of the NOT-gates built. This is, in essence, the circuit-building analogue of vector negation.

The following figure illustrates the bus that gets built when we execute the expression ~bb for a 4-gate bus bb.

Let us then look at the remaining operators:

def &(that: Bus)   = new Bus((this zip that).map(x => x._1 && x._2))
def |(that: Bus)   = new Bus((this zip that).map(x => x._1 || x._2))

In this case both operands (this and that) are buses. The operator & (respectively, the operator |) builds, one entry at a time, an AND-gate (OR-gate) that takes input from the corresponding entries (gates) in the left and right operands, and return a bus consisting of the AND-gates (OR-gates) built. This is the circuit-building analogue of vector addition.

The following figure illustrates the bus that gets built when we execute the expression aa | bb for two 4-gate buses aa and bb.

Combining the bus-level operators, we observe that executing (aa && !s)|(bb && s) indeed constructs the desired selector:

Convention on indexing the bits in a bus

When drawing circuits, it is customary to index the bits in a bus from right to left. That is, the bit with index 0 is the rightmost bit in a bus, and the indices increase from right to left, from the least significant bit to the most significant bit.

This convention makes it easy to work with buses that carry binary integers, because the integer is displayed on the bus directly in its customary binary form, with the most significant binary digit (bit) on the left, and the least significant binary digit on the right. (Recall our discussion of the positional number system on Round 2: Bits and data.)

Functional design – encapsulating code that builds subcircuits

To arrive at more intricate circuit designs, it is useful to encapsulate circuit-building code into procedures that hide the implementation and enable us to build larger circuits out of smaller component circuits. For example, our two-bus selector can be encapsulated as:

def buildTwoBusSelector(aa: Bus, bb: Bus, s: Gate) =
  (aa && !s)|(bb && s)

Here is a builder that reverses the order of bits in a bus:

def buildReverser(aa: Bus) =
  aa.reverse

Observe that a reverser actually builds no gates, but rather it simply reverses the order of bits in a bus. We display a reverser for word length 8 below:

Here is a builder that shifts in k zero bits from the right, and drops k bits out from the left:

def buildLeftShift(aa: Bus, k: Int) =
  Bus.falses(k) ++ aa.dropRight(k)

We display a left shift for k = 3 and word length 8 below:

Of course the power of such an approach is revealed when we start combining builders to yield more complex builders. Here is a builder for a circuit that outputs either its input aa, or aa reversed, depending on the value of a control input s:

def buildIdentityOrReverse(aa: Bus, s: Gate) =
  buildTwoBusSelector(aa, buildReverser(aa), s)

Observe how all the attention that we have put into making our tools convenient to use is now starting to pay off.

Here is a shifter that shifts to the left by 1 or 3, depending on the control input s:

def buildLeftShift1Or3(aa: Bus, s: Gate) =
  buildTwoBusSelector(buildLeftShift(aa,1),
                      buildLeftShift(aa,3),
                      s)

What about selecting among more than two possibilities?

Here is a builder for a selector (or multiplexer) that takes a sequence of input buses and a sequence (bus) of selector bits, and outputs the bus that corresponds to the most significant selector bit that is set to true, or an all-false bus if all selector bits are false:

def buildBusSelector(buses: Seq[Bus], selectors: Bus) =
  var rr = Bus.falses(buses(0).length)
  for i <- 0 until buses.length do
    val bb = buses(i)
    val s = selectors(i)
    rr = buildTwoBusSelector(rr,bb,s)
  end for
  rr
end buildBusSelector

Here is the same builder but written in a different style that makes use of the foldLeft operation and a case-expression to match the components of a tuple:

def buildBusSelector(buses: Seq[Bus], selectors: Bus) =
 (buses zip selectors).foldLeft(Bus.falses(buses(0).length)){
    case (rr,(bb,s)) => buildTwoBusSelector(rr,bb,s)
  }
end buildBusSelector

Let us now combine our tools for a bit of play. Here is a design for Toggler that shifts the 16-bit input by any amount of your choosing between 0 and 15 bits to the left:

val n             = 16
val input         = Bus.inputs(n)
val amount_select = Bus.inputs(n)
val shifts        = (0 until n).map(k => buildLeftShift(input, k))
val output        = buildBusSelector(shifts, amount_select)

val t = new Toggler()
  // reversion will display least significant bit on the right
t.watch("input",         input.reverse)
t.watch("amount_select", amount_select.reverse)
t.watch("output",        output.reverse)
t.go()

All right, that was fun. But suppose we wanted to give the selection as a binary input? That is, \(b\) bits suffice to select among \(2^{b}\) choices.

Here is a builder for a binary decoder circuit that takes an integer \(j = 0, 1, \ldots, 2^{b} - 1\) as a \(b\)-bit bus of input and gives a \(2^{b}\)-bit bus of output such that on input \(j\) exactly the output with index \(j\) is true.

def buildDecoder(aa: Bus) =
  aa.foldLeft(Bus(Gate.True))((d,a) => (d && !a)++(d && a))

To observe a binary decoder in operation with Toggler, copy and paste the following code to the console, toggle in any 4-bit binary number via the inputs, and witness exactly the output indexed by that number become true among the 16-bit output:

val amount_bits = 4
val input       = Bus.inputs(amount_bits)
val output      = buildDecoder(input)

val t = new Toggler()
  // reversion will display least significant bit on the right
t.watch("input",  input.reverse)
t.watch("output", output.reverse)
t.go()

Here is the previous shifter code, but now using a binary decoder so that the shift amount can be given in binary using 4 bits:

val n           = 16
val amount_bits = 4  // the base-2 log of n
val input       = Bus.inputs(n)
val amount      = Bus.inputs(amount_bits)
val shifts      = (0 until n).map(k => buildLeftShift(input, k))
val output      = buildBusSelector(shifts, buildDecoder(amount))

val t = new Toggler()
  // reversion will display least significant bit on the right
t.watch("input",  input.reverse)
t.watch("amount", amount.reverse)
t.watch("output", output.reverse)
t.go()

Remark. At this point we should observe and recognize the fruits of our efforts at making our tools convenient. With a few lines of code, we can build and play with intricate circuit designs that accept buses of data input and control input. Think about how many lines of code it would require to build these circuits out of individual gates if we had not paid attention to developing our tools to match the increased complexity.

With our tools sharpened to deal with bus-level designs, we are ready now ready to meet our goal for this round.