« Bad Website | Main | Golden Stairs »
November 06, 2006
Programming the Univac I in 1956
For today's post, we have a guest blogger. He's Michael Barr, Peter Redpath Emeritus Professor of Pure Mathematics at McGill University (but NOT the embedded systems expert of the same name), and more importantly my father:My first experience programming was about 50 years ago, although the program I wrote was never debugged or run. I think the basic idea was sound, but the machine cost about $5 a minute to use and ran at kHz speeds. Also the MTBF was about 5 minutes, so the only program you could run was a serious one.The Univac I was one of the first, if not the first, commercially available computers. You plunked down your million 1950 dollars, found a space large enough for a basketball court, got an electrical supply sufficient for a small village and you could get started computing. Of course there were details like a room full of vacuum tubes since the ones in the machine were continually burning out. That was why the arithmetic operations were done in triplicate; if two of the them gave the same answer, it was assumed correct. Otherwise the machine stopped on error. The entire memory contents were dumped to tape every minute or so in order not to have to restart from the beginning. Input was by paper tape, although I think they eventually added a punch card reader.
The University of Pennsylvania needed the room (essentially the basement of the Math and Physics building), the electric power, the service technicians, but not the million dollars. That is because the Moore school at Penn had been the home of EE professors Eckert and Mauchly, who built the ENIAC, one of the very first computers anywhwere and then went off to found the Eckert-Mauchly division of Remington-Rand that sold the the Univac I. About to put the Univac II on the market, which I believe used discrete transistor logic, they had one obsolete machine left and donated it to Penn. I don't know what the business tax rate was, but the personal tax rate was very high (up to 91% on taxable income above, IIRC, $200,000) and it probably was worth more to them as a charitable deduction than as a heavily discounted obsolete machine.
As a student I worked at something called the Johnson Foundation at Penn. (Originally founded in honor of Eldridge Reeves Johnson, who may have founded the Victor Talking Machine company, but was the one who sold it to RCA.) They had a rather large analog computer (the JFEAC--Johnson Foundation Electronic Analog Computer) that was used to solve the kind of chemical rate equations that some of the researchers at the JF worked on. I was, in fact, the operator of that machine. It was programmed by attaching modules to one another by phone cables. When the Univac came on campus, they decided to switch to that. In the meantime (as it happened, a very long meantime), they kept the analog computer running, so I was not involved in programming it. Truth-to-tell, it was hardly ever used, partly because tubes were always burning out and partly because no one ever actually came to me with a chemical kinetic problem to solve
Ah the memory. There were two kinds. The "fast" memory consisted of 100 tanks of mercury that had an electric to sound transducer at one end and a sound to electric transducer at the other. Think of it as tube in which 10 words of memory were coursing through. At any one time, one was just coming into the entry and one was exiting and the other eight were trapped at various places in the tube. I guess you could describe it as time-multiplexed. So of the 1000 memory locations, 900 were in the tanks at any one time and the remaining hundred were available for use. To read/store from memory, the machine had to wait for the right location to come around. One of the optimizations the programmers sometimes did for important parts of the program was called "minimal latency coding", trying to work out where to store something so that the machine didn't have to wait long for that location to become available. People had tables of average instruction time. I don't remember actually seeing the mercury tanks but I would guess they were about a foot long. The speed of sound in mercury is 1450 meters/second, so it would take perhaps 200 microseconds for the signal to travel the length of the tube.
The slow memory consisted of 12 magnetic tape readers. They were definitely state of the art, but were not random access no matter what. They were each about eight feet high, the size of a refrigerator. The program the JF eventually came up with used 80,000 words and about half of it consisted of "overlay" instructions, that is instructions to read the next routine to be used from the tape into the internal memory.
A word (really a double word, but the smallest addressable unit) consisted of 72 bits divided into 12 bytes of 6 bits each. It is now commonly thought that a byte is 8 bits (and the French word for byte is octet), but various machines had byte sizes from 6 to 9 bits. Naturally, they used only uppercase letters, numbers, and punctuation. I don't recall if the remaining 20 or so characters had any meaning. I don't think anyone had anticipated text processing.
The machine was hard wired to interpret a kind of primitive assembly language. There were two instructions per word and they had the format "A 324", which meant to add the contents of memory location 324 to the accumulator (essentially the arithmetic register), "M 324", which meant multiply the contents of location 324 by the accumulator and so on. In all cases the result was stored in the accumulator from which it could be written to memory. Multiply and divide used a second register. So there must have been instructions to move between the second register, and also tape instructions, but I forget them. There was talk of a "three memory instruction" machine, which would be able to, say, add two memory locations and store the result in a third, but this wasn't such a machine. Everything was accumulator and memory. The instructions were stored as written, so to store "A 234" it would store the encoding of an "A" (it used some encoding, not ASCII), then the encoding for a space, then the encoding for a second space (I recall some of the instructions were two characters), then the BCD encodings of 2, 3, and 4. This storage system was of course very wasteful of memory.
On overflow, the machine executed the instruction found at memory location 000, which was usually an unconditional jump. If it was anything other that such a jump, it resumed execution where it had been. Notice, incidentally, how inefficient the storage was, using 36 bits for each instruction. They used the extremely limited memory very inefficiently. Of course, the probably felt that they had as much storage as necessary on the magnetic tapes. And if that was slow by our standards, the computer was so much faster than the alternative that it certainly did not seem slow. But note that all programming was done in absolute memory locations. Later, Univac released a real assembler that allowed you to use relative addressing and also linked subroutines automatically, with a mechanism for inputting parameters. However the idea of a re-entrant program had not occurred to anyone so that unless you were using a parameter-free subroutine, you had to have as many copies of in memory (or overlaid) as there were uses in your program.
The machine was in a big room, with the control console, the paper punch, the reader, and the tape servos. The whole thing was built with vacuum tubes, not transistors. It was the largest vacuum tube computer ever built in the US; I heard the Soviets built some larger ones. The actual tubes were off in a separate room. Then there was a side room with a giant capacitor. You know capacitance is typically measured in micro-farads or micro-micro-farads. This thing had a one farad capacitor. Two thousand electrolytic capacitors in parallel, each 500 micro-farads, which occupied an entire room. I assume it was to deliver power to the machine.
I was curious about the computer and I had access to the programming manuals so I decided to try my hand at programming on my own, without any expectation that I would ever be able to run it. They had programming sheets (on a pad) that were laid out with spaces for (line) numbers on the left and then 12 boxes, into which you put two successive instructions. Of course these were written longhand and then someone else punched them into the paper tape. The program I wrote was to do double precision arithmetic. I only wrote it out and tried to check the logic, I never had it punched on tape or run. About 20 years later, I actually wrote such a program on a Wang minicomputer that my department bought in 1975 (and retired seven or eight years later). I never finished debugging that program either, inciedntally. The arithmetic on the Univac was BCD, incidentally. Pure binary would have seemed just too weird, especially to businessmen. Even today, many people are convinced that binary arithmetic is inherently less accurate than decimal, when actually the opposite is true. Since six bits were used to store each digit and another six for the sign, the result is that the range of numbers representable in single precision was plus or minus 10^{11}, while pure binary representation could have represented numbers up to plus or minus 2^{71}, about 2*10^{21}.
Anyway, the idea was independent of such considerations. To do double precision arithmetic, you have to work with numbers of the form a + tb, where t is a number of the form 10^{-k} or 2^{-k}, depending on the coding and k is the length of a single precision number. Let us represent such a number by (a,b). Then (a,b) + (c,d) = (a+c,b+d) or (a+c+1,b+d) depending on whether there is an overflow in the addition of b+d. Of course, there is also a potential overflow in the addition of a+c, but let us ignore that since that leads to an error state. An mechanism for dealing with overflow (more precisely, for allowing the programmer to write an overflow handler) was hard-wired in the machine.
Subtraction is handled in the same way as addition. Multiplication is more complicated, but the essential formula is that (a + tb)*(c + td) = (ac + t(ad+bc) + t^2(bd)), but the last term is too small to be saved. Actually, the machine did save the insignificant digits of the product, else this multiplication would not have been readily possible. The true formula used has to be (a,b)*(c,d) = ((ac)_h + t((ac)_l+(ad)_h+(bc)_h), where _h and _l stand for the high and low bits of the product. The understanding was that all numbers were less than 1, so multiplication could not overflow, although the addition could. although this was a problem it was manageable.
Division is more complicated. The basic formula is (a+tb)/(c+td) = (a+tb)*(c-td)/(c^2-t^2d^2). Since t^2 is insignicant, this can be replaced by (a+tb)*(c-td)/c^2. The multiplication routine can be used to compute the numerator, say (e+tf) and then you can divide twice by c. Since (e+tf)/c^2 = e/c^2 + t(f/c^2), this can be done in single precision and the results combined. You have to divide e by c and add the low precision digits of the result to f and then divide the new f by c. Repeat. Sort out all the possibilities of overflow. The result was not pretty and I rather doubt I had all the details worked out. High precision arithmetic is not for the faint of heart. My program was probably around 100 lines (so 200 instructions), although it would have been longer if debugged. I forgot about incorporating the lower bits from multiplication and division.
There is another possibility. When I was in school, I learned long division. We divided one digit at a time. It was slow, but it worked and there was no built-in limit to length. In binary, it is even easier, since the only possible next bit is 0 or 1. Try 1 and if it is too large, the next bit has to be 0. It works and it might be faster. I do know that in the 80s, I wrote a square root program along those lines in assembly language using Forth assembler. It was much faster than the square root supplied by my Forth vendor, based on a Newton iteration that used the rather slow division of the 8088 chip. I sent it to LMI and it was eventually included in their Forth distribution. There is life in those old algorithms yet.
This is Adam again. I was thinking about this and realized that this story is from 1956, and the original IBM PC came out in 1981, which is exactly halfway between then and now. Of course the PC was a general purpose computer. But the PC had about 64K of memory and a 1 MHz (or maybe it was 2 MHz) bus. So it had about 64 times as much memory as the Univac I (technically less since the Univac I used these 72-bit words, but it stored stuff so inefficiently that we'll call it a wash). Meanwhile today's computers have roughly 16,000 times as much memory as the original PC. And those mercury tanks might have taken an average of 100 microseconds to access memory, but the jump from the original PC's bus to today's machines may also be a larger factor of magnitude (I don't know enough about how buses really operated to figure out how to convert between a machine that could read 72 bits in 100 microseconds and one that transferred 16 bits at a time over a 1 MHz bus, or today's machines that transfer 32 bits over a 533 MHz bus, but if you just do the obvious calculation you get a bandwidth of 90K/sec for the Univac I, 2M/sec for the IBM PC, and about 2 gig/sec for today's machines, so again the jump is much greated from 1981 to 2006 than it was from 1956 to 1981). The Wikipedia article linked to above, incidentally, has some good information and links on the Univac I.
There is one aspect of this story that I find fascinating, which is how my father wound up at the Johnson Foundation to begin with. He grew up in Philadelphia in a family he described as "barely lower middle class". When he graduated from high school (in 1954) there was nothing saved for college. Tuition at Penn (which was just a few miles from their house) was $700. There was a vague notion that he could get a scholarship, but nothing was forthcoming. Then, what he describes as "a miracle" happened. He was looking for a summer job in June 1954 and saw an ad in the paper. It turned out not to be a summer job, but instead an opportunity to work full-time at the Johnson Foundation while allowing him to take classes at Penn's night school, as well as summer classes, and earn a degree in 5 years. He would be paid a salary and also be able to attend Penn for half-price, as an employee. He took the job (after first convincing somebody in the Pennsylvania government that it was OK for him to work in a lab before he turned 18). He wound up working there for 3 years, then switched to a regular student with a partial scholarship and loan, graduating after 4 1/2 years. After that he got a Ph.D. in mathematics from Penn and on to becoming a professor at McGill. But it's really astonishing to wonder where he would have wound up had he not gotten that job at the Johnson Foundation.
Posted by AdamBa at November 6, 2006 10:26 PM
Trackback Pings
TrackBack URL for this entry:
http://proudlyserving.com/cgi-bin/mt-tb.cgi/516
