diff --git a/include/bbdd b/include/bbdd index 47b08d4..8f5c692 160000 --- a/include/bbdd +++ b/include/bbdd @@ -1 +1 @@ -Subproject commit 47b08d44edeec62656360fa3394861686a849ad0 +Subproject commit 8f5c692c534fe92acbf9e9ae060f5192c6564ddc diff --git a/src/convert_bbdd.cpp b/src/convert_bbdd.cpp index 60c0876..3a9fb9a 100644 --- a/src/convert_bbdd.cpp +++ b/src/convert_bbdd.cpp @@ -1,166 +1,366 @@ // Copyright 2025 Oliver Theimer +#include +#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. + * + * @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 use_order_input = 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:")) != -1) { + while ((opt = getopt(argc, argv, "i:vhr:t:n:")) != -1) { switch (opt) { case 'i': - use_order_input = true; + 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] [-r ordering_output_file] " << std::endl; + << " [-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] " + 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; } - std::vector cvo_input_v; - if (use_order_input) { - std::string line; - std::cout << "Enter variable ordering separated by spaces (leave empty for " - "default ordering): "; - std::getline(std::cin, line); - std::stringstream str_s(line); - int num; - while (str_s >> num) { - cvo_input_v.push_back(num); + 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; } - if (cover._storage->inputs.size() != cvo_input_v.size() && - !cvo_input_v.empty()) { - std::cerr << "[ERROR] Number of variables in ordering does not match " - "number of inputs\n"; - return EXIT_FAILURE; + } + + // 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); + } } } - use_order_input = true; - cvo_input_v = {}; - printf("[INFO] cover with %zu nodes\n", cover._storage->nodes.size()); - Unique_table table; - table.init_table(table_size, cover.get_module_name()); - if (use_order_input && !cvo_input_v.empty()) { - table.init_cvo(cover._storage->inputs, cvo_input, cvo_input_v); - } else { - table.init_cvo(cover._storage->inputs, cvo_none); - } - std::filesystem::path order_output_dir_path; - std::filesystem::path base_name_path; - std::filesystem::path order_file_path; + ////////////////////////////////////////////////////////////////////////// + // 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; - if (use_order_input) { - order_output_dir_path = order_output_dir; - base_name_path = base_name; + 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 = order_output_dir_path / base_name_path; - bool order_file_exitsts = std::filesystem::exists(order_file_path); + 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 (!order_file_exitsts) { - order_file << "order_in;order_pos;height;nodes\n"; + if (!exists) { + order_file << "block;order_in;order_pos;height;nodes\n"; } } - cover_to_bbdd(&table, cover, use_height, sifting_repetitions); - std::cout << "[INFO] BBDD created\n"; - if (vis) { - std::cout << "[INFO] dumping result into .dot file\n"; - table.dump_table(); - table.dump_dot("temp/" + base_name + ".dot", cover.signal_map); - system( - ("dot -Tpng temp/" + base_name + ".dot -o temp/" + base_name + ".png") - .c_str()); - } + + 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"); + table.print_cache_stats(); + table.dump_cache_stats("temp/" + base_name + "_cache_stats.csv"); #endif - if (use_order_input) { - std::cout - << "[INFO] Writing ordering, total height, total number of nodes to " - << order_file_path << "\n"; - dump_ordering(table.cvo, order_file); - order_file << ";" << table.get_total_height() << ";" - << table.get_total_number_nodes() << "\n"; + + 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(); } - std::cout << "[INFO] Writing bbdd into blif file\n"; - table.write_blif( - "temp/" + base_name + "_bbdd" + (use_height ? "_height" : "") + ".blif", - cover.get_module_name(), cover.signal_map, cover._storage->inputs.size()); - table.free_table(); + + 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; }