The following is an HTML version of the Instructor's manual for Computer Organization and Assembly Language Programming by James L. Peterson, published by Academic Press, 1978. The Instructor's manual was originally published in 1980 (ISBN 0-12-552252-5). It is mostly a faithful reproduction of the content of the original printed book, with the exception that it has been modified to match the current HTML version of Computer Organization and Assembly Language Programming. The main difference is that all exercises are identified by number (1, 2, 3, ...) instead of their original mixture of numbers and letters (a, b, c, ...).

THE DESIGN OF A MIX SYSTEM

1.0 INTRODUCTION

MIX was introduced by Knuth [4,5,6,7] in 1968 to aid in the analysis and description of computer algorithms. It was designed to be like most machines, but not to be any particular machine. It has been used throughout the three volumes of The Art of Computer Programming [4,5,6] which have been written, and has also been adopted by some universities for the teaching of assembly language programming [3,11].

1.1 MIX For Teaching

The MIX machine is by no means ideal for teaching introductory machine organization and programming. Its major alternative is the use of a real machine. With the decreasing cost and increasing availability of minicomputer systems, the potential for teaching with a real computer system, such as the PDP-11, HP 2100, or other minicomputer, improves. Most textbooks for this subject are aimed more toward using a real computer than a simulated one. The PDP-11 in particular is a very popular choice.

1.2 Teaching A Real Machine Or Teaching MIX

It has been argued, however, that the use of a real machine has as many potential disadvantages as advantages. Specifically, although the IBM 370 and the PDP-11 computer systems (which are most commonly used for teaching assembly language programming) are quite common machines, a student is just as likely to end up programming on a computer from Univac, CDC, Data General, Interdata, or any of a number of other computer manufacturers, or even other architectures from IBM or DEC (such as the Series 1 or PDP-8 or DEC-10). Thus, what is important is the basic programming techniques and understanding, not a specific programming language. There is also the problem of programming features or quirks peculiar to the specific machine being used.

Accessibility is another potential problem. Either students must have sole use of the machine, or they must share it with other users. Sharing will necessitate the use of an operating system, which will both deny the student access to the real I/O instructions and require that operating system topics, such as system calls, file descriptor blocks, and so on, be discussed rather than the basic I/O concepts of the underlying machine. Thus, use of a large multiprogrammed campus computer is providing a simulated machine to the students; the simulation is defined by and provided by the operating system.

Using a small dedicated minicomputer system to provide the students with the ability to access and control the entire machine without operating system interference may cause other problems. One is the requirement for hardware maintenance, and the disruption of hardware failures. A simulated machine such as MIX can be made available on all computers on campus, allowing the job load to simply shift temporarily to any available backup computer system, even one remote from campus, if necessary. Another problem is caused by the cost of providing sufficient machine resources for the typically large number of students in an undergraduate assembly language course. A simulated machine can, of course, be run in a shared mode on a large fast system.

One last advantage of a simulated machine is the ability to know exactly what the system does in all cases, since the program listing is available for inspection. The only recourse for a real machine may well be an examination of the actual circuit diagrams which may themselves be either incorrect or vague. (I once worked with a machine with an instruction which moved the program counter into an index register. None of the manuals indicated when the program counter was updated, however, and our engineers never were able to decide either. Empirical testing indicated that either it was a rather complex function of the previous, current, and next instruction, or a race condition.)

Other considerations, such as simplicity, textbooks, cost, and so on can also be argued [3].

2.0 MIX SIMULATION SYSTEMS

All of the purported advantages of a simulated MIX computer, however, depend upon the existence of a MIX simulator. Since a MIX system requires a computer, and the computer probably has an assembler but probably does not have a MIX system, it is often easier to teach the available assembly language rather than construct a MIX system. The alternative to constructing your own MIX system is of course to import a MIX system written elsewhere.

Many MIX systems have been written, with various success and various capabilities. A MIX system written in 360 assembly language exists at Stanford [8]. Another system for the 360 is used at UCLA [2] and another at Central Missouri State College [9]. These are written specifically for the IBM 360/370 architecture, and could not then be moved to another computer, but should be able to be moved to another 360/370 site. Another system was written at the University of Texas [3,10] for CDC 6000 series computers, but it is written in a mixture of assembly language and an obsolete systems programing language for a locally developed operating system, so movement of the simulator even to similar computer systems is almost impossible.

Systems developed primarily for their portable nature include a Fortran system at the University of Wisconsin [12] and one at the University of British Columbia [1]. The latter system has several documents which explain the system and how to transport it. Additional systems may also be available.

3.0 MIX SYSTEM WRITING

