Programming MOSAICEdward Smith |
Introduction
MOSAIC (the Ministry of Supply Automatic Integrator and Calculator); did not have a formal symbolic assembly language, however a structured numeric method of representing instructions was devised, to remove the need for coding using binary formats. This approach was documented in the Programming for MOSAIC document (RRE Memorandum 1270), which is the nearest equivalent to EDSAC’s Wilkes, Wheeler and Gill document.
MOSAIC was part of the ACE lineage of computers and was based on version VII of Turing’s logical architecture. Like EDSAC, its storage system utilised mercury delay lines, but in contrast to EDSAC the programmer had to manage the timing challenges associated with delay line memory himself. There is no equivalent of the Sequence Control Tank and both instructions and data are addressed as a function of the current minor cycle and the selected delay line. MOSAIC had 63 usable long delay lines of 16 words (40 bits per word), 28 short lines of one word and three double lines of length two words.
Instructions were executed in two phases, the setup phase lasting one minor cycle and the obey phase, which lasted between 1 and 16 minor cycles. (A minor cycle was the time taken for a 40 bit word to circulate in a short delay line. A major cycle was 16 minor cycles or the time taken for a bit to traverse a long delay line). The programmer had the responsibility for organising his storage allocation, so that the computer spent as little time as possible waiting for a memory location to become available.
MOSAIC Overview
A description of MOSAIC is given in Resurrection101. In summary, the machine used 7,000 valves mounted in 12 standard Post Office racks and offered storage in the form of 63 long mercury delay lines, three double word lines and 28 single word short delay lines. The design was based around maximum hardware simplicity, even where this required the use of additional valves. Valve faults were comparatively easy to resolve compared with the issues involved in fixing issues with complex circuit failures. Speed of operation was paramount, even if this led to additional complexity for the programmer.
)
|
| Figure 1 – Format of the MOSAIC instruction word |
An instruction was represented within a 40 bit word, using the format shown in figure 1.
For example, the instruction to add the contents of short delay line 4 to those in short line 5, place the result in short line 6 and take the next instruction address as long line 27 is binary 0/1001/0010001/0/1010001/1/0110001/0/1011/10/11011. The function code of 1011 is the add function. (Note that MOSAIC numbered bits from the left to right, with the rightmost bit being the most significant.) The instruction is executed immediately (Go bit set), with the instruction execution being deferred, as indicated by the “α” bit being set, by the 9 minor cycles specified in the timing field. The 7 bit addresses are 0-63 (long lines), 64-95 (the 28 short lines and four double lines) and values greater than 95 as used for specific functions.
The two bit characteristic codes define the mode of execution as:
- Immediate (characteristic=0) – The execution started on the first obey cycle and continued for a further n minor cycles, where n is the timing count. Once execution had finished the next instruction could be setup and then executed.
- Deferred (characteristic=1) – The instruction executed for one minor cycle, scheduled for n+1 minor cycles after the setup beat.
- Forced Discrimination (characteristic=2) – was a type of immediate instruction, with discriminate (a one minor cycle delay) automatically applied so that Setup for the next instruction occurred n+2 rather than n+1 minor cycles after the setup beat. No instruction was executed during this additional cycle.
- Serial (characteristic=3) – For this the Obey Instruction Beat was 16 minor cycles with a gap of n minor cycles before the single execution minor cycle took place.
)
|
| Figure 2 – format for encoding an instruction in decimal form |
Input routines were developed that allowed instructions to be entered in a more symbolic fashion than a linear sequence of bits. Decimal coded instructions were punched one to a card and encoded using columns 11-28 and 10 rows of a single card. Using this convention, the instruction described above took the form given in figure 2. This method labelled long lines 0-31 as decimal 0-31 and 32-63 as 100-131; the short and double lines were signified as 200-231 and the special sources and destinations referred to using 300 and above.
The functions available were:
- Null (No operation).
- Signed and unsigned multiplication.
- Logical functions of AND, XOR and OR.
- Add functions that suppressed the carry on even, odd, all or no minor cycles.
- Subtract functions that suppressed the carry on even, odd all, or no minor cycles.
- A delay function which was effectively a right shift of up to 47 bit positions. Each shift position was a doubling of the number at the source 1 address.
The machine had a hardware multiplier which took up to 82 minor cycles to complete an operation. The results of the multiplication were held in a double delay line (the accumulator), labelled 231. (The other two double lines 228, 229 could be separately addressed and delay line 230 was a special address, which when loaded would automatically add its contents to the multiplier accumulator).
All operations were integer operations, any requirement for floating point being managed by the programmer defining the location of the decimal point in the data word and interpreting this consistently across the execution.
Programming Conventions
Programs were written using two mechanisms known respectively as the structure diagram, which incorporated flow charting techniques and the storage or sequence diagram. The structure diagram laid out the instructions in the order in which they were to be executed. This set out the logical flow of the program. The storage diagram allocated each instruction to a memory location determined by the timing, characteristics and Next Instruction Source of the previous instruction and the desired execution flow.
The final code once produced was encoded onto punched cards and was then verified by the programmer, who corrected any mistakes.
The efficient placing of instructions in storage, to make the best use of machine cycles, was known as Optimal Programming and gave the programmer greater control over the efficiency of execution; at the expense of complexity of programming.
Indexing
At the simplest level, MOSAIC could carry out simple vector manipulations without recourse to modification of instructions. For example just to add the contents of a five element array could be done using a single instruction:
031 13 201 1 201 004 003
Timing the first obey cycle to reference the first element of the array in delay line 31, then for the next five cycles, the contents of delay line 31 are added to the contents of short delay line 1 giving their sum. This is shown in figure 3.
)
|
| Figure 3 – changes in memory during execution or instruction summing the contents of a vector (both the start value and the end value are shown for the short line.) |
)
|
|
| Figure 4 – accumulating the modulii of a 16 element vector |
More sophisticated operations may require address manipulation as shown in the example below, where in an array held in delay line 32, the moduli of each element are added together in short line 2. This is shown in figure 4:
This example utilises conditional branches, special source and destination addresses, which will be described later. Short line 1 is first cleared, since this will be used to accumulate the sum of the array elements. The template of the instruction that will be used to extract the desired element from the vector is then loaded (but not executed) into short line 0. Instruction 4, then selects the instruction in short line 0 as the next instruction to be executed, before adding 1 to its count field. The instruction in short line 0 is a serial instruction and takes 16 obey cycles to execute, only transferring data from the vector specified in the source 1 field (long line 32) to short line 2 during the minor cycle specified in the count field.
Once this instruction has completed, the sign of the result is checked; if it is positive, it is added to the total in short line 1; if on the other hand it is negative then it is subtracted from the total, effectively adding it to the total in short line 1. The final stage is to check the effect of shifting the instruction in short line 0 33 places to the right. If the count has been incremented beyond 16, then it will have overflowed into the source 1 field making the shifted number negative. In this case the operation is complete, if not processing loops back to step 4.
This style of operation is clearly not for the faint hearted. It is possible to view the template instruction held at location 4 as an indexing mechanism; however the MOSAIC architecture did not explicitly accommodate an index register.
Special Sources and Destinations
In MOSAIC, special sources and destinations had specific meaning and were labelled using a value of 300 or more. Such sources or destinations were used in three cases; the first was the instruction to branch on negative or branch on a zero result. This has been alluded to in destination 301 in figure 4, as a test for a negative number. The second was for the loading of common bit patterns or numbers into store and the third was to allow and control input from the card reader and output to the card punch, both these functions being provided by a modified BTM tabulator device. An additional output device was a teletype writer device. Sources or destinations of zero had specific meanings (some are described later).
Jumps and Branches
Programs have two controls that when used together allow unconditional branching within a program, the timing count and the next instruction field. In programming, the completion of one instruction normally dictates where in storage the next instruction should be placed. However, it is possible to use these fields to execute an unconditional branch.
)
|
| Figure 5: Generalised conditional branching. |
Two options for conditional branching exist based on special addresses 300 and 301, which respectively test if a storage location contains a non-zero number and if it is negative. In these cases a discriminate cycle is introduced. For example consider the instruction
201 13 202 1 300 000 003
This will add the contents of short line 1 and short line 2 and if the result is zero, control will pass to the instruction two minor cycles on from this. If on the other hand the result is non-zero, then control is passed onto the instruction three minor cycles later (the additional beat is known as the discriminate cycle). This is generalised in figure 5.
Subroutines
MOSAIC also provided a mechanism to link to subroutines and hence allow the development of subroutine libraries.
A first order subroutine was defined as one that does not call another. It is called by a second order subroutine, which in turn may be called by a higher order subroutine, with the main routine being the highest order. Subroutines were always stored in consecutive long lines starting with minor cycle 0 of the first long line used. The first instruction to be obeyed in an nth order subroutine is the nth minor cycle of the major cycle. The number of the first line to be used is referred to as the address of the subroutine. Subroutines were called using a mechanism known as the Cue instruction, with return to the calling routine facilitated by a mechanism known as the Link instruction. Figure 6 shows the general layout of memory for a main routine executing in delay line 16, calling a third order subroutine held in delay line 5.
)
|
|
| Figure 6 – Memory allocation for subroutines |
In this example the Cue instruction would load the link instruction into delay line 1 during minor cycle 3 and transfer control to delay line 5 during the same minor cycle. The instruction (in this case held at minor cycle 1 in delay line 16) to do this could take the form:
016 02 000 1 001 000 005
If this is issued by the calling routine during minor cycle 1, it will take the instruction located in delay line 16, minor cycle 3, copy it to line 1 during minor cycle 3 and read the next instruction from delay line 5 at minor cycle 3, as the next instruction to be executed. The instruction placed in line 1 is the Link instruction. When the subroutine completes its processing, this is the instruction which needs to be executed to return control to the main program.
If this convention is followed then subroutine calls may be nested to a depth of 15, since the minor cycle (location in long line 1) reserved for the Link instruction for that subroutine is intrinsically associated with the order of the called subroutine.
Input-Output
Input to MOSAIC was through punched cards and output was either by card punch or by teletype writer using one of two character sets.
Binary input punched cards, with 80 columns and 12 rows, were used, with each row representing a single 40-bit binary number. Cards could be read at 200 cards per minute. Once the last row of a card had been read, the programmer needed to activate the card feed mechanism by issuing a “Hollerith Read” instruction using destination address 304. This took the form:
201 00 201 1 304 000 003
assuming the program is running in long line 3. To read the next line of a card required an instruction that specified the first source address as “0000000” (known as the “Input Dynamiciser”) and the destination address as the address to hold the incoming card. This was a wait type instruction that would be obeyed when the card reader had completed its read of the current line. The transfer was followed by a new instruction being set up. Such an instruction would take the form:
000 00 000 0 002 000 003
where the next line of the card would be read into long line 2. This mechanism is used to support the initial load of a program.
The Start button, on the machine front panel, was used to initiate a card feed. On initial load, the front panel Clear key needed to be pressed and released; this resulted in the current operation being suspended and the zeroth instruction consisting of all zeros was queued. By definition this is a Wait instruction, which would have no impact until the first row of the first card was read, following the operator pressing the Start button. Since this instruction had a destination address of zero, the incoming card would be used to form the next instruction. One possible sequence of card lines would be:
200 33 200 1 200 100 000
200 00 200 1 302 100 000
200 00 200 1 304 000 000
Here the zeroth instruction would read in and execute the instruction on the first card, which would have the effect of placing all zeros in short register 0, which would form the next instruction. This would be a zeroth instruction, which would read in and execute the second card, which is a reset of the output device (Staticiser Reset instruction) and specifies the short register 0 as the next instruction. Again this forms a wait instruction, which completes when the third card is read in. The third card then issues a Hollerith Read command to initiate a card read and queues a zeroth instruction as the next instruction. In this way a chain of input instructions is set up.
The first line of the next card to be read would begin the process of loading the instructions which would allocate the user program to specific locations in memory. This typically would be instructions to read the load sequence into a temporary storage area, interleaved with the actual load sequence instructions. These would take the form:
000 00 000 0 002 113 000 (Card type 1)
000 00 000 0 003 115 002 (Card type 2)
the first card reading in the second and placing it in long line 2 and the second is the instruction to read in the next line of the user program. The next instruction executed after the first card is obeyed is the zeroth instruction, which will normally read in the next card of type 1. The timing count of 13 specified ensures that the instruction on the next card of type 1 read in will be executed 17 (i.e. 1) minor cycles after the previous type 1 instruction.
Once all the type 2 cards have been read in, then the load of the program can be initiated by loading a card that transfers the execution path to the delay line holding the type 2 instructions. An example of this, where the code to be executed in long line 3, would be:
200 00 200 1 304 100 003
Note that the timing count would need to be adjusted so that the main routine would be entered at the right point of execution.
Where more than 12 rows are needed, the instructions described above would need to include a Hollerith Read instruction, and this would affect the timing, requiring adjustment of the timing count for some instructions. The input process was generalised as a standard input routine, which occupied four long delay lines. The “decimal number input subroutines” were two subroutines that were auxiliary to the instruction input subroutine and allowed it to read in numbers punched in decimal form. These routines provided the input mechanism used for the decimal coded instruction format already described.
Output was to a special destination (303), known as the Output Staticiser, which could be diverted to a specific device using the following special destinations:
- 305 caused any subsequent output directed at special destination 303 to be directed to the card punch.
- 306 would direct output to the teletypewriter
- 307 would direct output to the teletypewriter using an alternative character set.
If punched cards were selected for output, the punch was set in motion by issuing a “Hollerith Punch” instruction (special address . 303), which caused one card to be passed under the punching mechanism. For example in the instruction sequence
201 00 201 1 305 100 003
201 00 201 0 303 100 003
first selects the Hollerith Punch and then sends the contents of short line 1 to the punch. Note the latter is a wait instruction, the wait condition being satisfied once the punch is ready.
Data was initially produced in binary form, until the necessary mechanisms to convert between decimal and binary were created. A reproducer was used as the output device and a modified tabulator for input. For input and output, the card reader could be used as a slow-speed back-up store.
Printing to the teletypewriter was initiated by sending a word consisting of a single bit, representing the desired character, and all other bits zero to the device, using special destination 303.
The Output Staticiser needed to be reset to all zeros between uses. The “Staticiser Reset” was applied automatically after a punching, but for the first read-out of a calculation, the starting program for all calculations required a Staticiser Reset instruction (Destination 302).
Test facilities
MOSAIC had a front panel which provided a number of control and debugging capabilities. This had four functional capabilities, the first of which was the ability to set the contents of an instruction word using 40 switches, each switch representing an instruction bit. These could be used to load a card into the Input Dynamiciser.
There was an array of 40 lamps which showed the bit values of the current instruction being executed or the contents of a specific memory location.
The console itself had three lamps that reflected the current state of the machine, one showing the machine was under test and not available (red), one showing that the power was on (yellow) and one showing if the machine was in a wait state (green). One switch allowed the output to the card punch to instead be diverted to the array of 40 lamps. Another switch allowed the current instruction to be displayed on the array of lights. There was also a three way switch that could inhibit the go bit instructions, allow the machine to operate normally or inhibit the normal execution of instructions.
Finally there was a step button, which allowed instructions to be obeyed step by step. There was also the button to start the card reader.
There was a set of 10 switches that effectively provided a break point function. Five of these could select the long line carrying the instruction to be executed. Four would select the desired minor cycle on which to stop the sequence of instruction executing in the selected long line. The 10th switch enabled the interception of the selected instruction and prevented it from running.
When a program was being tested an examination subroutine could be installed. This enabled the contents of any storage location to be viewed, control to be passed to any storage location and store to be filled with a word set on the id keys. Control of the examination routine was achieved using the front panel controls.
Outside of these capabilities there were no further exception handling controls.
A Coding Example
As an example, I include the program described in my previous paper ( Resurrection101 ), which identified the highest factor of a number N, by beginning with a solution of a=N-1 and decrementing it until a value is found that is a factor of N. Each number a is repeatedly subtracted from N until a remainder of zero is seen, if the remainder is positive then a is again subtracted, if it is negative then the solution a =a-1 is tried. The logic followed is shown in figure 7 below.
)
|
)
|
| Figure 7: Logic flow of highest factor program | Figure 8 – Memory allocation for code for highest factor program |
This first needs to be translated into a series of instructions and these instructions then need to be allocated to a given memory location, as shown in figure 8.
The logic of the program is as follows: subtract 1 from N and store the result in short delay line 2 as a. The next step is to store the difference between N and a in short line 3. Subtracting short line 3 from short line 2 gives the value N-2a which is stored in short line 3, this will probably be negative for the first number a, but for smaller a may be positive (NB each step takes a minimum of two minor cycles).
The sign of the value in short line 3 is tested on minor cycle 6, if it is negative control is passed to the instruction at minor cycle 9, where a new trial divisor is formed and stored in short line 2 and the program is re-entered on minor cycle 2.
If, on the other hand, the value in short line 3 is positive, it is tested at minor cycle 8 to see if it is zero. If this is the case control is passed to the instruction at minor cycle 3, which resets the output staticiser. The correct answer is now in short delay line 2, but the instruction to select has been placed at minor cycle 10 as the most convenient next location. This is reached by specifying a timing count of 5 on the reset output statisicer instruction. If on the other hand short line 3 was not zero, control is passed to the instruction at minor cycle 4 and the main loop is iterated again.
Conclusions
Only one MOSAIC machine was ever built and neither it nor any reconstruction exists today; nor is any emulator readily available. This paper has been developed based on available documentation and an experimental emulator, currently under development.
MOSAIC was a powerful and versatile computer, however unlike EDSAC, its underlying dependence on delay lines was not hidden from the user. This made programming more complicated and potentially error prone. Through a technique known as optimal programming the number of wasted memory cycles could be minimised.
)
)
)
