MIX (abstract machine)

Last updated
MIX
Designer Donald Knuth
Bits 31-bit
Introduced1968
Design accumulator machine
Typehypothetical
Encoding Fixed
Branching Condition code and register test
Endianness Big
OpenYes, and royalty free
Registers
9 in total

MIX is a hypothetical computer used in Donald Knuth's monograph, The Art of Computer Programming (TAOCP). MIX's model number is 1009, which was derived by combining the model numbers and names of several contemporaneous, commercial machines deemed significant by the author. Also, "MIX" read as a Roman numeral is 1009.

Contents

The 1960s-era MIX has since been superseded by a new (also hypothetical) computer architecture, MMIX, to be incorporated in forthcoming editions of TAOCP.

Software implementations for both the MIX and MMIX architectures have been developed by Knuth and made freely available (named "MIXware" and "MMIXware", respectively). Several derivatives of Knuth's MIX/MMIX emulators also exist. GNU MDK is one such software package; it is free and runs on a wide variety of platforms.

Their purpose for education is quite similar to John L. Hennessy's and David A. Patterson's DLX architecture, from Computer Organization and Design - The Hardware Software Interface.

Architecture

MIX is a hybrid binary decimal computer. When programmed in binary, each byte has 6 bits (values range from 0 to 63). In decimal, each byte has 2 decimal digits (values range from 0 to 99). Bytes are grouped into words of five bytes plus a sign. Most programs written for MIX will work in either binary or decimal, so long as they do not try to store a value greater than 63 in a single byte.

A word has the range 1,073,741,823 to 1,073,741,823 (inclusive) in binary mode, and 9,999,999,999 to 9,999,999,999 (inclusive) in decimal mode. The sign-and-magnitude representation of integers in the MIX architecture distinguishes between “0” and “+0.” This contrasts with modern computers, whose two's-complement representation of integer quantities includes a single representation for zero, but whose range for a given number of bits includes one more negative integer than the number of representable positive integers.

MIX registers
30292827262524232221201918171615141312111009080706050403020100(bit position)
Registers
±A1A2A3A4A5rA, Accumulator
±X1X2X3X4X5rX, Extension
Index registers
 ±I1.4I1.5rI1, Index 1
 ±I2.4I2.5rI2, Index 2
 ±I3.4I3.5rI3, Index 3
 ±I4.4I4.5rI4, Index 4
 ±I5.4I5.5rI5, Index 5
 ±I6.4I6.5rI6, Index 6
Program counter
 J4J5rJ, Jump
Condition code flags
 OOverflow flag
 <=>Comparison flag

Registers

There are 9 registers in MIX:

A byte is assumed to be at least 6 bits. Most instructions can specify which of the "fields" (bytes) of a register are to be altered, using a suffix of the form (first:last). The zeroth field is the one-bit sign.

MIX also records whether the previous operation overflowed, and has a one-trit comparison indicator (less than, equal to, or greater than).

Memory and input/output

The MIX machine has 4000 words of memory (each with 5 bytes and a sign), addressed from 0 to 3999. A variety of input and output devices are also included:

Instructions

Each machine instruction in memory occupies one word, and consists of 4 parts: the address (2 bytes and the sign of the word) in memory to read or write; an index specification (1 byte, describing which rI index register to use) to add to the address; a modification (1 byte) that specifies which parts of the register or memory location will be read or altered; and the operation code (1 byte). All operation codes have an associated mnemonic.

30292827262524232221201918171615141312111009080706050403020100
±AddressIndexModificationOperation

MIX programs frequently use self-modifying code, in particular to return from a subroutine, as MIX lacks an automatic subroutine return stack. Self-modifying code is facilitated by the modification byte, allowing the program to store data to, for example, the address part of the target instruction, leaving the rest of the instruction unmodified.

MIX programs are typically constructed using the MIXAL assembly language; for an example, see the list hello world programs page.

