Gate-level design

Defining operators in Scala

So far so good. We know how to build combinational logic in Scala, and have some tools available to inspect what is going on inside a circuit. And, being diligent practitioners of bottom-up design, we have immediately put our tools to use and built a small circuit that tests whether its inputs are identical.

At this point it is a good idea to pause a bit and review our programming tools.

In principle we should be satisfied with our tools. They will build us any circuit we like.

But are our tools convenient to use? Is it fun to build and play with circuits? Recall that as programmers we have the power to create our own tools, so it is not only useful but necessary to review our tools. Are our tools up to the task of building far, far more intricate combinational logic than the small circuit we just built?

Let us be critical. Look at the Scala code that builds the small circuit:

val a = new InputElement()
val b = new InputElement()
val g1 = new AndGate(a,b)
val g2 = new NotGate(a)
val g3 = new NotGate(b)
val g4 = new AndGate(g2,g3)
val out = new OrGate(g1,g4)

What we should observe immediately that it takes a lot of typing to type the code in, and the code is not particularly readable. And this is a circuit with a grand total of seven (7) gates (two of which are input elements).

At this point an experienced programmer would signal that our tools will fail us when we start scaling up our designs.

Remark. We have just observed yet another advantage of bottom-up design. If we pay attention to potential pitfalls, we can catch them early in the process. (In practice this takes quite a bit of experience with programming, but we believe it is instructive to convey how an experienced programmer thinks about a design and critically reviews the design, right from the start.)

Before proceeding further into circuit construction, let us yet sharpen our tools for increased convenience. We have just observed that we are not happy with the boilerplate that it takes to build even a small circuit, so it is a good idea to do something about this right now, before our designs have grown larger and more difficult to understand and handle.

As a first attempt to make building circuits less cumbersome, we extend the base class Gate to get rid of the annoying “new”-statements when building new gates. In particular, we equip the base class with methods not, and, and or that construct a new gate so that the current object (this) is the (left) input to the gate being constructed, and the other (right) input, if any, is taken as a parameter (that). Here we go:

abstract class Gate():
  def value: Boolean     // implemented by the extending classes
  def not             = new NotGate(this)
  def and(that: Gate) = new AndGate(this, that)
  def or(that: Gate)  = new OrGate(this, that)
end Gate

This shortens our previous circuit-building code to:

val a = new InputElement()
val b = new InputElement()
val g1 = a.and(b)
val g2 = a.not
val g3 = b.not
val g4 = g2.and(g3)
val out = g1.or(g4)

Or what is the same, but avoiding the intermediate values:

val a = new InputElement()
val b = new InputElement()
val out = (a.and(b)).or(a.not.and(b.not))

The code for building the circuit is now short, but it still lacks readability. For example, think about a simple mathematical expression such as

x+y*(z-w)

and contrast this with writing the same expression as

x.plus(y.times(z.minus(w)))

Clearly the former expression is both easier to read and easier to write.

Mathematical operations of various types are frequently encountered in programming, and hence many programming languages, Scala included, make it possible for a programmer to define the meaning of operators such as +, -, *, and / when they are applied to programmer-defined objects.

In our case, we are interested in building new gates by applying a logical operator (NOT, AND, or OR) to one or two objects of type Gate. We can do this in Scala by defining the meaning of the corresponding Boolean operators !, &&, and || when they are applied to objects of type Gate. Operators that act on objects in a class are defined in Scala by defining methods with names unary_!, &&, and || inside class Gate (compare this with methods not, and, and or defined above):

abstract class Gate():
  def value: Boolean     // implemented by the extending classes
  def unary_!: Gate        = new NotGate(this)
  def &&(that: Gate): Gate = new AndGate(this, that)
  def ||(that: Gate): Gate = new OrGate(this, that)
end Gate

To build circuits, it now suffices to write expressions with Boolean operators and objects of type Gate, and the resulting method calls will construct the circuit for us. This makes it very convenient to build circuits in Scala. That is, we build a circuit using precisely the same convenient syntax as if we were evaluating a Boolean expression.

For example, our code for building exactly the same circuit as before now reads:

val a = new InputElement()
val b = new InputElement()
val out = (a && b) || (!a && !b)

The last line is just a syntactic shorthand for the following method calls in class Gate:

val out = (a.&&(b)).||(a.unary_!.&&(b.unary_!))

In fact, all operator expressions in Scala are just such shorthand for method calls. For example, a+b is a shorthand for a.+(b). One has to be careful with precedence though, for example, a+b*c is a shorthand for a.+(b.*(c)), not (a.+(b)).*(c).

