The Elements of Computing Systems: Building a Modern Computer from First Principles (12 page)

Read The Elements of Computing Systems: Building a Modern Computer from First Principles Online

Authors: Noam Nisan,Shimon Schocken

BOOK: The Elements of Computing Systems: Building a Modern Computer from First Principles
8.59Mb size Format: txt, pdf, ePub
Figure 3.4
Combinational versus sequential logic (in and out stand for one or more input and output variables). Sequential chips always consist of a layer of DFFs sandwiched between optional combinational logic layers.
 
Recall that the outputs of combinational chips change when their inputs change, irrespective of time. In contrast, the inclusion of the DFFs in the sequential architecture ensures that their outputs change only at the point of transition from one clock cycle to the next, and not within the cycle itself. In fact, we allow sequential chips to be in unstable states during clock cycles, requiring only that at the beginning of the next cycle they output correct values.
This “discretization” of the sequential chips’ outputs has an important side effect: It can be used to synchronize the overall computer architecture. To illustrate, suppose we instruct the arithmetic logic unit (ALU) to compute
x
+
y
where
x
is the value of a nearby register and
y
is the value of a remote RAM register. Because of various physical constraints (distance, resistance, interference, random noise, etc.) the electric signals representing
x
and
y
will likely arrive at the ALU at different times. However, being a combinational chip, the ALU is insensitive to the concept of time—it continuously adds up whichever data values happen to lodge in its inputs. Thus, it will take some time before the ALU’s output stabilizes to the correct
x
+
y
result. Until then, the ALU will generate garbage.
How can we overcome this difficulty? Well, since the output of the ALU is always routed to some sort of a sequential chip (a register, a RAM location, etc.), we don’t really care. All we have to do is ensure, when we build the computer’s clock, that the length of the clock cycle will be slightly longer that the time it takes a bit to travel the longest distance from one chip in the architecture to another. This way, we are guaranteed that by the time the sequential chip updates its state (at the beginning of the next clock cycle), the inputs that it receives from the ALU will be valid. This, in a nutshell, is the trick that synchronizes a set of stand-alone hardware components into a well-coordinated system, as we shall see in chapter 5.
3.2 Specification
This section specifies a hierarchy of sequential chips:
• Data-flip-flops (DFFs)
• Registers (based on DFFs)
• Memory banks (based on registers)
• Counter chips (also based on registers)
3.2.1 Data-Flip-Flop
The most elementary sequential device that we present—the basic component from which all memory elements will be designed—is the
data flip-flop
gate. A DFF gate has a single-bit input and a single-bit output, as follows:
Like Nand gates, DFF gates enter our computer archtecture at a very low level. Specifically, all the sequential chips in the computer (registers, memory, and counters) are based on numerous DFF gates. All these DFFs are connected to the same master clock, forming a huge distributed “chorus line.” At the beginning of each clock cycle, the outputs of all the DFFs in the computer commit to their inputs during the previous time unit. At all other times, the DFFs are “latched,” meaning that changes in their inputs have no immediate effect on their outputs. This conduction operation effects any one of the millions of DFF gates that make up the system, about a billion times per second (depending on the computer’s clock frequency).
Hardware implementations achieve this time dependency by simultaneously feeding the master clock signal to all the DFF gates in the platform. Hardware simulators emulate the same effect in software. As far as the computer architect is concerned, the end result is the same: The inclusion of a DFF gate in the design of any chip ensures that the overall chip, as well as all the chips up the hardware hierarchy that depend on it, will be inherently time-dependent. These chips are called sequential, by definition.
The physical implementation of a DFF is an intricate task, and is based on connecting several elementary logic gates using feedback loops (one classic design is based on Nand gates alone). In this book we have chosen to abstract away this complexity, treating DFFs as primitive building blocks. Thus, our hardware simulator provides a built-in DFF implementation that can be readily used by other chips.
3.2.2 Registers
A single-bit register, which we call Bit, or binary cell, is designed to store a single bit of information (0 or 1). The chip interface consists of an input pin that carries a data bit, a load pin that enables the cell for writes, and an output pin that emits the current state of the cell. The interface diagram and API of a binary cell are as follows:
The API of the Register chip is essentially the same, except that the input and output pins are designed to handle multi-bit values:
The Bit and Register chips have exactly the same read/write behavior:
 
Read:
To read the contents of a register, we simply probe its output.
Write:
To write a new data value d into a register, we put d in the in input and assert (set to 1) the load input. In the next clock cycle, the register commits to the new data value, and its output starts emitting d.
3.2.3 Memory
A direct-access memory unit, also called RAM, is an array of n
w
-bit registers, equipped with direct access circuitry. The number of registers (
n
) and the width of each register (
w
) are called the memory’s size and width, respectively. We will now set out to build a hierarchy of such memory devices, all 16 bits wide, but with varying sizes: RAM8, RAM64, RAM512, RAM4K, and RAM16K units. All these memory chips have precisely the same API, and thus we describe them in one parametric diagram:
Read:
To read the contents of register number m, we put
m
in the address input. The RAM’s direct-access logic will select register number m, which will then emit its output value to the RAM’s output pin. This is a combinational operation, independent of the clock.
Write:
To write a new data value d into register number m, we put
m
in the address input, d in the in input, and assert the load input bit. This causes the RAM’s direct-access logic to select register number m, and the load bit to enable it. In the next clock cycle, the selected register will commit to the new value (
d
), and the RAM’s output will start emitting it.
3.2.4 Counter
Although a
counter
is a stand-alone abstraction in its own right, it is convenient to motivate its specification by saying a few words about the context in which it is normally used. For example, consider a counter chip designed to contain the address of the instruction that the computer should fetch and execute next. In most cases, the counter has to simply increment itself by 1 in each clock cycle, thus causing the computer to fetch the next instruction in the program. In other cases, for example, in “jump to execute instruction number
n
,” we want to be able to set the counter to n, then have it continue its default counting behavior with n + 1, n + 2, and so forth. Finally, the program’s execution can be restarted anytime by resetting the counter to 0, assuming that that’s the address of the program’s first instruction. In short, we need a loadable and resettable counter.
With that in mind, the interface of our Counter chip is similar to that of a register, except that it has two additional control bits labeled reset and inc. When inc=1, the counter increments its state in every clock cycle, emitting the value out(t)= out (t-1)+1. If we want to reset the counter to 0, we assert the reset bit; if we want to initialize it to some other counting base
d
, we put d in the in input and assert the load bit. The details are given in the counter API, and an example of its operation is depicted in figure 3.5.
3.3 Implementation
Flip-Flop
DFF gates can be implemented from lower-level logic gates like those built in chapter 1. However, in this book we treat DFFs as primitive gates, and thus they can be used in hardware construction projects without worrying about their internal implementation.

Other books

A Glimpse of the Dream by L. A. Fiore
Aligned by Workman, Rashelle
What the Lady Wants by Jennifer Crusie
Arousing Amelia by Ellie Jones
Me & Emma by Elizabeth Flock
Lucky Break by Deborah Coonts