LDAADDR,i(0:5)rA:=memory[ADDR+rIi];
LDXADDR,i(0:5)rX:=memory[ADDR+rIi];
LD? ADDR,i(0:5)rI? := memory[ADDR + rIi];
LDANADDR,i(0:5)rA:=-memory[ADDR+rIi];
LDXNADDR,i(0:5)rX:=-memory[ADDR+rIi];
LD?N ADDR,i(0:5)rI? := - memory[ADDR + rIi];
STAADDR,i(0:5)memory[ADDR+rIi]:=rA;
STXADDR,i(0:5)memory[ADDR+rIi]:=rX;
ST? ADDR,i(0:5)memory[ADDR + rIi] := rI?;
STJADDR,i(0:5)memory[ADDR+rIi]:=rJ;
STZADDR,i(0:5)memory[ADDR+rIi]:=0;
ADDADDR,i(0:5)rA:=rA+memory[ADDR+rIi];
SUBADDR,i(0:5)rA:=rA-memory[ADDR+rIi];
MULADDR,i(0:5)(rA,rX):=rA*memory[ADDR+rIi];
DIVADDR,i(0:5)
rA:=int((rA,rX)/memory[ADDR+rIi]);rX:=(rA,rX)%memory[ADDR+rIi];
ENTAADDR,irA:=ADDR+rIi;
ENTXADDR,irX:=ADDR+rIi;
ENT? ADDR,irI? := ADDR + rIi;
ENNAADDR,irA:=-ADDR-rIi;
ENNXADDR,irX:=-ADDR-rIi;
ENN? ADDR,irI? := - ADDR - rIi;
INCAADDR,irA:=rA+ADDR+rIi;
INCXADDR,irX:=rX+ADDR+rIi;
INC? ADDR,irI? := rI? + ADDR + rIi;
DECAADDR,irA:=rA-ADDR-rIi;
DECXADDR,irX:=rX-ADDR-rIi;
DEC? ADDR,irI? := rI? - ADDR - rIi;
CMPAADDR,i(0:5)compare rA with memory[ADDR + rIi] and set comparison flag;
CMPXADDR,i(0:5)compare rX with memory[ADDR + rIi] and set comparison flag;
CMP? ADDR,i(0:5)compare rI? with memory[ADDR + rIi] and set comparison flag;
JMPADDR,i
rJ:=addressofnextinstruction;gotoADDR+rIi;
JSJADDR,igotoADDR+rIi;
JOVADDR,i
if(overflow)thenoverflow:=false;gotoADDR+rIi;
JNOVADDR,i
if(nooverflow)thengotoADDR+rIi;elseoverflow:=false;
JL, JE, JG ADDR,i
JGE, JNE, JLE ADDR,i
if(less,equal,greater)thengotoADDR+rIi;if(noless,unequal,nogreater)thengotoADDR+rIi;
JAN/JAZ/JAP ADDR,i
JANN/JANZ/JANP ADDR,i
if(rA<0orrA==0orrA>0)thengotoADDR+rIi;if(rA>=0orrA!=0orrA<=0)thengotoADDR+rIi;
JXN/JXZ/JXP ADDR,i
JXNN/JXNZ/JXNP ADDR,i
if (rX<0 or rX==0 or rX>0) then goto ADDR + rIi; if (rX>=0 or rX!=0 or rX<=0) then goto ADDR + rIi; 
J?N/J?Z/J?P ADDR,i
J?NN/J?NZ/J?NP ADDR,i
if (rI?<0 or rI?==0 or rI?>0) then goto ADDR + rIi; if (rI?>=0 or rI?!=0 or rI?<=0) then goto ADDR + rIi;
MOVEADDR,i(F)
for(n=0;n<F;n++,rI1++)memory[rI1]:=memory[ADDR+rIi+n];
SLA/SRA ADDR,i
SLAX/SRAX ADDR,i
SLC/SRC ADDR,i
shift rA to the left/right by ADDR+rIi bytes
shift (rA,rX) to the left/right by ADDR+rIi bytes
rotate (rA,rX) to the left/right by ADDR+rIi bytes
NOPdo nothing;
HLThalt execution;
INADDR,i(F)read in one block from input unit F
into memory[ADDR + rIi] onwards;
OUTADDR,i(F)output one block to unit F
from memory[ADDR + rIi] onwards;
IOCADDR,i(F)send control instruction to i/o unit F;
JREDADDR,i(F)if(i/ounitFisready)thengotoADDR+rIi;
JBUSADDR,i(F)if(i/ounitFisbusy)thengotoADDR+rIi;
NUMrA := numerical value of characters in (rA,rX);
CHAR(rA,rX) := character codes representing value of rA;