Remark 1. Before proceeding further, let us yet again reflect where we are and what we have done. We observed that we may be facing trouble unless we make it more convenient to build circuits, and with some effort we were able to improve our circuit-building tools. Experienced programmers are constantly engaging in such dialogue with colleagues and themselves with the aim to evaluate the convenience of a design and potential pitfalls that may arise when the tools are deployed in production.

Remark 2. (**) In case you are interested in the details of how expressions are constructed in Scala from operands and operators, you may want to study Section 6.12 (“Prefix, Infix, and Postfix Operations”) in the Scala Language Specification.

Our first design – the half adder

With our circuit-building and tinkering tools sharpened, let us continue towards our goal. To arrive at a circuit that adds two 64-bit integers, it would appear like a good first step to design a circuit that adds two 1-bit integers. We know how to add 1-bit integers, in binary:

\[\begin{split}0 + 0 &= 0\\ 0 + 1 &= 1\\ 1 + 0 &= 1\\ 1 + 1 &= 10\end{split}\]

It looks like we need to have a 2-bit output from our circuit, because \(1 + 1\) in binary produces the carry \(1 + 1 = 10\). So our specification reads:

\[\begin{split}0 + 0 &= 00\\ 0 + 1 &= 01\\ 1 + 0 &= 01\\ 1 + 1 &= 10\end{split}\]

Or in circuit terms, we need a circuit that takes two inputs, and produces two outputs, with the following specification:

Here is a circuit that meets the specification (check this!):

Or what is the same, in Scala (check this with Toggler):

val a = new InputElement()
val b = new InputElement()
val c = a && b
val s = (a || b) && !c

But hold on! How did we actually come up with the circuit?

How does one design circuits that meet a specification?

Specification and implementation – the truth table and synthesis

One way to specify what a circuit needs to do is to list what must happen at the output (or at each output, if there are multiple outputs) for every possible input to the circuit. Such a specification is called a truth table.

Here is a truth table that completely specifies a half adder:

There are two inputs, namely the summands a and b, and two outputs, namely the sum s and the carry c.

If we are dogmatic about our terminology, a truth table must specify exactly one output, so we actually have two truth tables to specify the half adder, one for each output:

A specification in general tells us in precise, unequivocal terms what must be done. For example, a specification could read as:

“The square root of a non-negative real number \(x\) is a non-negative real number \(y\) such that \(x = y^{2}\). Given a rational number \(x\) as input, determine a rational number that differs in absolute value from the square root of \(x\) by at most \(10^{-100}\).”

In our case, a specification tells us what the circuit must do. A truth table gives a precise specification for (one output of) a circuit.

An implementation in general tells us in precise, unequivocal terms how to do it, or, depending on perspective, “actually does it”. For example, square roots may be computed to an arbitrary precision using Newton’s method.

So how does one implement (or synthesize) a circuit from a truth table?

One possible strategy is to simply “read the 1-output rows” in a table. Namely, for each 1-output row, we write an AND-expression of inputs (or NOT-ted inputs) such that the AND-expression is true exactly when the inputs match the values given in the row.

Let us do this for both of our truth tables, one 1-output row at a time:

Next, we simply take the OR of the expressions that we have written. We now have an implementation of the specification.

Or what is the same, drawn as a circuit:

Circuits constructed in this form are called OR-AND circuits because of their “outer” (closer to outputs) layer of OR-gates and “inner” (closer to inputs) layer of AND-gates. Alternatively, OR-AND circuits are said to be in disjunctive normal form or DNF.

Remark. Again it is a good idea to pause and reflect what we have just learned. As soon as we know what we want (or more precisely, as soon as we can write a truth table), we also know how to get it. That is, we know how to build a machine (a Boolean circuit) that does what we want. We simply synthesize the circuit from the truth table.

Configurability – data and control

Let us now put our new skills at specification and implementation into action. In particular, since we now know how to build machines that do what we want, it is more than appropriate to make a first attack at resolving the mystery of programmability. How do we build machines that are programmable and will do whatever we instruct them to do?

Programming is about control. We have the power (instrumented by a programming language) to tell the machine what to do. But how is this power available and implemented, built into the machine? What is the origin of the versatility that we witness in a computer?

Again let us think about this by starting from the bottom up.

What is control? Simplified to the extreme, and thinking in Boolean terms, perhaps an ON/OFF switch would be a good starting point.

A switch – say, a light switch – is a clear instrument of control.

So how would an ON/OFF switch manifest itself in Boolean circuitry?

Perhaps all that is required is a simple but fundamental change in how we view a Boolean circuit. Indeed, if we want, we can view each one-bit input to a circuit as a switch. In the simplest case, there is one input (“the switch”) that controls what the circuit does with the rest of the inputs.

Let us explore this change of view in the small. Consider a circuit that consists of a single AND-gate, and designate one of the two inputs as “the switch” s:

