The Elements of Computing Systems: Building a Modern Computer from First Principles by Noam Nisan, Shimon Schocken Read Free Book Online Page A
Authors: Noam Nisan, Shimon Schocken
achieved by negating all the bits of x and adding 1 to the result. Thus subtraction can be easily handled by x – y = x + (– y ). Once again, hardware complexity is kept to a minimum.
The material implications of these theoretical results are significant. Basically, they imply that a single chip, called Arithmetic Logical Unit, can be used to encapsulate all the basic arithmetic and logical operators performed in hardware. We now turn to specify one such ALU, beginning with the specification of an adder chip.
2.2 Specification
2.2.1 Adders
We present a hierarchy of three adders, leading to a multi-bit adder chip:
• Half-adder: designed to add two bits
• Full-adder: designed to add three bits
• Adder: designed to add two n -bit numbers
Figure 2.2 Half-adder, designed to add 2 bits.
We also present a special-purpose adder, called incrementer, designed to add 1 to a given number.
Half-Adder The first step on our way to adding binary numbers is to be able to add two bits. Let us call the least significant bit of the addition sum, and the most significant bit carry. Figure 2.2 presents a chip, called half-adder, designed to carry out this operation.
Full-Adder Now that we know how to add two bits, figure 2.3 presents a full-adder chip, designed to add three bits. Like the half-adder case, the full-adder chip produces two outputs: the least significant bit of the addition, and the carry bit.
Adder Memory and register chips represent integer numbers by n -bit patterns, n being 16, 32, 64, and so forth—depending on the computer platform. The chip whose job is to add such numbers is called a multi-bit adder, or simply adder. Figure 2.4 presents a 16-bit adder, noting that the same logic and specifications scale up as is to any n -bit adder.
Incrementer It is convenient to have a special-purpose chip dedicated to adding the constant 1 to a given number. Here is the specification of a 16-bit incrementer:
Figure 2.3 Full-adder, designed to add 3 bits.
Figure 2.4 16-bit adder. Addition of two n -bit binary numbers for any n is “more of the same.”
2.2.2 The Arithmetic Logic Unit (ALU)
The specifications of the adder chips presented so far were generic, meaning that they hold for any computer. In contrast, this section describes an ALU that will later become the centerpiece of a specific computer platform called Hack. At the same time, the principles underlying the design of our ALU are rather general. Further, our ALU architecture achieves a great deal of functionality using a minimal set of internal parts. In that respect, it provides a good example of an efficient and elegant logic design.
The Hack ALU computes a fixed set of functions out = f i ( x , y) where x and y are the chip’s two 16-bit inputs, out is the chip’s 16-bit output, and f i is an arithmetic or logical function selected from a fixed repertoire of eighteen possible functions. We instruct the ALU which function to compute by setting six input bits, called control bits, to selected binary values. The exact input-output specification is given in figure 2.5, using pseudo-code.
Note that each one of the six control bits instructs the ALU to carry out a certain elementary operation. Taken together, the combined effects of these operations cause the ALU to compute a variety of useful functions. Since the overall operation is driven by six control bits, the ALU can potentially compute 2 6 = 64 different functions. Eighteen of these functions are documented in figure 2.6.
We see that programming our ALU to compute a certain function f ( x , y) is done by setting the six control bits to the code of the desired function. From this point on, the internal ALU logic specified in figure 2.5 should cause the ALU to output the value f ( x , y) specified in figure 2.6. Of course, this does not happen miraculously, it’s the result of careful design.
For example, let us consider the twelfth row of figure 2.6, where
The material implications of these theoretical results are significant. Basically, they imply that a single chip, called Arithmetic Logical Unit, can be used to encapsulate all the basic arithmetic and logical operators performed in hardware. We now turn to specify one such ALU, beginning with the specification of an adder chip.
2.2 Specification
2.2.1 Adders
We present a hierarchy of three adders, leading to a multi-bit adder chip:
• Half-adder: designed to add two bits
• Full-adder: designed to add three bits
• Adder: designed to add two n -bit numbers
Figure 2.2 Half-adder, designed to add 2 bits.
We also present a special-purpose adder, called incrementer, designed to add 1 to a given number.
Half-Adder The first step on our way to adding binary numbers is to be able to add two bits. Let us call the least significant bit of the addition sum, and the most significant bit carry. Figure 2.2 presents a chip, called half-adder, designed to carry out this operation.
Full-Adder Now that we know how to add two bits, figure 2.3 presents a full-adder chip, designed to add three bits. Like the half-adder case, the full-adder chip produces two outputs: the least significant bit of the addition, and the carry bit.
Adder Memory and register chips represent integer numbers by n -bit patterns, n being 16, 32, 64, and so forth—depending on the computer platform. The chip whose job is to add such numbers is called a multi-bit adder, or simply adder. Figure 2.4 presents a 16-bit adder, noting that the same logic and specifications scale up as is to any n -bit adder.
Incrementer It is convenient to have a special-purpose chip dedicated to adding the constant 1 to a given number. Here is the specification of a 16-bit incrementer:
Figure 2.3 Full-adder, designed to add 3 bits.
Figure 2.4 16-bit adder. Addition of two n -bit binary numbers for any n is “more of the same.”
2.2.2 The Arithmetic Logic Unit (ALU)
The specifications of the adder chips presented so far were generic, meaning that they hold for any computer. In contrast, this section describes an ALU that will later become the centerpiece of a specific computer platform called Hack. At the same time, the principles underlying the design of our ALU are rather general. Further, our ALU architecture achieves a great deal of functionality using a minimal set of internal parts. In that respect, it provides a good example of an efficient and elegant logic design.
The Hack ALU computes a fixed set of functions out = f i ( x , y) where x and y are the chip’s two 16-bit inputs, out is the chip’s 16-bit output, and f i is an arithmetic or logical function selected from a fixed repertoire of eighteen possible functions. We instruct the ALU which function to compute by setting six input bits, called control bits, to selected binary values. The exact input-output specification is given in figure 2.5, using pseudo-code.
Note that each one of the six control bits instructs the ALU to carry out a certain elementary operation. Taken together, the combined effects of these operations cause the ALU to compute a variety of useful functions. Since the overall operation is driven by six control bits, the ALU can potentially compute 2 6 = 64 different functions. Eighteen of these functions are documented in figure 2.6.
We see that programming our ALU to compute a certain function f ( x , y) is done by setting the six control bits to the code of the desired function. From this point on, the internal ALU logic specified in figure 2.5 should cause the ALU to output the value f ( x , y) specified in figure 2.6. Of course, this does not happen miraculously, it’s the result of careful design.
For example, let us consider the twelfth row of figure 2.6, where
Similar Books
Dark Solace
Tara Fox Hall
A Cup of Murder
Cam Larson
Smart Girl
Rachel Hollis
Some Rain Must Fall
Michel Faber
Trouble In Bloom
Heather Webber
The Versace League
Shan
Pandora Gets Angry
Carolyn Hennesy
Vs Reality
Blake Northcott
Hogs #4:Snake Eaters
Jim DeFelice
More Than You Can Say
Paul Torday