Implementations

MIX has been implemented in software by:

An implementation of MIX was created for the iCE40HX8K FPGA board in 2021. [3]

See also

Related Research Articles

<span class="mw-page-title-main">DEC Alpha</span> 64-bit RISC instruction set architecture

Alpha is a 64-bit reduced instruction set computer (RISC) instruction set architecture (ISA) developed by Digital Equipment Corporation (DEC). Alpha was designed to replace 32-bit VAX complex instruction set computers (CISC) and to be a highly competitive RISC processor for Unix workstations and similar markets.

In computer science, an integer is a datum of integral data type, a data type that represents some range of mathematical integers. Integral data types may be of different sizes and may or may not be allowed to contain negative values. Integers are commonly represented in a computer as a group of binary digits (bits). The size of the grouping varies so the set of integer sizes available varies between different types of computers. Computer hardware nearly always provides a way to represent a processor register or memory address as an integer.

MIPS is a family of reduced instruction set computer (RISC) instruction set architectures (ISA) developed by MIPS Computer Systems, now MIPS Technologies, based in the United States.

MMIX is a 64-bit reduced instruction set computing (RISC) architecture designed by Donald Knuth, with significant contributions by John L. Hennessy and Richard L. Sites. Knuth has said that,

MMIX is a computer intended to illustrate machine-level aspects of programming. In my books The Art of Computer Programming, it replaces MIX, the 1960s-style machine that formerly played such a role… I strove to design MMIX so that its machine language would be simple, elegant, and easy to learn. At the same time I was careful to include all of the complexities needed to achieve high performance in practice, so that MMIX could in principle be built and even perhaps be competitive with some of the fastest general-purpose computers in the marketplace."

<span class="mw-page-title-main">Endianness</span> Order of bytes in a computer word

In computing, endianness is the order in which bytes within a word of digital data are transmitted over a data communication medium or addressed in computer memory, counting only byte significance compared to earliness. Endianness is primarily expressed as big-endian (BE) or little-endian (LE), terms introduced by Danny Cohen into computer science for data ordering in an Internet Experiment Note published in 1980. The adjective endian has its origin in the writings of 18th century Anglo-Irish writer Jonathan Swift. In the 1726 novel Gulliver's Travels, he portrays the conflict between sects of Lilliputians divided into those breaking the shell of a boiled egg from the big end or from the little end. By analogy, a CPU may read a digital word big end first, or little end first.

In computer science, an instruction set architecture (ISA) is an abstract model that generally defines how software controls the CPU in a computer or a family of computers. A device or program that executes instructions described by that ISA, such as a central processing unit (CPU), is called an implementation of that ISA.

The Motorola 68000 series is a family of 32-bit complex instruction set computer (CISC) microprocessors. During the 1980s and early 1990s, they were popular in personal computers and workstations and were the primary competitors of Intel's x86 microprocessors. They were best known as the processors used in the early Apple Macintosh, the Sharp X68000, the Commodore Amiga, the Sinclair QL, the Atari ST and Falcon, the Atari Jaguar, the Sega Genesis and Sega CD, the Philips CD-i, the Capcom System I (Arcade), the AT&T UNIX PC, the Tandy Model 16/16B/6000, the Sun Microsystems Sun-1, Sun-2 and Sun-3, the NeXT Computer, NeXTcube, NeXTstation, and NeXTcube Turbo, early Silicon Graphics IRIS workstations, the Aesthedes, computers from MASSCOMP, the Texas Instruments TI-89/TI-92 calculators, the Palm Pilot, the Control Data Corporation CDCNET Device Interface, the VTech Precomputer Unlimited and the Space Shuttle. Although no modern desktop computers are based on processors in the 680x0 series, derivative processors are still widely used in embedded systems.

<span class="mw-page-title-main">64-bit computing</span> Computer architecture bit width