Writing a MIX system is not a particularly difficult task, however, and we would encourage you to seriously consider writing your own. Knuth has given a portion of the system and discussed the general approach, in Volume One [4]. Writing a system does require some time and care. The resulting system is typically large (some 70 pages for [1] and around 100 pages for [10]). Since it may exist for some time and may need to be moved from machine to machine, it should be well documented, modular, transportable, but also efficient in both time and space. Writing such a program is a good exercise in software engineering.

The most crucial part of a successful simulator system is a good basic design. The basic design of the system is implementation independent. A clear view of the complete design of the MIX simulator is very important for a successful product. This paper presents a top-down design for a MIX system. The design is presented only generally, in a narrative English, supplemented by some occasional Pascal-like data definitions and flow of control. We are mainly interested in the overall system design, and its components. Certain of these components, such as the assembler and the instruction execution simulator, have been adequately covered elsewhere [4,11], and we simply refer you to those references for that portion of the design. However, the entire system is composed of more than these two parts.

It is intended that the design presented here can be and will be freely implemented in many different languages by many different people on many different computers.

4.0 A DESIGN FOR A MIX SYSTEM

The most common problem with MIX systems is an incorrect assumption that the cpu instruction execution is the primary part of a MIX system. To the contrary, instruction execution is a minor portion of the simulated system. Figure 1 shows the hierarchical structure of our system design.

At the highest level, the MIX system consists of several parts. The MIXAL assembler reads an assembly language program and assembles it into MIX memory. The MIX computer system executes the program which is in MIX memory. MIX memory is the interface between the assembler and the computer system.

The flow of control between these two components is the main program of the MIX system. It can be written as simply as,

     BEGIN
          Zero MIX memory;
          Assemble a MIXAL program;
          If there are no assembly errors,
             Then execute the MIX program;
     END.

4.1 MIX Control Cards

An alternative, more complex but more general, MIX system uses MIX control cards to determine the flow of control between the components of the MIX system, rather than using a fixed flow of assemble/execute/quit. In this case, the general MIX system flow of control would be,

     BEGIN
          Zero MIX memory;
          While there are still more MIX control cards,
             do begin
                     get next control card;
                     Case control card type of
                           Assemble;
                           Execute;
                             ...
                     end Case;
          end While;
     END.

The design of the control card system must obviously be determined at each site, according to the normal usage at each site. Typically control cards are identified by a special character ($, @, ! or such) in the first column of an input line. This is followed by a keyword identifying the next step to be performed, and optionally, some parameters. A typical set of control card functions might include:

• $MIXAL - identifies the following cards as a MIXAL assembly program which is to be assembled into MIX memory. Possible parameters include: listing control, assembly time and line limits, input and output file locations, etc.
• $RUN - starts (or restarts) the execution of the program in MIX memory if there were no assembly errors. Data would normally follow this card. Possible parameters include: time limit, line limit, location of input data or output results, starting address, etc.
• $GO - simulate the GO button of exercise 1.3.1-26 of [4].
• $DUMP - prints MIX memory onto the output device. The output dump would be for debugging purposes and might include register contents and memory contents in octal, decimal, character or instruction format. Options would indicate first and last word addresses and format.
• $TRACE - turns on a tracing debug feature. Parameters might indicate which words are to be traced.

Other control cards might also be necessary or desired.

5.0 THE MIXAL ASSEMBLER

The MIXAL assembler has been discussed in great detail elsewhere [11], and we refer the reader to that discussion. Suffice it to say that the MIXAL assembler assembles the input MIXAL program into a MIX machine language program in MIX memory. The assembler produces a listing on the output device and preferably a cross reference listing also. The assembler may be one-pass or two-pass, may be extended to include additional pseudo-instructions, macros, conditional assembly or whatever is desired. The important feature of the assembler is that it is essentially self-contained and interfaces with the remainder of the MIX system through a small number of well-defined variables such as,

1. MIX memory.
2. The starting address (may be passed in the program counter).
3. The number and severity of assembly errors.

6.0 MIX MEMORY AND REGISTERS

MIX memory is an extremely important aspect of a MIX system. It is very important that the representation of the memory be very carefully thought out. We would recommend strongly that information hiding techniques be used to encapsulate the actual representation of memory and hide it from all other routines in the system.

In the abstract, of course, the definition of MIX memory is quite straightforward.

     MIX memory: array [0..3999] of MIX words;
     
     MIX words = record
                     sign: (positive, negative);
                     array [1..5] of byte;
                 end record;

