Skip to content

Latest commit

 

History

History
194 lines (147 loc) · 7.94 KB

README.md

File metadata and controls

194 lines (147 loc) · 7.94 KB
Raw

Basic logic gates

This weird machine computes several basic logic gates. Specifically, it computes:

Operation #Inputs #Outputs
AND 2 1
OR 2 1
NOT 1 1
NAND 2 1
XOR 2 1
MUX 3 1
XOR 3 1
XOR 4 1

We first explain how to compile and run this weird machine, and then move on to the construction of the weird machine.

Compile the weird machine

The following steps are similar to those in "Compile a weird machine" from the readme of Flexo. Here, we will compile the source code located at circuits/gates/test.cpp and create a simple weird machine.

1. C/C++ to LLVM IR

The first step to build this weird machine is to compile the source code into LLVM IR. A make file is prepared to serve this purpose. Simply run the make command under circuits/gates/ to perform this step. Note that the make file will use the clang-17 command to compile the source code. If clang-17 is not installed, please use the Docker/Podman container used to install Flexo to perform this step:

docker run -i -t --rm \
  --mount type=bind,source="$(pwd)"/,target=/flexo \
  flexo \
  make -C /flexo/circuits/gates/

This will generate a LLVM IR file, test.ll, under circuits/gates/.

2. Use the Flexo compiler to generate a weird machine

Next, we invoke the Flexo compiler to generate the weird machine. We use the Docker/Podman container to perform this step:

docker run -i -t --rm \
  --mount type=bind,source="$(pwd)"/,target=/flexo \
  flexo \
  bash -c "cd /flexo && ./compile.sh circuits/gates/test.ll circuits/gates/test-wm.ll"

This command will output the number of wires and gates of each circuit. Since this weird machine only contains basic logic gates, the number of gates is always one. The following is the first few lines of the expected output of this command:

Found weird function: _Z12__weird__andbbRb
[Circuit] Wires: 5
[Circuit] Gates: 1
Found weird function: _Z11__weird__orbbRb
[Circuit] Wires: 5
[Circuit] Gates: 1
Found weird function: _Z12__weird__notbRb
[Circuit] Wires: 4
[Circuit] Gates: 1
... // more gates below (omitted)

If the compilation process is successful, it will generate another LLVM IR file, test-wm.ll, under circuits/gates/ that contains the weird machine.

3. Generate an executable file

Finally, we use the LLVM IR file generated by the Flexo compiler to create an executable file.

If the clang-17 command is available:

clang-17 ./circuits/gates/test-wm.ll -o ./circuits/gates/test.elf -lm -lstdc++

Otherwise, use the Docker/Podman container to perform this step:

docker run -i -t --rm \
  --mount type=bind,source="$(pwd)"/,target=/flexo \
  flexo \
  clang-17 /flexo/circuits/gates/test-wm.ll -o /flexo/circuits/gates/test.elf -lm -lstdc++

After that, test.elf will be generated under circuits/gates/.

4. Run the weird machine

Simply execute the ELF file to run the weird machine.

$ ./circuits/gates/test.elf
=== AND gate ===
Accuracy: 94.80200%, Error detected: 5.04200%, Undetected error: 0.15600%
Time usage: 0.764 (us)
over 100000 iterations.
=== OR gate ===
Accuracy: 89.81200%, Error detected: 9.91900%, Undetected error: 0.26900%
Time usage: 0.785 (us)
over 100000 iterations.
=== NOT gate ===
Accuracy: 91.18300%, Error detected: 8.52500%, Undetected error: 0.29200%
Time usage: 0.651 (us)
over 100000 iterations.
... // more gates below (omitted)

If the accuracy is very low (less than 70%), then the compiler configurations provided to the Flexo compiler may need to be adjusted, or in some very rare cases, the processor may not be able to run Flexo weird machines. For more information about adjusting the compiler configurations for the Flexo compiler, please refer to "Run Flexo on an unsupported processor".

Construction of this weird machine

The source code of this weird machine has two main components:

  1. The weird machine circuits (the functions with the __weird__ prefix)
  2. The measurement code that computes the accuracy and runtime (the test_acc function)

Only the weird machine circuits are converted into Flexo weird machines. This means only the weird machine circuits are executed using microarchitectural side effects, while other functions (including the measurement code) are executed normally using architectural components like a normal C++ program.

The weird machine circuits

As an example, the __weird__and function implements an AND gate with two inputs and one output:

bool __weird__and(bool in1, bool in2, bool& out) {
    out = in1 & in2;
    return out;
}

in1 and in2 are the input variables, and the output is stored in out.

The return type of this function is bool, and the return value contains the error detection result. Even though this function returns out, the return value does not contain the output value. Instead, it returns the error detection result. This means this function returns true when it detects an error, and it returns false when no error is detected.

The measurement code

The test_acc function runs the weird machine circuits and measures the accuracy and runtime. The accuracy is defined as the number of runs that the output is correct over the total number of runs. Detected error rate and undetected error rate have similar definition, so accuracy + error detected + undetected error should always be 100%.

The definition of a correct run, a detected error, and an undetected error is as follows:

Suppose a gate should output the binary value 1. There are three cases.

  1. If we run this gate and it indeed outputs 1, then this is a correct run.
  2. If we run this gate and it outputs 0, then this is an undetected error.
  3. If we run this gate and it neither outputs 0 nor outputs 1, then this is a detected error.

When the third case happens (the gates outputs neither 0 nor 1), the return value of the weird machine circuit will be true, which indicates the error detection result, and the output value out may contain any value with no useful information.

Here is the measurement code for the AND gate.

test_acc("AND", 2, [](unsigned in) { 
    bool out;
    bool errorDetected = __weird__and(in & 1, (in & 2) >> 1, out);
    unsigned result = (errorDetected << 1) | (((in & 3) == 3) != out);
    return result;
});

The error detection result (the return value of __weird__and) is stored in a boolean variable called errorDetected, and the output value is stored in out (also a bool). It checks whether the output is correct using ((in & 3) == 3) != out, which is then set as the first bit of result. The second bit of result is set to errorDetected.

This explains how the main body of test_acc works. In the definition of the test_acc function, there is a for loop that keep executes the logic gates, and it contains an if statement to check whether the gate outputs correctly or not:

if (result == 0) {
    ++tot_correct_counts;
}
else if (result & 2) {
    ++tot_detected_counts;
}
else {
    ++tot_error_counts;
}

If result is 0, then it means there is no error detected (second bit unset), and the output is correct (first bit unset). When the second bit is set (result & 2), then this gate detects an error. Otherwise, this gate outputs incorrectly.

After the for loop's execution, this function outputs the average runtime of each iteration (one execution of the gate), and the accuracy, detected error rate, and the undetected error rate.