MIXing it up with Donald Knuth

The other day, I ran across an interesting interview with Donald Knuth. Knuth, of course, is world-famous as the creator of the Potrzebie System of Weights and Measures (1 potrzebie = The thickness of issue #26 of MAD Magazine - just ask Google!)

Only slightly less known is Knuth's series of books The Art of Computer Programming (TAOCP). Planned as a seven-volume set, the first three volumes were published in the 1970s and were considered "required reading" by most everyone studying computer science. In college, I was especially taken with Knuth's use of an invented computer architecture called MIX, as it was a mixture of several well-known (at the time) architectures, and like some other college students of the era, I wrote an extended MIX interpreter, (mine was in IBM System\370 Assembler in two boxes of punch cards), that I oh-so-cleverly called XIM.

My XIM implemented not only the standard MIX instruction set, but also added all of the architectural extensions Knuth described in the volumes, such as floating point and I/O. In the mid-70s, I wrote Knuth a letter describing XIM and asking, as an aside, when we might expect to see volume 4 published. I received a thoughtful and courteous reply, saying, essentially, not to hold my breath! Sadly, my only copy of XIM perished in an apartment fire.

Knuth since has rewritten and revised TAOCP volumes 1-3 multiple times, trying to keep it relevant for the times. (Algorithms for efficient sorting of data stored on magnetic tapes are probably not as useful as they once were.) What I missed, though, was the start, in 2005, of the publication of parts of TAOCP Volume 4! Still a work in progress, Knuth has published "Fascicles", sets of chapters from the book. Fascicles 1-4 are out, and Fascicle 0 has just been released.

What? Oh, yeah. The interview. Knuth has been an advocate of what he calls Literate Programming, which if I understand it correctly, has one write programs that are designed to be read by humans so that they can understand what the program is supposed to do. I'm all in favor of this, as a long time advocate of writing understandable code and letting the compiler handle the optimization.

Knuth also expressed disdain for "unit tests", saying "lots of time is wasted on activities that I simply never need to perform or even think about. Nothing needs to be 'mocked up.'" He also takes CPU manufacturers to task for moving to multicore:
... it looks more or less like the hardware designers have run out of ideas, and that they’re trying to pass the blame for the future demise of Moore’s Law to the software writers by giving us machines that work faster only on a few key benchmarks! I won’t be surprised at all if the whole multithreading idea turns out to be a flop, worse than the [Itanium] approach that was supposed to be so terrific-until it turned out that the wished-for compilers were basically impossible to write.
I know that important applications for parallelism exist-rendering graphics, breaking codes, scanning images, simulating physical and biological processes, etc. But all these applications require dedicated code and special-purpose techniques, which will need to be changed substantially every few years.

Well, some at Intel would take issue with that! It is certainly true that multithreading requires a different way of approaching algorithms, and there's a lot of progress in making threading easier, but there's lots more work to do.

Knuth has also revised the 1960s-era MIX, creating MMIX, a more modern 64-bit architecture.

Finally, I note that Knuth still plans to complete the seven-volume set of TAOCP. I'll look forward to that!
For more complete information about compiler optimizations, see our Optimization Notice.

1 comment

anonymous's picture

Even after finding a "full" set of the first three volumes of TAOCP (for a total of $24 so many cowznofskis ago!), I privately referred to the author as "Knuth Landwaster," which was a reference to the first Thomas Covenant trilogy by Stephen R. Donaldson.

After reading the Knuth interview and his multi-core comments, I thought he was a bit off base with the Itanium comparison. I think he really woud have wanted to make the comparison to New Coke (http://en.wikipedia.org/wiki/New_coke), a radical product change of massive proportions that met with customer disapproval and eventually was hounded from the market in favor of the original formula. I don't think Intel or AMD or IBM are going to go back to ramping clock speed on single core processors, though, no matter what hue and cry.

Add a Comment

Have a technical question? Visit our forums. Have site or software product issues? Contact support.