MMIX

MMIX is a 64-bit reduced-instruction-set (RISC) computer architecture designed by Donald Knuth, together with its assembly language MMIXAL. It is not a commercial chip but a carefully specified paper machine — a complete, internally consistent computer that exists primarily to teach machine-level programming and the precise analysis of algorithms. MMIX is the machine on which the running times in Knuth’s The Art of Computer Programming (TAOCP) are measured, and it was created expressly to retire MIX, the idiosyncratic decimal/binary hybrid machine that had served that role since the 1960s.

The name is a Roman numeral: MMIX = 2009, a playful nod to the new millennium in which the machine was meant to live, and a number Knuth chose because it is the arithmetic mean of the model numbers of several real machines that inspired its design. Knuth introduced MMIX in 1999 and, after more than a decade of refinement, came to regard the design as effectively final.

History & Origins

By the late 1990s, the MIX machine at the heart of TAOCP was showing its age. MIX dated from 1968 and reflected the computer architecture of that era: it could be operated in either a decimal or a binary mode, used byte sizes that were deliberately ambiguous, and bore little resemblance to the load/store RISC designs that had come to dominate real hardware. Knuth wanted a machine that students could relate to the processors actually being built, while remaining simple enough to reason about exactly.

Knuth did not design MMIX alone. He has credited substantial input from leading computer architects, most notably John L. Hennessy, a principal designer of the MIPS architecture, and Richard L. Sites, an architect of DEC’s Alpha. The result borrows the clean, regular flavor of commercial RISC machines while remaining a teaching instrument rather than a product.

MMIX was first presented publicly in 1999, in lectures at Stanford and to the Boston ACM chapter, and was documented the same year in the Springer volume MMIXware: A RISC Computer for the Third Millennium. That book is itself a literate program: the assembler, simulators, and test suite are presented as readable, woven source code in Knuth’s CWEB system.

Design Philosophy

MMIX is governed by a few strong principles, several of them characteristic of Knuth’s broader work.

A realistic but idealized RISC

MMIX is a load/store architecture: arithmetic and logical operations work only on registers, and dedicated LD*/ST* instructions move data to and from memory. Instructions are uniformly four bytes (32 bits) wide and almost all follow the same simple shape:

        OP  X, Y, Z

where OP is an 8-bit opcode and X, Y, and Z are 8-bit fields naming registers or immediate values. This regularity makes both hand-assembly and pipeline analysis tractable. The opcode space is fully populated — there are 256 opcodes, leaving essentially no undefined instructions — so the instruction set feels complete rather than ad hoc.

Generous, uniform registers

An MMIX machine has 256 general-purpose registers, written $0 through $255, each holding a 64-bit word. There are also 32 special-purpose registers (such as the remainder register rR, the arithmetic-status register rA, and registers supporting the procedure-call stack). General registers are untyped: the same 64 bits can be treated as a signed or unsigned integer, an IEEE 754 floating-point number, or an address, depending on the instruction applied.

Clean rules, few surprises

MMIX is big-endian and addresses memory as a flat 64-bit space of bytes, with naturally aligned access to wydes (2 bytes), tetras (4 bytes), and octas (8 bytes) — Knuth’s deliberately distinctive terminology. Floating-point arithmetic follows the IEEE 754 standard, and the architecture specifies exactly how exceptions, rounding, and interrupts behave, so that program behavior is fully determined and analyzable.

A register stack for procedure calls

One of MMIX’s more elegant features is a hardware-assisted register stack. The PUSHJ/POP mechanism and the “local” portion of the register file let a subroutine receive a fresh window of registers, making calling conventions cheap and clean — a teaching-friendly take on ideas seen in register-window machines like SPARC.

The MMIXAL Assembly Language

Programmers write MMIX code in MMIXAL (MMIX Assembly Language). It is a small, readable assembler with labels, the IS directive for symbolic constants, GREG for allocating global registers, and LOC for placing data and code. A short example:

        LOC   #100              % place code at address 0x100
Main    GETA  $255,String       % $255 <- address of the string
        TRAP  0,Fputs,StdOut    % print it
        TRAP  0,Halt,0          % stop
String  BYTE  "Hello, world!",10,0

MMIXAL is assembled into .mmo object files (MMIX object format), which run on Knuth’s simulators. The package ships two simulators: MMIX-SIM, a straightforward behavioral interpreter, and a more elaborate pipeline (meta-)simulator that models a configurable superscalar implementation, caches, and timing — useful for studying how instruction-level parallelism affects real running times.

Tooling and Ecosystem

Although MMIX is a paper machine, it has surprisingly real tooling:

• MMIXware — Knuth’s own assembler, simulators, documentation, and test suite, distributed as literate CWEB programs and placed in the public domain (royalty-free).
• GCC and GNU Binutils — the GNU toolchain carries an MMIX target (mmix-knuth-mmixware), contributed by Hans-Peter Nilsson and included in mainline GCC since the 3.1 series in 2002, so C and C++ can be compiled to MMIX.
• University resources — the Munich University of Applied Sciences hosts an extensive MMIX site with documentation, instruction references, and prebuilt binaries, and participates in maintaining the tools.
• Hardware experiments — projects like fpgammix describe MMIX in Verilog for FPGA synthesis, and Knuth has whimsically described what a hardware MMIX might contain, but no commercial MMIX processor has ever been manufactured.

Evolution

MMIX changed relatively little after its introduction, but its details were refined over more than a decade. The introductory material that became TAOCP Volume 1, Fascicle 1, MMIX: A RISC Computer for the New Millennium, circulated in draft form (a notable revision is dated February 15, 2004) and was published in book form in 2005. Knuth completed final versions of the core architecture, assembly-language, and simulator documents on October 17, 2013, and the MMIXware software received a last maintenance update on February 13, 2023, by which point he considered the design entirely stable and handed ongoing care to volunteers.

The larger evolution is editorial: Knuth’s long-term plan is for every machine-language example in The Art of Computer Programming to be expressed in MMIX rather than MIX. Because the earlier volumes were written against MIX, this is a substantial translation effort, taken up in part by the volunteer MMIXmasters.

Current Relevance

MMIX occupies a deliberately narrow but durable niche. It is unlikely you will ship production software for it, yet it remains one of the most carefully specified teaching architectures in existence, and it is the canonical machine for anyone working through TAOCP at the instruction level. Its presence in GCC also makes it a recurring example in discussions of compiler back-ends and code generation for a clean RISC target. Active maintenance has slowed by design — Knuth wanted a stable target so that published analyses would not drift — but documentation, simulators, and the GNU port all remain available and usable today.

Why It Matters

MMIX matters because of what it is trying to do: provide a single, exact, unchanging yardstick against which the cost of algorithms can be measured. By replacing the dated MIX with a machine that mirrors real RISC design — load/store operation, fixed-width instructions, a large uniform register file, IEEE floating point — Knuth gave generations of readers an idealized but believable computer to reason about. It is a reminder that an instruction set can be a work of pedagogy and even craftsmanship, designed not to sell silicon but to make the analysis of algorithms precise, honest, and teachable.

Sources: MMIX — Wikipedia, Knuth: MMIX News, MMIXware: A RISC Computer for the Third Millennium (Springer), MMIX Instruction Set — Hochschule München, GCC 3.1 Release Notes.