The Elements of Computing Systems: Building a Modern Computer from First Principles by Noam Nisan, Shimon Schocken Read Free Book Online Page B
Authors: Noam Nisan, Shimon Schocken
the ALU is instructed to compute the function x-1. The zx and nx bits are 0, so the x input is neither zeroed nor negated. The zy and ny bits are 1, so the y input is first zeroed, and then negated bit-wise. Bit-wise negation of zero, (000 ...00) two , gives (111 ...11) two , the 2’s complement code of -1. Thus the ALU inputs end up being x and -1. Since the f-bit is 1, the selected operation is arithmetic addition, causing the ALU to calculate x + (-1). Finally, since the no bit is 0, the output is not negated but rather left as is. To conclude, the ALU ends up computing x-1, which was our goal.
Figure 2.5 The Arithmetic Logic Unit.
Figure 2.6 The ALU truth table. Taken together, the binary operations coded by the first six columns effect the function listed in the right column (we use the symbols !, &, and | to represent the operators Not, And, and Or, respectively, performed bit-wise). The complete ALU truth table consists of sixty-four rows, of which only the eighteen presented here are of interest.
Does the ALU logic described in figure 2.6 compute every one of the other seventeen functions listed in the figure’s right column? To verify that this is indeed the case, the reader can pick up some other rows in the table and prove their respective ALU operation. We note that some of these computations, beginning with the function f ( x , y ) = 1, are not trivial. We also note that there are some other useful functions computed by the ALU but not listed in the figure.
It may be instructive to describe the thought process that led to the design of this particular ALU. First, we made a list of all the primitive operations that we wanted our computer to be able to perform (right column in figure 2.6). Next, we used backward reasoning to figure out how x, y, and out can be manipulated in binary fashion in order to carry out the desired operations. These processing requirements, along with our objective to keep the ALU logic as simple as possible, have led to the design decision to use six control bits, each associated with a straightforward binary operation. The resulting ALU is simple and elegant. And in the hardware business, simplicity and elegance imply inexpensive and powerful computer systems.
2.3 Implementation
Our implementation guidelines are intentionally partial, since we want you to discover the actual chip architectures yourself. As usual, each chip can be implemented in more than one way; the simpler the implementation, the better.
Half-Adder An inspection of figure 2.2 reveals that the functions sum( a , b) and carry( a , b) happen to be identical to the standard Xor( a , b) and And( a , b) Boolean functions. Thus, the implementation of this adder is straightforward, using previously built gates.
Full-Adder A full adder chip can be implemented from two half adder chips and one additional simple gate. A direct implementation is also possible, without using half-adder chips.
Adder The addition of two signed numbers represented by the 2’s complement method as two n -bit buses can be done bit-wise, from right to left, in n steps. In step 0, the least significant pair of bits is added, and the carry bit is fed into the addition of the next significant pair of bits. The process continues until in step n –1 the most significant pair of bits is added. Note that each step involves the addition of three bits. Hence, an n -bit adder can be implemented by creating an array of n full-adder chips and propagating the carry bits up the significance ladder.
Incrementer An n -bit incrementer can be implemented trivially from an n -bit adder. ALU Note that our ALU was carefully planned to effect all the desired ALU operations logically, using simple Boolean operations. Therefore, the physical implementation of the ALU is reduced to implementing these simple Boolean operations, following their pseudo-code specifications. Your first step will likely be to create a logic circuit that
Figure 2.5 The Arithmetic Logic Unit.
Figure 2.6 The ALU truth table. Taken together, the binary operations coded by the first six columns effect the function listed in the right column (we use the symbols !, &, and | to represent the operators Not, And, and Or, respectively, performed bit-wise). The complete ALU truth table consists of sixty-four rows, of which only the eighteen presented here are of interest.
Does the ALU logic described in figure 2.6 compute every one of the other seventeen functions listed in the figure’s right column? To verify that this is indeed the case, the reader can pick up some other rows in the table and prove their respective ALU operation. We note that some of these computations, beginning with the function f ( x , y ) = 1, are not trivial. We also note that there are some other useful functions computed by the ALU but not listed in the figure.
It may be instructive to describe the thought process that led to the design of this particular ALU. First, we made a list of all the primitive operations that we wanted our computer to be able to perform (right column in figure 2.6). Next, we used backward reasoning to figure out how x, y, and out can be manipulated in binary fashion in order to carry out the desired operations. These processing requirements, along with our objective to keep the ALU logic as simple as possible, have led to the design decision to use six control bits, each associated with a straightforward binary operation. The resulting ALU is simple and elegant. And in the hardware business, simplicity and elegance imply inexpensive and powerful computer systems.
2.3 Implementation
Our implementation guidelines are intentionally partial, since we want you to discover the actual chip architectures yourself. As usual, each chip can be implemented in more than one way; the simpler the implementation, the better.
Half-Adder An inspection of figure 2.2 reveals that the functions sum( a , b) and carry( a , b) happen to be identical to the standard Xor( a , b) and And( a , b) Boolean functions. Thus, the implementation of this adder is straightforward, using previously built gates.
Full-Adder A full adder chip can be implemented from two half adder chips and one additional simple gate. A direct implementation is also possible, without using half-adder chips.
Adder The addition of two signed numbers represented by the 2’s complement method as two n -bit buses can be done bit-wise, from right to left, in n steps. In step 0, the least significant pair of bits is added, and the carry bit is fed into the addition of the next significant pair of bits. The process continues until in step n –1 the most significant pair of bits is added. Note that each step involves the addition of three bits. Hence, an n -bit adder can be implemented by creating an array of n full-adder chips and propagating the carry bits up the significance ladder.
Incrementer An n -bit incrementer can be implemented trivially from an n -bit adder. ALU Note that our ALU was carefully planned to effect all the desired ALU operations logically, using simple Boolean operations. Therefore, the physical implementation of the ALU is reduced to implementing these simple Boolean operations, following their pseudo-code specifications. Your first step will likely be to create a logic circuit that
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