AMAZON multi-meters discounts AMAZON oscilloscope discounts
DEVELOPING AN ASM CHART FOR THE LD20
Fig. 14 is a high-level flowchart of the algorithm for emulating the PDP-8. We must reduce it to a more detailed flowchart that recognizes the architecture developed earlier in this section as well as the timing of the individual operations of the hardware. The ASM chart is the appropriate way to show these relationships.
In this section we will develop the ASM chart for the LD20 in detail since it is the most important step in reaching a good final design. We cannot over emphasize the importance of a good control algorithm. This portion of the design should occupy at least half of the time devoted to developing the digital system; every minute will be well spent. The design of the LD20 has been through at least five iterations and has had several hundred hours of thought devoted to it.
You may think this excessive, but it isn't, for design errors in the hardware can be very hard to correct after a system is completed. It is far better to produce the best possible design before construction begins.
We will develop each segment of the LD20's ASM systematically and many of the remaining figures in this section show fragments of the complete algorithm.
The entire ASM for the LD20 appears in three charts (Figs. 42, 43, and 44) toward the end of the section. You may wish to refer to these diagrams as you study the details in order to enhance your understanding of the inter relationship of the parts.
Conventions
We will adopt the conventions developed in Section 6 for naming states and any conditional output terms associated with them. The symbolic names for the states of the fetch phase of the LD20 are FI through F7, and for the execute phase are EO through ES. The first fetch state of each instruction is always FI, and the first execute state is always EO. Some of the states have many conditional outputs. We would like the names of the conditional output terms to reflect the parent state of the term. Our convention is simple. We give each conditional output term within a state a number and use a period to concatenate this number to the parent state name. Thus EO.IS is conditional output term 15 of state EO. A conditional output term may produce several output signals.
Occasionally, we will need to label other points or sections of the ASM chart, so that we can identify them in different figures. Our convention is to give the state's name, then a period followed by a nonnumeric name. For instance, the execute phase is divided early into two parts, one for manual operations, and one for normal processing of the instruction register; we call these parts EO.MAN and EO.IR, respectively.
The main purposes of the fetch phase are to get an instruction from memory, to prepare the effective address EA and its contents CA as required by the instruction, and then to go to the execute phase to process the instruction. We need a uniform mechanism for passing the instruction word, the EA, and the CA from the fetch phase to the execute phase. Obviously, the instruction should go into the instruction register IR. The memory address register MA is a good spot to place the address EA. What about CA?
From the discussion of the LD20's tentative architecture, you recall that CA comes from the memory word at location EA - the word whose address is in the MA register. During the fetch phase, we will perform the memory read operation to get CA for later use in the execute phase. Where can we put CA until it is needed? We could add another register to the data architecture for this purpose, but perhaps we already have a satisfactory intermediate register.
The memory buffer register MB is promising, and we adopt the standard convention that CA appears in register MB when we enter the execute phase. Notice that in Fig. 9 the MB is not connected to the data mux. If the MB is to be the source of CA, we must add MB to the data mux inputs. Our general data-routing scheme allows us to make this modification of the architecture immediately, without elaborate analysis.
Memory Control
It will be useful to define a protocol for memory control before we embark on the detailed development of an ASM for the LD20. We want to treat memory as a black box that will behave in a reliable and well-defined way when it is presented with proper input commands and data.
In Section 4 you saw how typical memory building blocks behave. Memory integrated circuit chips operate at their own pace, asynchronous to outside events.
Our design goals for the LD20 allow the system clock to operate at any reasonable rate. Depending on the clock speed and on the requirements of the particular memory device, the memory may be slower or faster than the LD20 clock. We must develop a set of rules-a protocol--according to which the LD20 will use the memory. We hope that these rules will be general enough to allow the use of memory independently of clock speeds and particular memory chips. What control signals and data are necessary to deal with a memory system? As far as the memory user (the LD20) is concerned, the memory box should have three elements for handling data:
(a) A memory address input.
(b) An input for memory write data.
(c) An output for memory read data.
To control the memory's activities, the box should have:
(d) An input command to start read operations.
(e) An input command to start write operations.
(f) An output that announces when the memory operation is finished.
In addition to these specific signals, the system clock is available, if it is needed.
Fig. 15 A control unit for the memory of the LD20.
Fig. 15 shows the black box for the memory.
At this point, we assume that the box exists, and we establish the protocol for using it in the ASM for our LD20. We will worry about the actual design of the box later. This modular approach to the problem of controlling the memory is an important aid to clear design, since we may put aside the intricacies of manipulating particular chips, knowing that the memory controller's interface with the outside world must conform to the established protocol.
In Fig. 9 we specified the data interconnections between the LD20 and its memory. The address input to the memory box comes from MA, the MB register provides memory-write data, and the memory's data output feeds into the data mux. There remains to specify the behavior of the control and status lines of the memory box. We will use START.READ, START.WRITE, and BUSY for the LD20 signals interfacing with the corresponding inputs and outputs of the memory box. Fig. 16 shows the resulting interface.
Fig. 16 The LD20's interface with its memory control unit.
We initiate a memory read by asserting START.READ during some state.
The memory controller senses this signal and begins the read operation on the next LD20 clock pulse. Thus read begins at the transition from the "start read" state. When the read operation begins, the memory-busy status signal BUSY must become true, and the controller must keep the signal true at least until the operation is complete. For convenience, we will require that changes in the BUSY signal be synchronous with the LD20 clock. The transition from BUSY = T to BUSY = F will occur at the next clock pulse after the memory box determines that the memory cycle is complete. The write operation, initiated by START. WRITE, behaves analogously.
The completion of a write operation implies that the memory box no longer needs the address and data inputs. Completion of a read operation means that the memory has had time to produce valid data, based on the stable address supplied to the box. As long as the address remains the same (or until another memory operation begins), the output data is valid.
Fig. 17 An ASM for a memory read.
Standard memory read and write sequences. The typical memory read sequence based on the memory protocol appears in the ASM chart of Fig. 17. The first state prepares to form a stable memory address in MA, and prepares to initiate the read operation. The second state loops until BUSY becomes false. We then exit that state while loading the now-valid memory data into a register. The third state is the earliest time that the contents of the register are available for use. This is a perfectly valid algorithm for reading a memory, and we could use it unhesitatingly in the LD20 ASM. It has the disadvantage that the memory activity is spread out over three states. If the design requires many accesses to memory, our ASM will contain quite a few states and will appear cluttered and unwieldy. Can we conveniently collapse the presentation of the algorithm into a more compact form? If we could arrange to wait upon, load, and then use the memory's contents in a single state, we may achieve some improvement. The following reasoning is useful.
We introduce a signal BUSY.HELD that behaves like BUSY except it remains true one clock cycle longer. The purpose of this signal is to help identify the first state time after BUSY becomes false; only then is BUSY = F while BUSY.HELD = T. This is the time when we wish to load the stable memory output into a register. Any time after this we may use the register contents.
This fancy footwork allows us to express the memory read sequence in only two states, as illustrated in Fig. 18.
We have reduced the number of states but have not improved the readability of the ASM sequence. On the contrary, it is more obscure than before. If we notice that it does no harm to load invalid memory data into the register as long as we finish by loading valid data, we may entirely eliminate the test on BUSY, leaving the single test signal BUSY.HELD, as shown in Fig. 19.
Fig. 18 Reducing states in the ASM for memory read.
Fig. 19 Improving the ASM for memory read.
Fig. 20 ASMs for the LD20's memory.
(a) Memory read
(b) Memory write
Last, as a matter of personal style, we choose to cast the remaining test in terms of the concept of Cycle Complete (CC), which in this treatment is the inverse of BUSY.HELD. Fig. 20a is the final form of a memory read sequence. The somewhat simpler sequence for memory write appears in Fig. 20b.
This is a general read-write protocol. The requirement on CC is that during the entire last clock cycle before CC became true, the memory operation was complete. We may now use the protocol with confidence, with all the detail packaged in the memory box and the associated CC circuit.
Fig. 21 ASM of state F1.
State F1 (Fig. 21)
Halt detection. State F1 is the first state of every fetch cycle, and is a good place to check for a halt condition. The LD20 must remember halt requests that arose during the processing of the last instruction, so we will add a halt status flip-flop HALTFF to the architecture. (At this time we do not care exactly what type of chip we use for the flip-flop, although we suspect it will be a JK since the ASM will set and clear the halt status at various points in its processing.) If a halt request occurred, the ASM will have set HALTFF to T, and we can
test it in state F1. If HALTFF is true at this time, the ASM should move to an idle state IDLE, which will inhibit further processing of instructions. If HALTFF is false, the fetch phase proceeds.
Detecting an interrupt. State F1 is the proper place to test the status of the interrupt request system. Using the commands ION (6001 8) and IOF (60028), the programmer may enable or disable the interrupt system. To record the current enabled or disabled condition, we need a memory element; this addition to the LD20 architecture is the INT. EN (Interrupt Enabled) flip-flop.
Let INTREQ be the interrupt request signal coming into the LD20, and let INT represent a detected interrupt signal. Then:
INT = INTREQoINT.ENoION
The term ION ensures that interrupt recognition will be inhibited immediately after an ION command, in conformity with the PDP-8's instructions. At the time the ASM enters state FI to start processing a new instruction, the instruction register IR still contains the previous instruction. If that instruction was an ION, we must ignore any pending interrupt request and instead allow an additional instruction to complete its execution. The equation for interrupt recognition means that INT is true only if INTREQ is true and INT.EN is true and ION is false. INT is interrogated in state FI, and if it has the value T at that time, interrupt processing takes place.
If INT is true, we must force a subroutine jump to location 0000 (JMS 0) and disable the interrupt system. Jump commands require an effective address EA, and the execute portion of the ASM expects to find the EA for a JMS in the memory address register and the operation code in the instruction register.
Therefore, the proper response to interrupt recognition is shown in the conditional output term Fl.2 in Fig. 21.
A style-motivated digression. Term Fl.2 changes the MA and IR registers.
We ask ourselves if there is any condition which would make us regret destroying the old values of MA and IR. As long as the machine is running at full speed we would never notice, since the overall processing of the interrupt would be correct-the changes in console displays for MA and IR would last only a few microseconds. The only time we might notice a change is when the machine is stopped, when its clock is operating at slow or manual speed, or when the single instruction switch is on and we are executing individual instructions. Suppose an interrupt request arose during the execution of a halt instruction. In that case HALTFF would be true upon the next entry to state Fl. In Fig. 21 we see that the HALTFF test occurs before the INT test in state FI, so the machine will go to IDLE without interrupting, with the old instruction in IR; there is no problem with this behavior.
In manual clock mode, or at slow clock speeds, we are presumably checking for correct machine operation or debugging a newly constructed machine. Then we would want to see all the detailed micro-operations of the hardware, including any interrupt processing, so our ASM is appropriate for this situation also.
The remaining condition arises when the single instruction switch is on and we are single-stepping through the program when the interrupt occurs. But again, the HALTFF flip-flop would be true, causing the machine to return to IDLE after each instruction, with the old values of MA and IR preserved. Thus we find that we may jam 0 into MA and the JMS operation code into IR bits 0-2 without the loss of useful information. This digression points up the desirability of thorough study of a design in its conceptual stages; now is the easiest time to detect and correct design flaws.
Normal processing of instructions. If HALTFF and INT are both false, normal instruction processing will proceed and the ASM must prepare to get the next instruction from memory. In state FI, the program counter PC contains the address of the next instruction. Since we have to perform a read from memory at that location to get the next instruction, in Ft.t we transfer the contents of the program counter to the memory address register, in preparation for the read. Later in the fetch phase the memory data becomes the current instruction. The effective address EA (which may be needed by this new instruction) is formed by concatenating a 5-bit page address with the 7-bit page offset. For this purpose, the EA computation may require PC bits 0 through 4, so we must preserve PC until EA is formed. But the formation of EA must await the arrival of the new instruction from the memory. Normal instruction sequencing dictates that PC be incremented by t, and we wish to do this in the fetch phase so as not to waste time in the execute phase. (The execution of a branch instruction will later replace the program counter's value with a branch address.) Now we have a subtle problem: We must hasten to increment PC, yet we must save PC for possible use in forming EA. PC bits 0-4 may be different in the incremented PC than in the current PC. (Why?) Our solution is to look for a temporary place to hold the current value of the PC until EA is formed. The memory buffer register ME will serve. Until this point, ME's only role has been to hold data to write into memory and to hold CA for instruction execution. Neither of these is occurring now, so ME may hold the old PC awhile. F1.1 moves PC to ME.
State F2 (Fig. 22)
Incrementing the program counter is an operation common to all one-address computers. Such machines assume that the next instruction will come from the memory location immediately following the current instruction, unless there is a jump instruction. We can achieve the normal sequential case by incrementing PC in state F2. We also initiate a memory read cycle to obtain the next instruction.
MA contains the address, placed there in state Fl. The downward arrow in Fig. 22 implies that the start-read operation is to begin at the end of the state (like a register load or a flip-flop set).
Fig. 22 ASM of state F2.
State F3 (Fig. 23)
This state serves two main purposes:
(a) To wait for the memory to finish the read process started at the end of state F2, and load the memory data into the instruction register.
(b) To generate the effective address EA from the instruction newly placed in IR.
We use the standard protocol for controlling the memory read operation: The ASM loops in state F3 until the cycle complete signal CC becomes true. During the last loop with CC = F, the memory data copied into IR at term F3. 2 comprises the new instruction.
Fig. 23 ASM of state F3.
Once the new instruction is in IR, control will pass through term F3.1.
Here we generate EA for the new instruction by concatenating the 5-bit page address with the 7-bit page offset, according to Eq. (7-2). The program counter PC no longer points to the current instruction, since state F2 incremented the PC register. However, we saved the old value of PC in the MB register, so we can calculate EA by:
(\ EA = [(MBO-MB4)oIR4] [IR5-IRll] ( eqn 3)
(Remember that if IR4 is 0, the first 5 bits of EA are 0.) Since in the execute phase the effective address is to be found in the memory address register, we move EA to MA in F3.1.
Early exits to Execute. We now have an opportunity to be clever by noticing that certain instructions need no more fetch-phase processing. Two such instructions are IOT and OP, which do not reference the memory. The instruction bits that would normally be treated as a part of a memory address have a different meaning. All the information that Execute needs is already in the instruction register, so we may immediately branch to the execute phase.
Three other instructions are possible candidates for this early exit to Execute: the directly addressed versions of DCA, HMP, and JMS. These instructions do something to or at a memory location, but they do not require the contents of that location. For example, a JMP X instruction will jump to location X regardless of the value stored in X. Remember the meanings of EA and CA: EA: The target address of the operand after any indexing or indirect addressing is done.
CA: The contents of the word at the target address: CA = (EA).
The PDP-8 does not have an index register. If the instruction calls for direct addressing (bit IR3 is 0), then we are already moving the final EA into the MA register. For the directly addressed DCA, JMP, and JMS instructions, we may exit immediately to state EO. Since the condition for branching to EO involves several logic terms, we find it convenient to define a new variable NOMEM (No Memory Reference) to express the opportunities to exit to EO at this point:
NOMEM = OP + IOT + DIRECT o (DCA + JMS + JMP)
Where:
DIRECT = IR3
We may use NOMEM in the ASM chart for state F3 as a compact representation of the EO branching condition.
If NOMEM is true, the ASM goes to state EO. If NOMEM is false, the instruction in IR requires further memory accesses, so we may initiate a read from the memory in term F3.3 as we exit from state F3. The memory read will use the newly established value of the memory address register.
State F4 (Fig. 24)
Since state F3 initiated a read operation, state F4 must observe the memory read protocol and loop on CC, capturing the memory's output. We are reading an operand at this point, so the memory buffer register MB is the correct place to put the memory data, in anticipation that this operand will be required by Execute. This activity occurs in term F4.1 of Fig. 24.
Fig. 24 ASM of state F4.
If the instruction involves direct addressing, we have just acquired the necessary operand CA and we may go immediately to state EO. This case arises when there are directly addressed AND, TAD, and ISZ instructions. We have already defined the variable DIRECT as IR3; if DIRECT is true, we now exit to state EO. In order to continue, all remaining fetch instructions have DIRECT = F (IR3 = 1). We are now on a path for indirect addressing, since IR3 = 1. We must test to see if we are referencing one of the auto index memory locations, which have addresses 108 through 178. If a PDP-8 instruction accesses one of these locations for use as an indirect address, the location is automatically incremented and put back into the memory before it is used for indirect addressing. To keep the ASM chart compact, we introduce a variable A UTO that is true if the effective address EA specifies one of the locations 108 through 178. These addresses have bits 0-8 in common, whereas bits 9-11 select the particular address. Since the effective address is in MA at this time, the equation for AUTO is AUTO = MAO· MA1· MA2 • MA3 • MA4 • MA5 • MA6 • MA7 • MAS
If AUTO is true in state F4, auto indexing must occur. The ASM must increment MB, which holds the contents of the auto index location, and also initiate a memory-write operation. The MA register still points to the auto index location and remains unchanged during the write operation. The auto indexing preparation takes place in term F4.2; the ASM must then move to a state (F5) that will wait for the completion of the write.
If no auto indexing was associated with the indirect addressing, the ASM exits from state F4 into state F6, where indirect processing continues.
State F5 (Fig. 25)
This state completes the auto indexing operation and then merges into the main fetch stream at state F6. Auto indexing appeared as a "side operation" from state F4, and it has no further influence on indirect addressing.
State F6 (Fig. 26)
We enter this state only in the presence of a memory referencing instruction involving indirect addressing. Indirect addressing requires that we use the current Contents of Effective Address CA (held in ME) as the final Effective Address EA. Thus state F6 moves MB into MA. If the instruction is of the type DCA, JMS, or JMP that does not use the contents of EA, we may again exit immediately to state EO. The surviving instructions are indirectly-addressed AND, TAD, and ISZ. They require memory contents as operand data, and so we must start one last read operation and move to a final fetch state F7 to complete the read.
Fig. 25 ASM of state F5.
Fig. 26 ASM of state F6.
State F7 (Fig. 27)
In state F7 we complete the acquisition of the necessary CA data for indirectly addressed instructions. The contents of the memory go into the MB register, as required by our conventions for the entry into the execute phase of the LD20's ASM.
Fig. 27 ASM of state F1.
State IDLE
In many respects, IDLE is the most important state in the machine; without it we would have no way to halt or start the computer. The function of IDLE is to scan the control panel switches for activity. When it occurs, IDLE must pass control to an appropriate section of the ASM. When the machine is in IDLE, the LD20 will loop in that state as long as no switch is depressed.
Control panel switches. Let's consider what control switches we desire on the control panel.
CONT (Continue): This is the start switch. When the IDLE ASM senses that CONT = T, it will branch to the fetch phase to continue routine processing of instructions.
Loading the registers: Our design calls for the contents of each main register to be continuously on display. We also desire to be able to load the contents of each register from the control panel's switch register SR. We provide six switches for this purpose:
LDMA (Load memory address register from SR)
LDMB (Load memory buffer register from SR) LDPC (Load program counter register from SR)
LDIR (Load instruction register from SR)
LDAC (Load accumulator register from SR)
LDMEM (Load the memory word at address MA from SR)
These load switches are not part of the commercial
PDP-8 but are a great convenience to the LD20 designer during implementation and to the LD20 programmer who is debugging programs and operating the computer.
Two more switches have counterparts in the PDP-8:
DEP (Deposit) is used to load the panel switch register SR into sequential memory locations. Since it advances MA after each memory load, DEP is useful for entering programs or other data into consecutive locations.
EXAM (Examine): The currently addressed word is always on display in the memory's panel lights. EXAM advances the memory address register MA, allowing the operator to view the next word. This is of value for examining the contents of consecutive memory locations.
Three more switches complete the panel controls: CLR (Clear) fulfills a PDP-8 requirement that the operator be able to clear the link bit and the interrupt enable flag from the control panel.
RESET is the master reset switch. Its function is to force the LD20 into the IDLE state, regardless of the present condition of the machine. This operation is useful for starting the LD20 and, during debugging, for escaping from any hangup that may arise from improper design or implementation, or from mal functioning components.
SING.INST (Single Instruction): In its normal operating mode, when SING. INST is false, the LD20 processes a continuous sequence of instructions.
When SING.INST is true, the LD20 halts after processing each instruction.
Whereas the other control switches are "momentary-on" pushbuttons which return to the false condition after the button is released, Single Instruction is a toggle switch that has stable false and true positions.
The IDLE state examines the condition of all the LD20 control switches except RESET and SING. INS T. State EO processes SING.INST; the action of the RESET switch is asynchronous to the LD20's clock.
The other switches are also asynchronous to the LD20's system clock, but we will insist that our design handle them within the synchronous ASM structure that we are now developing. The output of each of the switches will have the appended to its name to indicate its asynchronous nature.
IDLE operations. To specify the operation of the IDLE state, it is useful to define a signal MANSW* that is a composite of 10 manual pushbutton signals:
MANSW* = LDMA* + LDMB* + LDPC* + LDIR* + LDAC*
+ LDMEM* + DEP* + EXAM* + CLR* + CONn
In the IDLE state MANSW* can assist in detecting a depressed switch. By now you should be sensitive to our two old problems: testing asynchronous signals and processing a signal from a pushbutton more than once. We can coordinate IDLE's scan of the pushbuttons with the operator's push of the button by synchronizing MANSW*. This will synchronize the pushbutton operation with the LD20. If the operator keeps the button down until the operation is completed, we will not need to synchronize each individual switch signal.
We must also arrange to handle each depression of a switch just once. For practice, you might consider what would happen if depressions of the DEP, EXAM, or CaNT pushbuttons were acted upon more than once. Of the several schemes for dealing with the problem, we choose to add a single pulser to the architecture to isolate the first whole clock period in which MANSW* is true.
As we showed in Section 6, the single pulser provides for synchronizing the input and delivering truth on the output for only the first clock period after the input becomes true. In the present case, the input to the single pulser is MANSW* and the output is MANPULSE. IDLE can test MANPULSE, and the operation appears in the ASM in a compact form.
With MANPULSE true, IDLE will go to state F1 if CONT* is also true, and will go to state EO otherwise. The execute phase therefore not only controls the execution of instructions, but also provides for manual operations. At various points, the execute phase will depend on whether entry to state EO was from Fetch (normal instruction processing) or from IDLE (manual operations). We provide a storage element MANEX (Manual Execution) in the architecture that will be true in Execute only if state EO was entered from IDLE. MANEX protects the execute phase from improper pushbutton depressions, since Execute will respond to manual signals only if MANEX is true.
The IDLE state performs one further function: In the normal process of halting the LD20, state Fl finds HALTFF = T and branches to IDLE. Since HALTFF has served its purpose, IDLE must reset the flip-flop to false.
Fig. 28 shows the ASM for state IDLE.
Fig. 28 ASM of the IDLE state.
Execute-Phase Processing
The execute phase processes program instructions and manual operations. Within each category, we must perform a many-way branch to accomplish the processing for each type of command. In Fig. 29 we show the structure of the execute phase. Each square box represents the sequence of actions required for that operation. Our task is to convert this general flow diagram into an ASM chart.
State EO: The Single-Instruction Switch
Fig. 29 The execute phase of the LD20. (This is not an ASM chart.)
The main state in Execute is EO; it is rather complex because each of the 17 different operations begins (and many also end) in this state. In addition to the individual operations, some Execute activities are common to all the operations.
The principal common activity is the examination of the Single Instruction Switch, a switch that allows the operator to select either continuing instruction processing or a halt after the execution of each instruction. The signal emerging from the debounced toggle switch is SING.INST*. Before testing this signal, we must synchronize it with the LD20 system clock. We use a clocked D flip-flop with input SING.INST* and output SING.INST. If SING.INST is true, then state EO sets the halt flip-flop HALTFF to true; otherwise, state EO will set the halt flip-flop to false. In other words, HALTFF receives the value of SING.INST during state EO. Setting HALTFF to true will not stop the machine immediately, since the ASM does not examine the value of HALTFF until state Fl of the next fetch phase. If HALTFF is true at that time, the ASM will jump to IDLE rather than continuing to process instructions routinely. There is no need for a separate stop switch on the LD20, since it would duplicate the effect of the single instruction switch.
State EO: Detection of Manual Operations
The execute phase is entered from a fetch state or from IDLE. Entering EO from Fetch implies normal instruction processing; entering from IDLE must cause processing of the relevant manual switch. For calls from IDLE, the manual execute flip-flop MANEX is true, having been set in IDLE.1 so that Execute can determine the correct type of processing. Experience has shown us that it is advantageous to elaborate slightly on the simple testing of MANEX in EO. In debugging, we often wish to execute the instruction in the instruction register IR without going through the normal fetch process. This is especially true in the early stages of debugging, when the memory system is not yet working.
During normal operations the system clock will be running at microsecond speeds.
A debounced depression of a manual switch lasts for at least 100 msec, which would be on the order of 100,000 clock cycles. Thus, during normal operation, a manual switch that causes a call to Execute will be depressed for the entire duration of the execute phase. However, during debugging, the operator will advance the system clock at a slow rate, probably manually. The operator can press a button for one clock period to escape from the IDLE state, and then release the button before the next clock edge arrives. The LD20 is then in state EO, deciding either to process a manual pushbutton or to process the contents of the instruction register. When no button is depressed, the composite pushbutton signal MANSW* is false. By insisting that MANSW* be true in order to process manual operations, we have a way to force the machine to process an instruction, even though we did not reach Execute by way of Fetch.
We now have two requirements for manual operations: MANEX must be true to assure that any manual activity originated from IDLE, and MANSW* must be true to show that a button is still depressed. We define the relevant test signal as
MANEX.SW* = MANEX·MANSW*
If MANEX.SW* is false, the execute phase will process the contents of IR. The ASM chart for the beginning stages of EO is shown in Fig. 30.
Fig. 30 Initial processing in state EO.
Here is what the operator does when debugging a given instruction while bypassing the fetch phase: (a) Loads IR from SR with the desired command, using a high-speed clock and the LDIR button.
(b) Loads the desired effective address into MA, using the LDMA switch.
(c) Loads the desired operand into MB, using the LDMB switch.
(d) Switches to a low-speed (or manual) clock.
(e) Holds any manual pushbutton down for the duration of one clock edge.
This will cause a transition from IDLE to EO.
(f) Releases the pushbutton before the next clock edge. The ASM will now be in state EO on the false path in Fig. 30. (g) Proceeds through the execute ASM chart.
When MANEX is true, we may thus traverse either the manual or instruction parts of the execute phase. We must clear MANEX to false before we leave the execute phase. It is tempting to put this clearing operation into the unconditional part of state EO, right up front. This will not work, because throughout its duration the execute phase needs a knowledge of the status of MANE X to control the flow. We must remember to insert the term F ---? MANEX just before any exits from the execute phase back to Fetch or IDLE. This is a subtle point, and in one of the exercises at the end of this section we ask you to consider what would happen if MANEX were reset unconditionally in EO. As we develop the ASM for the execute phase, we will insert the F ---? MANEX term at the appropriate places, without further comment.
Execute Phase: Manual Commands
Most of the LD20's manual pushbuttons are not a part of the standard PDP-8 computer. We have incorporated them into this design for the convenience of the operator. Six pushbutton signals load a given register from the SR: LDMA*, LDMEM*, LDMB*, LDPC*, LDAC*, and LDIR*. LDMEM* requires that the MA be set appropriately. The EXAM pushbutton supports a sequential dump to the memory lights on the display panel: each depression of the EXAM switch will increment MA, and thus the contents of the next memory location will appear in the lights. Recall the design of the memory box. As long as MA is stable, the memory box produces good output data after the short memory read cycle. The DEP pushbutton enables a sequential memory load from SR. It acts like LDMEM except that, after loading the memory, it increments MA, so that the next word appears in the memory lights and is available for changing.
The ASM description of most of these pushbutton operations is straight forward. EXAM does not require us to perform an ASM memory read because as long as MA is stable, the read occurs automatically at a speed thousands of times faster than human reactions. According to the memory protocol, LDMEM and DEP activities require the execution of a state after the state that initiates the write operation. Also, looking ahead to instruction processing, we know that at least DCA (Deposit and Clear Accumulator) requires a memory write.
We could declare a separate state for each path from EO (for LDMEM, DEP, DCA, etc.), but the memory write operations have so much in common that we should see if it is convenient to combine all these second execute states into a single state. Let's call the new state El. If any of the users of state El require special processing during or after El, we must be prepared to introduce a many way branch, similar to but smaller than the one in EO. With this in mind, we derive the ASM descriptions of the manual operations (see Fig. 31). The EXAM and DEP operations require that the MA register be incremented.
According to our plan for the LD20's architecture, we perform the incrementing by routing the MA through the ALU, and routing the incremented value, on the ALUBUS, back into the MA. This action requires that MA be attached to the data multiplexer as a source. Our design allows us to add this register immediately, without difficulty.
Execute Phase: Memory-Accessing Instructions
Our convention upon entering state EO from Fetch is that MA contains the effective address EA, and MB contains the contents of that address, whenever these values are relevant to the instruction. The ASM descriptions of the memory accessing instructions are simple and are based directly on the descriptions of the PDP-8's instructions earlier in this section. Fig. 32 is the ASM for AND, TAD, ISZ, DCA, JMS, and JMP.
Execute Phase: The IOT Instruction
This instruction performs input and output operations to or from the LD20 accumulator. It is an important command, and PDP-8 input-output procedures require careful study. We defer a detailed discussion of PDP-8 input-output programming and interfacing until Section 9; at this time we treat only the LD20's responsibilities for the execution of IOT instructions. The IOT instruction has three fields: the operation code (1102), a 6-bit device address field, and a 3-bit control field. The format of the instruction word is:
p395
The interface between the LD20 and the external devices consists of the following signals: (a) Six device address lines from the LD20: lR3-IR8.
(b) Twelve data lines from the LD20: ACO-ACII.
(c) Three control lines IOP1, IOP2, and IOP4 from the LD20, derived as requested by IR11, IR1O, and lR9, respectively.
(d) Twelve external data lines into the LD20: lNPUT0-lNPUTll.
(e) Three control lines into the LD20: IOSKlP, ACCLR, and ORAC.
IOT protocol. The protocol requires the following. With the device address stable on the outgoing device address lines, the LD20 issues a sequence of 0 to 3 IOP signals, as specified by 1-bits in IR11, IR10, and IR9. IOP1 will be issued first, if requested by lRll, followed by IOP2 and then IOP4, if requested. During the lifetime of each of these three IOP signals, the LD20 must interrogate the three incoming control signals, in the order IOSKlP, ACCLR, and ORAC. If IOSKlP is true, the LD20 must skip an instruction. If ACCLR is true, the LD20 must clear the AC, and if ORAC is true, the LD20 must perform a bit-by-bit OR operation of incoming data into the AC:
AC + INPUT --> AC
Fig. 33 shows the general structure of IOT processing in the LD20. IOT architecture and control algorithm. To support the IOT protocol, the LD20 needs:
(a) A way to assert the requested IOP signals, in order.
(b) Within each IOP time, a way to interrogate the incoming control signals, in the specified order.
Fig. 31 ASM of manual operations in the execute phase.
Fig. 32 ASM of instructions that access the memory in the execute phase.
Fig. 33 General flow of an IOT instruction. (This is not an ASM chart.)
We have chosen a simple yet effective design. During the execution of an IOT instruction, state EO is responsible for creating each requested IOP signal. An asserted IOP signal stays true throughout three more states, E3, E4, and E5, which perform a sequence of tests on IOSKIP, ACCLR, and ORAC. State E5, in addition to testing the ORAC signal, determines if three passes through the state sequence EO, E3, E4, E5 have elapsed. If fewer than three passes have occurred, state E5 will return control to state EO for another pass; otherwise, control passes to state FI, ending the execution of the IOT instruction.
The architecture must contain an element to produce the requested IOP signals in the proper sequence and hold them throughout the execution of the E3, E4, and ES states. A 4-bit parallel-in parallel-out shift register, one of our standard building blocks, serves nicely to provide the sequencing of the IOP signals. We initialize the shift register with the binary bit pattern TFFF prior to reaching the execute phase. For an IOT instruction, passage through state EO shifts the bits one position to the right. Think of the bit positions as being named 0, 1,2, and 4. Output signals from bits 1,2, and 4 represent the enabling conditions for the respective IOP signals, say IOP I.EN, IOP2.EN, and IOP4.EN. For instance, after two right shifts, the bit pattern in the IOP enabler is FFTF. This corresponds to IOP2 time and IOP2.EN is true; if the programmer has requested an IOP2 signal (with instruction bit IRIO = 1), it will be issued at this time. The logic equivalent of this operation is
IOP2 = IOP2.EN-IRIO
Fig. 34 is a functional sketch of the IOP enabler system.
The LD20 ASM of the execute phase of IOT processing is shown in Fig. 35. Our architecture for the LD20 already can support the PC (+) 1 ~ PC and the 0 ~ AC operations required in response to the incoming control signals.
To accomplish AC + INPUT ~ AC, we must provide a data path for the 12 bits of INPUT into the ALU, where the OR operation will occur. Since we have adopted a readily expansible data routing scheme, we can easily add INPUT to the list of items on the data multiplexer inputs.
State F1 is a convenient place to initialize the IOP enabler; see Fig. 39a.
Fig. 34 An enabler for the IOP signals.
The initialization to TFFF occurs with each instruction fetch; this does no harm since the only shifting of the IOP enabler occurs with IOT instructions.
Enabling and disabling the interrupt system. The IOT instruction contains the ION (Interrupt System On) and IOF (Interrupt System Off) commands, which allow the programmer to enable or disable the interrupt system. The instruction format for these operations is 60018 for ION and 60028 for IOF; in both cases the device address is O. Execution of these commands requires that the ASM set the interrupt enable flip-flop INT.EN to T or F, respectively. Fig. 35 shows actions in state EO that handle these activities.
State EO: Operate Microinstructions
Operate priority system. From the programmer's point of view, the PDP-81's Operate instruction is divided into two groups, G1 and G2. In our hardware, the important structural feature of the Operate instruction is the priority system for specifying the sequence of micro-operations. The simplest way to process the Operate instruction is to devote four states to it, one for each priority level, as shown in Fig. 36.
Frequently, a programmer will use an Operate instruction that specifies only one micro-operation. For example, CLA (72008 ), a priority-1 operation, has only the CLA bit set. The ASM chart in Fig. 36 would perform the CLA in the first state and then do nothing in the next three states except waste time.
Fig. 35 ASM of the IOT instruction.
Fig. 36 A primitive ASM of the Operate instruction.
We prefer to use only one clock period to process the CLA bit and then go immediately to the fetch phase for the next instruction. Similarly, an RAR instruction involves a single priority-4 operation. We prefer to bypass the first three priority states and go directly to the fourth state. In general, we wish to process the highest-priority micro-operation, followed in order by lower-priority operations, without wasting clock cycles on unpopulated priorities.
We may formalize this priority-resolution problem by assuming that there exist four requests for service, RQSTI through RQST4, each representing one priority level. The requests are initialized prior to the execute phase of the Operate instruction, based on the pattern of bits in the instruction word. For example, if the instruction specifies IAC, a priority-3 operation, then RQST3 would be true after the initialization. If the highest-priority request (RQSTI) is true, the LD20 must perform the specified priority-1 operations and set RQSTI false; then if any priority requests remain, the LD20 must return for another pass through the execute phase of the Operate instruction. If RQSTI is false (which is possible the first time through, and will definitely be so the second time), then RQST2 is examined; and so on. Fig. 37 is a flowchart of this process.
The hardware for this scheme involves storage elements for the RQST terms; four flip-flops will serve. Also, we need the ability to determine if any priority requests remain after a pass, so that control may return for more processing of the instruction. We will define a variable MOREOP to be true when more processing is needed and false otherwise. We may test this variable at the end of each pass and act accordingly.
The ASM chart for managing
Operate instruction priorities is almost within our grasp. One final point needs study. The shift microinstructions (the "rotates") generate either a 1-bit or a 2-bit shift. The shift register building blocks described in Section 4 perform only 1-bit shifts per clock cycle, leading us to implement the 2-bit rotate operations as two I-bit rotates. This will mean looping twice through the priority-4 part of the Operate ASM. We need a flag to tell the ASM when a second pass through priority 4 is needed, so we will add to the architecture a flip-flop with output DOUBLE, to serve as a signal to "shift again." When DOUBLE is false, no more shifts are needed. When DOUBLE is true, another shift must occur, and DOUBLE, having served its purpose, must be reset to false. Bit IRIO = 1 specifies a double shift, and IRIO = 0 denotes a single shift.
We may initialize DOUBLE with the value of bit IR1O, once the instruction has been acquired but before the execute phase begins.
With these additions to the LD20's architecture, we may specify the ASM chart for the priority control of the Operate instruction. The execute phase for this instruction occurs entirely within state EO. Fig. 38 is the ASM counterpart of the flowchart in Fig. 37.
Fig. 37 The general flow of an efficient execution of the Operate instruction.
(This is not an ASM chart.)
Fig. 38 ASM of the Operate instruction's priority system.
Initializing the priority request flip-flops. To complete the processing of the Operate instruction, we must arrange to initialize the priority request flip flops prior to entering state EO. This must occur during Fetch, after the instruction reaches the instruction register IR. Examining the fetch-phase ASM, we see that there is only one place to do this-in term F3.1 of state F3. We will set or reset the request flip-flops (and also the DOUBLE flip-flop for shifts) at this point, according to the values of the bits in the instruction. These additions to the fetch-phase ASM appear in Fig. 39b; Fig. 39a contains the addition to state Fl for initializing the IOP enabler.
Individual microinstructions. We have conquered the Operate instruction priority system in an elegant way. There remains the specification of the individual micro-operations at each of the four priority levels. Except for the skip and rotate operations, the ASMs are simple. We have already developed a structure that will handle both single and double rotates. Let's examine the skip instructions.
Bit 8 of the Operate instruction specifies the sense of the skip logic. We may define a variable SKIP that will tell the LD20 whether the condition for a skip is met. In a group 2 Operate instruction, SKIP = T will mean that the LD20 must skip an instruction; SKIP = F will mean no skip. To aid the description of the logic, we require variables that indicate the three skip criteria: a zero accumulator, a minus accumulator, and a nonzero link. For the last condition, the value of the link bit suffices. In the PDP-8's two's-complement representation of numbers, bit ACO gives the sign of the number in the accumulator: ACO = 0 for positive numbers and ACO = 1 for negative numbers. We use a new variable (AC=O) to denote a zero accumulator; its implementation in terms of the bits of the accumulator is given in Section 8.
Fig. 39 Additions to the fetch phase of the IOT and Operate instructions.
Fig. 40 Fragments of the ASM of the Operate instruction .
Assume that a group 2 Operate instruction is in the instruction register and that the skip-sense bit (bit IRS) is O. Then we may describe the PDP-8's skip actions for this situation by a variable SKIPO:
SKIPO = SMA·ACO + SZA ·(AC=O) + SNL-LINK
If bit 8 is 1, then we may declare another variable SKIPI to express this condition:
SKIP1 = SMA·ACO + SZA·(AC -0) + SNL·LINK
The definition of the PDP-8's skip micro-operation expresses SMA as bit IR5, SZA as bit IR6, and SNL as bit IR7. Noticing that SKIP1 = SKIPO, we may combine these two conditions into a single equation for the skip operation:
SKIP = IR8·SKIPO + IR8·SKIP1
= IR8·SKIPO + IR8·SKIPO
= IR8 EB SKIPO
= IR8 EB (IR5·ACO + IR6 o (AC=0) + IR7o LINK)
We now have all the tools for describing the individual Operate micro operations. In Fig. 40 we show the ASMs of each of the four priority levels.
Fig. 41 Architecture of the LD20: main data paths; one of twelve 1-bit slices.
Fig. 42 ASM of the LD20's fetch phase.
Fig. 43 ASM of the LD20's execute phase, excluding the Operate instruction.
CONCLUSION
Now that we have derived the details of the LD20's architecture and control, it is desirable to collect the results into a more compact form. Fig. 41
shows the architecture of the main data paths in the LD20; each of the 12 bits has a similar diagram. (In Section 8 we will make one further refinement to this architecture to support possible expansions of the system.) In addition to this main data structure, the LD20's architecture at this point includes simple storage elements for the following variables:
LINK:
HALTFF:
INT. EN:
Link bit
Halt status
Interrupt enable
Fig. 44 ASM of the LD20's Operate instruction.
MANEX: Denotes that the execute phase was reached from IDLE
SING.INST: Synchronized single-instruction switch signal
RQSTi : Four priority request flip-flops for the Operate instruction
DOUBLE: Number of I-bit rotate micro-operations specified
The architecture also has a single-pulser unit with output MANPULSE, to denote the first full clock cycle after the depression of a manual pushbutton. The IOP signal enabler, consisting primarily of a shift register, completes the list.
Figures 42, 43, and 44 present the LD20's ASM in three charts: the fetch phase, the execute phase, and the complex Operate instruction. These three ASM charts will be of great use in Section 8.
This completes the specification of the architecture and the control for the LD20. The implementation lies before us! This will involve:
(a) Deriving the logic equations for the ASM outputs.
(b) Developing the state generator.
(c) Specifying the hardware for the architecture and converting the ASM output equations to fit the exact integrated circuits.
(d) Specifying hardware for the control logic and the ASM outputs.
READINGS AND SOURCES
BELL, C. GORDON, J. CRAIG MUDGE, and JOHN E. McNAMARA, Computer Engineering A DEC View of Hardware Systems Design. Digital Press, Bedford, Mass., 1978. Section 8 discusses the history and structure of the PDP-8 family.
KUCK, DAVID J., The Structure of Computers and Computations, Vol. 1. John Wiley & Sons, New York, 1978.
MANO, M. MORRIS, Computer System Architecture, 2nd ed. Prentice-Hall, Englewood Cliffs, N.J., 1982.
PDP8/1 and PDP8/L Small Computer Handbook. Digital Equipment Corp., Maynard, Mass., 1972. User's manual for the PDP-8I minicomputer.
PROSSER, FRANKLIN, and ROBERT WEHRMEISTER, C421-C422 Advanced Computer Organization Laboratory Manual. Computer Science Department, Indiana University, Bloomington, Ind. 47405, 1985. Laboratory manual to support the construction, debugging, and study of the LD20 and LD30 implementations of the PDP-81. The laboratory project uses the Logic Engine Development System, manufactured by Logic Design, Inc. Ask the authors of this guide for information.
EXERCISES
1. What determines the maximum number of words in the PDP-81's memory? What determines the size of a memory page? What two pages of the PDP-8I are directly accessible from an instruction? What memory locations are accessible using indirect addressing?
2. Here are the contents of six words of PDP-8 memory. Treat each word as an instruction and give the command, the effective address EA, and, where appropriate, the contents of the effective address CA. All numbers are in octal.
(0061) = 0261 (0071) = 0061 (0342) = 3245 (1000) = 5725 (1015) = 2600 (2410) = 1471
3. Some computers allow multilevel indirect addressing, such that each word used as an indirect address can specify an additional level of indirect addressing. Why is this not possible in the PDP-8?
4. Explain the PDP-8's auto indexing. Here are the contents of three memory locations (all numbers are in octal): (0016) = 0016 (0017) = 0016 (0020) = 0016
Starting always from this point, show the results of executing each of the following instructions:
(a) 0417 (b) 0420 (c) 0416 (d) 2016 (e) 2416 (f) 2420
5. Describe the PDP-8's interrupt mechanism. How is an interrupt request conveyed to the PDP-8? What does the machine do if it detects an interrupt request? How can the programmer control the issuing of interrupts? What are the programmer's responsibilities for processing an interrupt?
6. Explain why the PDP-8's ION (Interrupt System On) command does not take effect until after the execution of one additional instruction.
7. What is meant by a static design? Why is this such a valuable attribute of a digital system?
8. List the principal elements of the LD20's architecture. Which of these elements may the LD20 programmer directly manipulate?
9. Why does the LD20's architecture have the accumulator register as the sole source for one of the two ALU inputs?
10. Why is the instruction register IR not attached to the LD20 data multiplexer as a source?
11. Design a three-state data bus for the LD20, to replace the multiplexer bus control system used in the text.
12. What are the principal types of commands needed to control the LD20 architecture?
13. What is the principal function performed by the fetch ASM? The idle ASM? The execute ASM?
14. This exercise takes you through most of the fetch ASM and parts of the execute ASM. Assume the following (numbers are in octal):
HALTFF = INT = F
(0010) = 2221 (0200) = 2222 (2222) = 1111
(AC) = 1234 (PC) = 0305
Starting from state Fl, trace the LD20's ASM operations in each of the following cases.
(a) (0305) = 5200 (b) (0305) = 3200 (c) (0305) = 0200 (d) (0305) = 0600 (e) (0305) = 0410
15. This exercise takes you through the major sections of the execute ASM. Assume that (MA) = 0200 and (MB) = 2222. Trace the ASM flow from state EO to state Fl for each of the following instructions. (X means "irrelevant." All numbers are in octal.) (a) (IR) = 1XXX (b) (IR) = 2XXX (c) (IR) = 4XXX (d) (IR) = 6XXX
16. This exercise takes you through the operate section of the execute ASM. Trace each of the following instructions from state EO to state Fl. The numbers are in binary.
(a) (IR) = 111 011 000 001 (b) (IR) = 111 000 100 001 (c) (IR) = 111 000 010 111 (d) (IR) = 111 101 001 010
17. Make a table showing the sequence of fetch-phase states for each distinct form of the eight PDP-8I instructions. Also list the total number of memory references required in each case (including memory references in the execution phase).
18. Why does the LD20 not process an interrupt request immediately upon its assertion?
19. Explain carefully the significance of the three terms in the interrupt generation signal:
INT = INTREQoINT.ENoWN
20. In the LD20 ASM, is it feasible to move the test for interrupt from its present position in state Fl into state F2?
21. Give a specific illustration to show why we must save the LD20 program counter (in state Fl) for later use in computing the effective address EA. Why not use the value in PC at the time EA is generated?
22. What is the latest point in the fetch ASM that we may place the PC (+) 1 ---'? PC operation?
23. Refer to the memory control interface in Fig. 16. Carefully state the difference between the similar labels inside and outside the box.
24. Explain the memory accessing protocol of the LD20 as displayed in Fig. 20. What are the conditions under which this protocol works?
25. Redraft the LD20's fetch phase using the basic read protocol of Fig. 17. Can you see a strong argument against using this memory control ASM? 7-26. State two ways in which the LD20 user may cause the machine to halt.
27. Why is it desirable that the RESET* pushbutton signal perform an asynchronous reset of the LD20?
28. Show why the asynchronous CONT* input in the IDLE state does not need to be synchronized with the LD20 system clock.
29. The most complex processing in the fetch phase involves a memory-referencing instruction that employs indirect addressing and auto indexing to fetch an operand.
The minimum number of fetch-phase clock cycles for such an instruction is 11.
(a) Give an example of a PDP-8 instruction that requires at least this number of LD20 clock cycles.
(b) Verify from Fig. 42 that 11 clock cycles are minimal for this type of instruction.
(c) Can you find a way to shorten the number of clock cycles by modifying the fetch ASM? (Hint: Look at state F6.)
30. With the present architecture of the LD20, why can't we eliminate state F2 by including F2's actions in a conditional output of state F1?
31. Suppose you wish to reduce the number of states in the LD20's fetch phase (Fig. 42). (a) Collapse states F2 and F3 into a single state that performs actions equivalent to the former two states.
(b) What are the disadvantages of the collapse in part (a)?
32. Suppose that all the F ---'? MANEX commands in the execute phase were replaced by a single unconditional F ---'? MANEX in state EO. What would be the effect on the execution of the LD20 ASM?
33. (a) With the present LD20, show what happens if an operator depresses a manual pushbutton such as LDAC while the LD20 is not in the IDLE state. (b) Answer part (a) assuming that the entire MANEX signal is deleted from the ASM.
34. The LD20's manual operations are performed in the execute phase, like regular instruction processing. An attractive alternative would be to perform manual push button executions in a manual phase, using states separate from Execute.
(a) Develop an LD20 ASM with such a manual phase.
(b) What simplifications does this form of LD20 ASM introduce? (c) What disadvantage of this form of ASM can you see?
35. State E2 may be eliminated from the LD20 ASM. Eliminate it. What are the advantages and disadvantages of this elimination?
36. Design a detailed ASM for the LD20's Operate instruction along the pattern of Fig. 36. Discuss the advantages and disadvantages of this primitive approach.
37. Modify the ASM of the LD20's Operate instruction to replace the two-position rotate flag DOUBLE by a fifth priority level, RQST5.
38. The LD20's algorithm for the IOT instruction always makes three passes through states E3, E4, and E5, regardless of the number of IOP signals requested by the instruction. Modify the LD20's ASM so that E3, E4, and E5 (or their equivalent) are executed only When the LD20 asserts one of the IOP signals.
39. Suppose the PDP-8 IOT instruction protocol is altered so that the computer issues all requested IOP signals at one time. How will this affect the LD20's ASM?
40. Combine states E3, E4, and E5 for the IOT instruction into a single state that performs activities equivalent to the former three states.
Related Articles -- Top of Page -- Home