The Von Neumann Architecture, a friend and a foe

First Draft of a Report on the EDVAC - Von Neumann

Von Neumann, anoth­er star from Göttingen, gave the next import­ant step in com­pu­ta­tion after Turing (check­out my pre­vi­ous post for Turing’s first step), in a way that, to this day, you can­’t talk about com­puters without talk­ing about Von Neumann.

Which came first: the Hardware, or the Software and Languages? In an ana­log­ous way to the chick­en and the egg prob­lem, does­n’t it seem like a fair ques­tion? Last time we saw that, even before com­puters were in people’s ima­gin­a­tion, Turing man­aged to decouple them eleg­antly. So it was a mat­ter of time for them to grow and become spe­cial­ised. I’d argue today, as a fair answer, that Von Neumann made hard­ware come first, in a way that con­di­tioned the second forever. Let’s ana­lyse this problem.

The Von Neumann Architecture.

The com­puters as we know them, are essen­tially run­ning on the Von Neumann archi­tec­ture (set aside any vari­ants, Harvard machines, stack machines, register machines… they’re all just slight vari­ations for this mat­ter), an abstract machine that mod­els a phys­ic­al imple­ment­a­tion of what we know as a computer.

It came to be known in the fam­ous paper First Draft of a Report on the EDVAC, a truly remark­able paper for his time, where Von Neumann (togeth­er with the EDVAC team) describes fam­ously, in 1945, a draft of an abstract machine, a stored-pro­gram and bin­ary machine, suc­cessor to the ENIAC, fun­ded by and for the U.S. Army’s Ballistics Research Laboratory. 1

What is it?

In §2.0, we can find a fant­ast­ic over­view of the paper, where he divides the sys­tem in six pieces:

  1. Since the device is primar­ily a com­puter, it will have to per­form the ele­ment­ary oper­a­tions of arith­met­ic most fre­quently”: a cent­ral arith­met­ic unit will have to exist, respons­ible of these oper­a­tions: what today has evolved as the ALU. [§2.2]
  2. A Central Control (CC) part to sequence the instruc­tions must be giv­en, as a gen­er­al con­trol­ler that assures instruc­tions are car­ried out. [§2.3]
  3. Any device which is to carry out long and com­plic­ated sequences of oper­a­tions must have a con­sid­er­able memory”, called M, to remem­ber the instruc­tions, the tables of val­ues of spe­cial func­tions, ini­tial con­di­tions of a prob­lem, inter­me­di­ate com­pu­ta­tions, etc. [§2.4, §2.5]
  4. An out­side record­ing medi­um R, cap­able of main­tain­ing input and out­put, inde­pend­ent of M, and there­fore decoup­ling memory from stor­age for per­form­ance reas­ons, and that can be pro­duced by any mean (typ­ing, mag­net­ic tapes, punch­ing cards, etc), there­fore decoup­ling the inter­face of R from its imple­ment­a­tion. [§2.5]
  5. An input organ I, to trans­fer inform­a­tion from R into CC and M.
  6. An out­put organ O, to trans­fer inform­a­tion from CC and M back into R.

This is, essen­tially, what the Von Neumann archi­tec­ture is all about.

The interoperation of the parts

It’s quite remark­able, if you’re some­how famil­i­ar with mod­ern hard­ware, to notice how much we owe to Von Neumann. Quite advanced at his time, he was aware of so many details we’re still fix­ing today!

The Central Arithmetic Unit, or today, the Arithmetic Logic Unit

The first and most import­ant thing is the ALU, and which oper­a­tions it requires. This mech­an­ism will always oper­ate on two ele­ments of input, i and j, built as mod­ern registers, and out­put the res­ult to a third register o. Addition and mul­ti­plic­a­tion are essen­tial, and you can imple­ment sub­trac­tion and divi­sion based on the former two [§7], or imple­ment them in ded­ic­ated hard­ware for per­form­ance reas­on [§8], as well as per­haps a square root oper­at­or for func­tion inter­pol­a­tion. Very import­antly, is a com­par­is­on oper­at­or, great­er than [§11.4], bin­ary-to-decim­al and decim­al-to-bin­ary con­ver­sions, and input and out­put oper­a­tions for the registers. The CA might pipeline instruc­tions to improve per­form­ance: Von Neumann notices that oper­a­tions like mul­ti­plic­a­tion might take many clock cycles, so pipelin­ing is then an easy improvement.

A glob­al syn­chron­ising clock will oper­ate over the entire sys­tem, mak­ing the ele­ments work at ticks of the clock: Von Neumann even goes at length dis­cuss­ing the fre­quency this clock should have in order not to tick faster than the relays and vacu­um tubes that com­pound oth­er pieces of the architecture.

Memory, the bottleneck