In fact, efficiency in time and space demand a more complex representation of memory. At the least, bytes should be packed to minimize memory usage. In the Stanford MIX system, a decimal machine, each MIX word occupies a double word (8 bytes, 64 bits). The UT-MIX system stores six 6-bit quantities in one 60-bit word, with the high-order 6-bit byte being either 0 (a positive sign) or 63 (a negative sign). John Baker's MIX system uses the lower 30 bits of a word to represent bytes 1:5 of a binary MIX word and the next bit to be the sign (0=positive; 1=negative). The major problem with all of these is the need for a minimum of 31 bits per word.

On a 16-bit minicomputer or an 8-bit microprocessor, alternative schemes may be needed. One approach is of course simply to use multi-word programming techniques to simulate a 32-bit word from four 8-bit bytes, in which a MIX word is then packed. For a binary MIX machine, this may require considerable shifting and masking, since the five 6-bit bytes will not be conveniently aligned within the four 8-bit bytes. An alternative scheme (also needed for decimal MIX machines) is to store each 6-bit MIX byte in one 8-bit machine byte. This leaves at least one bit per byte left over. One of these can be used as the sign, and others can be used for debugging flags, if desired. The Stanford MIX system uses some extra bits to catch accesses to undefined memory locations, and to locations which are currently being used for input or output.

Probably the most important attribute of the MIX memory should be the limited access allowed to it. Ideally, MIX memory should be treated as an abstract data structure, and all accesses to it should be made through a very small number of routines. The most obvious candidates would be a STORE(address,value) and a LOAD(address,value) pair of routines which would load or store the value to or from memory[address]. An alternative, or complementary, set of routines would be

     LOADBYTE (address,value,L,R)
     STOREBYTE (address,value,L,R)

With proper design and restraint on the part of the programmer, only these two routines, and the routines to perform arithmetic and comparison operations on MIX words need ever know how memory is represented. Such an approach would thus allow the memory representation to be easily changed, if this were desired.

7.0 THE MIX COMPUTER SYSTEM

As indicated in Figure 1, the MIX computer system is itself composed of several separate parts. The reason for this decomposition is to allow the representation of realistic parallelism between the input/output system and the central processor unit. While it is easiest to write a MIX simulator which ignores I/O-cpu overlap, this prevents the programmer from learning about this very important part of assembly language programming.

The most appropriate programming technique to use for controlling the computer simulation is an event-driven simulation. This is possible because all events in the MIX system are deterministic in their time behavior.

As an example, assume that the cpu is computing along, and executes an IN instruction for the card reader, with the current clock at 1274 MIX time units. The IN instruction takes one MIX unit moving the clock to 1275. If it takes 1000 MIX units to read a card, then the card reader will be busy until 2275. So we post the event "card reader done" to occur at time 2275. The cpu then continues with the next instruction. If the next instruction is an OUT to the line printer which takes 1200 MIX units to print a line, we post the event "line printer done" for time 2476. If the next instruction, after the OUT, were an IOC to tape unit 0, taking 400 MIX units to rewind tape 0, we post another event "tape unit 0 done" for time 1677. Now we continue executing instructions until the first posted event occurs. As the clock ticks, each event must be handled at the appropriate time.

An event driven simulation requires only that every time the clock is advanced, the current clock value is compared against the posted time for all pending events, and if it is time for any event, that event should then be handled. A simple implementation of this uses an event queue. The event queue is a list of all pending events. Posting an event means entering an element into the event queue. Events are taken off the queue when it is time for them to occur. Each event is described by a record which would contain,

1. the scheduled time for the event
2. the type of event
3. other parameters (such as device unit number)
4. a pointer to the next pending event

The queue should be kept sorted by scheduled time of events. This reduces the search time to find the next event to occur. Entry into the queue requires a sorted entry (insertion sort should be adequate). The time of the next pending event is the time of the event at the front of the queue. This allows the general flow of the MIX computer system to be:

While the computer is not halted
   do begin

       while the queue is empty
          or the next event time in the queue > clock
          do execute the next instruction;

       remove the event at the front of the queue;
       case event of ... end case;

     end while;

Some problems with this approach can still exist for the purist. The design given above does not allow events to occur except between instruction execution. Consider an event scheduled to occur at time 4201, with the current clock value being 4200. Since it is not yet time for the event, we execute the next instruction. If the next instruction is, say, a MOVE of 24 words (taking 49 time units), the clock value will be 4249 before we check the front of the queue again. Thus the scheduled event may occur late. In most cases this does not matter, but if the late event creates a new event, what time is used for the new event? Does it occur a fixed amount of time after the late event should have occurred (its scheduled time) or its late time? This can be a complicated question.

