Note: The following was prepared from a talk given at the Fall meeting of Ohio Section of the M.A.A. on October 25, 1996 at Denison University.
February 1996 marked the 50th Anniversary of the ENIAC, the first all-electronic computer. However, the 1946 ENIAC was not the first stored program computer. That distinction probably goes to the Manchester Mark I Prototype which successfully ran the first stored program, Kilburn['s] Highest Factor Routine, on June 21, 1948. We'll look at the code for Kilburn's program and show how the Manchester Mark I prototype with only 32 words of 32-bit memory and 7 instructions (no division instruction) was used to factor integers. There are no surprises here but it's interesting to see how much could be done with so little.
A third approach used a Cathode Ray Tube (CRT) like the monitors used as display devices in today's computers. With CRT memory technology, a scanning election beam was used to deposit a charge on the surface of a phosphor coated screen (incidently causing the phosphor coating to glow). Binary information, 0's and 1's, could be stored a different sized charges on the phosphor screen. Unlike the Acoustic Delay Line technology where information was only periodically available, the CRT memory technology was truly "random" in the sense that the time to access any bit was constant. An additional feature was that the contents of memory could be directly read by observing the pattern of glowing dots on the phosphor screen. However, a drawback was that a charge on the phosphor screen leaked away after a fraction of a second so any information stored in CRT memory had to be continually refreshed. Ways were eventually found to efficiently refresh the screen permitting a number of early computers, like the Manchester Mark I (1949), the IAS (1952) and IBM's 701 (1953), to use CRT memory.
Frederic C. Williams, was an engineer originally from Manchester. During the war he worked at the Telecommunications Research Establishment where he did work on radar and other military applications of electronics. On a visit to MIT shortly after the war he became acquainted with the research on using CRT memory technology and on his return to England he continued this line of research. He returned to Manchester where discovery of the "anticipation pulse effect" lead to a design breakthrough that made charge regeneration for CRT memory technically feasible. His CRT memory design was called the Williams Tube.
Tom Kilburn was a mathematician who after the war became interested in the design of computing machines. At Manchester, he lead the design and building of the Manchester Mark I Prototype computer which was based on the Williams Tube memory technology.
The Manchester group can also trace its roots to work done at the Code and Cipher School at Bletchley Park during the Second World War. Also at Manchester was the mathematician, M.H.A. Newman, who during the war worked at Bletchley Park. The British Code and Cipher School at Bletchley Park was responsible for deciphering the Enigma and Geheimschreiber codes used by Germany. The nature of the deciphering work lead to the design and construction of a number of special-purpose computers. Neuman was responsible for designing the COLOSSUS, a special purpose all-electronic computer used to decipher the Geheimschreiber codes. Men like M. H. A. Newman and Alan Turing who also worked at Bletchely Park became prominent in the early history of computing. After the war Neuman returned to the University of Manchester where he obtained a grant from the Royal Society for the development of computing machinery.
The Manchester Mark I Prototype made use of three Williams Tubes:
The A Tube was a 32 bit accumulator. The C Tube corresponded to the Program Counter and the Instruction Register of a modern computer. We note here that the CI line held the address of the current instruction instead of the address of the next instruction which is normally the contents of the Program Counter in today's computer. The S (Store) Tube memory consisted to 32 32-bit word s. Two's complement representation of integer values was used giving a range of -2^31 .. +2^31-1 or -2,147,483,648..+2,147,483,647
A second interesting feature was that all information was displayed in "reverse-binary" with the least significant bit being on the left and not the right. (For example 6 would display as 011000000000...00 instead of 000...00000000110), Bits were numbered 0 to 31 left to right.
All instruction were 16 bits long with the five left most bits (bits 0 - 4) containing the operand address and bits 13 - 15 containing a three bit opcode. The middle eight bits (bits 5 - 12) were not used nor were the upper sixteen bits (bits 16 - 31) making the instruction format somewhat hard to pick out on unless you knew exactly where to look .
There was no I/O per se. Code and data was toggled directly into memory. Output was accomplished by directly observing the contents of the Williams tubes.
Note that the codes are in "reverse binary"
Code Instruction Effect
---- ----------- ------
000 Jump (indirect) CI <- Store[address]
100 Jump Relative (indirect) CI <- CI + Store[address]
010 Load Negative A <- -Store[address]
110 Store Accumulator Store[address] <- A
001 Subtract A <- A - Store[address]
101 (not defined)
011 Skip if Accumulator < 0 if A < 0 Then CI <- CI + 1
111 Halt
There are a number of unusual features to the Mark I Prototype instruction set. Note one address format;
the Accumulator is assumed to be the other operand in a two operand instruction.
Since the Manchester Mk I Prototype reversed this sequence, Jump instructions took some thought to make them work correctly. Recall that Jump instructions used indirection so the target address for the jump had to be stored. But since the Manchester Mark I Prototype incremented the CI line, you had to store one less than the target address. In other words, if you wished to jump to address 9 and continue execution from that point, you had store the value 8 in memory and use the address where the 8 was stored in the instruction.
Since the CI was incremented first, the first instruction was normally placed at address 1 with the CI line initialized to 0.
For example to add two numbers, C := A + B, on the Mark I Prototype, you had to load negative A into the Accumulator, subtract B, then negate the answer by storing it at C, doing a load negative then storing it back to C. That is C := - ((-A) - B). This took five instructions!
Suppose A is stored at Store[29], B at Store[30] and we want to deposit the results C at Store[31]. We list the machine code below. Note that everything is in reverse binary, the operand address in contained in the five left-most bits and the opcode in the three right most bits.
a. C := A + B : C = - ((-A) - B)
10111 00000000 010 ; load negative A, Store[29]
01111 00000000 001 ; subtract B, Store[30]
11111 00000000 110 ; store C, Store[31]
11111 00000000 010 ; load negative C, Store[31]
11111 00000000 110 ; store C, Store[31]
00000 00000000 111 ; halt
Subtraction wasn't much easier! To subtract B from A required a load negative, store, load negative
sequence to load positive A into the accumulator before B was subtracted.
b. C := A - B : C := (-(-A))-B
10111 00000000 010 ; load negative A, Store[29]
10111 00000000 110 ; store -A at A, Store[29]
10111 00000000 010 ; load negative A (AC = A)
01111 00000000 001 ; subtract B, Store[30]
11111 00000000 110 ; store C, Store[31]
00000 00000000 111 ; halt
Multiplication could be done by repeated addition. To compute C := A + B, add A to C, B times which
requires using a loop. The code (below) starts at address 1. It loads negative B into the Accumulator and
tests if the Accumulator is negative (i.e. B is positive). If so, it skips the next instruction (otherwise it
quits), subtracts -1 (-1 is stored as a constant at address 28) and performs a store, load negative, store
sequence which had the effect of subtracting 1 from B.
The code then adds A to C ( five instructions) and goes back to the beginning.
We should point out a couple of things about the Jump instructions at S3 and S13. The Jump Indirect Store[27] at S3 loads the contents of Store[27], a 13, into the CI line. Then the Increment-Fetch-Execute cycle increments the CI to 14 and fetches the Halt instruction at S14 to halt the program. The Jump Indirect Store[0] at line S13 load the contents of Store[0], a 0, into the CI. Then the Increment-Fetch-Execute cycle increment the CI to 1, fetches the Load Negative instruction at address 1 to perform the loop.
S0: 00000000000000000000000000000000 ; 0
S1: l0111 00000000 010 ; load negative B, Store[30]
S2: 00000 00000000 011 ; skip if AC <0
S3: 11011 00000000 000 ; jump indirect Store[27]
S4: 00111 00000000 011 ; subtract -1, Store[28]
S5: 01111 00000000 110 ; store B, Store[30]
S6: 01111 00000000 010 ; load negative B, Store[30]
S7: 01111 00000000 110 ; store B, Store[30]
S8: 11111 00000000 010 ; load negative C, Store[31]
S9: 10111 00000000 011 ; subtract A, Store[29]
S10: 11111 00000000 110 ; store C, Store[31]
S11: 11111 00000000 010 ; load negative C, Store[31]
S12: 11111 00000000 110 ; store C, Store[31]
S13: 00000 00000000 000 ; jump Store[0]
S14: 00000 00000000 111 ; Halt
.....
S27: 10110000000000000000000000000000 ; 13
S28: 11111111111111111111111111111111 ; -1
S29:
S30:
S31:
Successfully executed on June 21, 1948, Kilburn's Highest Factor Routine is believed to be the first program ever run on a stored program computer. A hand-written copy of the code (dated 18/7/48) still exists and the run time of 52 minutes was reported in the September 1948 issue of Nature magazine.
The code was apparently not meant to be a model of efficiency so much as to test whether the Manchester Mark I Prototype computing environment was stable enough to run lengthy programs. Hence all seven instructions were incorporated into the code.
The Mark I Prototype machine code for Kilburn's Highest Factor Routine is given below preceded by pseudo-code that helps explain the logic. Number, the value for which the largest divsor is found, equals 2^18 = 262144 and the initial Trial Divisor equals 2^18 -1 = 262143. The program starts out by making two copies of the Trial Divisor, a positive copy (+Trial Divisor) and a negative copy (-Trial Divisor).
1. Make copies of +Trial Divisor and -Trial Divisor
2. Move Number into Accumulator
3. While Accumulator > 0 Do
2.1 Subtract +Trial Divisor from Accumulator
{ At this point either the Accumulator = -Trial Divisor so the Trial
Divisor divides the Number or Accumulator > -Trial Divisor }
4. Add Trial Divisor back into Accumulator (i.e. subtract -Trial Divisor)
5. Negate Result
6. If Result < 0 Then
6.1 Subtract 1 from Trial Divisor
6.2 Store as +Trial Divisor and -Trial Divisor
6.3 Goto Step 2
7. Else Result = 0 so Trial Divisor divides Number - Halt
Here is the machine code for Kilburn's Highest Factor Program. It was generated
from the handwritten copy dated 18/7/48. To understand it, you should match the
description above with the code below. The program searches for the largest divisor
of 2^18 = 262144 but in the code it uses the negative value, -262144, instead.
The first Trial Divisor was one less than this Number, 2^18 - 1 = 262143
S0: 00000|00000000|000|0000000000000000 ; 0 S1: 00011|00000000|010|0000000000000000 ; Load Neg. S24 (1st Divisor) S2: 01011|00000000|110|0000000000000000 ; Store S26 (-Trial Divisor) S3: 01011|00000000|010|0000000000000000 ; Load Neg. S26 S4: 11011|00000000|110|0000000000000000 ; Store S27 (+Trial Divisor) S5: 11101|00000000|010|0000000000000000 ; Load Neg. S23 (+Number) S6: 11011|00000000|001|0000000000000000 ; Sub. S27 (+Trial Divisor) S7: 00000|00000000|011|0000000000000000 ; Skip if AC < 0 S8: 00101|00000000|100|0000000000000000 ; Jump Rel. Indirect S20 S9: 01011|00000000|001|0000000000000000 ; Sub. S26 (Restore) S10: S10 10011|00000000|110|0000000000000000 ; Store S25 S11: 10011|00000000|010|0000000000000000 ; Load Neg. S25 S12: 00000|00000000|011|0000000000000000 ; Skip if AC < 0 (test if 0) S13: 00000|00000000|111|0000000000000000 ; Halt S14: 01011|00000000|010|0000000000000000 ; Load Neg. S26(-Trial Divisor) S15: 10101|00000000|001|0000000000000000 ; Subtract S21 (+1) S16: 11011|00000000|110|0000000000000000 ; Store S27 (+Trial Divisor) S17: 11011|00000000|010|0000000000000000 ; Load Neg. S27 S18: 01011|00000000|110|0000000000000000 ; Store S26 (-Trial Divisor) S19: 01101|00000000|000|0000000000000000 ; Jump I S22 (=4) S20: 10111 11111111 111 1111111111111111 ; -3 (jump address) S21: 10000 00000000 000 0000000000000000 ; +1 (constant) S22: 00100 00000000 000 0000000000000000 ; 4 (jump address) S23: 00000 00000000 000 0011111111111111 ; -(2^18)= -262144 (-Number) S24: 11111 11111111 111 1100000000000000 ; 2^18 - 1 = 262143 S25: 00000 00000000 000 0000000000000000 ; S26: 00000 00000000 000 0000000000000000 ; -Trial Divisor S27: 00000 00000000 000 0000000000000000 ; +Trial Divisor S28 00000 00000000 000 0000000000000000 S29 00000 00000000 000 0000000000000000 S30: 00000 00000000 000 0000000000000000 S31: 00000 00000000 000 0000000000000000
The four variables A, CI, PI, and S define the Accumulator, Control, and Store Tubes. The procedure Execute will execute a MADM Mark I Prototype Instruction.
Simply add your own code to display the contents of the A, CI, PI lines and the S Store as well as code to enter MADM Mark I Prototype machine code into the S Store array. (To see a more complete version of this code written for Turbo Pascal V6.0, - Click Here.)
Program MADM_Mk1_Sim(input,output);
Type
LineType = LongInt;
StoreType = array[0..31] of LineType;
Var
A : LineType; { Accumulator Tube }
CI : LineType; { Control Tube - Current Instruction Line }
PI : LineType; { Control tube - Program Instruction Line }
S : StoreType; { Store Tube - 32 x 32 bit Lines }
Run : boolean;
Procedure Execute(var A, CI, PI : LineType;
var S : StoreType;
var Run : Boolean);
{ Desc : Execute MADM Mk I Instruction
CI := CI + 1;
PI := S[CI];
Execute Instruction PI }
var
Fcn,
Line : LongInt;
begin { Execute }
CI := (CI + 1) Mod 32; { Increment CI }
PI := S[CI]; { Fetch current instruction}
Fcn := (PI AND $0000E000) SHR 13; { Extract Opcode }
Line := (PI AND $0000001F); { Extract Operand }
Case Fcn of { Execute }
0 : CI := S[Line]; { Jump }
1 : CI := CI + S[Line]; { Jump Relative }
2 : A := -S[Line]; { Load Negative }
3 : S[Line] := A; { Store }
4 : A := A - S[line]; { Subtract }
5 : A := A - S[Line]; { " }
6 : If A < 0 Then { Skip if A < 0 }
CI := (CI + 1) AND $0000001F;
7 : Run := False; { Halt }
end ; (* case *)
end; { Execute }
begin
{ Enter Code to Initialize Store }
{ Execute }
...
Run := True;
While Run do
Execute(A,CI,PI,S,Run);
...
{ Display A, C, and Store Tubes }
end.
A commercial model of the Manchester Mark I, the Ferranti Mark I came out in 1951. It had 50 instructions, eight index registers, and a 256 word fast CRT memory (backed by a slower drum memory of 4096 words). An advanced version, the Ferranti Mark I Star came out in 1953. It had 416 word fast CRT memory (backed by a slower drum memory of 16384 words).
In the September 1948 issue of Nature, Williams and Kilburn published a brief article outlining their work on the Manchester Mark I Prototype.
To quote from the article
"The capacity of the store is at present only 32 'words', each of 31 binary digits, to hold instructions, data, and working. Hence only simple arithmetic routines devised to test the machine can be run. Examples of problems that have been carried out are: (1) Long division by the standard process. (For (2^30-1)/31, this took 1 1/2 seconds, the quotient being given to 39 significant binary figures of which the 13 least significant, to the left of the binary point, were zero, since 31 is a factor of 2^30 -1.) (2) H.C.F. by the standard process. ( For 314,159,265 and 271,828,183, which are co-prime, approximately 0.5 seconds). (3) Factoring an integer. For (3) the method was deliberately chosen to give a long run the result of which could be easily checked. Thus the highest proper factor of 2^18 was found by trying in a single routine every integer from 2^18 - 1 downward, the necessary divisions being done not by long division, but by the primitive process of repeated subtraction of the divisor. Thus about 130,000 numbers were tested, involving some 3.5 million operations. The correct answer was obtained in a 52-minute run. The instruction table contained 17 entries." (F.C. Williams and T. Kilburn: Electronic digital computers.Nature 162, 487 (Sept 1948)).Given the limited capabilities of the Manchester Mark I Prototype, how were these routines coded? The answers can be found in an article titled "Early Programs on the Manchester Mark I Prototype" which appeared in the July - September 1998 issue of the IEEE Annals of the History of Computing. Included in the article is a reconstruction of the original Kilburn's Highest Factor Program (the original was lost - an amended version was given in this paper).