Studying the truth table from our newly adopted viewpoint, we see that when “the switch” s is set to false, the output r stays at false no matter what the value of the other input to the AND gate. When “the switch” s is set to true, the AND gate simply passes the other input b as is to its output r. Already this appears like a property that we could put into good use.

So let us get more ambitious. Could we make a circuit that selects between two inputs, based on what “the switch” (a third input) says?

Of course we can. Simply write out the truth table and synthesize the circuit:

By studying the truth table, we observe that the design indeed performs as intended. If the switch s is set to false, the output r equals the input a. If the switch s is set to true, the output r equals the input b.

Just to be sure that this is the case, let us witness the circuit operate in Toggler:

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

val t = new Toggler()
t.watch("s", s)
t.watch("a", a)
t.watch("b", b)
t.watch("r", r)
t.go()

After a minute or two of fun with Toggler, we should be convinced that the switch s indeed selects between the inputs a and b, just as we designed. Incidentally, an equivalent and more succinct design is:

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

Let us now step back and reflect a little. At this point it would appear that Boolean circuits have suddenly become more powerful, since we can now control what a circuit does. Of course this is not strictly speaking true, since the only thing that changed was our view of Boolean circuits. From a design perspective, it is useful to view that some of the inputs to a circuit are data inputs and some of the inputs are control inputs that affect how the circuit operates on the data inputs to produce the outputs. A different way of saying the same thing is that the control inputs configure the circuit.

So, in terms of the big picture, are we done yet? Is configurability the same as programmability?

No, not really. The computer is more than combinational logic.

But we are getting closer to understanding the computer. (Indeed, take a peek at programmable logic!)

Efficiency – circuit depth and size (*)

Let us conclude this section on gate-level design by briefly thinking about what constitutes an efficient circuit design for a task. Indeed, whenever we have succeeded in producing at least one design that performs a task, from an engineering perspective a key question is whether a more efficient design exists.

So what properties of a combinational circuit measure its efficiency?

If we think about a physical implementation of a circuit, numerous possibilities present themselves, ranging from power consumption to speed. In our case, however, we have chosen to abstract away physical details from our Scala circuit simulation, so physical properties are not available to enable comparison of designs.

Yet, our circuits have two properties that we can use to compare designs, and these properties are natural measures of efficiency also in the context of physical design. These two properties are circuit depth and circuit size. In physical terms, the first property measures, roughly, how fast we can run the circuit, and the second measures, again roughly, the resources required to successfully manufacture the circuit and, very roughly, its power consumption when it is operated.

Circuit depth. Physical circuits are physical objects that require time to operate. It takes time for electric signals to propagate in conductors, and it takes time for gates to stabilize their output value once their input value(s) are stable. A rough measure of the speed at which we can run a circuit is its depth, that is, the length of the longest sequence of gates whose values need to stabilize when we change the values of the input elements.

In more precise terms, the depth of a gate is defined inductively as follows. The input elements to the circuit have depth zero. The depth of a logic gate is the maximum of the depths of its input gates, plus one. The depth of a circuit is the maximum of the depths of all of its gates.

The smaller the depth, the faster we can operate a circuit. Thus, among multiple possible designs for a task, we should prefer circuits that have small depth if we desire a fast circuit.

Example. Suppose we need to take the logical AND of 8 input elements. That is, we require a circuit that has one output that evaluates to true if and only if each of its 8 input elements evaluates to true. It is immediate that such a circuit can be implemented with two-input AND-gates, and a little reflection shows that exactly 7 two-input AND-gates are both necessary and sufficient. But there are many ways to connect the 7 gates with each other and the input elements. Here are two possibilities:

The circuit on the left has depth 3, the circuit on the right has depth 7. Clearly the circuit on the left is more efficient in terms of the depth. Many more possibilities exist beyond the two displayed circuits, but the circuit on the left is in fact the circuit with the minimum depth for the task. (What if we had 16 inputs? Or 1048576 inputs?)

Circuit size. Physical circuits are physical objects that require energy to operate and material to manufacture the circuits. Very roughly, the more gates the circuit has, the more energy and materials it requires, assuming each individual gate requires a fixed amount of both. Furthermore, a large number of gates means also increased complexity and e.g. increased probability of defects in the manufacturing process compared with a smaller design. Thus, among multiple possible designs for a task, we should prefer circuits that use the least amount of gates if we aim for low resource consumption.

To adopt a precise definition for purposes of our simulated circuits, let us define the size of a circuit to be the total number of gates in the circuit, including both logic gates and input elements.

Example. Let us revisit two of the half-adder designs that we built above. The first design has 2 inputs and 4 logic gates, so its size is 6:

The second design has 2 inputs and 11 logic gates, so its size is 13:

Both circuits implement the half-adder, but clearly the first one is more efficient in terms of circuit size.