Communications of the ACM
Historical reflections
Alan Turing's Other Universal Machine
Jim Wilkinson (left) and Donald Davies (right) with the Pilot ACE, May 1950.
Credit: Archive for the History of Computing, Manchester University
All computer scientists know about the Universal Turing Machine, the theoretical construct the British genius Alan Turing described in his famous 1936 paper on the Entscheidungsproblem (the halting problem). The Turing Machine is one of the foundation stones of theoretical computer science. Much less well known is the practical stored program computer he proposed after the war in February 1946. The computer was called the ACEAutomatic Computing Enginea name intended to evoke the spirit of Charles Babbage, the pioneer of computing machines in the previous century.
Almost all post-war electronic computers were, and still are, based on the famous EDVAC Report written by John von Neumann in June 1945 on behalf of the computer group at the Moore School of Electrical Engineering at the University of Pennsylvania. Von Neumann was very familiar with Turing's 1936 Entscheidungsproblem paper. In 1937, Turing was a research assistant at the Institute for Advanced Study at Princeton University, where von Neumann was a professor of mathematics. Beyond these known facts, however, it is not possible to say how much influence the Turing Machine had on the design of the EDVAC. But there is no doubt the ACE was heavily influenced by the EDVAC Report.
The war in Europe ended in May 1945 and the institutions of Britain began to get back to their peacetime roles. Computers were in the air and universities at Manchester, Cambridge, and elsewhere established electronic computer projects. Outside the academic sphere, in London, the National Physical Laboratory (NPLBritain's equivalent of the National Bureau of Standards) started a mathematics division to provide a computing service for industry. With a staff of 40 and equipped with desk calculating machines, punched card equipment, and a differential analyzer, it was an impressive organization. In October 1945, Turing was brought in to establish an electronic computer project. He was a department of one, and over the next few months he evolved the design of the ACE. His report was formally presented to the NPL's executive committee in February 1946.
Although the ACE drew heavily on the EDVAC Report, it had many novel features and was a design of great originality. When he heard about the EDSAC that was being planned at Cambridge University by Maurice Wilkes, which was based very directly on the EDVAC, Turing was unimpressed. He wrote in a private note: "The 'code' which [Wilkes] suggests is however very contrary to the line of development here, and much more in the American tradition of solving one's problems by means of much equipment rather than by thought. I should imagine that to put his code (which is advertised as 'reduced to the simplest possible form') into effect would require a very much more complex control circuit than is proposed in our full-size machine."
Turing's brilliant innovation in the ACE was to eliminate delay-line waiting time by what was later called optimum programming.
Wilkes took the view that building the EDSAC to a conventional design would be enough of a challenge. Moreover, the EDSAC would be several thousand times faster than existing techniques and users would be best served by having a conventional machine sooner rather than a novel design later. There was merit in both of their positions.
ACE Design
The ACE was designed to fully exploit the potential of a mercury delay-line memory. The delay line was a spin-off from echo-cancellation devices in radar, and in 1946 it was the only proven memory technology. When used in the main memory of a computer, the delay line consisted of a five-foot mercury-filled steel tube. Digital data was converted to acoustic energy at one end of the tube and converted back to electrical signals at the other end. By feeding the output back into the input, digital data could be stored indefinitely. A five-foot tube had an acoustic delay of about one millisecond and the typical pulse duration of a computer was one microsecond; hence the delay line could store about 1,000 bits of information (usually 1,024 bits, of course). This was enough to store several instructions or numbers. Apart from its high cost and unreliability, the mercury delay line memory also had the problem of latency. That is, when an instruction or number was needed, the machine had to wait until it emerged from the delay linean average time of half a millisecond. For this reason most delay-line based computers spent more time waiting for instructions and numbers than processing them.
Turing's brilliant innovation in the ACE was to eliminate this waiting time by what was later called optimum programming. On a conventional machine instructions were stored in consecutive locations, so that latency effects dramatically slowed up the machine. In the ACE design, however, each instruction specified the location of its successor. In this way instructions (and numbers) could be placed optimally in the memory so that they emerged from a delay line just as they were needed. The optimum coding idea showed a rather direct connection to the "instruction tables" of the Turing Machine, in which each order specified the next to be obeyed. This simple idea alone would make the ACE about three times faster than other delay-line based computers. Optimum coding, it should be noted, was much more difficult than conventional programming, but for a decade it was the way to get maximum performance from delay-line or drum-based machines.
But there was more. In the ACE design Turing avoided having a single central register (known as the accumulator in EDVAC-type machines) in which all computation took place. Instead, he had separate registers for addition and subtraction, multiplication, logical operations, shifting, and so on. To a degree Turing was anticipating what would later be called the von Neumann bottleneck.
ACE Construction
Turing proposed that the ACE would contain 200 delay lines in the main memory and estimated the constructional cost at £11,200 (about $45,000). Turing was a better mathematician than an engineer and his estimates were wildly unrealistic. Building the ACE got off to a shaky start and not much happened for several months. Then in 1947 an American, Harry Husky, who had been a member of the Moore School computer group, began a sabbatical year at the NPL. He proposed building a small prototype of the ACE, which he called the Test Assembly. Still, little progress was made and Turing left the NPL in September 1947 for a sabbatical year at King's College, Cambridge University. He never returned to the NPL. At last in early 1949, work really got going on another small version known as the Pilot ACE and the development logjam was broken by Donald Davies, a new recruit to the NPL. Davies was an outstanding scientist and administrator. He later became head of computer science at the NPL and was one of the inventors of packet switching technology.
Besides the DEUCE, the Pilot ACE spun off several other worthy derivatives.
The Pilot ACE sprang into life in May 1950. It had just 10 delay lines, but when augmented with a drum store it was a highly capable computing machine. Benchmarks showed that it was five to 10 times faster than contemporary machines. Moreover, the Pilot ACE had just 800 tubes compared with 3,000 in the Cambridge EDSAC and 3,500 in the Manchester Mark I.
ACE Derivatives
The English Electric Company, a manufacturer of airplanes and electrical equipment and a contractor to the NPL, decided make a copy of the Pilot ACE; unsurprisingly, the machine was named the DEUCE. This set the ball rollingEnglish Electric's competitors decided they would like a machine too and the company found itself in the computer business. Sold from 1955, the DEUCE was especially popular with engineering companies that had heavy computational needs. Sales to aerospace companies were given a boost following the Comet air disaster of 1954, which had resulted in the statutory requirement for airplane manufacturers to conduct so-called flutter calculations. The DEUCE came with a superb library of matrix software developed by Jim Wilkinson, originally Turing's assistant but later a distinguished numerical analyst and winner of the 1970 ACM A.M. Turing Award.
Besides the DEUCE, the Pilot ACE spun off several other worthy derivatives. The most important was the Bendix G-15 introduced in 1956. The machine was designed for the West Coast's Bendix Aviation Corporation by Harry Husky, who had returned to the U.S. and joined the faculty of the University of California, Berkeley. Optimum coding gave the machine an edge over rival machines, and the G-15 became a workhorse for the American engineering industry. About 400 were eventually sold.
Conclusion
As to the ACE itself, the full-scale, 200-delay-line machine was finally completed in 1958. Sadly, by the time it was built the heyday of delay-line storage was over, and new computers were using random access core memory. Even the NPL admitted the machine was a technological dinosaur. Turing died in 1954, so he never lived to see either the triumph of the DEUCE or the whimper of the full-scale ACE. English Electric went on to become a cornerstone of the early British computer industry. After the DEUCE went out of production in 1960 it was succeeded by the KDF9, an innovative machine with a stack-based architectureit showed the company had lost none of the design verve it had inherited from Turing.
Figures
Figure. The Pilot ACE, May 1950. Jim Wilkinson (center right) and Donald Davies (right).
Figure. Control desk of the English Electric DEUCE, 1955.
Figure. A brochure for the Bendix G-15 computer, introduced in 1956.
The Digital Library is published by the Association for Computing Machinery. Copyright © 2012 ACM, Inc.
No entries found