Files
dsh 0bc5f1e6b8 Phase-parallel tape search: 22 minutes down to 2.7
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.
2026-11-06 13:24:09 +08:00

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;
}