The BFS used to walk the whole 1<<CELL_SIZE table for every edge, keep the
states in an unordered_set and the parents in a second unordered_map. For
the six plane full adder layer 4 is 642729 states, and layer 5 never
finished (75s, heading for GBs).
A state is now CELL_SIZE bit planes, each a truth table over only the
inputs that influence the answer, so a state is CELL_SIZE * 2^K bits --
48 bits for every adder-shaped problem -- and a block is a handful of
64-bit ops. The instruction list also lost its duplicated encodings
(378 instead of 762 for six planes).
The bigger win is not expanding the last layer at all. A block clears its
own plane, so for the goal to be its target goal[s] must be 0; the
preimages of the goal under each such block are enumerated exactly and
looked up in the BFS table. For full_add that is 9.3e3 lookups instead of
7.4e9 edges, which turns "unreachable" into "5 blocks, proven shortest,
7 seconds".
Results (r8veritas<6>, max_depth 5, MSVC /O2):
copy 2 33 states
clb_and 3 3398
clb_half_add 4 32898
half_add 4 32898
full_add_S 4 656528
full_add_Co 5 20388515
full_add 5 20388515 7.2s
All of those lengths are proven minimal, and the old bit_raw_add needed
eight blocks for the same slice.
Richer instruction sets were tried as well -- per destination OR/XOR, and
adding set_0 on top (6144 blocks) -- and neither admits a four-block full
adder, so five is not an artifact of the model.
CELL_SIZE stays a template parameter; the truth table compression picks K
at run time and dispatches on it. CMake flags got the same fix as r8asm:
stop clobbering CMAKE_CXX_FLAGS so Debug keeps /RTC1 and MSVC keeps /EHsc.
114 lines
3.1 KiB
C++
114 lines
3.1 KiB
C++
#include "r8veritas.hh"
|
|
#include <cstdlib>
|
|
#include <iostream>
|
|
#include <string>
|
|
#include <vector>
|
|
|
|
using problem_t = r8veritas<6>;
|
|
|
|
static problem_t::cell func_copy(problem_t::cell inp) {
|
|
const unsigned A = inp & 0b1;
|
|
return problem_t::cell((A << 1) | A);
|
|
}
|
|
|
|
static problem_t::cell func_clb_and(problem_t::cell inp) {
|
|
bool A = inp & 0b1;
|
|
bool B = inp & 0b10;
|
|
return (A & B) << 2;
|
|
}
|
|
|
|
static problem_t::cell func_clb_half_add(problem_t::cell inp) {
|
|
bool A = inp & 0b1;
|
|
bool B = inp & 0b10;
|
|
return ((A ^ B) << 1) | (A & B);
|
|
}
|
|
|
|
static problem_t::cell func_half_add(problem_t::cell inp) {
|
|
bool A = inp & 0b1;
|
|
bool B = inp & 0b10;
|
|
return ((A ^ B) << 3) | ((A & B) << 2) | (inp & 0b11);
|
|
}
|
|
|
|
static problem_t::cell func_full_add_Co(problem_t::cell inp) {
|
|
bool A = inp & 0b1;
|
|
bool B = inp & 0b10;
|
|
bool C = inp & 0b100;
|
|
bool Co = (A & B) | (A & C) | (B & C);
|
|
return (Co << 4) | (inp & 0b111);
|
|
}
|
|
|
|
static problem_t::cell func_full_add_S(problem_t::cell inp) {
|
|
bool A = inp & 0b1;
|
|
bool B = inp & 0b10;
|
|
bool C = inp & 0b100;
|
|
bool S = A ^ B ^ C;
|
|
return (S << 3) | (inp & 0b111);
|
|
}
|
|
|
|
static problem_t::cell func_full_add(problem_t::cell inp) {
|
|
bool A = inp & 0b1;
|
|
bool B = inp & 0b10;
|
|
bool C = inp & 0b100;
|
|
bool S = A ^ B ^ C;
|
|
bool Co = (A & B) | (A & C) | (B & C);
|
|
return (Co << 4) | (S << 3) | (inp & 0b111);
|
|
}
|
|
|
|
struct problem {
|
|
const char *name;
|
|
problem_t::op fn;
|
|
};
|
|
|
|
int main(int argc, char **argv) {
|
|
const int max_depth = argc > 1 ? std::atoi(argv[1]) : 5;
|
|
const bool verbose = argc > 2 ? std::atoi(argv[2]) != 0 : false;
|
|
|
|
std::vector<problem> problems = {
|
|
{"copy", func_copy},
|
|
{"clb_and", func_clb_and},
|
|
{"clb_half_add", func_clb_half_add},
|
|
{"half_add", func_half_add},
|
|
{"full_add_S", func_full_add_S},
|
|
{"full_add_Co", func_full_add_Co},
|
|
{"full_add", func_full_add},
|
|
};
|
|
|
|
for (const auto &p : problems) {
|
|
problem_t problem_obj;
|
|
problem_obj.initialize_nicknames();
|
|
problem_obj.initialize_tp_paths();
|
|
|
|
auto raw = problem_obj.generate_truthtable(p.fn);
|
|
auto compressed = problem_obj.compress_stat_space(raw);
|
|
|
|
problem_t::options opt;
|
|
opt.max_depth = max_depth;
|
|
opt.verbose = verbose;
|
|
|
|
auto res = problem_obj.solve(compressed, opt);
|
|
std::cout << "==== " << p.name << "\n";
|
|
if (!res.found) {
|
|
std::cout << " no program of length <= " << max_depth << " ("
|
|
<< res.states << " states, " << res.seconds << "s) "
|
|
<< res.message << "\n\n";
|
|
continue;
|
|
}
|
|
const bool ok = problem_obj.run_program(compressed, res.program);
|
|
std::cout << " length " << res.program.size()
|
|
<< (res.proven_optimal ? " (proven shortest)" : " (unproven)")
|
|
<< " " << res.states << " states, " << res.seconds << "s"
|
|
<< " replay: " << (ok ? "ok" : "MISMATCH") << "\n ";
|
|
problem_obj.print_program(res.program, std::cout, true);
|
|
std::cout << "\n";
|
|
|
|
if (std::string(p.name) == "full_add") {
|
|
std::cout << " r8asm:\n";
|
|
for (const auto &i : res.program) {
|
|
problem_obj.output_ins(i, std::cout, false);
|
|
std::cout << "\n";
|
|
}
|
|
}
|
|
}
|
|
return (0);
|
|
}
|