Consider the case of the event being an input or output of one word to or from memory, such as is suggested below. Words are moved between the I/O system and memory at regular intervals (the transfer time divided by the number of words per record). Thus, without the problem mentioned above transfer would happen at time k, k+t, k+2t, k+3t, ... If the transfer at time k occurs at time k', are all later transfers rescheduled? Consider that for memory reference instructions or MOVES, memory referencing would in fact be delayed, either for the cpu or the I/O device because of memory interference, but for shifts, MUL and DIV, only the first time unit (corresponding to instruction fetch) could cause interference; at any other time cpu processing and memory referencing for I/O would occur in parallel. Also note that on most systems, I/O has priority over cpu memory references.

Correct simulation at this level of detail is rather difficult and requires the MIX memory access routines to check the event queue for I/O transfers whenever access to memory is made by the cpu. It is felt that this level of detail is unnecessary and would overly complicate the simulator.

8.0 INPUT/OUTPUT DEVICE SIMULATION

Each I/O device should be represented by a description in the I/O device array. As defined by Knuth, only 20 devices are possible, although the architecture clearly allows up to 64 devices. A device descriptor would be indexed by the device unit number and probably contain at least the following information:

1. device name
2. device type: (card reader, tape, disk, ...)
3. device record length
4. device buffer (of the appropriate length). All actual I/O would be between the host machine operating system and this buffer. Words would be transferred between here and MIX memory at appropriate times.
5. device existence (exists/does not exist for this configuration)
6. device status (busy/ready)
7. time when device will be ready
8. other device state information

The device event routines will vary from device to device, but they can all be written in much the same form. For an I/O instruction which transfers between MIX memory and an I/O device, the simulator should transfer words one at a time between MIX memory and the device buffer in the descriptor record. Each device would transfer words at regular intervals with a possible start up delay and a stop delay. Suitable values for start-up, stop and word transfer times can be determined by examining times for I/O devices for typical minicomputers.

These three times would also typically correspond to the actions that must be taken by the simulator. For example, for an IN instruction, the first event would be the IN instruction. This would require the appropriate host I/O to read the next MIX record into the device buffer (in the descriptor). We would also need to compute and save the effective address in MIX memory to transfer to, and set the device status busy. This corresponds to the start up delay. An event "transfer i^th word into memory[address]" would be posted to occur after the start up delay, with i=1 and the address being the effective address.

When the event "transfer i^th word into memory[address]" occurs, the i^th word would be transferred from the device buffer into MIX memory. Another event "transfer i^th word into memory[address]" would be posted to occur after a transfer delay time with i and the memory address incremented by one, unless the value of i corresponds to the last word in the input record. In this case, we would post an event "device j input is complete" to occur after a stop time delay. The "device j input is complete" event merely clears the device status back to ready and any other necessary clean-up.

Output is similar.

An alternative to this approach is to schedule all of the transfer instructions to occur at their respective times when the IN or OUT instruction is executed. The difference between these two approaches lies in the size of the event queue. In the first approach, only one event per device will be scheduled, but that event may cause a new event to be scheduled. In the second approach, 16 or 24 or 100 events may be scheduled per device at one time, but none of these events will create any new events.

From this discussion, we can see that the following events would probably be sufficient:

"IN instruction", device, address
"OUT instruction", device, address
"IOC instruction", device, address
"move word in", device, word number, address
"move word out", device, word number, address
"I/O operation complete", device

The simulation of card reader and line printer devices should present no real problem, but tape and disk drives may require careful thought. A magnetic tape device can be simulated by most sequentially accessed files. Simulating a disk or drum, on the other band, would require both random access files and the language features to access them. If the simulator is implemented in Fortran, such random access files are non-standard, and hence the system will not be transportable. Also, operating system conventions for creating, opening, closing, and deleting the files for these devices may be quite tiresome and clumsy. If at all possible, however, the system should simulate at least a few tape and/or disk drives. I/O device timing is an area which allows some creative programming. As mentioned, most devices can be characterized by a word transfer time and (possibly zero) start and stop times. These times can be determined by guess, or by examining manufacturers' literature for typical small machine peripherals. The IN and OUT instructions are thus quite straightforward. The IOC instruction, on the other hand, can be quite interesting.

1. Line Printer - IOC 0 means skip to the top of the page. The time for this is a function of the distance from the top of the page, in lines. IOC n (skip n lines) is a function of n. Both suggest the need to count output lines to keep track of the current output line.
2. Magnetic Tape - IOC 0 (rewind) is a function of the current position of the tape. IOC n or IOC -n (move tape n records forward or back) is a function of n. Notice that IOC n can be difficult to simulate in some systems with sequential files and might then be best simulated with a direct access file.
3. Disk - An IOC (seek) takes a time which varies according to the current position of the head and the desired position (in the X register) of the head. Introducing rotational delay for IN and OUT instructions as well as head movement delay could be complex.