If you’ve heard today about RAM, or Random Access Memory, well, Von Neumann thought of it first. He acknow­ledges very early that memory would be the main per­form­ance bot­tle­neck [§12.4]: try­ing to dis­cuss the best size for M, and organ­iz­ing its lay­out, he argues that it’s import­ant the memory be organ­ised in a ran­dom access fash­ion, where cells have an address you can refer to and fetch at zero extra cost.

The Central Control Unit, CC

A fas­cin­at­ing ele­ment of the sys­tem, is that who is respons­ible for con­trol. A Central Control Unit CC will fetch M through input I word-at-a-time, and dis­tin­guish if it is an oper­a­tion, or data for the oper­a­tion, expli­citly spe­cif­ing that data and instruc­tions live togeth­er in the same memory [§14.1]. The word should prob­ably be of 32bits size, of which one is reserved for this dis­tinc­tion. Data will have a second key bit, to dis­tin­guish pos­it­ive from neg­at­ive num­bers, and the remain­ing 30 bits will rep­res­ent a float­ing point bin­ary num­ber, with $latex 28$ digits of pre­ci­sion, which he argues will be enough for all purposes.

CC will fetch the next word in sequen­tial order as how they’re dis­played in the memory lay­out: two pos­sible excep­tions are allowed to trans­fer the con­nec­tion to a dif­fer­ent place in M. These are, fetch­ing a dis­tant data, in which case con­trol is imme­di­ately trans­ferred back once the data is fetched, or a strict jump, in which case the CC will con­tin­ue being instruc­ted in the sequen­tial order from the place being jumped to [§14.3]. Just like mod­ern hard­ware does it: a CA and a CC is essen­tially all a mod­ern CPU is.

A Universal Turing Machine

This machine, as described, is indeed a UTM.

  • It has a tape with ran­dom access to improve per­form­ance, but that’s equi­val­ent to a tape where you go left or right arbit­rar­ily far as instruc­ted by the tape to the con­trol unit.
  • It has a head that reads and moves along the tape, that is, the Control Centre.
  • It has a determ­in­ist­ic trans­ition func­tion, spe­cified by the instruc­tions defined in the ALU.
  • It is Universal, it sim­u­lates every oth­er TM: the descrip­tion of a TM is mod­elled by the set of instruc­tions liv­ing in M, that is, the tape, to be fed to the CC. It can con­di­tion­ally branch, and it can arbit­rar­ily modi­fy its memory.
  • And a last touch, it is eas­ily repro­gram­mable! Change the source R, load the new source into M, and you can very eas­ily change the whole sim­u­la­tion to a new TM!

Down the rabbit hole

Down the Rabbit HoleVon Neumann remains sat­is­fied giv­ing per­form­ance num­bers: the vacu­um tubes of his times were already a thou­sand times faster than a human neur­al syn­apse [§4.3], and tech­niques to reduce com­pu­ta­tion needs for cer­tain oper­a­tions were easy to find and eleg­ant to imple­ment [§5.4]. He even said once on an inter­view that he’d nev­er expect more than half a dozen com­puters on a coun­try: even a vis­ion­ary would­n’t ima­gine how far would we go with computers!

But Von Neumann is not see­ing the prob­lem, or at he’s releg­at­ing it to some­thing unim­port­ant. CC will fetch the next word” [§14.1], “The device will in gen­er­al pro­duce more numer­ic­al mater­i­al than the final res­ult” [§1.3], “There must be orders avail­able to instruct CC to trans­fer con­trol to any oth­er desired point in M” [§14.3], and so on and so forth. His pro­grams name the inter­me­di­ate steps, struc­ture their flow of con­trol with far jumps and reads, and fetch instruc­tion and data through a bot­tle­neck. Something is going on there, perhaps.

Next, we’ll see how this mod­el con­di­tioned Hardware and Programming for times to come. And the cri­ti­cism will come from per­haps a man that inflic­ted more dam­age to these wounds. Stay tuned!

  1. Remember as well Von Neumann’s involve­ment in the Manhattan Project, which, by the way, launched its infam­ous atom­ic bombs just two months after the pub­lic­a­tion of this paper.

3 Replies to “The Von Neumann Architecture, a friend and a foe”

  1. […] C abstract machine to which the C lan­guage codes, is, as I have said before, a sequen­tial V.N. machine, where memory is flat and lives far away from the arith­met­ic unit, its cells are addressed by […]

  2. […] On a pre­vi­ous post, we talked about Von Neumann’s Turing Complete mod­el for a com­puter. A CPU, some Memory, and I/O. It was beau­ti­ful, but it had its dis­ad­vant­ages, and an unfor­tu­nate leg­acy. Today, John Backus will lead our jour­ney through these matters. […]

  3. […] Next, Von Neumann will take over Turing’s papers, and design an archi­tec­ture for a Turing com­plete machine, that is, a machine equi­val­ent to the UTM, which is, a machine that can com­pute everything com­put­able; i.e., essen­tially, a UTM. […]

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.