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)