The Elements of Computing Systems: Building a Modern Computer from First Principles (15 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
12.65Mb size Format: txt, pdf, ePub
In addition, the hardworking A register is also used to facilitate direct access to the instruction memory. Similar to the memory access convention, Hack jump instructions do not specify a particular address. Instead, the convention is that any jump operation always effects a jump to the instruction located in the memory word addressed by A. Thus, if we want to effect the operation goto 35, we use one instruction to set A to 35, and a second instruction to code a goto command, without specifying an address. This sequence causes the computer to fetch the instruction located in InstructionMemory[35] in the next clock cycle.
Example
Since the Hack language is self-explanatory, we start with an example. The only non-obvious command in the language is
@value
, where value is either a number or a symbol representing a number. This command simply stores the specified value in the A register. For example, if sum refers to memory location 17, then both @17 and @sum will have the same effect: A←17.
Since the Hack language is self-explanatory, we start with an example. The only non-obvious command in the language is
@value
, where value is either a number or a symbol representing a number. This command simply stores the specified value in the A register. For example, if sum refers to memory location 17, then both @17 and @sum will have the same effect: A←17.
And now to the example: Suppose we want to add the integers 1 to 100, using repetitive addition. Figure 4.2 gives a C language solution and a possible compilation into the Hack language.
Although the Hack syntax is more accessible than that of most machine languages, it may still look obscure to readers who are not familiar with low-level programming. In particular, note that every operation involving a memory location requires two Hack commands: One for selecting the address on which we want to operate, and one for specifying the desired operation. Indeed, the Hack language consists of two generic instructions: an address instruction, also called
A
-instruction, and a compute instruction, also called
C
-instruction. Each instruction has a binary representation, a symbolic representation, and an effect on the computer, as we now specify.
4.2.2 TheA
-instruction, and a compute instruction, also called
C
-instruction. Each instruction has a binary representation, a symbolic representation, and an effect on the computer, as we now specify.
A
-Instruction
The
A
-instruction is used to set the A register to a 15-bit value:
A
-instruction is used to set the A register to a 15-bit value:
This instruction causes the computer to store the specified value in the A register. For example, the instruction @ 5, which is equivalent to 0000000000000101, causes the computer to store the binary representation of 5 in the A register.
The
A
-instruction is used for three different purposes. First, it provides the only way to enter a constant into the computer under program control. Second, it sets the stage for a subsequent
C
-instruction designed to manipulate a certain data memory location, by first setting A to the address of that location. Third, it sets the stage for a subsequent
C
-instruction that specifies a jump, by first loading the address of the jump destination to the A register. These uses are demonstrated in figure 4.2.
A
-instruction is used for three different purposes. First, it provides the only way to enter a constant into the computer under program control. Second, it sets the stage for a subsequent
C
-instruction designed to manipulate a certain data memory location, by first setting A to the address of that location. Third, it sets the stage for a subsequent
C
-instruction that specifies a jump, by first loading the address of the jump destination to the A register. These uses are demonstrated in figure 4.2.
Figure 4.2
C and assembly versions of the same program. The infinite loop at the program’s end is our standard way to “terminate” the execution of Hack programs.
C and assembly versions of the same program. The infinite loop at the program’s end is our standard way to “terminate” the execution of Hack programs.
C
-Instruction
The
C
-instruction is the programming workhorse of the Hack platform—the instruction that gets almost everything done. The instruction code is a specification that answers three questions: (a) what to compute, (b) where to store the computed value, and (c) what to do next? Along with the
A
-instruction, these specifications determine all the possible operations of the computer.
C
-instruction is the programming workhorse of the Hack platform—the instruction that gets almost everything done. The instruction code is a specification that answers three questions: (a) what to compute, (b) where to store the computed value, and (c) what to do next? Along with the
A
-instruction, these specifications determine all the possible operations of the computer.
The leftmost bit is the
C
-instruction code, which is 1. The next two bits are not used. The remaining bits form three fields that correspond to the three parts of the instruction’s symbolic representation. The overall semantics of the symbolic instruction
dest
= comp;jump is as follows. The comp field instructs the ALU what to compute. The dest field instructs where to store the computed value (ALU output). The jump field specifies a jump condition, namely, which command to fetch and execute next. We now describe the format and semantics of each of the three fields.
C
-instruction code, which is 1. The next two bits are not used. The remaining bits form three fields that correspond to the three parts of the instruction’s symbolic representation. The overall semantics of the symbolic instruction
dest
= comp;jump is as follows. The comp field instructs the ALU what to compute. The dest field instructs where to store the computed value (ALU output). The jump field specifies a jump condition, namely, which command to fetch and execute next. We now describe the format and semantics of each of the three fields.
The Computation Specification
The Hack ALU is designed to compute a fixed set of functions on the D, A, and M registers (where M stands for Memory[A]). The computed function is specified by the a-bit and the six c-bits comprising the instruction’s comp field. This 7-bit pattern can potentially code 128 different functions, of which only the 28 listed in figure 4.3 are documented in the language specification.
The Hack ALU is designed to compute a fixed set of functions on the D, A, and M registers (where M stands for Memory[A]). The computed function is specified by the a-bit and the six c-bits comprising the instruction’s comp field. This 7-bit pattern can potentially code 128 different functions, of which only the 28 listed in figure 4.3 are documented in the language specification.
Recall that the format of the
C
-instruction is 111a cccc ccdd djjj. Suppose we want to have the ALU compute D-1, the current value of the D register minus 1. According to figure 4.3, this can be done by issuing the instruction 111
0 0011 10
00 0000 (the 7-bit operation code is in bold). To compute the value of D|M, we issue the instruction 111
1 0101 01
00 0000. To compute the constant-1, we issue the instruction 111
0
1110
10
00 0000, and so on.
C
-instruction is 111a cccc ccdd djjj. Suppose we want to have the ALU compute D-1, the current value of the D register minus 1. According to figure 4.3, this can be done by issuing the instruction 111
0 0011 10
00 0000 (the 7-bit operation code is in bold). To compute the value of D|M, we issue the instruction 111
1 0101 01
00 0000. To compute the constant-1, we issue the instruction 111
0
1110
10
00 0000, and so on.
The Destination Specification
The value computed by the comp part of the
C
-instruction can be stored in several destinations, as specified by the instruction’s 3-bit dest part (see figure 4.4). The first and second d-bits code whether to store the computed value in the A register and in the D register, respectively. The third d-bit codes whether to store the computed value in M (i.e., in Memory[A]). One, more than one, or none of these bits may be asserted.
The value computed by the comp part of the
C
-instruction can be stored in several destinations, as specified by the instruction’s 3-bit dest part (see figure 4.4). The first and second d-bits code whether to store the computed value in the A register and in the D register, respectively. The third d-bit codes whether to store the computed value in M (i.e., in Memory[A]). One, more than one, or none of these bits may be asserted.
Figure 4.3
The compute field of the
C
-instruction. D and A are names of registers. M refers to the memory location addressed by A, namely, to Memory[A]. The symbols + and - denote 16-bit 2’s complement addition and subtraction, while !, |, and & denote the 16-bit bit-wise Boolean operators Not, Or, and And, respectively. Note the similarity between this instruction set and the ALU specification given in figure 2.6.
The compute field of the
C
-instruction. D and A are names of registers. M refers to the memory location addressed by A, namely, to Memory[A]. The symbols + and - denote 16-bit 2’s complement addition and subtraction, while !, |, and & denote the 16-bit bit-wise Boolean operators Not, Or, and And, respectively. Note the similarity between this instruction set and the ALU specification given in figure 2.6.
Recall that the format of the
C
-instruction is 111a cccc ccdd djjj. Suppose we want the computer to increment the value of Memory[7] by 1 and to also store the result in the D register. According to figures 4.3 and 4.4, this can be accomplished by the following instructions:
The first instruction causes the computer to select the memory register whose address is 7 (the so-called M register). The second instruction computes the value of M + 1 and stores the result in both M and D.
C
-instruction is 111a cccc ccdd djjj. Suppose we want the computer to increment the value of Memory[7] by 1 and to also store the result in the D register. According to figures 4.3 and 4.4, this can be accomplished by the following instructions:
Figure 4.4
The dest field of the
C
-instruction.
The dest field of the
C
-instruction.
The Jump Specification
The
jump
field of the
C
-instruction tells the computer what to do next. There are two possibilities: The computer should either fetch and execute the next instruction in the program, which is the default, or it should fetch and execute an instruction located elsewhere in the program. In the latter case, we assume that the A register has been previously set to the address to which we have to jump.
The
jump
field of the
C
-instruction tells the computer what to do next. There are two possibilities: The computer should either fetch and execute the next instruction in the program, which is the default, or it should fetch and execute an instruction located elsewhere in the program. In the latter case, we assume that the A register has been previously set to the address to which we have to jump.
Whether or not a jump should actually materialize depends on the three j-bits of the jump field and on the ALU output value (computed according to the comp field). The first j-bit specifies whether to jump in case this value is negative, the second j-bit in case the value is zero, and the third j-bit in case it is positive. This gives eight possible jump conditions, shown in figure 4.5.
The following example illustrates the jump commands in action:
The last instruction (0; JMP) effects an unconditional jump. Since the
C
-instruction syntax requires that we always effect some computation, we instruct the ALU to compute 0 (an arbitrary choice), which is ignored.
Figure 4.5
The
jump
field of the
C
-instruction.
Out
refers to the ALU output (resulting from the instruction’s comp part), and jump implies “continue execution with the instruction addressed by the A register.”
The
jump
field of the
C
-instruction.
Out
refers to the ALU output (resulting from the instruction’s comp part), and jump implies “continue execution with the instruction addressed by the A register.”
C
-instruction syntax requires that we always effect some computation, we instruct the ALU to compute 0 (an arbitrary choice), which is ignored.
Other books
The Rest of Us Just Live Here by Patrick Ness
Falling In by Alexa Riley
Jude Stephens by Touch of a VAmpire
Falling For My Husband (British Billionaires) by Ann, Pamela
Influence: Science and Practice by Robert B. Cialdini
0.5 Meeting Monday by Robert Michael
The Organist Wore Pumps (The Liturgical Mysteries) by Schweizer, Mark
Jump Start by Susannah McFarlane
Kaputt by Curzio Malaparte
A Field Guide for Heartbreakers by Kristen Tracy
