This chapter is from the book
This chapter is from the book
This chapter is from the book
The ARMAC: 1955–1958
The MC continued to make improvements to the design, and they built new machines based upon the ARRA.
The FERTA was built two years later (1955) and was installed at the Fokker factory next to Schiphol Airport. It was used to calculate matrices used for the design of the wings of the F27 Friendship. The architecture was similar to the ARRA, but memory was expanded to 4,096 34-bit words and speed was doubled to ∽100 instructions per second, probably because the density of each track on the drum had doubled.
The ARMAC was another ARRA derivative that followed one year later (1956). It could execute 1,000 instructions per second because a small bank of core memory was used to buffer tracks on the drum. This machine had 1,200 tubes and consumed 10 kilowatts.
This was a period of intense hardware experimentation and improvement, but not much improvement in the software architecture—particularly the instruction set. However, the increase in memory and speed allowed Dijkstra to consider a previously untenable problem.
Dijkstra’s Algorithm: The Minimum Path
“What is the shortest way to travel from Rotterdam to Groningen, in general: from given city to given city. It is the algorithm for the shortest path, which I designed in about twenty minutes. One morning [in 1956] I was shopping in Amsterdam with my young fiancée, and tired, we sat down on the café terrace to drink a cup of coffee and I was just thinking about whether I could do this, and I then designed the algorithm for the shortest path. As I said, it was a twenty-minute invention. In fact, it was published in ’59, three years later. The publication is still readable, it is, in fact, quite nice. One of the reasons that it is so nice was that I designed it without pencil and paper. I learned later that one of the advantages of designing without pencil and paper is that you are almost forced to avoid all avoidable complexities. Eventually, that algorithm became to my great amazement, one of the cornerstones of my fame.”
—Edsger Dijkstra, 2001
Dijkstra chose the problem because he wanted to demonstrate the power of the ARMAC with a non-numerical problem that normal people could understand. He wrote the demonstration code to find the shortest path from one city to another through a simplified traffic network between 647 cities in the Netherlands.
The algorithm is not a difficult one to understand. It’s a matter of a few nested loops, a bit of sorting, and a fair bit of data manipulation. But imagine writing this code without pointers. Without recursion. Without a call instruction for your subroutines. Imagine having to access your data by modifying the addresses within individual instructions. Further, consider the problems of optimizing this program to keep track of data from being flushed in and off the drum from the core buffer. My mind rebels at the thought!
Having dispensed with the demonstration, Dijkstra then created a similar algorithm to solve a more practical problem. The backplane of the next computer, the X1, had a vast number of interconnections, and copper is a precious metal. So he wrote the minimum spanning tree algorithm to minimize the amount of copper wire used on that backplane.
Solving these kinds of graph algorithms was a step toward the computer science that we recognize today. Dijkstra used the computer to solve problems that were not strictly numerical in nature.
