diff --git a/include/util/cover_to_bbdd.hpp b/include/util/cover_to_bbdd.hpp index 44872e1..9baaa27 100644 --- a/include/util/cover_to_bbdd.hpp +++ b/include/util/cover_to_bbdd.hpp @@ -1,272 +1,234 @@ // Copyright 2025 Oliver Theimer #pragma once #include #include #include #include #include "../bbdd/include/bbdd.hpp" #include "../bbdd/include/bbdd_node.hpp" #include "../bbdd/include/unique_table.hpp" #include "mockturtle/traits.hpp" #include "partition.hpp" #include "util.hpp" #define LEFT_CHILD(node) node.children[0].index #define RIGHT_CHILD(node) node.children[1].index #define CUBE(node) ntk._storage->data.covers[node.data[1].h1] int nodes_visited; using namespace mockturtle; -/** - * @brief maps network nodes to the bbdd variables of a single block - * - * The bbdd chain variable ordering addresses its variables through - * `POS(in, cvo)`, which is a plain `in % cvo->size()`, so the variable ids of - * a block have to be the contiguous range `2 .. k+1` for that modulo to be a - * bijection. Network node indices of a block are arbitrary, hence this - * indirection: `local[n]` is the variable id of node `n`, or 0 when `n` is not - * a leaf of the block. - */ -struct leaf_map_t { - /// node index -> bbdd variable id in 2..k+1, 0 when not a leaf - std::vector local; - /// bbdd variable id - 2 -> node index - std::vector nodes; - - uint32_t operator[](uint64_t n) const { return local[n]; } - size_t size() const { return nodes.size(); } -}; - -/** - * @brief builds the leaf map of a block - * - * @param network_size number of nodes in the network the block came from - * @param leaves leaves of the block, at most one bbdd variable each - * @return leaf map assigning the contiguous ids 2..k+1 to the leaves - */ -inline leaf_map_t make_leaf_map(size_t network_size, - std::vector const &leaves) { - leaf_map_t map; - map.local.assign(network_size, 0); - map.nodes.reserve(leaves.size()); - for (uint64_t const &l : leaves) { - map.local[l] = static_cast(map.nodes.size()) + 2; - map.nodes.push_back(l); - } - return map; -} /** * @brief recursively creates a bbdd based on the given network * * Recursion stops at leaf_map leaves (PIs, plus boundary nets when * partitioned). * * @tparam Ntk template for which network type is used * @param table unique table in which the bbdd should be stored in * @param ntk input network data structure that should be converted * @param leaf_map maps the leaves of the block to their bbdd variable ids * @param node_i starting node from which onwards the bbdd should be created, * will be used for the recursion * @param output_completed statistics that are used in the recursion to properly * show the progress bar * @param show_progress whether the progress bar should be drawn * @return root node of the created bbdd */ template static bbdd_node_t *create_bbdd(Unique_table *table, Ntk &ntk, leaf_map_t const &leaf_map, const auto &node_i, int output_completed, bool show_progress) { static_assert(has_is_ci_v, "Ntk does not implement the is_ci method"); const auto &node = ntk._storage->nodes[node_i]; bbdd_node_t *f, *g, *result; if (node_i == 1 || node_i == 0) { return table->get_node_p(node_i); } // block leaf (PI or boundary net) -> variable if (leaf_map[node_i]) { assert(node_i < pow(2, 31)); return table->insert_node({{leaf_map[node_i], INT_MAX}, 0, 1}); } bbdd_op_t op = Util::cube_to_bbdd_op(CUBE(node)); if (ntk.visited(node_i)) { return table->get_node_p(ntk.visited(node_i)); } #ifdef DEBUG_COVER printf("[INFO] CREATE: node %d with op %s\n", node_i, bbdd_op_s[op].c_str()); #endif assert((node.children.size() == 2 || node.children.size() == 1) && "node is not a leaf of the block but has no usable fanin"); // all the logic gates except buf and inv if (node.children.size() == 2) { node_index_t f_i = LEFT_CHILD(node), g_i = RIGHT_CHILD(node); if (leaf_map[f_i] && leaf_map[g_i]) { result = base_case_two_inputs(table, leaf_map[f_i], leaf_map[g_i], op); #ifdef DEBUG_COVER printf("[INFO] CREATE: two input case %d: %d %s %d\n", result->index, f_i, bbdd_op_s[op].c_str(), g_i); #endif return result; } f = create_bbdd(table, ntk, leaf_map, LEFT_CHILD(node), output_completed, show_progress); g = create_bbdd(table, ntk, leaf_map, RIGHT_CHILD(node), output_completed, show_progress); result = merge_bbdds(table, f, g, op); #ifdef DEBUG_COVER std::cout << "[INFO] CREATE: merging " << result->index << ": " << f->index << " " << bbdd_op_s[op] << " " << g->index << "\n"; dump_node(g); #endif ntk.set_visited(node_i, result->index); if (show_progress) { Util::show_progress_bar( {{"Output", {output_completed, ntk._storage->outputs.size()}}, {"Nodes", {++nodes_visited, ntk._storage->nodes.size()}}}, 50); } return result; } else { // buf and inverter nodes f = create_bbdd(table, ntk, leaf_map, LEFT_CHILD(node), output_completed, show_progress); if (op == bbdd_inv) { result = negate_recursive(table, f); ntk.set_visited(node_i, result->index); if (show_progress) { Util::show_progress_bar( {{"Output", {output_completed, ntk._storage->outputs.size()}}, {"Nodes", {++nodes_visited, ntk._storage->nodes.size()}}}, 50); } return result; } ntk.set_visited(node_i, f->index); if (show_progress) { Util::show_progress_bar( {{"Output", {output_completed, ntk._storage->outputs.size()}}, {"Nodes", {++nodes_visited, ntk._storage->nodes.size()}}}, 50); } return f; } } /** * @brief converts one block of a partition into a bbdd forest * * One bbdd per root. The caller sets up a fresh table (CVO over the leaf ids) * per block and clears the visited flags in between. * * @tparam Ntk template of network type that should be used * @param table unique table in which the data structure should be stored * @param ntk network that holds the block * @param block block that should be converted * @param leaf_map maps the leaves of the block to their bbdd variable ids * @param root_names name of each root of the block, in the same order * @param use_height if true the height of the bbdd is used as the target * function for the sifting algorithm, otherwise the number of nodes is used * @param sifting_repetitions how often sifting should be repeated at the end * @param sift_height_limit skip sifting when the forest is taller than this, * 0 disables the limit * @param show_progress whether the per-node progress bar should be drawn */ template void block_to_bbdd(Unique_table *table, Ntk &ntk, block_t const &block, leaf_map_t const &leaf_map, std::vector const &root_names, bool use_height, int sifting_repetitions, uint32_t sift_height_limit = 30, bool show_progress = false) { assert(block.roots.size() == root_names.size()); for (size_t i = 0; i < block.roots.size(); i++) { bbdd_node_t *output = add_ref(create_bbdd(table, ntk, leaf_map, block.roots[i], static_cast(i), show_progress)); table->add_output(root_names[i], output); } for (int i = 0; i < sifting_repetitions; i++) { if (sift_height_limit == 0 || table->get_total_height() < sift_height_limit) { if (use_height) { sift(table, &Unique_table::get_total_height, table); } else { sift(table, &Unique_table::get_total_number_nodes, table); } } } } /** * @brief main conversion function that should be used as an interface, it * interact with the recursive function, instantiates the progress bar and * registers output in the unique table * * @tparam Ntk template of network type that should be used * @param table unique table in which the data structure should be stores * @param ntk data strucutre that stores the input network type which should be * converted * @param use_height if true the height of the bbdd is used as the target * function for the sifting algorithm, otherwise the number of nodes i used * @param sifting_repetitions indicates how often the sifting algorithm should be repeated at the end of the conversion */ template void cover_to_bbdd(Unique_table *table, Ntk &ntk, bool use_height, int sifting_repetitions) { static_assert(has_foreach_co_v, "Ntk does not implement the foreach_pi method"); static_assert(has_get_node_v, "Ntk does not implement the get_node method"); static_assert(has_set_visited_v, "Ntk does not implement the set_visited method"); static_assert(has_visited_v, "Ntk does not implement the set_visited method"); int index = ntk._storage->inputs.size() + 2; int output_completed = 0; nodes_visited = 0; leaf_map_t leaf_map = make_leaf_map( ntk._storage->nodes.size(), std::vector(std::begin(ntk._storage->inputs), std::end(ntk._storage->inputs))); Util::show_progress_bar( {{"Output", {output_completed, ntk._storage->outputs.size()}}, {"Nodes", {++nodes_visited, ntk._storage->nodes.size()}}}, 50); ntk.foreach_co([&ntk, &table, &index, &output_completed, &leaf_map]( const auto &node_i) { const auto &node = ntk.get_node(node_i); #ifdef DEBUG_COVER auto &n = ntk._storage->nodes[node_i]; std::cout << "output with node_i: " << node_i << " and n->index: " << " : " << n.children.size() << "\n"; #endif bbdd_node_t *output = add_ref(create_bbdd(table, ntk, leaf_map, node, output_completed, true)); Util::show_progress_bar( {{"Output", {++output_completed, ntk._storage->outputs.size()}}, {"Nodes", {++nodes_visited, ntk._storage->nodes.size()}}}, 50); table->add_output(ntk.get_signal_name(index), output); index++; }); for (int i = 0; i < sifting_repetitions; i++) { if (table->get_total_height() < 30) { if (use_height) { sift(table, &Unique_table::get_total_height, table); } else { sift(table, &Unique_table::get_total_number_nodes, table); } } } } diff --git a/include/util/partition.hpp b/include/util/partition.hpp index 93aa7b6..55ee763 100644 --- a/include/util/partition.hpp +++ b/include/util/partition.hpp @@ -1,380 +1,744 @@ // Copyright 2025 Oliver Theimer #pragma once #include #include #include #include #include #include "mockturtle/networks/cover.hpp" #include "mockturtle/utils/window_utils.hpp" #include "mockturtle/views/color_view.hpp" /** * @class block_t * @brief one subcircuit of a support-bounded partition * * Every gate is owned by exactly one block; a leaf is a primary input, a * constant, or a root of another block. */ struct block_t { /// input support of the block, at most `max_inputs` entries std::vector leaves; /// gates owned by the block, disjoint between blocks, includes the roots std::vector gates; /// gates that drive a primary output or a gate outside of this block std::vector roots; }; +/** + * @brief maps network nodes to the decision diagram variables of a single block + * + * Renumbers a block's leaves to the contiguous ids 2..k+1, because bbdd's + * POS(in, cvo) is `in % cvo->size()`. BuDDy gets `id - 2`. + */ +struct leaf_map_t { + /// node index -> diagram variable id in 2..k+1, 0 when not a leaf + std::vector local; + /// diagram variable id - 2 -> node index + std::vector nodes; + + uint32_t operator[](uint64_t n) const { return local[n]; } + size_t size() const { return nodes.size(); } +}; + +/** + * @brief builds the leaf map of a block + * + * @param network_size number of nodes in the network the block came from + * @param leaves leaves of the block, at most one diagram variable each + * @return leaf map assigning the contiguous ids 2..k+1 to the leaves + */ +inline leaf_map_t make_leaf_map(size_t network_size, + std::vector const &leaves) { + leaf_map_t map; + map.local.assign(network_size, 0); + map.nodes.reserve(leaves.size()); + for (uint64_t const &l : leaves) { + map.local[l] = static_cast(map.nodes.size()) + 2; + map.nodes.push_back(l); + } + return map; +} + namespace partition_detail { using cover_color_view = mockturtle::out_of_place_color_view; /// number of times the cut is allowed to exceed the budget before giving up, /// mirrors mockturtle::expand_towards_tfi static constexpr uint32_t MAX_ITERATIONS = 5u; /** * @brief zero cost expansion of a cut towards the transitive fanin * * mockturtle::expand0_towards_tfi, except that gates owned by another block * are terminal too, so a cone never duplicates foreign logic. * * @param ntk network wrapped in a color view * @param leaves cut that should be expanded, modified in place * @param is_terminal predicate that decides where the expansion has to stop * @return true if and only if every leaf is a terminal */ template bool expand0_bounded(Ntk const &ntk, std::vector &leaves, TermFn &&is_terminal) { using node = typename Ntk::node; bool trivial_cut = true; bool changed = true; std::vector new_leaves; while (changed) { trivial_cut = true; changed = false; for (auto it = std::begin(leaves); it != std::end(leaves);) { if (is_terminal(*it)) { ++it; continue; } trivial_cut = false; // count the fanins that are already part of the cut uint32_t count_fanin_inside = 0; std::optional outside; ntk.foreach_fanin(*it, [&](auto const &fi) { node const f = ntk.get_node(fi); if (ntk.eval_color( f, [&ntk](auto c) { return c == ntk.current_color(); })) { ++count_fanin_inside; } else { outside = f; } }); // expansion would grow the cut, leave this leaf alone if (count_fanin_inside + 1 < ntk.fanin_size(*it)) { ++it; continue; } if (outside) { if (ntk.eval_color(*outside, [&ntk](auto c) { return c != ntk.current_color(); })) { new_leaves.push_back(*outside); ntk.paint(*outside); } } it = leaves.erase(it); changed = true; } std::copy(std::begin(new_leaves), std::end(new_leaves), std::back_inserter(leaves)); new_leaves.clear(); } return trivial_cut; } /** * @brief selects the next fanin that should be pulled into the cut * * select_next_fanin_to_expand_tfi with a custom terminal predicate: the most * referenced fanin wins, ties go to the higher fanout. * * @param ntk network wrapped in a color view * @param leaves current cut * @param is_terminal predicate that decides which leaves cannot be expanded * @return the fanin to expand, or nothing when the cut is terminal */ template std::optional select_next_fanin(Ntk const &ntk, std::vector const &leaves, TermFn &&is_terminal) { using node = typename Ntk::node; std::vector> candidates; for (auto const &l : leaves) { if (is_terminal(l)) { continue; } ntk.foreach_fanin(l, [&](auto const &fi) { node const f = ntk.get_node(fi); if (ntk.is_constant(f)) { return; } auto it = std::find_if(std::begin(candidates), std::end(candidates), [&f](auto const &p) { return p.first == f; }); if (it == std::end(candidates)) { candidates.emplace_back(f, 1u); } else { ++it->second; } }); } if (candidates.empty()) { return std::nullopt; } std::pair best = candidates.front(); for (auto const &candidate : candidates) { if (candidate.second > best.second || (candidate.second == best.second && ntk.fanout_size(candidate.first) > ntk.fanout_size(best.first))) { best = candidate; } } return best.first; } +/// how many merge partners one block examines per visit; caps the merge pass +/// on designs that start out with tens of thousands of blocks +static constexpr size_t MAX_MERGE_CANDIDATES = 64u; + +/// how often the merge pass sweeps all blocks before giving up on a fixpoint +static constexpr uint32_t MAX_MERGE_PASSES = 4u; + +/** + * @brief leaf set that two blocks would have if they were merged + * + * Union of both leaf sets minus the nets either block drives, since those + * become internal. + * + * @param a leaves of the first block, sorted + * @param b leaves of the second block, sorted + * @param owner gate -> block id + 1, 0 for anything that is not a gate + * @param id_a id of the first block + * @param id_b id of the second block + * @return the merged leaf set, sorted + */ +inline std::vector merge_leaf_sets(std::vector const &a, + std::vector const &b, + std::vector const &owner, + uint32_t id_a, uint32_t id_b) { + std::vector u; + u.reserve(a.size() + b.size()); + std::set_union(std::begin(a), std::end(a), std::begin(b), std::end(b), + std::back_inserter(u)); + u.erase(std::remove_if(std::begin(u), std::end(u), + [&](uint64_t l) { + uint32_t const o = owner[l]; + return o == id_a + 1 || o == id_b + 1; + }), + std::end(u)); + return u; +} + +/** + * @brief merges blocks for as long as the budget allows + * + * Growth stops every cone on gates an earlier cone claimed, so no block ever + * exceeds one output cone. This greedily merges pairs whose merged support + * still fits `max_inputs`. Candidates are the block driving a leaf and the + * blocks sharing a leaf, capped per visit. + * + * @param ntk network the blocks were derived from + * @param cntk the same network in the color view, for collect_outputs + * @param blocks partition to merge in place; roots are recomputed afterwards + * @param owner gate -> block id + 1, updated in place and stale once the + * surviving blocks are renumbered + * @param refs scratch reference counts for collect_outputs, restored to 0 + * @param max_inputs maximum input support per block + */ +template +inline void merge_blocks(mockturtle::cover_network const &ntk, + ColorNtk const &cntk, std::vector &blocks, + std::vector &owner, + std::vector &refs, uint32_t max_inputs) { + using node = mockturtle::cover_network::node; + + uint32_t const count = static_cast(blocks.size()); + if (count < 2) { + return; + } + + std::vector alive(count, 1); + + // leaf -> blocks that have it as a leaf, so that two blocks over the same + // support find each other without scanning the whole partition + std::vector> leaf_blocks(ntk.size()); + for (uint32_t b = 0; b < count; b++) { + for (node const &l : blocks[b].leaves) { + leaf_blocks[l].push_back(b); + } + } + + // dedupes the candidate list without clearing a set on every visit + std::vector stamp(count, 0); + uint32_t stamp_id = 0; + std::vector candidates; + + bool changed = true; + for (uint32_t pass = 0; changed && pass < MAX_MERGE_PASSES; pass++) { + changed = false; + for (uint32_t b = 0; b < count; b++) { + // saturate this block before moving on: every merge changes its leaf + // set, which can open up a partner that did not fit a moment ago + for (bool grown = true; alive[b] && grown;) { + grown = false; + + ++stamp_id; + stamp[b] = stamp_id; + candidates.clear(); + for (node const &l : blocks[b].leaves) { + if (owner[l] != 0 && stamp[owner[l] - 1] != stamp_id) { + stamp[owner[l] - 1] = stamp_id; + candidates.push_back(owner[l] - 1); + } + for (uint32_t const &o : leaf_blocks[l]) { + if (stamp[o] == stamp_id) { + continue; + } + stamp[o] = stamp_id; + candidates.push_back(o); + if (candidates.size() >= MAX_MERGE_CANDIDATES) { + break; + } + } + if (candidates.size() >= MAX_MERGE_CANDIDATES) { + break; + } + } + + // smallest merged support first; first-fit gets stuck far earlier + uint32_t best = UINT32_MAX; + std::vector best_leaves; + for (uint32_t const &c : candidates) { + if (c == b || !alive[c]) { + continue; + } + std::vector leaves = + merge_leaf_sets(blocks[b].leaves, blocks[c].leaves, owner, b, c); + if (leaves.size() > max_inputs) { + continue; + } + if (best == UINT32_MAX || leaves.size() < best_leaves.size()) { + best = c; + best_leaves = std::move(leaves); + } + } + + if (best != UINT32_MAX) { + uint32_t const c = best; + std::vector leaves = std::move(best_leaves); + + std::vector gates; + gates.reserve(blocks[b].gates.size() + blocks[c].gates.size()); + std::merge(std::begin(blocks[b].gates), std::end(blocks[b].gates), + std::begin(blocks[c].gates), std::end(blocks[c].gates), + std::back_inserter(gates)); + for (node const &g : blocks[c].gates) { + owner[g] = b + 1; + } + + blocks[b].leaves = std::move(leaves); + blocks[b].gates = std::move(gates); + blocks[c] = block_t{}; + alive[c] = 0; + + for (node const &l : blocks[b].leaves) { + if (leaf_blocks[l].empty() || leaf_blocks[l].back() != b) { + leaf_blocks[l].push_back(b); + } + } + grown = true; + changed = true; + } + } + } + } + + // drop the absorbed blocks and recompute the roots of the survivors: a + // boundary net that a merge turned into an internal net is not a root any + // more unless something outside the merged block still reads it + std::vector survivors; + survivors.reserve(count); + for (uint32_t b = 0; b < count; b++) { + if (!alive[b]) { + continue; + } + std::vector roots = mockturtle::collect_outputs( + cntk, blocks[b].leaves, blocks[b].gates, refs); + std::stable_sort(std::begin(roots), std::end(roots)); + survivors.push_back(block_t{std::move(blocks[b].leaves), + std::move(blocks[b].gates), std::move(roots)}); + } + blocks = std::move(survivors); +} + } // namespace partition_detail /** * @brief splits a network into subcircuits with a bounded input support * - * Grows a cone backwards from every primary output for as long as its input - * support stays within the budget. A fanin that would push the support over - * the budget is cut instead: it becomes a boundary net, which is a leaf of the - * current block and the root of a block of its own. Repeating this until no - * boundary net is left covers every gate of the network exactly once. - * - * With a budget of at least the number of primary inputs the result is one - * block per primary output cone whose leaves are the primary inputs, which is - * the behaviour of the unpartitioned flow. + * Grows a cone back from every primary output while its support fits the + * budget; a fanin that would exceed it becomes a boundary net and the root of + * a new block. merge_blocks then joins blocks while the budget allows. + * `n >= |PI|` short-circuits to the unpartitioned single block. * * @param ntk network that should be partitioned * @param max_inputs maximum input support per block, 0 disables partitioning * @return the blocks, in the order they were discovered */ inline std::vector partition_cover(mockturtle::cover_network &ntk, uint32_t max_inputs) { using node = mockturtle::cover_network::node; const uint32_t size = ntk.size(); std::vector blocks; - // no partitioning: a single block holding the whole network - if (max_inputs == 0) { + // n == 0 or n >= |PI|: one block over all inputs. Handled explicitly because + // greedy pairwise merging can get stuck before reaching it. + if (max_inputs == 0 || max_inputs >= ntk._storage->inputs.size()) { block_t all; all.leaves.assign(std::begin(ntk._storage->inputs), std::end(ntk._storage->inputs)); ntk.foreach_gate([&](auto const &n) { all.gates.push_back(n); }); ntk.foreach_co([&](auto const &f) { node const d = ntk.get_node(f); if (std::find(std::begin(all.roots), std::end(all.roots), d) == std::end(all.roots)) { all.roots.push_back(d); } }); blocks.emplace_back(std::move(all)); return blocks; } assert(max_inputs >= mockturtle::cover_network::min_fanin_size + 1 && "budget too small to ever cover a single gate"); // block id + 1 for owned gates, 0 while a gate is still unassigned std::vector assigned(size, 0); // scratch reference counts for collect_outputs, always restored to 0 std::vector refs(size, 0); // guards against queueing the same root twice std::vector queued(size, 0); partition_detail::cover_color_view cntk{ntk}; auto is_terminal = [&](node n) { return ntk.is_constant(n) || ntk.is_ci(n) || assigned[n] != 0; }; // seed with the primary output drivers, in a deterministic order so that // repeated runs on the same design produce the same partition std::vector worklist; ntk.foreach_co([&](auto const &f) { node const d = ntk.get_node(f); if (!queued[d]) { queued[d] = 1; worklist.push_back(d); } }); // the worklist grows while it is walked: every boundary net that is cut // becomes the root of a block of its own for (size_t w = 0; w < worklist.size(); ++w) { node const root = worklist[w]; if (is_terminal(root)) { // a primary output driven straight by an input or a constant, or a // boundary net that a later cone happened to absorb continue; } // grow the cone from the root towards the inputs std::vector leaves{root}; cntk.new_color(); cntk.paint(root); bool trivial = partition_detail::expand0_bounded(cntk, leaves, is_terminal); std::optional> best; if (leaves.size() <= max_inputs) { best = leaves; } uint32_t iterations = 0; while (!trivial && (leaves.size() <= max_inputs || iterations < partition_detail::MAX_ITERATIONS)) { - auto next = partition_detail::select_next_fanin(cntk, leaves, is_terminal); + auto next = + partition_detail::select_next_fanin(cntk, leaves, is_terminal); if (!next) { break; } leaves.push_back(*next); cntk.paint(*next); trivial = partition_detail::expand0_bounded(cntk, leaves, is_terminal); iterations = leaves.size() > max_inputs ? iterations + 1 : 0; if (leaves.size() <= max_inputs && (!best || best->size() <= leaves.size())) { best = leaves; } } if (best) { leaves = *best; } // the budget could not be met even by a single gate, fall back to a block // holding just the root so that the partition still covers the network if (leaves.size() > max_inputs) { leaves.clear(); ntk.foreach_fanin(root, [&](auto const &fi) { node const f = ntk.get_node(fi); if (std::find(std::begin(leaves), std::end(leaves), f) == std::end(leaves)) { leaves.push_back(f); } }); } // everything strictly between the root and the leaves belongs to the block std::vector gates = mockturtle::cover(cntk, root, leaves); if (gates.empty()) { continue; } const uint32_t id = static_cast(blocks.size()); for (node const &g : gates) { assert(assigned[g] == 0 && "gate claimed by two blocks"); assigned[g] = id + 1; } // a gate whose fanout count is not fully explained by uses inside the // block drives either a primary output or a foreign block std::vector roots = mockturtle::collect_outputs(cntk, leaves, gates, refs); // every leaf that is a gate is a boundary net and needs a block of its own for (node const &l : leaves) { if (!ntk.is_constant(l) && !ntk.is_ci(l) && !assigned[l] && !queued[l]) { queued[l] = 1; worklist.push_back(l); } } std::stable_sort(std::begin(leaves), std::end(leaves)); std::stable_sort(std::begin(gates), std::end(gates)); std::stable_sort(std::begin(roots), std::end(roots)); - blocks.push_back(block_t{std::move(leaves), std::move(gates), - std::move(roots)}); + blocks.push_back( + block_t{std::move(leaves), std::move(gates), std::move(roots)}); } + partition_detail::merge_blocks(ntk, cntk, blocks, assigned, refs, max_inputs); + return blocks; } +/** + * @brief merges blocks for as long as the merged diagram is actually smaller + * + * Like merge_blocks, but a merge is kept only if cost_fn(merged) is below the + * sum of its parts, so the total node count never rises. Support is a poor + * proxy for diagram size. `cap` bounds the support, and with it the cost of + * a trial build; the smallest support is tried first. + * + * @param ntk network the blocks were derived from + * @param blocks partition to merge in place; roots are recomputed as it goes + * @param cap maximum input support a merged block may have + * @param max_passes how often all blocks are swept before giving up + * @param max_candidates how many partners one block examines per visit + * @param cost_fn builds a block and returns its node count; must leave the + * network as it found it + */ +template +inline void merge_blocks_by_gain(mockturtle::cover_network &ntk, + std::vector &blocks, uint32_t cap, + uint32_t max_passes, uint32_t max_candidates, + CostFn &&cost_fn) { + using node = mockturtle::cover_network::node; + + uint32_t const count = static_cast(blocks.size()); + if (count < 2 || cap == 0) { + return; + } + + partition_detail::cover_color_view cntk{ntk}; + std::vector refs(ntk.size(), 0); + std::vector owner(ntk.size(), 0); + for (uint32_t b = 0; b < count; b++) { + for (node const &g : blocks[b].gates) { + owner[g] = b + 1; + } + } + + std::vector alive(count, 1); + std::vector cost(count, 0); + for (uint32_t b = 0; b < count; b++) { + cost[b] = cost_fn(blocks[b]); + } + + std::vector> leaf_blocks(ntk.size()); + for (uint32_t b = 0; b < count; b++) { + for (node const &l : blocks[b].leaves) { + leaf_blocks[l].push_back(b); + } + } + + // dedupes the candidate list without clearing a set on every visit + std::vector stamp(count, 0); + uint32_t stamp_id = 0; + std::vector>> candidates; + + bool changed = true; + for (uint32_t pass = 0; changed && pass < max_passes; pass++) { + changed = false; + for (uint32_t b = 0; b < count; b++) { + // saturate this block before moving on: a merge changes its leaf set, + // which can open up a partner that did not fit a moment ago + for (bool grown = true; alive[b] && grown;) { + grown = false; + + ++stamp_id; + stamp[b] = stamp_id; + candidates.clear(); + + auto consider = [&](uint32_t c) { + if (c == b || !alive[c] || stamp[c] == stamp_id) { + return; + } + stamp[c] = stamp_id; + std::vector leaves = partition_detail::merge_leaf_sets( + blocks[b].leaves, blocks[c].leaves, owner, b, c); + if (leaves.size() > cap) { + return; + } + candidates.emplace_back(c, std::move(leaves)); + }; + + for (node const &l : blocks[b].leaves) { + if (owner[l] != 0) { + consider(owner[l] - 1); + } + for (uint32_t const &o : leaf_blocks[l]) { + consider(o); + } + if (candidates.size() >= max_candidates) { + break; + } + } + + std::stable_sort(std::begin(candidates), std::end(candidates), + [](auto const &x, auto const &y) { + return x.second.size() < y.second.size(); + }); + if (candidates.size() > max_candidates) { + candidates.resize(max_candidates); + } + + for (auto &candidate : candidates) { + uint32_t const c = candidate.first; + + block_t merged; + merged.leaves = std::move(candidate.second); + merged.gates.reserve(blocks[b].gates.size() + blocks[c].gates.size()); + std::merge(std::begin(blocks[b].gates), std::end(blocks[b].gates), + std::begin(blocks[c].gates), std::end(blocks[c].gates), + std::back_inserter(merged.gates)); + merged.roots = mockturtle::collect_outputs(cntk, merged.leaves, + merged.gates, refs); + std::stable_sort(std::begin(merged.roots), std::end(merged.roots)); + + uint64_t const merged_cost = cost_fn(merged); + if (merged_cost >= cost[b] + cost[c]) { + continue; + } + + for (node const &g : blocks[c].gates) { + owner[g] = b + 1; + } + blocks[b] = std::move(merged); + blocks[c] = block_t{}; + alive[c] = 0; + cost[b] = merged_cost; + + for (node const &l : blocks[b].leaves) { + if (leaf_blocks[l].empty() || leaf_blocks[l].back() != b) { + leaf_blocks[l].push_back(b); + } + } + grown = true; + changed = true; + break; + } + } + } + } + + std::vector survivors; + survivors.reserve(count); + for (uint32_t b = 0; b < count; b++) { + if (alive[b]) { + survivors.push_back(std::move(blocks[b])); + } + } + blocks = std::move(survivors); +} + /** * @brief checks the invariants a partition has to satisfy * * Meant to be called behind an assert or from a test: every gate is owned by * exactly one block, no block exceeds the budget, and every leaf is either a * primary input, a constant, or a root of some block. * * @param ntk network the blocks were derived from * @param blocks partition that should be checked * @param max_inputs budget the partition was built with, 0 skips the check * @return true if and only if the partition is well formed */ inline bool partition_is_valid(mockturtle::cover_network const &ntk, std::vector const &blocks, uint32_t max_inputs) { using node = mockturtle::cover_network::node; std::vector owner(ntk.size(), 0); std::vector is_root(ntk.size(), 0); for (size_t i = 0; i < blocks.size(); i++) { if (max_inputs > 0 && blocks[i].leaves.size() > max_inputs) { std::cerr << "[ERROR] block " << i << " has " << blocks[i].leaves.size() << " leaves, budget is " << max_inputs << "\n"; return false; } for (node const &g : blocks[i].gates) { if (owner[g] != 0) { std::cerr << "[ERROR] gate " << g << " owned by block " << owner[g] - 1 << " and block " << i << "\n"; return false; } owner[g] = static_cast(i) + 1; } for (node const &r : blocks[i].roots) { is_root[r] = 1; } } for (auto const &b : blocks) { for (node const &l : b.leaves) { if (ntk.is_constant(l) || ntk.is_ci(l)) { continue; } if (!is_root[l]) { - std::cerr << "[ERROR] leaf " << l << " is neither an input nor a root\n"; + std::cerr << "[ERROR] leaf " << l + << " is neither an input nor a root\n"; return false; } } } bool complete = true; ntk.foreach_gate([&](auto const &n) { if (owner[n] == 0) { std::cerr << "[ERROR] gate " << n << " is not covered by any block\n"; complete = false; } }); return complete; } diff --git a/src/convert_bbdd.cpp b/src/convert_bbdd.cpp index 28b666e..53e3289 100644 --- a/src/convert_bbdd.cpp +++ b/src/convert_bbdd.cpp @@ -1,351 +1,415 @@ // Copyright 2025 Oliver Theimer #include #include #include #include #include #include #include #include #include "bbdd/include/bbdd.hpp" #include "bbdd/include/unique_table.hpp" #include "util/cover_to_bbdd.hpp" #include "util/partition.hpp" #include #include #include #include /** * @brief size of the unique table to allocate for a block * * 8 * 2^k entries, floor 16k, capped by -t. init_table zeroes the whole table, * so sizing per block avoids clearing a huge one thousands of times. The * factor is empirical (peaks come from intermediate nodes, not the final * diagram). Overflow aborts, since there is no resize; raise -t. * * @param leaf_count number of variables of the block * @param table_size upper bound requested on the command line * @return capacity to allocate for this block */ static uint64_t block_table_size(size_t leaf_count, int table_size) { const uint32_t shift = static_cast(std::min(leaf_count, 17)); uint64_t wanted = 8ull * (1ull << shift); if (wanted < 16384ull) { wanted = 16384ull; } if (wanted > static_cast(table_size)) { wanted = static_cast(table_size); } return wanted; } int main(int argc, char *argv[]) { bool vis = false; bool use_height = false; bool dump_order = false; std::string order_output_dir; + // -o: where the netlist and stats go + std::string out_dir = "temp"; int sifting_repetitions = 1; int table_size = 20000000; uint32_t max_inputs = 0; + // -g: support cap for gain-driven merging, 0 = off + uint32_t gain_cap = 0; int opt; - while ((opt = getopt(argc, argv, "i:vhr:t:n:")) != -1) { + while ((opt = getopt(argc, argv, "i:vhr:t:n:g:o:")) != -1) { switch (opt) { case 'i': dump_order = true; order_output_dir = optarg; break; + case 'o': + out_dir = optarg; + break; case 'v': vis = true; break; case 'h': use_height = true; break; case 'n': { char *endptr = nullptr; long parsed = std::strtol(optarg, &endptr, 10); if (*endptr != '\0' || parsed < 0) { std::cerr << "[ERROR] Invalid integer for option -n: " << optarg << std::endl; return EXIT_FAILURE; } if (parsed != 0 && parsed < 2) { std::cerr << "[ERROR] -n must be 0 (disabled) or at least 2\n"; return EXIT_FAILURE; } max_inputs = static_cast(parsed); break; } + case 'g': { + char *endptr = nullptr; + long parsed = std::strtol(optarg, &endptr, 10); + if (*endptr != '\0' || parsed < 0) { + std::cerr << "[ERROR] Invalid integer for option -g: " << optarg + << std::endl; + return EXIT_FAILURE; + } + gain_cap = static_cast(parsed); + break; + } case 't': { char *endptr = nullptr; table_size = std::strtol(optarg, &endptr, 10); if (*endptr != '\0') { std::cerr << "[ERROR] Invalid integer for option -t: " << optarg << std::endl; return EXIT_FAILURE; } if (table_size < 0 || table_size > pow(2, 31)) { std::cerr << "[ERROR] Invalid integer: " << optarg << std::endl; return EXIT_FAILURE; } break; } case 'r': { char *endptr = nullptr; sifting_repetitions = std::strtol(optarg, &endptr, 10); if (*endptr != '\0') { std::cerr << "[ERROR] Invalid integer for option -r: " << optarg << std::endl; return EXIT_FAILURE; } break; } default: std::cerr << "Usage: " << argv[0] << " [-v] [-h] [-r repetitions] [-t table_size] " - "[-n max_inputs] [-i ordering_output_dir] " + "[-n max_inputs] [-g gain_cap] [-o output_dir] " + "[-i ordering_output_dir] " << std::endl; return EXIT_FAILURE; } } if (optind >= argc) { std::cout << "[ERROR] input file in blif format is missing\n"; - std::cerr << "[INFO] Usage: " << argv[0] << " [-v] [-n max_inputs] " + std::cerr << "[INFO] Usage: " << argv[0] + << " [-v] [-n max_inputs] [-o output_dir] " << std::endl; return EXIT_FAILURE; } std::string benchmark(argv[optind]); if (!std::filesystem::exists(benchmark)) { std::cout << "[ERROR] File does not exist\n"; return EXIT_FAILURE; } std::filesystem::path path(benchmark); std::string base_name = path.stem().string(); mockturtle::cover_network cover; if (lorina::read_blif(benchmark, mockturtle::blif_reader(cover)) != lorina::return_code::success) { std::cout << "[ERROR] While Lorina tried to read in file\n"; return EXIT_FAILURE; } printf("[INFO] cover with %zu nodes\n", cover._storage->nodes.size()); ////////////////////////////////////////////////////////////////////////// // partition the network into blocks with a bounded input support ////////////////////////////////////////////////////////////////////////// std::vector blocks = partition_cover(cover, max_inputs); assert(partition_is_valid(cover, blocks, max_inputs)); + ////////////////////////////////////////////////////////////////////////// + // merge further, but only where the merged diagram is measurably smaller + ////////////////////////////////////////////////////////////////////////// + if (gain_cap > max_inputs && max_inputs != 0 && blocks.size() > 1) { + size_t const before = blocks.size(); + // trial build, same as the writer; root names only need to be distinct + auto block_cost = [&](block_t const &b) -> uint64_t { + leaf_map_t leaf_map = make_leaf_map(cover._storage->nodes.size(), + b.leaves); + std::vector local_ids; + local_ids.reserve(b.leaves.size()); + for (size_t i = 0; i < b.leaves.size(); i++) { + local_ids.push_back(i + 2); + } + std::vector root_names; + root_names.reserve(b.roots.size()); + for (size_t i = 0; i < b.roots.size(); i++) { + root_names.push_back("t" + std::to_string(i)); + } + + Unique_table table; + if (table.init_table(block_table_size(b.leaves.size(), table_size), + cover.get_module_name()) != 0) { + // out of capacity is not a smaller diagram; refuse the merge + return UINT32_MAX; + } + table.init_cvo(local_ids, cvo_none); + block_to_bbdd(&table, cover, b, leaf_map, root_names, use_height, + sifting_repetitions, /*sift_height_limit=*/30, + /*show_progress=*/false); + uint64_t const nodes = table.get_total_number_nodes(); + table.free_table(); + delete table.cvo; + // the visited flags memoize indices of the table that was just freed + cover.clear_visited(); + return nodes; + }; + + merge_blocks_by_gain(cover, blocks, gain_cap, /*max_passes=*/3u, + /*max_candidates=*/8u, block_cost); + assert(partition_is_valid(cover, blocks, gain_cap)); + printf("[INFO] gain merge (cap %u): %zu block(s) -> %zu\n", gain_cap, + before, blocks.size()); + } + size_t max_support = 0, total_support = 0, max_gates = 0; for (block_t const &b : blocks) { max_support = std::max(max_support, b.leaves.size()); total_support += b.leaves.size(); max_gates = std::max(max_gates, b.gates.size()); } printf("[INFO] %zu block(s), support max %zu avg %.1f, largest block %zu " "gates\n", blocks.size(), max_support, blocks.empty() ? 0.0 : static_cast(total_support) / blocks.size(), max_gates); ////////////////////////////////////////////////////////////////////////// // give every signal that appears in the output netlist a name ////////////////////////////////////////////////////////////////////////// std::vector canonical(cover._storage->nodes.size()); canonical[0] = "$false"; canonical[1] = "$true"; for (uint64_t const &pi : cover._storage->inputs) { canonical[pi] = cover.get_signal_name(pi); } // primary outputs in declaration order, together with their driver std::vector> po_list; { uint32_t index = cover._storage->inputs.size() + 2; cover.foreach_co([&](auto const &f) { po_list.emplace_back(cover.get_node(f), cover.get_signal_name(index)); index++; }); } // a root that drives a primary output is named after it, so that the common // case needs no extra buffer std::vector po_first(cover._storage->nodes.size()); for (auto const &po : po_list) { if (po_first[po.first].empty()) { po_first[po.first] = po.second; } } // every root has to be named before any block is written, because a block // may use a root of a later block as one of its leaves for (block_t const &b : blocks) { for (uint64_t const &r : b.roots) { if (canonical[r].empty()) { canonical[r] = !po_first[r].empty() ? po_first[r] : "part_w" + std::to_string(r); } } } ////////////////////////////////////////////////////////////////////////// // write the netlist: one header, then the diagrams of every block ////////////////////////////////////////////////////////////////////////// - std::string out_file = "temp/" + base_name + "_bbdd" + - (use_height ? "_height" : "") + ".blif"; + std::string out_file = out_dir + "/" + base_name + "_bbdd.blif"; std::ofstream blif(out_file); if (!blif) { std::cerr << "[ERROR] cannot open " << out_file << " for writing\n"; return EXIT_FAILURE; } blif << ".model " << cover.get_module_name() << "\n"; blif << ".inputs"; for (uint64_t const &pi : cover._storage->inputs) { blif << " " << canonical[pi]; } blif << "\n.outputs"; for (auto const &po : po_list) { blif << " " << po.second; } blif << "\n.names $true\n1\n"; blif << ".names $false\n"; std::ofstream order_file; std::filesystem::path order_file_path; if (dump_order) { std::filesystem::path base_name_path(base_name); base_name_path.replace_extension(".csv"); order_file_path = std::filesystem::path(order_output_dir) / base_name_path; bool exists = std::filesystem::exists(order_file_path); order_file.open(order_file_path, std::ios::app); if (!exists) { order_file << "block;order_in;order_pos;height;nodes\n"; } } uint32_t total_nodes = 0, max_height = 0, max_free_pos = 0; for (size_t id = 0; id < blocks.size(); id++) { block_t const &b = blocks[id]; leaf_map_t leaf_map = make_leaf_map(cover._storage->nodes.size(), b.leaves); // names of the block's variables, indexed by variable id minus 2 std::vector signal_map; signal_map.reserve(b.leaves.size()); for (uint64_t const &l : b.leaves) { signal_map.push_back(canonical[l]); } std::vector root_names; root_names.reserve(b.roots.size()); for (uint64_t const &r : b.roots) { root_names.push_back(canonical[r]); } std::vector local_ids; local_ids.reserve(b.leaves.size()); for (size_t i = 0; i < b.leaves.size(); i++) { local_ids.push_back(i + 2); } // a fresh table per block: the merge and extend caches hold indices that // only mean something within one table Unique_table table; const uint64_t capacity = blocks.size() == 1 ? static_cast(table_size) : block_table_size(b.leaves.size(), table_size); // Unique_table::return_codes is private, SUCCESS is 0 if (table.init_table(capacity, cover.get_module_name()) != 0) { std::cerr << "[ERROR] could not allocate the unique table for block " << id << "\n"; return EXIT_FAILURE; } table.init_cvo(local_ids, cvo_none); block_to_bbdd(&table, cover, b, leaf_map, root_names, use_height, sifting_repetitions, /*sift_height_limit=*/30, /*show_progress=*/blocks.size() == 1); if (vis && blocks.size() == 1) { std::cout << "[INFO] dumping result into .dot file\n"; table.dump_table(); - table.dump_dot("temp/" + base_name + ".dot", signal_map); - system(("dot -Tpng temp/" + base_name + ".dot -o temp/" + base_name + - ".png") + table.dump_dot(out_dir + "/" + base_name + ".dot", signal_map); + system(("dot -Tpng " + out_dir + "/" + base_name + ".dot -o " + out_dir + + "/" + base_name + ".png") .c_str()); } max_free_pos = std::max(max_free_pos, table.get_free_pos()); max_height = std::max(max_height, table.get_total_height()); total_nodes += table.get_total_number_nodes(); if (dump_order) { order_file << id << ";"; dump_ordering(table.cvo, order_file); order_file << ";" << table.get_total_height() << ";" << table.get_total_number_nodes() << "\n"; } // a single block owns the whole module, so its node indices are already // unique and the netlist stays identical to an unpartitioned run table.write_blif_body(blif, signal_map, blocks.size() == 1 ? "" : "b" + std::to_string(id) + "_"); #ifdef CACHE_STATS table.print_cache_stats(); - table.dump_cache_stats("temp/" + base_name + "_cache_stats.csv"); + table.dump_cache_stats(out_dir + "/" + base_name + "_cache_stats.csv"); #endif table.free_table(); delete table.cvo; // the visited flags memoize node indices of the table that was just freed cover.clear_visited(); } // outputs that are not named after their driver need an explicit buffer: // a primary input or constant wired straight through, or a second primary // output on the same driver for (auto const &po : po_list) { if (canonical[po.first] != po.second) { blif << ".names " << canonical[po.first] << " " << po.second << "\n1 1\n"; } } blif << ".end\n"; blif.close(); if (dump_order) { std::cout << "[INFO] Wrote per block ordering to " << order_file_path << "\n"; order_file.close(); } printf("[INFO] BBDD created: %u nodes, max height %u, peak table use %u\n", total_nodes, max_height, max_free_pos); std::cout << "[INFO] Wrote bbdd into " << out_file << "\n"; // machine readable summary for the regression runner - std::ofstream stats("temp/" + base_name + "_bbdd_stats.csv"); + std::ofstream stats(out_dir + "/" + base_name + "_bbdd_stats.csv"); if (stats) { stats << "blocks;max_support;avg_support;max_block_gates;bbdd_nodes;" "max_height;peak_table\n"; stats << blocks.size() << ";" << max_support << ";" << (blocks.empty() ? 0.0 : static_cast(total_support) / blocks.size()) << ";" << max_gates << ";" << total_nodes << ";" << max_height << ";" << max_free_pos << "\n"; } return EXIT_SUCCESS; }