The Elements of Computing Systems: Building a Modern Computer from First Principles (20 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
6.76Mb size Format: txt, pdf, ePub
Instruction Execution
The various fields of the instruction (i-, a-, c-, d-, and j-bits) are routed simultaneously to various parts of the architecture, where they cause different chips to do what they are supposed to do in order to execute either the
A
-instruction or the
C
-instruction, as mandated by the machine language specification. In particular, the a-bit determines whether the ALU will operate on the A register input or on the Memory input, the c-bits determine which function the ALU will compute, and the d-bits enable various locations to accept the ALU result.
The various fields of the instruction (i-, a-, c-, d-, and j-bits) are routed simultaneously to various parts of the architecture, where they cause different chips to do what they are supposed to do in order to execute either the
A
-instruction or the
C
-instruction, as mandated by the machine language specification. In particular, the a-bit determines whether the ALU will operate on the A register input or on the Memory input, the c-bits determine which function the ALU will compute, and the d-bits enable various locations to accept the ALU result.
Next Instruction Fetching
As a side effect of executing the current instruction, the CPU also determines the address of the next instruction and emits it via its pc output. The “driver” of this task is the
program counter
—an internal part of the CPU whose output is fed directly to the CPU’s pc output. This is precisely the PC chip built in chapter 3 (see figure 3.5).
As a side effect of executing the current instruction, the CPU also determines the address of the next instruction and emits it via its pc output. The “driver” of this task is the
program counter
—an internal part of the CPU whose output is fed directly to the CPU’s pc output. This is precisely the PC chip built in chapter 3 (see figure 3.5).
Most of the time, the programmer wants the computer to fetch and execute the next instruction in the program. Thus if
t
is the current time-unit, the default program counter operation should be PC(
t
) = PC(
t
- 1) + 1. When we want to effect a
goto n
operation, the machine language specification requires to first set the A register to n (via an
A
-instruction) and then issue a jump directive (coded by the j-bits of a subsequent
C
-instruction). Hence, our challenge is to come up with a hardware implementation of the following logic:
t
is the current time-unit, the default program counter operation should be PC(
t
) = PC(
t
- 1) + 1. When we want to effect a
goto n
operation, the machine language specification requires to first set the A register to n (via an
A
-instruction) and then issue a jump directive (coded by the j-bits of a subsequent
C
-instruction). Hence, our challenge is to come up with a hardware implementation of the following logic:
Conveniently, and actually by careful design, this jump control logic can be easily effected by the proposed CPU implementation. Recall that the PC chip interface (figure 3.5) has a load control bit that enables it to accept a new input value. Thus, to effect the desired jump control logic, we start by connecting the output of the A register to the input of the PC. The only remaining question is when to enable the PC to accept this value (rather than continuing its steadfast counting), namely, when does a jump need to occur. This is a function of two signals: (a) the j-bits of the current instruction, specifying on which condition we are supposed to jump, and (b) the ALU output status bits, indicating whether the condition is satisfied. If we have a jump, the PC should be loaded with A’s output. Otherwise, the PC should increment by 1.
Additionally, if we want the computer to restart the program’s execution, all we have to do is reset the program counter to 0. That’s why the proposed CPU implementation feeds the CPU’s reset input directly into the reset pin of the PC chip.
5.3.2 MemoryAccording to its specification, the Memory chip of the Hack platform is essentially a package of three lower-level chips: RAM16K, Screen, and Keyboard. At the same-time, users of the Memory chip must see a single logical address space, spanning from location 0 to 24576 (0x0000 to 0x6000—see figure 5.7). The implementation of the Memory chip should create this continuum effect. This can be done by the same technique used to combine small RAM units into larger ones, as we have done in chapter 3 (see figure 3.6 and the discussion of n-register memory that accompanies it).
5.3.3 ComputerOnce the CPU and the Memory chips have been implemented and tested, the construction of the overall computer is straightforward. Figure 5.10 depicts a possible implementation.
5.4 PerspectiveFollowing the general spirit of the book, the architecture of the Hack computer is rather minimal. Typical computer platforms have more registers, more data types, more powerful ALUs, and richer instruction sets. However, these differences are mainly quantitative. From a qualitative standpoint, Hack is quite similar to most digital computers, as they all follow the same conceptual paradigm: the von Neumann architecture.
Figure 5.10
Proposed implementation of the topmost Computer chip.
Proposed implementation of the topmost Computer chip.
In terms of function, computer systems can be classified into two categories:
general-purpose computers,
designed to easily switch from executing one program to another, and dedicated computers, usually embedded in other systems like cell phones, game consoles, digital cameras, weapon systems, factory equipment, and so on. For any particular application, a single program is burned into the dedicated computer’s ROM, and is the only one that can be executed (in game consoles, for example, the game software resides in an external cartridge that is simply a replaceable ROM module encased in some fancy package). Aside from this difference, general-purpose and dedicated computers share the same architectural ideas: stored programs, fetch-decode-execute logic, CPU, registers, program counter, and so on.
general-purpose computers,
designed to easily switch from executing one program to another, and dedicated computers, usually embedded in other systems like cell phones, game consoles, digital cameras, weapon systems, factory equipment, and so on. For any particular application, a single program is burned into the dedicated computer’s ROM, and is the only one that can be executed (in game consoles, for example, the game software resides in an external cartridge that is simply a replaceable ROM module encased in some fancy package). Aside from this difference, general-purpose and dedicated computers share the same architectural ideas: stored programs, fetch-decode-execute logic, CPU, registers, program counter, and so on.
Unlike Hack, most general-purpose computers use a single address space for storing both data and instructions. In such architectures, the instruction address as well as the optional data address specified by the instruction must be fed into the same destination: the single address input of the shared address space. Clearly, this cannot be done at the same time. The standard solution is to base the computer implementation on a two-cycle logic. During the fetch cycle, the instruction address is fed to the address input of the memory, causing it to immediately emit the current instruction, which is then stored in an instruction register. In the subsequent execute cycle, the instruction is decoded, and the optional data address inferred from it is fed to the memory’s address input, allowing the instruction to manipulate the selected memory location. In contrast, the Hack architecture is unique in that it partitions the address space into two separate parts, allowing a single-cycle fetch-execute logic. The price of this simpler hardware design is that programs cannot be changed dynamically.
In terms of I/O, the Hack keyboard and screen are rather spartan. General-purpose computers are typically connected to multiple I/O devices like printers, disks, network connections, and so on. Also, typical screens are obviously much more powerful than the Hack screen, featuring more pixels, many brightness levels in each pixel, and colors. Still, the basic principle that each pixel is controlled by a memory-resident binary value is maintained: instead of a single bit controlling the pixel’s black or white color, several bits are devoted to control the level of brightness of each of the three primary colors that, together, produce the pixel’s ultimate color. Likewise, the memory mapping of the Hack screen is simplistic. Instead of mapping pixels directly into bits of memory, most modern computers allow the CPU to send high-level graphic instructions to a graphics card that controls the screen. This way, the CPU is relieved from the tedium of drawing figures like circles and polygons directly—the graphics card takes care of this task using its own embedded chip-set.
Finally, it should be stressed that most of the effort and creativity in designing computer hardware is invested in achieving better performance. Thus, hardware architecture courses and textbooks typically evolve around such issues as implementing memory hierarchies (cache), better access to I/O devices, pipelining, parallelism, instruction prefetching, and other optimization techniques that were sidestepped in this chapter.
Historically, attempts to enhance the processor’s performance have led to two main schools of hardware design. Advocates of the Complex Instruction Set Computing (CISC) approach argue for achieving better performance by providing rich and elaborate instruction sets. Conversely, the Reduced Instruction Set Computing (RISC) camp uses simpler instruction sets in order to promote as fast a hardware implementation as possible. The Hack computer does not enter this debate, featuring neither a strong instruction set nor special hardware acceleration techniques.
5.5 ProjectObjective
Build the Hack computer platform, culminating in the topmost Computer chip.
Build the Hack computer platform, culminating in the topmost Computer chip.
Resources
The only tools that you need for completing this project are the hardware simulator supplied with the book and the test scripts described here. The computer platform should be implemented in the HDL language specified in appendix A.
The only tools that you need for completing this project are the hardware simulator supplied with the book and the test scripts described here. The computer platform should be implemented in the HDL language specified in appendix A.
Contract
The computer platform built in this project should be capable of executing programs written in the Hack machine language, specified in chapter 4. Demonstrate this capability by having your Computer chip run the three programs given here.
The computer platform built in this project should be capable of executing programs written in the Hack machine language, specified in chapter 4. Demonstrate this capability by having your Computer chip run the three programs given here.
Component Testing
We supply test scripts and compare files for unit-testing the Memory and CPU chips in isolation. It’s important to complete the testing of these chips before building and testing the overall Computer chip.
We supply test scripts and compare files for unit-testing the Memory and CPU chips in isolation. It’s important to complete the testing of these chips before building and testing the overall Computer chip.
Test Programs
A natural way to test the overall Computer chip implementation is to have it execute some sample programs written in the Hack machine language. In order to run such a test, one can write a test script that loads the Computer chip into the hardware simulator, loads a program from an external text file into its ROM chip, and then runs the clock enough cycles to execute the program. We supply all the files necessary to run three such tests, as follows:
A natural way to test the overall Computer chip implementation is to have it execute some sample programs written in the Hack machine language. In order to run such a test, one can write a test script that loads the Computer chip into the hardware simulator, loads a program from an external text file into its ROM chip, and then runs the clock enough cycles to execute the program. We supply all the files necessary to run three such tests, as follows:
1. Add.hack: Adds the two constants 2 and 3 and writes the result in RAM[0].
2. Max.hack: Computes the maximum of RAM[0] and RAM[1] and writes the result in RAM[2].
3. Rect.hack: Draws a rectangle of width 16 pixels and length RAM[0] at the top left of the screen.
Before testing your Computer chip on any one of the above programs, read the test script associated with the program and be sure to understand the instructions given to the simulator. Appendix B may be a useful reference here.
Steps
Build the computer in the following order:
Build the computer in the following order:
■
Memory:
Composed from three chips: RAM16K, Screen, and Keyboard. The Screen and the Keyboard are available as built-in chips and there is no need to build them. Although the RAM16K chip was built in the project in chapter 3, we recommend using its built-in version, as it provides a debugging-friendly GUI.
Memory:
Composed from three chips: RAM16K, Screen, and Keyboard. The Screen and the Keyboard are available as built-in chips and there is no need to build them. Although the RAM16K chip was built in the project in chapter 3, we recommend using its built-in version, as it provides a debugging-friendly GUI.
■
CPU:
Can be composed according to the proposed implementation given in figure 5.9, using the ALU and register chips built in chapters 2 and 3, respectively. We recommend using the built-in versions of these chips, in particular ARegister and DRegister. These chips have exactly the same functionality of the Register chip specified in chapter 3, plus GUI side effects.
CPU:
Can be composed according to the proposed implementation given in figure 5.9, using the ALU and register chips built in chapters 2 and 3, respectively. We recommend using the built-in versions of these chips, in particular ARegister and DRegister. These chips have exactly the same functionality of the Register chip specified in chapter 3, plus GUI side effects.
In the course of implementing the CPU, it is allowed (but not necessarily recommended) to specify and build some internal chips of your own. This is up to you. If you choose to create new chips not mentioned in the book, be sure to document and test them carefully before you plug them into the architecture.
■
Instruction Memory:
Use the built-in ROM32K chip.
Instruction Memory:
Use the built-in ROM32K chip.
■
Computer:
The topmost Computer chip can be composed from the chips mentioned earlier, using figure 5.10 as a blueprint.
Computer:
The topmost Computer chip can be composed from the chips mentioned earlier, using figure 5.10 as a blueprint.
The Hardware Simulator
As in the projects in chapters 1-3, all the chips in this project (including the topmost Computer chip) can be implemented and tested using the hardware simulator supplied with the book. Figure 5.11 is a screen shot of testing the Rect.hack program on a Computer chip implementation.
As in the projects in chapters 1-3, all the chips in this project (including the topmost Computer chip) can be implemented and tested using the hardware simulator supplied with the book. Figure 5.11 is a screen shot of testing the Rect.hack program on a Computer chip implementation.
Other books
Celebrate by Kim Dare
Angels in the Architecture by Sue Fitzmaurice
Riding the River by Jeanne Harrell
The Childhood of Jesus by J. M. Coetzee
The Trials of Phillis Wheatley by Henry Louis Gates
Red Widow (Vivian Xu, Book 1) by Nathan Wilson
Diamonds Fall by Rebecca Gibson
The Prime-Time Crime by Franklin W. Dixon
W. E. B. Griffin - Presidential Agent 07 by Covert Warriors
Five Women by Rona Jaffe