In computer architecture, 64-bit integers, memory addresses, or other data units are those that are 64 bits wide. Also, 64-bit central processing units (CPU) and arithmetic logic units (ALU) are those that are based on processor registers, address buses, or data buses of that size. A computer that uses such a processor is a 64-bit computer.

The DLX is a RISC processor architecture designed by John L. Hennessy and David A. Patterson, the principal designers of the Stanford MIPS and the Berkeley RISC designs (respectively), the two benchmark examples of RISC design.

<span class="mw-page-title-main">Memory address</span> Reference to a specific memory location

In computing, a memory address is a reference to a specific memory location used at various levels by software and hardware. Memory addresses are fixed-length sequences of digits conventionally displayed and manipulated as unsigned integers. Such numerical semantic bases itself upon features of CPU, as well upon use of the memory like an array endorsed by various programming languages.

The Burroughs B2500 through Burroughs B4900 was a series of mainframe computers developed and manufactured by Burroughs Corporation in Pasadena, California, United States, from 1966 to 1991. They were aimed at the business world with an instruction set optimized for the COBOL programming language. They were also known as Burroughs Medium Systems, by contrast with the Burroughs Large Systems and Burroughs Small Systems.

In computing, a word is the natural unit of data used by a particular processor design. A word is a fixed-sized datum handled as a unit by the instruction set or the hardware of the processor. The number of bits or digits in a word is an important characteristic of any specific processor design or computer architecture.

In computer architecture, 128-bit integers, memory addresses, or other data units are those that are 128 bits wide. Also, 128-bit central processing unit (CPU) and arithmetic logic unit (ALU) architectures are those that are based on registers, address buses, or data buses of that size.

A bit field is a data structure that consists of one or more adjacent bits which have been allocated for specific purposes, so that any single bit or group of bits within the structure can be set or inspected. A bit field is most commonly used to represent integral types of known, fixed bit-width, such as single-bit Booleans.

<span class="mw-page-title-main">TI-990</span> Series of 16-bit computers by Texas Instruments.

The TI-990 was a series of 16-bit minicomputers sold by Texas Instruments (TI) in the 1970s and 1980s. The TI-990 was a replacement for TI's earlier minicomputer systems, the TI-960 and the TI-980. It had several unique features, and was easier to program than its predecessors.

Little Computer 3, or LC-3, is a type of computer educational programming language, an assembly language, which is a type of low-level programming language.

An instruction set architecture (ISA) is an abstract model of a computer, also referred to as computer architecture. A realization of an ISA is called an implementation. An ISA permits multiple implementations that may vary in performance, physical size, and monetary cost ; because the ISA serves as the interface between software and hardware. Software that has been written for an ISA can run on different implementations of the same ISA. This has enabled binary compatibility between different generations of computers to be easily achieved, and the development of computer families. Both of these developments have helped to lower the cost of computers and to increase their applicability. For these reasons, the ISA is one of the most important abstractions in computing today.

The IBM System/360 architecture is the model independent architecture for the entire S/360 line of mainframe computers, including but not limited to the instruction set architecture. The elements of the architecture are documented in the IBM System/360 Principles of Operation and the IBM System/360 I/O Interface Channel to Control Unit Original Equipment Manufacturers' Information manuals.

In computer architecture, 256-bit integers, memory addresses, or other data units are those that are 256 bits wide. Also, 256-bit central processing unit (CPU) and arithmetic logic unit (ALU) architectures are those that are based on registers, address buses, or data buses of that size. There are currently no mainstream general-purpose processors built to operate on 256-bit integers or addresses, though a number of processors do operate on 256-bit data.

<span class="mw-page-title-main">COP400</span> 4-bit microcontroller family

The COP400 or COP II is a 4-bit microcontroller family introduced in 1977 by National Semiconductor as a follow-on product to their original PMOS COP microcontroller. COP400 family members are complete microcomputers containing internal timing, logic, ROM, RAM, and I/O necessary to implement dedicated controllers. Some COP400 devices were second-sourced by Western Digital as the WD4200 family. In the Soviet Union several COP400 microcontrollers were manufactured as the 1820 series.

References

  1. mix(1)   9front manual page
  2. Hardware::Simulator::MIX Perl module from CPAN
  3. "Michael Schröder / mix-fgpa". GitLab.