diff --git a/include/util/cover_to_bbdd.hpp b/include/util/cover_to_bbdd.hpp index 7506652..44872e1 100644 --- a/include/util/cover_to_bbdd.hpp +++ b/include/util/cover_to_bbdd.hpp @@ -1,288 +1,272 @@ // 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 * - * The recursion stops at the leaves of the block, which are the primary inputs - * for an unpartitioned run and additionally the boundary nets of the block - * otherwise. Leaves become bbdd variables, everything above them is built as - * bbdd nodes. + * 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; - // constants are shared between every block and are always in the table if (node_i == 1 || node_i == 0) { return table->get_node_p(node_i); } - // a leaf of the block: a primary input, or a boundary net that another - // block drives. Either way it terminates the recursion and becomes a - // variable of this block's bbdd. + // 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 - // a node that is neither a constant nor a leaf has to be a gate of the block 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 * - * Builds one bbdd per root of the block over the block's leaves and registers - * it in the table under the matching name. The caller owns the table: it has - * to be initialised with a chain variable ordering over the leaf ids of this - * block, and it has to be freed and reinitialised between blocks. - * - * The visited flags of the network are used to memoize nodes to table indices. - * They therefore have to be cleared by the caller between two blocks, because - * indices of a previous table do not mean anything in the current one. + * 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 * - * Converts the whole network as a single block, which is the unpartitioned - * behaviour: every primary input is a bbdd variable and every primary output - * gets its own bbdd. - * * @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 a2701ca..93aa7b6 100644 --- a/include/util/partition.hpp +++ b/include/util/partition.hpp @@ -1,391 +1,380 @@ // 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 * - * A block is a cone of logic whose input support is limited to a configurable - * number of signals. Blocks are disjoint with respect to their gates, so every - * gate of the network is owned by exactly one block, and they are connected to - * each other through boundary nets: a leaf of one block is either a primary - * input, a constant, or a root of another block. + * 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; }; 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 * - * Mirrors mockturtle::expand0_towards_tfi, with one difference: a node that is - * already owned by another block terminates the expansion just like a primary - * input does. Without that the cone would grow through foreign blocks and - * duplicate their logic. - * - * Only replaces a leaf by its fanins when doing so does not increase the size - * of the cut, hence "zero cost". Expects all leaves to be painted in the - * current color and paints every node it pulls into the cut. + * 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 * - * Mirrors mockturtle::detail::select_next_fanin_to_expand_tfi with a caller - * supplied terminal predicate. Picks the fanin that is referenced most often - * by the current cut, because expanding it is the most likely to be paid back - * by a later zero cost merge, and breaks ties towards the higher fanout node. + * 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; } } // 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. * * @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) { 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); 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)}); } return blocks; } /** * @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"; 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 3a9fb9a..28b666e 100644 --- a/src/convert_bbdd.cpp +++ b/src/convert_bbdd.cpp @@ -1,366 +1,351 @@ // 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 * - * init_table zeroes every entry it allocates, so handing each of a few - * thousand blocks the full table size would spend far more time clearing - * memory than building diagrams. The table therefore scales with the block's - * variable count, capped by what the user asked for with -t. - * - * The factor is empirical. Peak occupancy is driven by the intermediate nodes - * that merging and sifting create, not by the size of the final diagram, and - * nothing is collected in between, so it runs well above the 2^k bound on the - * reduced diagram. Measured peaks on c432 and c880: - * - * k 6 8 10 12 14 16 - * peak 1.1k 2.6k 5.0k 11.3k 26.4k 86.5k - * - * 8 * 2^k with a floor of 16k keeps three to fifteen times headroom over - * those. A block that still overflows aborts inside the library, which has no - * resize; raising -t is the escape hatch, and the peak occupancy is reported - * so it is visible how close a run came. + * 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; int sifting_repetitions = 1; int table_size = 20000000; uint32_t max_inputs = 0; int opt; while ((opt = getopt(argc, argv, "i:vhr:t:n:")) != -1) { switch (opt) { case 'i': dump_order = true; order_output_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 '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] " << 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::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)); 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::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]); } - // the chain variable ordering is built over the renumbered ids, which are - // the contiguous range 2..k+1 that POS(in, cvo) needs to stay a bijection 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") .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"); #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"); 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; } diff --git a/synth.sh b/synth.sh index 6344227..7f4a020 100755 --- a/synth.sh +++ b/synth.sh @@ -1,208 +1,203 @@ #!/bin/bash BBDD_SCRIPT="yosys/bbdd_synth_muxxor.ys" BDD_SCRIPT="yosys/bdd_synth.ys" MUXIG_SCRIPT="yosys/muxig_synth.ys" TEMP_DIR="temp" LIBERTY_FILE="liberty/nem_thesis.lib" TIMEOUT="2m" #1 minute timeout for now TECHMAP_BBDD="yosys/techmap_bbdd.v" TABLE_SIZE="300000" MAX_INPUTS=0 # 0 disables partitioning, i.e. one diagram over all inputs print_options(){ echo "(1) Synthesis Verilog file with bbdd optimization" echo "(2) Synthesis Verilog file with bdd optimization" echo "(3) Synthesis Verilog file with muxig optimization" echo "(e) Exit" } safe_path() { local unsafe_path="$1" echo "$(printf '%s\n' "$unsafe_path" | sed 's/[&/\]/\\&/g')" } process_input() { file_name=$(basename "$file_path") # with extension file_base="${file_name%.*}" # without # get top module name read -p "top module [default=${file_base}] " top_module top_module=${top_module:-${file_base}} #safe_file_path=$(printf '%s\n' "$file_path" | sed 's/[&/\]/\\&/g') safe_file_path=$(safe_path "$file_path") #safe_techmap_path=$(printf '%s\n' "$TECHMAP_BBDD" | sed 's/[&/\]/\\&/g') } run_yosys() { # Run yosys if $nosat; then sat_replacement="#" # comment out {{SAT}} else sat_replacement="" # replace {{SAT}} with nothing fi # options handed to the converter; the bbdd template picks them up through # {{CONV_FLAGS}}. convert_bdd takes no options, and its template has no # placeholder, so the substitution is a no-op there. conv_flags="-t $TABLE_SIZE" if [ "$MAX_INPUTS" -gt 0 ] 2>/dev/null; then conv_flags="$conv_flags -n $MAX_INPUTS" fi echo "Synthesising $file_base" sed -e "s/{{VERILOG_FILE}}/$safe_file_path/g" \ -e "s/{{TEMP_DIR}}/$TEMP_DIR/g" \ -e "s/{{TOP_MODULE}}/$top_module/g" \ -e "s/{{BASE_NAME}}/$file_base/g" \ -e "s/{{TECHMAP_BBDD}}/$safe_techmap_path/g" \ -e "s/{{LIBERTY_FILE}}/$safe_liberty_path/g" \ -e "s/{{OUT_DIR}}/$safe_out_path/g" \ -e "s/{{TIMEOUT}}/$TIMEOUT/g" \ -e "s/{{SAT}}/$sat_replacement/g" \ -e "s/{{CONV_FLAGS}}/$(safe_path "$conv_flags")/g" \ "$yosys_script" > "$TEMP_DIR/${file_base}_synth.ys" if $STRIP_NOSCOPEINFO; then sed -i 's/flatten -noscopeinfo/flatten/' "$TEMP_DIR/${file_base}_synth.ys" fi mkdir -p ${out_dir}/${file_base}/ /usr/bin/time -f "Time: %E\nCPU: %P\nMemory: %M KB" -o ${out_dir}/${file_base}/yosys_${opt_name}_time.txt yosys${yosys_flags} ${TEMP_DIR}/${file_base}_synth.ys if [ -e ${out_dir}/${file_base} ]; then - # The summary is a convenience on top of a finished run, so a missing - # interpreter or an uninstalled plotting dependency must not be reported - # as if the synthesis itself had failed. + # the summary is optional; don't report its failure as a synthesis failure if [ -n "$PYTHON" ]; then "$PYTHON" ./yosys/print_summary.py ${out_dir}/${file_base} \ || echo "[WARN] print_summary.py failed; results are still in ${out_dir}/${file_base}" else echo "[WARN] no python interpreter found; skipping print_summary.py" fi else echo "${file_base} did not finish in time" fi } synth_verilog() { local yosys_script="$1" local opt_name="$2" if ! $verbose; then yosys_flags=" -q" # is quite mode else yosys_flags="" fi safe_techmap_path=$(safe_path "$TECHMAP_BBDD") safe_liberty_path=$(safe_path "$LIBERTY_FILE") echo "Using script: $yosys_script" read -e -p 'Input file path: ' file_path # Get Output Dir read -e -p 'Output directory: ' out_dir safe_out_path=$(safe_path "$out_dir") out_dir="${out_dir%/}/" if [ -f "$file_path" ]; then process_input run_yosys if ! $nocleanup; then rm ${TEMP_DIR}/${file_base}_synth.ys rm ${TEMP_DIR}/${file_base}.blif rm -f ${TEMP_DIR}/${file_base}_bbdd.blif rm -f ${TEMP_DIR}/${file_base}_bdd.blif fi exit elif [ -d "$file_path" ]; then # extend / if not present file_path="${file_path%/}/" for file in "$file_path"*.v; do if [ -e "$file" ]; then safe_file_path=$(safe_path "$file") file_name=$(basename "$file") # with extension file_base="${file_name%.*}" # without top_module="$file_base" yosys_flags=" -q" run_yosys if ! $nocleanup; then rm ${TEMP_DIR}/${file_base}_synth.ys rm ${TEMP_DIR}/${file_base}.blif rm -f ${TEMP_DIR}/${file_base}_bbdd.blif rm -f ${TEMP_DIR}/${file_base}_bdd.blif fi fi done exit else echo "[ERROR] File ${file_path} does not exist" fi } handle_selection() { case "$1" in 1) synth_verilog $BBDD_SCRIPT "bbdd";; 2) synth_verilog $BDD_SCRIPT "bdd";; 3) synth_verilog $MUXIG_SCRIPT "muxig";; e) echo "Exiting..."; exit 0 ;; *) echo "Invalid option. Please try again." ;; esac } # Initialize booleans as false nocleanup=false nosat=false verbose=false # Parse flags while [[ $# -gt 0 ]]; do case "$1" in -nocleanup) nocleanup=true shift ;; -nosat) nosat=true shift ;; -v) verbose=true shift ;; -n) MAX_INPUTS="$2" shift 2 ;; *) echo "Unknown option: $1" echo "Usage: $0 [-nocleanup] [-nosat] [-v] [-n MAX_INPUTS]" exit 1 ;; esac done -# print_summary.py is invoked through whichever interpreter this host actually -# has; `python` is absent on distributions that ship only python3. +# some distros ship only python3 PYTHON="" for candidate in python3 python; do if command -v "$candidate" >/dev/null 2>&1; then PYTHON="$candidate" break fi done -# yosys 0.40 added `flatten -noscopeinfo`; on older yosys the flag is a hard -# error ("Command syntax error: Unknown option"), and plain `flatten` is -# equivalent there because no $scopeinfo cells are produced in the first place. -# Detect once and patch the rendered script if needed. +# yosys < 0.40 has no `flatten -noscopeinfo` (and no $scopeinfo cells to +# drop), so strip the flag there. No -q: it would silence `help` too. STRIP_NOSCOPEINFO=false if ! yosys -qp "help flatten" 2>/dev/null | grep -q -- "-noscopeinfo"; then STRIP_NOSCOPEINFO=true echo "[INFO] yosys $(yosys -V 2>/dev/null | awk '{print $2}') has no 'flatten -noscopeinfo'; stripping the flag" fi # get input file mkdir -p $TEMP_DIR while true; do if [ "$nosat" = false ]; then echo "Satisfiability check is enabled" fi print_options read -p "Enter your choice [1-3]: " choice handle_selection "$choice" echo "" done