Muxcomp

Muxcomp uses an idea from FPGA logic block design: an N:1 multiplexer can be used to implement an arbitrary Boolean function of log_2(N) inputs. For example, to implement any Boolean function of 5 bits, you can use 32 bits of memory and a 32:1 mux with 5 select lines. The result of this would always be a single bit.
Most machines (and, therefore, languages) operate on 32 or 64 bits at a time. The muxcomp32 and muxcomp64 languages are two specific implementations of the muxcomp idea, simply replicating a muxcomp bit-slice 32 or 64 times respectively.
The muxcompN language uses a random-access memory model with N address bits. In other words, muxcomp32 addresses 32 bits of memory and muxcomp64 addresses 64 bits of memory, and so on.
The muxcomp32 instruction format is as follows:
 DD sel0
 DD sel1
 DD sel2
 DD sel3
 DD sel4
 DD op
 DD res
Each word is actually a 32-bit pointer, not an immediate value. This permits separation of code and data, if desired. The sel0-sel4 words encode the bit-slices of the select lines. The op word is the encoding of the Boolean function which this instruction implements.
The muxcomp64 instruction format is almost identical, it simply includes one more select word (and words are 64 bits, not 32):
 DQ sel0
 DQ sel1
 DQ sel2
 DQ sel3
 DQ sel4
 DQ sel5
 DQ op
 DQ res
Here are some example muxcomp64 instructions:
 AND:
 sel0
 sel1
 sel2
 sel3
 sel4
 sel5
 8000000000000000 #op
 res
(numeric values in hexadecimal)
This performs a bitwise-AND of sel0-sel5. Let's assign a value to sel0 and sel1 and set all other fields to ff's:
 0123456789abcdef # sel0
 123456789abcdef0 # sel1
 ffffffffffffffff # ...
 ffffffffffffffff
 ffffffffffffffff
 ffffffffffffffff
 8000000000000000 #op 
The result of executing this is:
 0020446088a8cce0
Here's another example Boolean function:
 XOR:
 0123456789abcdef # sel0
 123456789abcdef0 # sel1
 0000000000000000 # ...
 0000000000000000
 0000000000000000
 0000000000000000
 6996966996696996 #op
The result of executing this is:
 1317131f1317131f
AND and XOR are common, simple Boolean functions but you can implement more complex functions (any Boolean function of 6 inputs), such as F=(XY + Z). Combining multiple Boolean operations into a single instruction can be used to save computation steps in muxcomp.
You can also rotate the op (instruction shown with a sample value in op):
 ROL4:
 aaaaaaaaaaaaaaaa #sel0
 cccccccccccccccc #sel1
 0f0f0f0f0f0f0f0f #sel2
 f00ff00ff00ff00f #sel3
 fff0000ffff0000f #sel4
 fffffff00000000f #sel5
 0123456789abcdef #op
The result of executing this is:
 123456789abcdef0
One memory location is defined as the Program Counter (PC). Writing to this memory location has the effect of altering the flow of evaluation of instructions. The muxcomp32 language auto-increments the PC by 7 (muxcomp64 increments by 8) before each instruction is executed. If the instruction writes to the PC, the next instruction will be evaluated at the new location pointed to by the PC.
A simulator has been written in Perl with a small library of Boolean functions and some shifts. An assembler is under construction and a planned implementation of a Kogge-Stone adder will illustrate how this minimal language can be used to perform complex operations.
The planned assembler will implement two important macros, called SLICE and BOOL.
SLICE (for muxcompN) accepts a list N values, between 0 and N-1. These are encoded as slices in the select lines. For example, to implement the ROL4 instruction above:
 ROL4: SLICE[4..63,0..3]
The BOOL macro accepts any N-bit value, which is applied to the select lines. For example, to implement the XOR function above:
 XOR: BOOL[6996966996696996]
ClaytonB 00:25, 15 October 2010 (UTC)