MIX

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 storage (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];
CMPXADDR,i(0:5)compare rX with memory[ADDR + rIi];
CMP? ADDR,i(0:5)compare rI? with memory[ADDR + rIi];
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">Binary-coded decimal</span> System of digitally encoding numbers

In computing and electronic systems, binary-coded decimal (BCD) is a class of binary encodings of decimal numbers where each digit is represented by a fixed number of bits, usually four or eight. Sometimes, special bit patterns are used for a sign or other indications.

<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.

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."

In computing, endianness is the order or sequence of bytes of a word of digital data in computer memory. Endianness is primarily expressed as big-endian (BE) or little-endian (LE). A big-endian system stores the most significant byte of a word at the smallest memory address and the least significant byte at the largest. A little-endian system, in contrast, stores the least-significant byte at the smallest address. Bi-endianness is a feature supported by numerous computer architectures that feature switchable endianness in data fetches and stores or for instruction fetches. Other orderings are generically called middle-endian or mixed-endian.

A computer number format is the internal representation of numeric values in digital device hardware and software, such as in programmable computers and calculators. Numerical values are stored as groupings of bits, such as bytes and words. The encoding between numerical values and bit patterns is chosen for convenience of the operation of the computer; the encoding used by the computer's instruction set generally requires conversion for external use, such as for printing and display. Different types of processors may have different internal representations of numerical values and different conventions are used for integer and real numbers. Most calculations are carried out with number formats that fit into a processor register, but some software systems allow representation of arbitrarily large numbers using multiple words of memory.

x86 assembly language is the name for the family of assembly languages which provide some level of backward compatibility with CPUs back to the Intel 8008 microprocessor, which was launched in April 1972. It is used to produce object code for the x86 class of processors.

KERNAL is Commodore's name for the ROM-resident operating system core in its 8-bit home computers; from the original PET of 1977, followed by the extended but strongly related versions used in its successors: the VIC-20, Commodore 64, Plus/4, C16, and C128.

<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.

<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.

<span class="mw-page-title-main">Decimal computer</span> Computer operating on base-10 numbers

Decimal computers are computers which can represent numbers and addresses in decimal as well as providing instructions to operate on those numbers and addresses directly in decimal, without conversion to a pure binary representation. Some also had a variable wordlength, which enabled operations on numbers with a large number of digits.

In computing and telecommunications, a unit of information is the capacity of some standard data storage system or communication channel, used to measure the capacities of other systems and channels. In information theory, units of information are also used to measure information contained in messages and the entropy of random variables.

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.

<span class="mw-page-title-main">Nicolet 1080</span>

The Nicolet 1080 computer was the successor of the Nicolet 1070/PDP-8 computer, released in 1971 by Nicolet Instrument Corporation, which operated between 1966 and 1992 in Madison, Wisconsin. As a part of a data processing mainframe, model 1080 allowed NMR spectrum analysis by the use of fast Fourier transform (FFT) algorithms. The processing of big amounts of data at a fast rate was possible thanks to the uncommon 20 bits architecture, which was a significant performance advantage over other systems based on 8 and 16 bits architectures.

<span class="mw-page-title-main">COP400</span>

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.

References

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