The sequential search is memory bound on its hash table, so the split that
works is inside a Dial bucket, not across the graph:
* the table is read only for the whole bucket, so threads probe it with no
locking -- 99.7% of the work, since only about one edge in four hundred
lands on an unseen state
* misses and dist improvements are buffered per thread and applied by one
serial pass after the bucket
Cost order is untouched, so the answer is identical. Measured at limit 60:
threads wall states
1 12.40s 7,671,626
8 2.68s 7,671,626
16 2.20s 7,671,626
32 2.14s 7,671,626
and at the full limit 82 (the run that used to take 1350s): 162s, 414,631,673
states, cost 75 in 6 blocks -- the same program.
%synth now uses this by default. examples/full_add.r8asm assembles in 166s
instead of ~23 minutes and still produces the 90 character tape, checked on the
machine for all eight combinations.
The earlier attempt -- one worker per possible first block -- stays in
r8veritas.hh behind opt.threads but off by default; it duplicated the middle of
the graph and cost three to four times the work.
70 lines
2.4 KiB
C++
70 lines
2.4 KiB
C++
// Drives the phase-parallel tape search on the full adder so it can be timed
|
|
// against the sequential one.
|
|
#include "r8forge/r8veritas.hh"
|
|
#include "r8forge/r8veritas_phase.hh"
|
|
#include <cstdlib>
|
|
#include <iostream>
|
|
|
|
using V = r8veritas<6>;
|
|
|
|
int main(int argc, char **argv) {
|
|
const int limit = argc > 1 ? std::atoi(argv[1]) : 82;
|
|
const unsigned threads = argc > 2 ? unsigned(std::atoi(argv[2])) : 1u;
|
|
|
|
V v;
|
|
auto raw = v.generate_truthtable([](V::cell inp) -> V::cell {
|
|
unsigned a = inp & 1, b = (inp >> 1) & 1, c = (inp >> 2) & 1;
|
|
unsigned s = a ^ b ^ c;
|
|
unsigned co = (a & b) | (a & c) | (b & c);
|
|
return V::cell((co << 4) | (s << 3) | (inp & 0b111));
|
|
});
|
|
|
|
// same input space r8veritas uses: the 3 relevant bits, identity start
|
|
using E = r8par::engine<6, 3>;
|
|
using key = typename E::key;
|
|
key start = {}, goal = {};
|
|
for (int j = 0; j < 8; j++)
|
|
for (int b = 0; b < 6; b++) {
|
|
if (j & (1 << b))
|
|
E::put(start, b, E::get(start, b) | (uint64_t(1) << j));
|
|
if ((*raw.second)[size_t(j)] & (1u << b))
|
|
E::put(goal, b, E::get(goal, b) | (uint64_t(1) << j));
|
|
}
|
|
|
|
// the 378 blocks: pure sacrifice plus every mask, both op modes
|
|
std::vector<std::array<int, 3>> ins;
|
|
for (int s = 0; s < 6; s++) {
|
|
ins.push_back({s, 0, 0});
|
|
for (int sub = 1; sub < (1 << 5); sub++) {
|
|
int m = 0, bit = 0;
|
|
for (int b = 0; b < 6; b++)
|
|
if (b != s)
|
|
m |= ((sub >> bit++) & 1) << b;
|
|
ins.push_back({s, m, 0});
|
|
ins.push_back({s, m, 1});
|
|
}
|
|
}
|
|
|
|
std::array<int, 6> addr = {0, 1, 2, 3, 4, 5};
|
|
std::cout << "limit " << limit << ", threads " << threads << ", "
|
|
<< ins.size() << " blocks\n";
|
|
const auto res = r8par::search<6, 3>(start, goal, ins, addr, limit, threads,
|
|
600'000'000ull);
|
|
if (!res.found) {
|
|
std::cout << "no program <= " << limit << " " << res.states
|
|
<< " states, " << res.seconds << "s " << res.message << "\n";
|
|
return res.proven ? 0 : 2;
|
|
}
|
|
std::cout << "cost " << res.cost << ", " << res.prog.size() << " blocks, "
|
|
<< res.states << " states, " << res.seconds << "s\n";
|
|
for (const auto &i : res.prog) {
|
|
std::cout << " sacrifice " << i[0] << " " << (i[2] ? "SET1" : "FLIP")
|
|
<< " {";
|
|
for (int b = 0; b < 6; b++)
|
|
if (i[1] & (1 << b))
|
|
std::cout << " " << b;
|
|
std::cout << " }\n";
|
|
}
|
|
return 0;
|
|
}
|