MMIX 2009

a RISC computer for the third millennium

Thirty years have passed since the MIX computer was designed, and computer architecture has been converging during those years towards a rather different style of machine. Therefore it is time to replace MIX with a new computer that contains even less saturated fat than its predecessor.

Exercise 1.3.1--25 in Fundamental Algorithms speaks of an extended MIX called MixMaster, which is upward compatible with the old version. But MixMaster itself is hopelessly obsolete; although it allows for several gigabytes of memory, we can't even use it with ASCII code to get lowercase letters. And ouch, the standard subroutine calling convention of MIX is irrevocably based on self-modifying instructions! Decimal arithmetic and self-modifying code were popular in 1962, but they sure have disappeared quickly as machines have gotten bigger and faster. A completely new design is called for, based on the principles of RISC architecture as expounded for example in Computer Architecture by Hennessy and Patterson.

So I have developed MMIX, a computer that I plan to use instead of MIX when I prepare the ``ultimate'' editions of Volumes 1--3. For the next ten years or so, I plan to be working on Volume 4 and issuing it in fascicles of about 128 pages each; I will also be putting out a few fascicles of updates to Vols. 1--3, whenever Volume 4 refers to material that should logically be in prior volumes but wasn't known when those volumes came out. For example, one section of Volume 4 will talk about using the fullword logical operators of MMIX; therefore I've already prepared the First Fascicle, a Volume-1-update tutorial about MMIX. (You can also purchase it as a spiffy paperback and/or eBook.)

On this webpage I will mention only the bare bones of the design, so that people can decide if they want to dig deeper.

Brief outline

MMIX is a machine that operates primarily on 64-bit words. It has 256 general-purpose 64-bit registers that each can hold either fixed-point or floating-point numbers. Most instructions have the 4-byte form `OP X Y Z', where each of OP, X, Y, and Z is a single 8-bit byte. For example, if OP is the code for ADD the meaning is ``X=Y+Z''; i.e., ``Set register X to the contents of register Y plus the contents of register Z.'' The 256 possible OP codes fall into a dozen or so easily remembered categories.

The designers of important real-world processor chips (e.g., MIPS and ALPHA) have helped me with the design of MMIX. So I'm excited about the prospects.

The operating system

The original MIX computer ran fine without an operating system. You could bootstrap it with punched cards or paper tape and do everything yourself. But nowadays such power is no longer in the hands of ordinary users. The MMIX hardware, like all other computing machines made today, relies on an operating system to get jobs started in their own address spaces and to provide I/O capabilities.

Whenever anybody has asked if I will be writing a book about operating systems, my reply has always been ``Nix.'' Therefore the name of MMIX's operating system, NNIX, should come as no surprise.

From time to time I will necessarily have to refer to things that NNIX does for its users, but I have no intention of building NNIX myself. Life is too short. It would be wonderful if some expert in operating system design became inspired to write a book that explains exactly how to construct a nice, clean NNIX kernel for an MMIX chip. The MMIX fascicle includes a level-50 exercise that asks a highly motivated reader to ``Write a book about operating systems, which includes a complete design of an NNIX kernel for the MMIX architecture.'' Other alternatives are also possible; for example, somebody at the Free Software Foundation might decide to come up with an alternative system called GNNIX.

Why have a machine language?

Many readers are no doubt thinking, ``Why does Knuth replace MIX by another machine instead of just sticking to a high-level programming language? Hardly anybody uses assemblers these days.''

Such people are entitled to their opinions, and they need not bother reading the machine-language parts of my books. But the reasons for machine language that I gave in the preface to Volume 1, written in the early 1960s, remain valid today:

• One of the principal goals of my books is to show how high-level constructions are actually implemented in machines, not simply to show how they are applied. I explain coroutine linkage, tree structures, random number generation, high-precision arithmetic, radix conversion, packing of data, combinatorial searching, recursion, etc., from the ground up.
• The programs needed in my books are generally so short that their main points can be grasped easily.
• People who are more than casually interested in computers should have at least some idea of what the underlying hardware is like. Otherwise the programs they write will be pretty weird.
• Machine language is necessary in any case, as output of many of the software programs I describe.
• Expressing basic methods like algorithms for sorting and searching in machine language makes it possible to carry out meaningful studies of the effects of cache and RAM size and other hardware characteristics (memory speed, pipelining, multiple issue, lookaside buffers, the size of cache blocks, etc.) when comparing different schemes.

Moreover, if I did use a high-level language, what language should it be? In the 1960s I would probably have chosen Algol W; in the 1970s, I would then have had to rewrite my books using Pascal; in the 1980s, I would surely have changed everything to C; in the 1990s, I would have had to switch to C++ and then probably to Java. In the 2000s, yet another language will no doubt be de rigueur. I cannot afford the time to rewrite my books as languages go in and out of fashion; languages aren't the point of my books, the point is rather what you can do in your favorite language. My books focus on timeless truths.

Therefore I will continue to use English as the high-level language in TAOCP, and I will continue to use a low-level language to indicate how machines actually compute. Readers who only want to see algorithms that are already packaged in a plug-in way, using a trendy language, should buy other people's books.

The good news is that programming for RISC machines is pleasant and simple, when the RISC machine has a nice clean design. So I need not dwell on arcane, fiddly little details that distract from the main points. In this respect MMIX will be significantly better than MIX.

Call for volunteers

All of the MIX programs in Volumes 1--3 will need to be rewritten in MMIX, before I finish the ``ultimate'' edition of those volumes that I plan to write after Volume 5 is completed. The current target date for the ultimate volumes is the year 2020, so there is plenty of time to do the conversion. But I think it will be an instructive undertaking if different groups of students from around the world try to do the necessary translations first, perhaps in friendly competitions, long before I get into the act.