AMAZON multi-meters discounts AMAZON oscilloscope discounts
You are ready to tackle a really substantial project to round out your study of hardwired design. Nothing will sharpen your design skills more than wading through the design of a complex project from start to finish. Thus far, you have studied pieces of the design process; in the next three sections we will help you forge your knowledge into an integrated and workable design tool. What project should we choose? Such an undertaking should be detailed yet elegant, large yet not too large. Let's design a computer! Our aim is to design an entire operational computer system, taking no shortcuts, leaving nothing out. Most computers, even the smallest microcomputers, are highly complex structures-too complex to be a suitable teaching illustration at the MSI and LSI level of design. Instead, we choose the first minicomputer, the Digital Equipment Corporation PDP-8.
Above: Digital's PDP-8
The PDP-8 has had a successful history. More than 100,000 units have been installed, many of which are still in use. The PDP-8 also has an extensive library of software and is a good machine for illustrating device interfacing.
The great advantage of the PDP-8 for our purpose is that it has a simple structure with only eight basic instructions. It exists in several models; each executes the same basic set of instructions, but they differ in minor ways. We will use the PDP-8I as the basis for our exercise. We will develop our design from first principles and make no reference to the Digital Equipment Corporation's design. The result will be functionally equivalent to the PDP-8I-for example, it will run PDP-8I software-but we will use top-down design techniques. The only detailed information we need about the PDP-8I is a description of the action of each instruction. We shall call our design the LD20. t The statement of the problem is brief: build a computer that will execute the PDP-8I instruction set.
PDP-8I SPECIFICATIONS
The first step is the obvious one of studying the PDP-8I to see what we must emulate. The major characteristics of the PDP-8I are:
(a) A 12-bit word size. This is quite small and will cause memory-addressing limitations. If a memory word is used to hold an address, it can refer to only 4096 (212) different locations. Therefore, the standard PDP-8 is limited to 4096 words of addressable memory.
(b) A single accumulator. Several instructions refer to an accumulator (AC), used to store intermediate results for later manipulation. Having only one accessible register forces a programmer to use care in saving and restoring vital data in the AC, for example upon subroutine entry and exit. Many computers have several registers, which can speed the execution of programs but which expose the programmer to subtle bugs if the data in all registers is not properly handled. In many applications the single AC is a blessing!
(c) A 3-bit operation code. Each instruction occupies a 12-bit word, of which 3 bits are devoted to the operation code. This provides eight basic commands-an adequate but hardly abundant number. Only 9 bits remain in the instruction for such purposes as addressing memory, whereas the 4096 word memory requires a full 12-bit address.
(d) Paging. Addressing limitations in minicomputers and microcomputers have forced computer architects to find a number of ingenious solutions. The PDP-8's method is based on memory pages of 128 (27) words. The 4096 word address space is divided into 32 pages, and each memory-referencing instruction has 7 bits to address a word within a page. The missing 5 bits of the address are not a part of the instruction, but are derived implicitly from the context. Without some trick of this sort there would be no way to pack a 3-bit command and an address into a 12-bit word. Maneuvers such as this are common features of minicomputers. The paging mechanism of the PDP-8 is perhaps the simplest technique and serves as a foundation for studying more complicated schemes used in other computers.
Throughout this design exercise, we will use the octal numbering system to specify particular values of the PDP-8's instructions, addresses, and so on.
The LD20 design developed in this guide is used in instructional laboratories for digital design. The equipment to support this design and the LD30 microprogrammed version is produced by Logic Design, Inc. A laboratory manual for the LD20 and LD30 is available. See Readings and Sources at the end of this section.
Any such numbers not in octal will have an explicitly designated base. Thus 305 is 305 octal, 10112 is 1011 binary, and 4210 is 42 decimal.
PDP-8 Memory Addressing In many memory addressing schemes for small instructions, the location of the current instruction is used to specify part of the operand address. For example, assume a program with five instructions stored sequentially, starting at location 300. Call these instructions CMO (command 0) through CM4 (command 4). A memory map of this program would be:
Location | Contents
300 CMO
301 CMl
302 CM2
303 CM3
304 CM4
If instruction CM3 is being executed, we know that it is located at address 303, since that is where we placed it. Instruction CM3 can employ a subset of the 12 bits in its word to reference data located close to location 303. In the PDP-8, "close to" means in the same page.
The PDP-8 splits 4096 words of memory into 32 pages of 128 words each, as shown in Fig. 1. Instruction CM3 is in page 1; 7 bits are sufficient for that instruction to access any word in that page.
Fig. 1 Page structure of the memory of the PDP-8.
We now have a mechanism such that an instruction needs only 7 bits to access a memory cell in one particular page. Let us call these 7 bits the page offset, and let the page offset occupy the rightmost 7 bits of a PDP-8 instruction:
Suppose location 301 contains the 12 bits 001 XYl 000 1012 , (for the moment we will ignore the 2 bits X and Y). The operation code is 0012 , which means an addition of the AC and the contents of a memory location. Which location? The 7 page-offset bits are 1 000 1012 = 1058 , The instruction is to add the contents of location 105 in this page (the page containing the add instruction) to the accumulator. We know that the instruction is at location 301, and since the instruction is in page 1, the page offset is referring to page 1. Thus we will get the contents of word 105 in page 1 and add it to the AC. What if instructions in different pages require the same data? It would be nice if some common page could be accessed by instructions in any page. In the PDP-8, page 0 has this function. We have two precious unused bits in the instruction, and we need one of them to tell if we want word 105 in the current page (page 1 in our example) or word 105 in the common page (page 0). In the PDP-8, the Y bit is used for this page selection; we call it the page hit.
If the page bit is 1, the page address of the current instruction is concatenated with the 7-bit offset in the instruction to form a full 12-bit address, which is sufficient to identify any word of the 4096-word memory. If the page bit is 0, the reference will be to a word in page 0 of the memory.
If we execute an instruction at location 301 that contains 001 011 000 1012 , we will add the contents of location 105 in page 1 to the AC. Location 105 in page 1 is memory location 305
p263a
If location 301 contains 001 001 000 1012 , the instruction would mean to add the contents of location 105 in page 0 to the AC. Location 105 in page 0 is memory location 105.
Indirect addressing. We have shown how the page bit and the page offset combine to yield an address either in page 0 or in the current instruction page.
What happens if a command in page 2 needs to access a location in page 7? We must use all 12 bits of a word as address bits. We can do this if the word accessed by an instruction is treated not as an operand but as the address of an operand. This extra step is called indirect addressing. The PDP-8 uses the remaining instruction bit X as the indirect hit to specify indirect addressing. The complete format of a memory referencing instruction is:
p263b
In the previous examples, the contents of locations 305 or 105 (for page bits 1 or 0) were treated as 12-bit data words. If the indirect bit is on, these contents are treated as 12-bit addresses of data. We require one extra memory cycle to access this final indirectly addressed data location.
Indirect addressing is a powerful concept since it provides a way to specify arbitrary 12-bit addresses. Into some memory word IND that is close to our instruction or in page 0, we load the address of the final location that we wish to access. We can then access the location by indirectly addressing it through IND. It is useful to have a shorthand for the final memory location referenced in an instruction after all applicable paging and indirect addressing are invoked.
We call this final location the effective address, EA. The contents of location EA is called the contents of the effective address, CA. (CA is sometimes called the effective operand.) Using EA and CA, we can compactly describe the memory references of any PDP-8 instruction.
Examples of memory addressing. Here are some examples of referencing memory using PDP-8 instructions. The addresses will have 12 bits, since the PDP-8 has 4096 words of memory. We refer to the contents of an addressed memory location by enclosing the address in parentheses: If location 0301 contains 0305, then (0301) = 0305. Note that (EA) = CA.
Now assume that the following memory locations have been loaded with the data shown:
(0301) = 1305
(0302) = 1105
(0303) = 1705
(0304) = 1505
(0305) = 1234
(0105) = 4321
(1234) = 5567
(4321) = 7765
(a) What are the EA and the CA for the instruction located at 0301?
This instruction would add the quantity 1234 to the contents of the AC. (b) What are the EA and the CA for the instruction located at 0302?
p265a
This instruction would add the quantity 4321 to the contents of the AC. (c) What are the EA and the CA for the instruction located at 0303?
p265b
This instruction would add the quantity 5567 to the contents of the AC. (d) What are the EA and the CA for the instruction located at 0304?
p265c
This instruction would add the quantity 7765 to the contents of the AC. Auto indexing. The PDP-8 has a feature called auto indexing that provides some flexibility in addressing. Most large computers have index registers to facilitate access to arrays of data. Unfortunately, specifying an index register takes 1 or more bits of the instruction and we have no bits left. The PDP-8's auto indexing is a primitive way to index without using bits in the instruction.
An auto index register is a word in the memory that will be automatically incremented every time it is used as the source of an indirect address. The word is incremented before it is used as an address. Repeated use of the same auto index register will sequence the effective address EA throughout the full address space of the memory. There are 8 auto index registers in the PDP-8's main memory, locations 109 through 17g • When not performing auto indexing, these locations behave like normal memory words.
Here are some examples of auto indexing. Assume that the following locations have the contents shown:
(0013) = 4102
(4102) = 1111
(4103) = 2000
(a) Instruction: 1013 = 001 00 0 001 0112
Command = 001, = TAD II
Indirect bit = 0
Page bit = 0
EA = 0013
CA = (0013) = 4102
Although location 0013 is the address, there is no auto indexing because the indirect bit is O. This instruction adds the quantity 4102 to the contents of the AC.
(b) Instruction: 1413 = 001 10 0 001 0112
Command = 001, = TAD II
Indirect bit = 1
Page bit = 0
The initial address is 0013. This is an auto index location used as an indirect address. The auto indexing feature causes
Then
(0013) (+) 1 ~ (0013), or
4102 (+) 1 ~ (0013)
EA = (0013) = 4103
CA = (4103) = 2000
The effect of executing this instruction is to increment the contents of location 0013 by 1, and to add the quantity 2000 to the contents of the AC. PDP-81 Instructions
Its instruction set characterizes a computer, and therefore we must carefully study the PDP-81's instructions. The effective address EA and contents of the effective address CA notations allow a compact description of the memory referencing instructions.
AND (Twelve-bit logical AND). Operation code 0002 = 08 , AC·CA ~AC
This is a bit-by-bit AND of the AC with the effective address contents. For example,
AC = 001 101 111 0002
CA = 110 111 101 100 2
AC·CA = 000 101 101 0002
The value of AC·CA replaces the old contents of the AC.
TAD (Two's-complement add). Operation code 0012 18 • AC(+)CA~AC
The addition is performed in the two's-complement mode; that is, the instruction implies that the numbers are 12-bit signed quantities represented in the two's complement notation. If an arithmetic overflow occurs, the CPU toggles (complements) a special flag called the link bit (LINK).
ISZ (Increment and skip if 0). Operation code 0102 = 28 • CA (+) 1 ~ (EA); then, if CA (+) 1 = 0, skip the next instruction; otherwise execute the next instruction.
This instruction is useful in controlling loop execution.
DCA (Deposit and clear AC). Operation code 0112 38 • AC ~ (EA); then 0 ~ AC
The contents of the AC goes into the specified memory location, then the AC is set to O.
JMP (Jump). Operation code 1012 = 58.
Jump to location with address EA for the next instruction.
JMS (Jump to subroutine). Operation code 1002 = 48 •
Store the address of the word following the JMS instruction (i.e., the return location) in the memory word with address EA. Then jump to the location with address EA (+) 1 for the next instruction.
The return location is the word after the JMS instruction. This instruction stores the return address in the first word of the subroutine and then jumps to the second word, which must contain the starting instruction for the subroutine.
The normal entry to a subroutine X is thus with a JMS X, which saves the return address in location X. The normal exit from the subroutine is with a JMP *X (indirect jump through location X).
OP (Operate). Operation code 1112 = 78 •
This is by far the most complex command in the PDP-So It does not reference memory, so the address field bits are available for other purposes. The Operate instruction permits the following basic actions:
Clear accumulator: O~AC
Clear link bit: o ~ LINK
Complement accumulator: AC ~ AC
Complement link bit: LINK ~ LINK
Increment accumulator: AC (+) 1 ~ AC
Rotate the concatenated accumulator and link bit right or left, 1 or 2 bit positions.
OR console switches with AC: SR + AC ~ AC
Skip on various conditions of the accumulator or link bit.
Halt the computer.
Each of these operations is controlled by 1 or more bits in the address field of the instruction. These are sometimes called micro-coded instructions or micro-instructions. The programmer may invoke combinations of these micro-instructions within one Operate instruction. There is a huge number of possible combinations; about 20 of these are useful to the programmer. These combinations of microinstructions ease the pinch of having only eight basic instructions in the PDP-8.
The operation code 1112 occupies bits 0 through 2, as usual. Instruction bits 3 through 11 have individual functions. The Operate instruction on the PDP 81 is split into two groups, group 1 (G 1) and group 2 (G2). Bit 3 specifies the group: in group 1, bit 3 = 0; in group 2, bit 3 = 1,
The format for group 1 is:
p268a
The meaning of the microcode bits in G1 is:
p268b
The format for group 2 is:
p269a
The meaning of the microcode bits in G2 is:
Bit | Mnemonic | Name
4 CLA Clear accumulator
5 SMA Skip on minus accumulator
6 SZA Skip on zero accumulator
7 SNL Skip on nonzero link
8 (specifies sense of skips; see discussion)
9 OSR OR switch register into accumulator
10 HLT Halt the computer
(In group 2 micro-operations, bit 11 is O. On the PDP-8I, the condition of bit 11 is irrelevant, but some other models of the PDP-8 computer have another set of microinstructions, group 3, identified by bits 3 and 11, both of which are set to 1.) To find the exact result of combining microinstructions, we must define the sequence in which the operations of each group occur. The PDP-8 describes the sequence in terms of priorities. There are four priority levels, 1 through 4: priority 1 operations occur before priority 2, and so on. The priority sequences of the micro-operations of Gland G2 are
Priority Group 1 Group 2
1 CLA CLL Skips
2 CMA CML CLA
3 IAC OSR HLT
4 Rotates
The group 2 "skip" microinstructions require further explanation. There are three conditions for skipping: SMA, SZA, and SNL. Bit 8 determines the skip mode. The operations are as follows: If bit 8 is 0: a skip occurs if any of the chosen conditions is satisfied; otherwise, no skip occurs.
If bit 8 is 1: no skip occurs if any of the chosen conditions is satisfied; otherwise, a skip occurs.
IOT (input-output transfer). The operation code is 1102 = 68, The PDP 8 has a primitive but adequate facility for the input and output of data. We will discuss the IOT instruction more thoroughly later; but now we will note how data enters and leaves the computer. Outgoing data (from the PDP-8 to the external world) comes from the AC. Incoming data reaches the AC by being ORed with the existing contents of the AC. There is a programmable facility for clearing the AC prior to accepting incoming data. Thus the basic input operations are:
0 --> AC (optional)
Input. Data + AC --> AC
The IOT instruction also permits the programmer to enable and disable the PDP-8's interrupt system. These IOT subcommands are ION (Interrupt System On) and IOP (Interrupt System Oft), and have instruction bit patterns 60018 and 60028, respectively. The presence of interrupt commands alerts us to the need to investigate the interrupt mechanism.
Interrupts. The PDP-8 specification requires that the machine be able to sense the presence of an external interrupt request. This request originates in some peripheral device and means that the device wishes to report an event of interest to the computer program. Any number of devices can request interrupt processing through this one external interrupt request line. When the PDP-8's interrupt system is activated, the computer monitors the interrupt request signal to see if any device needs servicing. If so, then at an appropriate time in the normal instruction processing cycle, the PDP-8 will force an automatic subroutine jump (JMS) to a fixed memory location (cell 0000). It is the programmer's responsibility to see that a valid subprogram for processing interrupts begins at location 0000. This subroutine is responsible for reading data from the peripheral device, writing data, or perhaps placing control information into the device. The characteristics of the device generating the interrupt determine what the interrupt subprogram must do. Therefore, the interrupt subprogram must determine which device is responsible for the interrupt and then perform actions tailored to that device needs servicing the interrupt, the subprogram will make a normal subroutine return through cell 0000 and processing of regular instructions will resume.
Interrupt requests originate from external devices running at their own pace, and may interrupt the program at any time. This is both a blessing and a curse to the programmer. Interrupt requests can occur whenever a peripheral device decides it needs service from the main computer. This is a potent programming tool, since the computer program need not waste time continually checking its peripheral devices to see if one needs service.
Interrupts are powerful; they are also tricky. The difficulty arises because interrupt requests originate from external devices and are therefore not reproducible.
An interrupt may occur when the resident computer program is not prepared to handle it. For instance, suppose that the programmer has not established an interrupt service routine beginning at memory location 0000. Then the program will not run correctly if the computer recognizes an interrupt and jumps to location 0000. Even if the interrupt service program is present, it may not properly treat all the interrupt requests that may arise. These problems are difficult to diagnose, since the debugger of the program cannot reproduce the exact sequence of instructions that led to the difficulty. Interrupt programming requires much more foresight and care than conventional programming.
To allow more control over this difficult programming task, computers with interrupts always allow the programmer to enable (turn on) and disable (turn off) the computer's interrupt detection apparatus. The programmer may select those times when interrupt requests may result in the interruption of the program.
Some computers permit the handling of several types of interrupts, each type having its own interrupt jump location. We will not pursue this subject, because our focus is on the PDP-S's interrupt capabilities.
The PDP-S programmer may enable or disable the recognition of interrupts by using the ION (Interrupt System On) and IOF (Interrupt System Off) sub commands of the IOT instruction. The PDP-S's hardware will automatically disable the interrupt system whenever an interrupt causes a jump to location 0000. This action is needed to give the programmer's interrupt service routine enough time to react to one interrupt without the danger of another interrupt occurring in the middle of the processing of the first interrupt. It is the programmer's responsibility to enable the interrupt system again at the proper time, to permit the detection of further interrupts. This gives rise to a subtle problem. The interrupt subroutine will normally leave the interrupt system disabled until it is time to return to the main (interrupted) program. At this time the interrupt subprogram must enable the interrupt system and return. The last two instructions of the subprogram are:
ION
JMP*O
(Turn on interrupt system)
(Indirect jump to point of interruption)
We must make sure that we can execute the return jump to get back to the main program. Consider what would happen if an interrupt request is pending at the time the ION command is executed. The ION would reenable the interrupt system and the computer would immediately jump again to location 0000 without executing the jump instruction after the ION. The interrupt-forced JMS 0 causes cell 0000 to receive the address of the point of interruption-the address following the ION in this example. This act destroys the old return address in location 0000 which the unexecuted JMP *0 instruction wanted to use. The PDP-S's solution to this dilemma is to inhibit the recognition of interrupt requests for one instruction following an ION command, thus allowing the program the time to execute the crucial JMP *0 to return to the interrupted program before the computer recognizes any additional interrupt requests.
Interrupts are a complex feature of computers, and they place a heavy responsibility on the programmer. Whether or not the programmer does the job correctly, the computer must faithfully perform its assigned duty of detecting interrupt requests and forcing subroutine jumps to location 0000 whenever the interrupt system is enabled.
THE ARCHITECTURE OF THE LD20
We will now choose the main building blocks and data paths for the LD20. In order to be consistent with the principles set forth in Section 5, we plan for our design to be synchronous and static. We may make a few basic observations about the architecture:
(a) All major building blocks should be "out in the open." We wish to use building blocks of the right scale for our example. We could build everything from transistors or from AND, OR, and NOT circuit elements, as designers were forced to do a few years ago, but such approaches are far too detailed and would not teach you how to use higher-level building blocks. At the other end of the scale, it is possible to buy a complete PDP-8 processor in a single integrated circuit chip, and we would expect you to use such a chip in appropriate designs. However, a one-chip processor would be a poor vehicle for studying digital logic design, since all the interesting structure is buried inaccessibly within the chip.
(b) The control panel should continuously display all the major registers and control signals, so that the observer may see at a glance what is happening in the machine. With lamp drivers and LEDs (light-emitting diodes), the cost of displaying signals is minimal. Now is the time for the beginning designer to think about making designs that are easy to understand and debug.
(c) The control panel should provide ample mechanisms for the operator to control the progress of the machine. Synchronous, static design implies that we have ways to control the speed of the master clock, halt the clock entirely, and deliver manually produced clock pulses. The ability to reset or restart the machine is crucial in debugging. Since the basic unit of computer operation is the instruction, the ability to allow only one complete instruction at a time to be executed (single-stepping) is a powerful debugging aid. As creative designers, we will be eager to include such useful features in the control panel.
The Principal Elements of the Architecture
Our knowledge of the PDP-8 lets us specify certain architectural structures immediately.
Accumulator (AC). We will need a 12-bit register to store intermediate results.
Link. LINK is a I-bit storage register used primarily to handle arithmetic overflow during addition to the AC. It also participates with the AC in shifting operations.
Memory (MEM). The PDP-8I has 4096 words of 12-bit memory. We will use standard RAM chips. The memory system requires two data items for its operation: a memory address and a memory buffer.
Memory address (MA). This is a natural part of any RAM, since the memory system must know where in its memory to perform a read or write operation. We will provide a register to hold the address-the memory address register MA. Memory buffer (MB). Our selected memory presents read data on a set of output lines (MEM) for use in other parts of the computer. The memory must receive write data at a closely specified time in its cycle; this data is generated by other parts of the computer at earlier times. We need to hold the data until it is needed for the write operation, so we store it in a memory buffer register MB. Control panel switches. Every PDP-8 contains a switch register SR of 12 toggle switches that allows the user to enter data into the computer manually.
Calling these switches a register is unusual, since the data is stored in mechanical switches instead of flip-flops. Nonetheless, the switches are a memory device, and so we retain the nomenclature. The control panel also contains control switches such as START, STOP, and CLEAR, which will be described more fully in a later section.
Arithmetic logic unit (ALU). We must develop a building block to handle the various logical and arithmetic operations required by the PDP-8's instructions.
The description of the PDP-8's instructions shows that the LD20 must perform the following operations on 12-bit data words: Logical AND: from the AND instruction.
Logical OR: from one of the Operate microinstructions.
Logical NOT: from the Complement AC microinstruction.
Clear to zero: There are a number of times when a register must be cleared.
The best way is to synchronously load the register with 12 bits of zero generated by the ALU.
Add: from the TAD instruction.
Increment: from the Increment AC microinstruction.
The ALU must be able to perform all these operations. We plan to use the 74LS181 Four-Bit ALU chip for this function, since it can perform all 16 logical operations as well as addition, subtraction, and incrementing. The 74LS181 is the only integrated-circuit chip that we specify at this time. Most of the actual selection of chips will be made much later in the design process. The only reason to fix on the 74LS181 now is to identify the likely features and limitations of our ALU. We care only about its functional characteristics, not about the details of how it is controlled.
Program counter (PC). Every computer has a program counter that specifies the location of the next instruction to be executed.
Instruction register (IR). The IR is another register found in every computer; it holds the current instruction for the duration of its execution.
Data Paths
We have identified major elements of the LD20's architecture by looking at the PDP-8's functions. Now that we have this set of elements, how do we put them together? In true top-down spirit, we will leave them scattered about on the desk and back off far enough to ask a question. How does the PDP-8 instruction set say they should be connected? Contemplating this question will lead us surprisingly close to the final architecture. We assume that the ALU has two 12-bit input paths and that it will handle all logical and arithmetic operations.
Let's see how the PDP-8's instructions guide us to a model of the data paths among the building blocks.
(a) IAC Increment Accumulator: AC (+) 1 ~ AC. If the ALU does the addition, the AC and the ALU must be connected in a manner similar to Fig. 2.
(In this and subsequent figures, the data paths are all 12 bits wide, and we call the output of the ALU the ALUBUS.) Execution of the IAC microinstruction must result in setting the ALU control lines to force the ALU to increment the input and place the result on the ALUBUS. (b) TAD Two's-Complement Add: AC (+) CA ~ AC. This instruction requires an architecture like that in Fig. 3. Here the ALU's control lines must make the ALU add its two data input quantities and place the result on the ALUBUS.
Fig. 2 Data flow for incrementing the AC.
Fig. 3 Data flow for addition.
(c) AND: AC·CA ---+ AC. This instruction again leads to Fig. 3, where this time the ALU must perform the bit-by-bit logical AND of its data inputs.
(d) OSR OR Switch Register: AC + SR ---+ AC. Both the switch register and the AC must be inputs to the ALU, as shown in Fig. 4.
(e) Increment the program counter: PC (+) 1 ---+ PC. This operation is implied in any computer, since after one instruction is completed the next one will be executed. This normal sequencing will continue, instruction after instruction, until a programmed branch operation causes the PC to be set to a branch address. Normal (nonbranch) sequencing leads to Fig. 5, in which the ALU performs the increment operation.
(f) Load the program counter: This results from the branching case mentioned above and requires the operation EA ---+ PC. At this point we could establish a private data path into the PC so that EA ---+ PC; but look at the requirements of operations (a) through (e) that are leading to a common architecture.
Examining those cases, we may reason as follows.
Fig. 4 Data flow for the OR Switch Register (OSR) instruction.
Fig. 5 Data flow for incrementing the program counter (PC).
Developing the main bus structure. The AC seems to have pinned down one of the two data inputs that are a part of the ALU building block. The other input comes from a variety of sources: the contents of the effective address CA, the switch register SR, and the program counter PC, so we require a way of selecting the proper input to the ALU. Recall the discussions of data busing in Sections 3 and 4. One good way to route several data sources to an output is to have· three-state buffers on each source output. Enabling one of the source buffers lets that source "talk" to the ALU, as shown in Fig. 6. (Remember, all data paths are 12 bits wide.) This is an economical way to route the data.
Some register integrated circuits include three-state output control; using such chips might eliminate some of the separate buffers in Fig. 6.
Fig. 6 Controlling the input to the ALU with three-state buffers.
Another approach to the selection of the ALU's input is to use the multiplexer building block to select the appropriate input (see Fig. 7). There is one multiplexer for each bit of the 12-bit data path. We have two good choices for busing the ALU input. To design the LD20, we have chosen the mux method of Fig. 7, primarily for its ease of debugging.
Fig. 7 Selecting the input to the ALU with a multiplexer.
Our study of PDP-8 operations has led to this architecture. We may ask if the structure could be generalized to handle the case EA ~ PC, which arises when the PC register is loaded with a branch address. The answer is, of course, yes: we add an EA input to the data multiplexer. To execute the branch operation, we must set the mux control inputs to select EA, and must set the AL V controls to pass this ALU input unchanged to the ALUEVS. If a load signal to the PC accompanies these operations, we would perform EA ~ Pc. It is significant that we have accomplished the goal by generalization rather than specialization.
This is a discovery that we should try to carry as far as we can. We now have a mechanism for moving data from one register to any other, as well as a way of performing logical or arithmetic operations on the ALU data inputs.
These capabilities are nearly all the structure we need to build a computer.
Again, let us note that we were led to the architecture in a direct manner by a careful consideration of the fundamental requirements of the PDP-8's instruction set.
This is not the way some designers proceed. They start with a structure (a guess, really) based on a certain set of integrated circuit chips, and then try to bend the design to fit that guess. Sometimes the bending can require enormous leverage, when it could be side-stepped by redefining the architecture. Unfortunately, at that point it is too late; the designer's mind is already in a groove and it is difficult to jolt it out. If you let your target lead you to the architecture, you can avoid this groove until the last possible moment and save yourself anguish.
Adding memory. Now it is a simple matter to expand the tentative architecture of the LD20 to handle the remaining data transfers. We need to take care of memory and its interaction with the memory address and memory buffer registers MA and MB. The MA register gives memory the address at which to perform a read or write operation; therefore, MA must be wired directly to the memory. MA must be loaded with address data from various sources (e.g., EA), so we make MA a destination on the ALUBUS. So that data from the memory can reach other destinations, the output of memory connects to the data mux. Memory write operations require input from MB in addition to MA. The MB holds the write data and must be connected directly to the memory.
The memory buffer register's input may come from a variety of sources yet
to be specified, so we will make MB a destination on the ALUBUS. Fig. 8 shows
the p
roposed routing of the memory data.
Fig. 8 The data flow in the memory system.
Handling CA. This is a good time to investigate CA, the contents of address EA. CA is not a register; rather, it is a concept that we introduced to aid our understanding of the operations of PDP-8 instructions. Where do values for CA come from? Remember that CA = (EA): CA is the contents of the location referenced by EA. Thus CA comes from the memory. We have just proposed an architecture for reading and writing memory data. If we route an address EA into MA over the existing paths, then a subsequent memory read command will give us CA. Therefore, we may eliminate CA from our data mux inputs, realizing that our recent addition of the memory system incorporates the data movement for CA. Fetching instructions. Can we use our basic data routing scheme to acquire the next instruction from memory and move it to the instruction register IR? The memory is already a source on the data bus, so we simply make the IR a destination on the ALUBUS. At the time of instruction fetch, our design must select MEM through the data mux, cause the ALU to pass its input without modification, and then cause the IR to load the result from the ALUBUS. Handling shift operations. Last, we must lay a plan for the data movements for the left and right shift instructions, which involve the AC and the link bit.
One approach would be to include the shifting capability in the ALU building block. This would be acceptable design practice. On the other hand, one of our basic MSI building blocks is the parallel-in parallel-out shift register, which will shift or retain its value or load a new value upon command. Since the shift operations in the PDP-8 involve only the AC and LINK, let's make the AC a shift register in addition to its earlier assignment as a holding register. In this event it appears unlikely that the shift operations will affect the basic routing of the data.
The LD20 data bus. The initial proposal for the architecture of the data path is complete, and appears in Fig. 9. We have derived the structure from first principles based on the requirements of the PDP-8's instructions, and although we have used our knowledge of good building blocks we have not committed ourselves to any particular chip other than the 74LS181 ALU. This initial architecture turns out to be very close to the final requirements that will emerge from more detailed study.
It is now time to consider the LD20's control algorithm. We use our tentative architecture as a framework for developing the control; understanding the control will, in turn, lead us to a refined architecture. Throughout all this, we remain aloof from the actual hardware until we thoroughly understand both the architecture and the control.
Fig. 9 An initial proposal for the architecture of the main data path in the
LD20.
A PRELIMINARY SKETCH OF THE LD20'S CONTROL
You have seen how a study of the PDP-8's instruction set led naturally to a tentative specification of the LD20's data storage and data paths. In this section we will write a control algorithm that will make the architecture execute the PDP-8's instructions. If we have chosen the tentative architecture well, we can write the control flowchart with only minor changes to the architecture. If we must make any major change to our structure because of the algorithm, we should start over and reconsider the architecture on the basis of our increased understanding of the problem. As you will see, our preliminary structure is a good one, requiring little revision.
First, we draw a preliminary flowchart of the control process. This broad treatment, although not detailed enough to serve as an implementation specification, nevertheless can help us understand the complex flow of operations involved in processing the instructions. Then, guided by our general description, we will develop a detailed ASM chart. It is at this point that we will find the ASM chart forcing small changes in the architecture. A complete ASM chart is the key to a good design. By its very nature, it requires us to think through our problem completely before we touch a gate or a soldering iron. This is the time to avoid problems, and a good ASM chart is worth all the effort expended on it.
We have proposed a preliminary structure that can move data among registers, perform arithmetic and logical operations on the A C, and load the memory control registers MA and MB with data to support a memory read or write. The major commands required to accomplish these results are: (a) Data multiplexer select controls. These signals select one of the data multiplexer input registers and present the data to the ALU. (b) ALU controls. These signals tell the ALU what logical or arithmetic operation to perform on its inputs. The result appears as output on the data bus ALUBUS, for distribution throughout the machine.
(c) Register load commands. The ALUBUS distributes data to the registers of the machine. At any time, only certain selected registers must load this data. The loading operations are controlled by a load signal for each register.
(d) Memory control. The memory unit requires read and write commands, delivered in accordance with a standard memory control protocol.
The function of the control hardware is to generate a properly sequenced set of these commands to carry out the control algorithm. Before we plunge into an ASM chart formulation, we will express the control algorithm as a simplified diagram analogous to a programmer's flowchart, one which does not carry the detailed timing and signal information that will appear later in the ASM chart.
Fetch and Execute
At this stage, we are looking for ways to subdivide the control algorithm into manageable parts. In computer design, a common practice is to split the control flow into units for instruction fetch and instruction execute phases. Fetch is that portion of the control algorithm responsible for fetching the next instruction and getting the operands or operand addresses required to execute that instruction.
Execute is that portion of the algorithm that carries out the operations required by a given instruction. Fetch calls Execute, which calls Fetch, and so on until the computer is halted. Fig. 10 shows the gross flow of the control.
Fig. 10 The fetch and execute phases of the LD20.
Investigating the Fetch Phase
From our discussion of PDP-8 instruction codes, we may divide the LD20's instructions into three categories: (a) Those that require neither EA nor CA. For example, a CMA (Complement AC) microinstruction needs no information other than the instruction word.
(b) Those that need an effective address EA but do not require CA. An example is a JMP instruction. We jump to the memory word at the EA but we do not care about the contents of that word.
(c) Those that require the contents CA of the effective address. An example is the AND instruction, which ANDS the CA and the AC.
The fetch unit in Fig. 10 is rather crude, since it always obtains an EA and a CA, whereas only a few instructions require CA and some instructions do not even need an EA. Can we expand the fetch phase to take advantage of these facts? If the instruction obtained from memory is CMA, for example, we could go to the execute phase as soon as we know that the instruction code did not require EA or CA. We modify Fig. 10 into the more efficient Fig. 11.
Fig. 11 Saving time in the fetch phase.
The CMA microinstruction takes the "No" branch in Fig. 11. Another example is the DCA instruction. The location at the effective address EA will receive the contents of the AC. The contents of location EA (in other words, CA) will be destroyed, so the execution phase will not need CA from Fetch.
Examples of instructions that will take the "Yes" branch in Fig. 11 are AND and TAD; these instructions operate on the contents of the EA, which is CA. Forming EA and CA. We must explore the effect of the PDP-8's memory accessing arrangements on the formation of the effective address EA. Recall that a PDP-8 memory referencing instruction has, in addition to the operation code, a page bit, a 7-bit page offset, and an indirect addressing bit. When the indirect addressing bit is 0, we may generate the EA as soon as we know what the operation code is. If the indirect addressing bit is 1, the formation of EA requires an additional memory access.
If the page bit is 1, the page address is the page that contains the instruction.
If the page bit is 0, the page address is page 0. We expect to derive knowledge of the current instruction's location from the program counter PC. We may specify the 5-bit address as
PAGE.ADDRESS = (PCO-PC4)·PAGE.BIT (7-1)
The high-order 5 bits of PC specify the page of the current instruction. If the page bit is 1, we wish to use these 5 bits·· of PC as our page address. If the page bit is 0, we need 5 zero bits for the page address. Equation (7-1) specifies that the page address is the logical AND of the page bit with each bit PCO through PC4.
For direct addressing, the 12-bit effective address EA is the 5-bit page address concatenated with the 7-bit page offset:
EA = PAGE.ADDRESS PAGE. OFFSET (7-2)
If the instruction requires an operand, we must access the memory at location EA to get CA. Instructions with indirect addressing require another iteration to obtain the final EA and CA. Thus, if the instruction requires an operand or if it specifies indirect addressing, we must obtain the contents of the memory location EA. We may think of the contents of EA as a tentative CA. For direct addressing, this is actually the CA we seek. For indirect addressing, this tentative CA becomes the new EA, so that the indirect process may continue. Fig. 12 shows the result of this analysis.
Fig. 12 An LD20 with indirect addressing.
Auto indexing requires a further addition to our general fetch flowchart.
If the acquisition of an indirect EA makes use of one of the auto index locations 108 through 178 , we must increment the contents of that location before we use it as an indirect address. This activity is shown in Fig. 13.
You can see that, little by little, as our understanding of the control process grows, the general flowchart becomes more complex and our notations become more succinct. This is characteristic of work on both hardware and software: as understanding grows, the detail increases and the notation is compressed.
Fig. 13 An LD20 with auto indexing.
Halts and interrupts. The LD20's flowchart must make provision for halting and for detection of interrupts in a systematic way. A halt can result either from manual intervention or from the execution of the HLT microinstruction.
In either case, the machine must move to an idle state whose purpose is to monitor the manual start switch. Halt processing must wait until the machine has finished the execution of the current instruction; the natural place to look for a halt is therefore at the start of the next fetch cycle.
This is also the natural place to examine interrupt requests. If the LD20 were to process an interrupt request at the instant it arose, chaos would result, since the LD20 would no doubt be in the middle of processing some instruction of a program. The proper time to handle interrupts is after an instruction is executed but before the computer fetches the next instruction from memory.
Thus we will add a section for handling interrupt requests to our flowchart. Fig. 14 shows these additions.
Fig. 14 A preliminary flowchart for the LD20.
The fetch portion of our preliminary flowchart for the LD20 is now complete.
Since Fetch involves some rather complex steps (to produce the proper EA and CA), it was useful to undertake this preliminary study of the control algorithm.
The execute phase of the LD20's control algorithm consists primarily of well separated sections for each instruction, and we will be able to handle these when we produce the actual ASM chart, without needing a detailed preliminary analysis. NEXT>>
PREV. | NEXT
Related Articles -- Top of Page -- Home