9.0 THE CPU INSTRUCTION INTERPRETER

The cpu instruction execution unit is a simple standard simulator. Knuth sketches the design of such a simulator in 1.4.3 of [4]. We would remark only that the optional instructions and features (binary instructions, indirect addressing, floating point instructions) can be added to make the system more complete.

10.0 DEBUGGING FACILITIES

What debugging facilities are to be provided for the user of the MIX system? Remember the MIX is basically an educational system, and so careful thought is needed concerning debugging facilities. The following might be considered:

1. Dumps - Either partial or full dumps of MIX memory should be available whenever a fatal error occurs during execution. It may also be necessary to dump on command from the user. MIX memory is small enough that a complete dump may be reasonable, particularly if some scheme is used to avoid printing sequences of identical lines (like first identical, ..., last identical), and if MIX memory is initialized to zero.
2. Traces - A line by line trace of instruction, program counter, register contents, clock, effective address, and contents of the effective address (where appropriate) should be available when requested. An interesting possibility used in the Stanford system [8] is to trace any location at most a fixed number of times (default was 2). This prevents long loops from being followed too often but generally gives enough information to find errors. This would require a counter with every instruction in MIX memory, but the counter would also allow an execution profile to be provided showing how often each instruction is executed.
3. Snaps and Breakpoints - These are dumps and traces triggered by a specific program counter value. For example, a breakpoint at a particular location will cause a line of trace every time that instruction is executed; a snap will dump an area of memory every time a specified instruction is executed.
4. Memory Monitoring - A common problem is the mysterious store which destroys the contents of a location but the programmer does not know where the store is (typically it is an indexed or indirect store, or an incorrectly modified instruction). Monitoring a particular memory location will produce trace and dump information whenever the specified location is read or written (as selected).
5. Execution History - Another common problem is the fatal error which terminates the program with the program counter being either a data location or undefined memory. Some help on this can be obtained by providing the user, upon request, with a history of the instructions executed before the fatal error. This can be in the form of a complete backwards trace of the last n instructions, or a list of the last n jump addresses (address of jump and address jumped to) allowing the user to deduce the probable flow of control into the unknown.

All of these debugging aids can obviously be much more effective in a time-shared interactive environment. Notice that the change from batch to interactive use is only a change in the MIX control card input source and output device.

11.0 CONCLUSIONS

We have sketched the basic design of a complete MIX system, giving the major component pieces and mentioning the major problems involved. Still much work will need to be done by the programmer. Actual code has not been given here, since that is very machine and language dependent. However, the overall design should be clear. The remainder then is mere implementation.

12.0 REFERENCES

1. Baker, J. L., "A MIX System", notes, Department of Computer Science, University of British Columbia, 1974.
2. Braden, R. T., "MIX Users Guide", Campus Computing Network, UCLA, 1975.
3. Greenawalt, E. M., and Good, D. I., "The MIX Computer as an Educational Tool", ACM National Conference, 1972.
4. Knuth, D. E., The Art of Computer Programming, Volume 1: Fundamental Algorithms, Addison-Wesley, 1968, Second Edition, 1973.
5. Knuth, D. E., The Art of Computer Programming, Volume 2: Seminumerical Algorithms, Addison-Wesley, 1971.
6. Knuth, D. E., The Art of Computer Programming, Volume 3: Sorting and Searching, Addison-Wesley, 1973.
7. Knuth, D. E., MIX, Addison-Wesley, 1970.
8. Knuth, D. E., and Sites, R. L., "MIX/360 Users Guide", STAN-CS-71-197, Computer Science Department, Stanford University, (March, 1971).
9. Ohlendorf, M. W., "CMSC MIX: A Simulator System for the MIX Computer", Master's Thesis, Department of Computer Sciences, University of Texas, (August, 1972).
10. Peterson, J. L., "UT-MIX Reference Manual", TR-64, Department of Computer Sciences, University of Texas, (January, 1977).
11. Peterson, J. L., Computer Organization and Assembly Language Programming, Academic Press, 1978.
12. "MIX Users Guide", Computer Sciences Department, University of Wisconsin, (January 1970).
13. Dale, P. B., Margolin, C. G., and Williams, G. H., "MIX and MIXAL (A User's Manual)", Computation Center, Union College, Schenectady, New York, 1975.