| /* |
| * Prepacking: Group together technology-mapped netlist blocks before packing. |
| * This gives hints to the packer on what groups of blocks to keep together during packing. |
| * Primary purpose: |
| * 1) "Forced" packs (eg LUT+FF pair) |
| * 2) Carry-chains |
| * Duties: Find pack patterns in architecture, find pack patterns in netlist. |
| * |
| * Author: Jason Luu |
| * March 12, 2012 |
| */ |
| |
| #include <cstdio> |
| #include <cstring> |
| #include <map> |
| using namespace std; |
| |
| #include "vtr_util.h" |
| #include "vtr_assert.h" |
| #include "vtr_memory.h" |
| |
| #include "vpr_types.h" |
| #include "vpr_error.h" |
| |
| #include "read_xml_arch_file.h" |
| #include "globals.h" |
| #include "atom_netlist.h" |
| #include "hash.h" |
| #include "prepack.h" |
| #include "vpr_utils.h" |
| #include "echo_files.h" |
| |
| /*****************************************/ |
| /*Local Function Declaration */ |
| /*****************************************/ |
| static int add_pattern_name_to_hash(t_hash **nhash, |
| const char *pattern_name, int *ncount); |
| static void discover_pattern_names_in_pb_graph_node( |
| t_pb_graph_node *pb_graph_node, t_hash **nhash, |
| int *ncount); |
| static void forward_infer_pattern(t_pb_graph_pin *pb_graph_pin); |
| static void backward_infer_pattern(t_pb_graph_pin *pb_graph_pin); |
| static t_pack_patterns *alloc_and_init_pattern_list_from_hash(const int ncount, |
| t_hash **nhash); |
| static t_pb_graph_edge * find_expansion_edge_of_pattern(const int pattern_index, |
| const t_pb_graph_node *pb_graph_node); |
| static void forward_expand_pack_pattern_from_edge( |
| const t_pb_graph_edge *expansion_edge, |
| t_pack_patterns *list_of_packing_patterns, |
| const int curr_pattern_index, int *L_num_blocks, const bool make_root_of_chain); |
| static void backward_expand_pack_pattern_from_edge( |
| const t_pb_graph_edge* expansion_edge, |
| t_pack_patterns *list_of_packing_patterns, |
| const int curr_pattern_index, t_pb_graph_pin *destination_pin, |
| t_pack_pattern_block *destination_block, int *L_num_blocks); |
| static int compare_pack_pattern(const t_pack_patterns *pattern_a, const t_pack_patterns *pattern_b); |
| static void free_pack_pattern(t_pack_pattern_block *pattern_block, t_pack_pattern_block **pattern_block_list); |
| static t_pack_molecule *try_create_molecule( |
| t_pack_patterns *list_of_pack_patterns, |
| std::multimap<AtomBlockId,t_pack_molecule*>& atom_molecules, |
| const int pack_pattern_index, |
| AtomBlockId blk_id); |
| static bool try_expand_molecule(t_pack_molecule *molecule, |
| const std::multimap<AtomBlockId,t_pack_molecule*>& atom_molecules, |
| const AtomBlockId blk_id, |
| const t_pack_pattern_block *current_pattern_block); |
| static void print_pack_molecules(const char *fname, |
| const t_pack_patterns *list_of_pack_patterns, const int num_pack_patterns, |
| const t_pack_molecule *list_of_molecules); |
| static t_pb_graph_node* get_expected_lowest_cost_primitive_for_atom_block(const AtomBlockId blk_id); |
| static t_pb_graph_node* get_expected_lowest_cost_primitive_for_atom_block_in_pb_graph_node(const AtomBlockId blk_id, t_pb_graph_node *curr_pb_graph_node, float *cost); |
| static AtomBlockId find_new_root_atom_for_chain(const AtomBlockId blk_id, const t_pack_patterns *list_of_pack_pattern, |
| const std::multimap<AtomBlockId,t_pack_molecule*>& atom_molecules); |
| |
| /*****************************************/ |
| /*Function Definitions */ |
| /*****************************************/ |
| |
| /** |
| * Find all packing patterns in architecture |
| * [0..num_packing_patterns-1] |
| * |
| * Limitations: Currently assumes that forced pack nets must be single-fanout |
| * as this covers all the reasonable architectures we wanted. |
| * More complicated structures should probably be handled either downstream |
| * (general packing) or upstream (in tech mapping). |
| * If this limitation is too constraining, code is designed so that this limitation can be removed. |
| */ |
| t_pack_patterns *alloc_and_load_pack_patterns(int *num_packing_patterns) { |
| int i, j, ncount, k; |
| int L_num_blocks; |
| t_hash **nhash; |
| t_pack_patterns *list_of_packing_patterns; |
| t_pb_graph_edge *expansion_edge; |
| auto& device_ctx = g_vpr_ctx.device(); |
| |
| /* alloc and initialize array of packing patterns based on architecture complex blocks */ |
| nhash = alloc_hash_table(); |
| ncount = 0; |
| for (i = 0; i < device_ctx.num_block_types; i++) { |
| discover_pattern_names_in_pb_graph_node( |
| device_ctx.block_types[i].pb_graph_head, nhash, &ncount); |
| } |
| |
| list_of_packing_patterns = alloc_and_init_pattern_list_from_hash(ncount, nhash); |
| |
| /* load packing patterns by traversing the edges to find edges belonging to pattern */ |
| for (i = 0; i < ncount; i++) { |
| for (j = 0; j < device_ctx.num_block_types; j++) { |
| expansion_edge = find_expansion_edge_of_pattern(i, device_ctx.block_types[j].pb_graph_head); |
| if (expansion_edge == nullptr) { |
| continue; |
| } |
| L_num_blocks = 0; |
| list_of_packing_patterns[i].base_cost = 0; |
| backward_expand_pack_pattern_from_edge(expansion_edge, |
| list_of_packing_patterns, i, nullptr, nullptr, &L_num_blocks); |
| list_of_packing_patterns[i].num_blocks = L_num_blocks; |
| |
| /* Default settings: A section of a netlist must match all blocks in a pack |
| * pattern before it can be made a molecule except for carry-chains. |
| * For carry-chains, since carry-chains are typically quite flexible in terms |
| * of size, it is optional whether or not an atom in a netlist matches any |
| * particular block inside the chain */ |
| list_of_packing_patterns[i].is_block_optional = (bool*) vtr::malloc(L_num_blocks * sizeof(bool)); |
| for(k = 0; k < L_num_blocks; k++) { |
| list_of_packing_patterns[i].is_block_optional[k] = false; |
| if(list_of_packing_patterns[i].is_chain && list_of_packing_patterns[i].root_block->block_id != k) { |
| list_of_packing_patterns[i].is_block_optional[k] = true; |
| } |
| } |
| break; |
| } |
| } |
| |
| //Sanity check, every pattern should have a root block |
| for(i = 0; i < ncount; ++i) { |
| if(list_of_packing_patterns[i].root_block == nullptr) { |
| VPR_THROW(VPR_ERROR_ARCH, "Failed to find root block for pack pattern %s", list_of_packing_patterns[i].name); |
| } |
| } |
| |
| free_hash_table(nhash); |
| |
| *num_packing_patterns = ncount; |
| |
| |
| return list_of_packing_patterns; |
| } |
| |
| /** |
| * Adds pack pattern name to hashtable of pack pattern names. |
| */ |
| static int add_pattern_name_to_hash(t_hash **nhash, |
| const char *pattern_name, int *ncount) { |
| t_hash *hash_value; |
| |
| hash_value = insert_in_hash_table(nhash, pattern_name, *ncount); |
| if (hash_value->count == 1) { |
| VTR_ASSERT(*ncount == hash_value->index); |
| (*ncount)++; |
| } |
| return hash_value->index; |
| } |
| |
| /** |
| * Locate all pattern names |
| * Side-effect: set all pb_graph_node temp_scratch_pad field to NULL |
| * For cases where a pattern inference is "obvious", mark it as obvious. |
| */ |
| static void discover_pattern_names_in_pb_graph_node( |
| t_pb_graph_node *pb_graph_node, t_hash **nhash, |
| int *ncount) { |
| int i, j, k, m; |
| int index; |
| bool hasPattern; |
| /* Iterate over all edges to discover if an edge in current physical block belongs to a pattern |
| If edge does, then record the name of the pattern in a hash table |
| */ |
| |
| if (pb_graph_node == nullptr) { |
| return; |
| } |
| |
| pb_graph_node->temp_scratch_pad = nullptr; |
| |
| for (i = 0; i < pb_graph_node->num_input_ports; i++) { |
| for (j = 0; j < pb_graph_node->num_input_pins[i]; j++) { |
| hasPattern = false; |
| for (k = 0; k < pb_graph_node->input_pins[i][j].num_output_edges; k++) { |
| for (m = 0; m < pb_graph_node->input_pins[i][j].output_edges[k]->num_pack_patterns; m++) { |
| hasPattern = true; |
| index = add_pattern_name_to_hash(nhash, |
| pb_graph_node->input_pins[i][j].output_edges[k]->pack_pattern_names[m], ncount); |
| if (pb_graph_node->input_pins[i][j].output_edges[k]->pack_pattern_indices == nullptr) { |
| pb_graph_node->input_pins[i][j].output_edges[k]->pack_pattern_indices = |
| (int*) vtr::malloc(pb_graph_node->input_pins[i][j].output_edges[k]->num_pack_patterns |
| * sizeof(int)); |
| } |
| pb_graph_node->input_pins[i][j].output_edges[k]->pack_pattern_indices[m] = index; |
| } |
| } |
| if (hasPattern == true) { |
| forward_infer_pattern(&pb_graph_node->input_pins[i][j]); |
| backward_infer_pattern(&pb_graph_node->input_pins[i][j]); |
| } |
| } |
| } |
| |
| for (i = 0; i < pb_graph_node->num_output_ports; i++) { |
| for (j = 0; j < pb_graph_node->num_output_pins[i]; j++) { |
| hasPattern = false; |
| for (k = 0; k < pb_graph_node->output_pins[i][j].num_output_edges; k++) { |
| for (m = 0; m < pb_graph_node->output_pins[i][j].output_edges[k]->num_pack_patterns; m++) { |
| hasPattern = true; |
| index = add_pattern_name_to_hash(nhash, |
| pb_graph_node->output_pins[i][j].output_edges[k]->pack_pattern_names[m], ncount); |
| if (pb_graph_node->output_pins[i][j].output_edges[k]->pack_pattern_indices == nullptr) { |
| pb_graph_node->output_pins[i][j].output_edges[k]->pack_pattern_indices = |
| (int*) vtr::malloc(pb_graph_node->output_pins[i][j].output_edges[k]->num_pack_patterns |
| * sizeof(int)); |
| } |
| pb_graph_node->output_pins[i][j].output_edges[k]->pack_pattern_indices[m] = index; |
| } |
| } |
| if (hasPattern == true) { |
| forward_infer_pattern(&pb_graph_node->output_pins[i][j]); |
| backward_infer_pattern(&pb_graph_node->output_pins[i][j]); |
| } |
| } |
| } |
| |
| for (i = 0; i < pb_graph_node->num_clock_ports; i++) { |
| for (j = 0; j < pb_graph_node->num_clock_pins[i]; j++) { |
| hasPattern = false; |
| for (k = 0; k < pb_graph_node->clock_pins[i][j].num_output_edges; k++) { |
| for (m = 0; m < pb_graph_node->clock_pins[i][j].output_edges[k]->num_pack_patterns; m++) { |
| hasPattern = true; |
| index = add_pattern_name_to_hash(nhash, |
| pb_graph_node->clock_pins[i][j].output_edges[k]->pack_pattern_names[m], ncount); |
| if (pb_graph_node->clock_pins[i][j].output_edges[k]->pack_pattern_indices == nullptr) { |
| pb_graph_node->clock_pins[i][j].output_edges[k]->pack_pattern_indices = |
| (int*) vtr::malloc(pb_graph_node->clock_pins[i][j].output_edges[k]->num_pack_patterns |
| * sizeof(int)); |
| } |
| pb_graph_node->clock_pins[i][j].output_edges[k]->pack_pattern_indices[m] = index; |
| } |
| } |
| if (hasPattern == true) { |
| forward_infer_pattern(&pb_graph_node->clock_pins[i][j]); |
| backward_infer_pattern(&pb_graph_node->clock_pins[i][j]); |
| } |
| } |
| } |
| |
| for (i = 0; i < pb_graph_node->pb_type->num_modes; i++) { |
| for (j = 0; j < pb_graph_node->pb_type->modes[i].num_pb_type_children; j++) { |
| for (k = 0; k < pb_graph_node->pb_type->modes[i].pb_type_children[j].num_pb; k++) { |
| discover_pattern_names_in_pb_graph_node( |
| &pb_graph_node->child_pb_graph_nodes[i][j][k], nhash, ncount); |
| } |
| } |
| } |
| } |
| |
| /** |
| * In obvious cases where a pattern edge has only one path to go, set that path to be inferred |
| */ |
| static void forward_infer_pattern(t_pb_graph_pin *pb_graph_pin) { |
| if (pb_graph_pin->num_output_edges == 1 && pb_graph_pin->output_edges[0]->num_pack_patterns == 0 && pb_graph_pin->output_edges[0]->infer_pattern == false) { |
| pb_graph_pin->output_edges[0]->infer_pattern = true; |
| if (pb_graph_pin->output_edges[0]->num_output_pins == 1) { |
| forward_infer_pattern(pb_graph_pin->output_edges[0]->output_pins[0]); |
| } |
| } |
| } |
| static void backward_infer_pattern(t_pb_graph_pin *pb_graph_pin) { |
| if (pb_graph_pin->num_input_edges == 1 && pb_graph_pin->input_edges[0]->num_pack_patterns == 0 && pb_graph_pin->input_edges[0]->infer_pattern == false) { |
| pb_graph_pin->input_edges[0]->infer_pattern = true; |
| if (pb_graph_pin->input_edges[0]->num_input_pins == 1) { |
| backward_infer_pattern(pb_graph_pin->input_edges[0]->input_pins[0]); |
| } |
| } |
| } |
| |
| /** |
| * Allocates memory for models and loads the name of the packing pattern |
| * so that it can be identified and loaded with more complete information later |
| */ |
| static t_pack_patterns *alloc_and_init_pattern_list_from_hash(const int ncount, |
| t_hash **nhash) { |
| t_pack_patterns *nlist; |
| t_hash_iterator hash_iter; |
| t_hash *curr_pattern; |
| |
| nlist = (t_pack_patterns*)vtr::calloc(ncount, sizeof(t_pack_patterns)); |
| |
| hash_iter = start_hash_table_iterator(); |
| curr_pattern = get_next_hash(nhash, &hash_iter); |
| while (curr_pattern != nullptr) { |
| VTR_ASSERT(nlist[curr_pattern->index].name == nullptr); |
| nlist[curr_pattern->index].name = vtr::strdup(curr_pattern->name); |
| nlist[curr_pattern->index].root_block = nullptr; |
| nlist[curr_pattern->index].is_chain = false; |
| nlist[curr_pattern->index].index = curr_pattern->index; |
| curr_pattern = get_next_hash(nhash, &hash_iter); |
| } |
| return nlist; |
| } |
| |
| void free_list_of_pack_patterns(t_pack_patterns *list_of_pack_patterns, const int num_packing_patterns) { |
| int i, j, num_pack_pattern_blocks; |
| t_pack_pattern_block **pattern_block_list; |
| if (list_of_pack_patterns != nullptr) { |
| for (i = 0; i < num_packing_patterns; i++) { |
| num_pack_pattern_blocks = list_of_pack_patterns[i].num_blocks; |
| pattern_block_list = (t_pack_pattern_block **)vtr::calloc(num_pack_pattern_blocks, sizeof(t_pack_pattern_block *)); |
| free(list_of_pack_patterns[i].name); |
| free(list_of_pack_patterns[i].is_block_optional); |
| free_pack_pattern(list_of_pack_patterns[i].root_block, pattern_block_list); |
| for (j = 0; j < num_pack_pattern_blocks; j++) { |
| free(pattern_block_list[j]); |
| } |
| free(pattern_block_list); |
| } |
| free(list_of_pack_patterns); |
| } |
| } |
| |
| /** |
| * Locate first edge that belongs to pattern index |
| */ |
| static t_pb_graph_edge * find_expansion_edge_of_pattern(const int pattern_index, |
| const t_pb_graph_node *pb_graph_node) { |
| int i, j, k, m; |
| t_pb_graph_edge * edge; |
| /* Iterate over all edges to discover if an edge in current physical block belongs to a pattern |
| If edge does, then return that edge |
| */ |
| |
| if (pb_graph_node == nullptr) { |
| return nullptr; |
| } |
| |
| for (i = 0; i < pb_graph_node->num_input_ports; i++) { |
| for (j = 0; j < pb_graph_node->num_input_pins[i]; j++) { |
| auto& input_pin = pb_graph_node->input_pins[i][j]; |
| for (k = 0; k < input_pin.num_output_edges; k++) { |
| for (m = 0; m < input_pin.output_edges[k]->num_pack_patterns; m++) { |
| if (input_pin.output_edges[k]->pack_pattern_indices[m] == pattern_index) { |
| return input_pin.output_edges[k]; |
| } |
| } |
| } |
| } |
| } |
| |
| for (i = 0; i < pb_graph_node->num_output_ports; i++) { |
| for (j = 0; j < pb_graph_node->num_output_pins[i]; j++) { |
| auto& output_pin = pb_graph_node->output_pins[i][j]; |
| for (k = 0; k < output_pin.num_output_edges; k++) { |
| for (m = 0; m < output_pin.output_edges[k]->num_pack_patterns; m++) { |
| if (output_pin.output_edges[k]->pack_pattern_indices[m] == pattern_index) { |
| return output_pin.output_edges[k]; |
| } |
| } |
| } |
| } |
| } |
| |
| for (i = 0; i < pb_graph_node->num_clock_ports; i++) { |
| for (j = 0; j < pb_graph_node->num_clock_pins[i]; j++) { |
| auto& clock_pin = pb_graph_node->clock_pins[i][j]; |
| for (k = 0; k < clock_pin.num_output_edges; k++) { |
| for (m = 0; m < clock_pin.output_edges[k]->num_pack_patterns; m++) { |
| if (clock_pin.output_edges[k]->pack_pattern_indices[m] == pattern_index) { |
| return clock_pin.output_edges[k]; |
| } |
| } |
| } |
| } |
| } |
| |
| for (i = 0; i < pb_graph_node->pb_type->num_modes; i++) { |
| auto& pb_mode = pb_graph_node->pb_type->modes[i]; |
| for (j = 0; j < pb_mode.num_pb_type_children; j++) { |
| for (k = 0; k < pb_mode.pb_type_children[j].num_pb; k++) { |
| edge = find_expansion_edge_of_pattern( |
| pattern_index, &pb_graph_node->child_pb_graph_nodes[i][j][k]); |
| if (edge != nullptr) { |
| return edge; |
| } |
| } |
| } |
| } |
| return nullptr; |
| } |
| |
| /** |
| * This function expands forward from the given expansion_edge. If a primtive is found that |
| * belongs to the pack pattern we are searching for, create a pack pattern block of using |
| * this primtive to be added later to the pack pattern when creating the pack pattern |
| * connections in the backward_expand_pack_pattern_from_edge function. |
| * |
| * expansion_edge: starting edge to expand forward from |
| * list_of_packing_patterns: list of packing patterns in the architecture |
| * curr_pattern_index: current packing pattern that we buildng |
| * L_num_blocks: number of primitives found to belong to this pattern so far |
| * make_root_of_chain: flag indicating that the given expansion_edge is connected |
| * to a primitive that is the root of this packing pattern |
| * |
| * Convention: Pack pattern block connections are made on backward expansion only (to make |
| * future multi-fanout support easier) so this function will not update connections |
| */ |
| static void forward_expand_pack_pattern_from_edge( |
| const t_pb_graph_edge* expansion_edge, |
| t_pack_patterns *list_of_packing_patterns, |
| const int curr_pattern_index, int *L_num_blocks, bool make_root_of_chain) { |
| int i, j, k; |
| int iport, ipin, iedge; |
| bool found; /* Error checking, ensure only one fan-out for each pattern net */ |
| t_pack_pattern_block *destination_block = nullptr; |
| t_pb_graph_node *destination_pb_graph_node = nullptr; |
| |
| found = expansion_edge->infer_pattern; |
| // if the pack pattern shouldn't be infered check if the expansion |
| // edge is annotated with the current pack pattern we are expanding |
| for (i = 0; !found && i < expansion_edge->num_pack_patterns; i++) { |
| if (expansion_edge->pack_pattern_indices[i] == curr_pattern_index) { |
| found = true; |
| } |
| } |
| // if this edge isn't annoted with the current pack pattern |
| // no need to explore it |
| if (!found) { |
| return; |
| } |
| |
| found = false; |
| // iterate over the expansion edge output pins |
| for (i = 0; i < expansion_edge->num_output_pins; i++) { |
| // check if expansion_edge parent node is a primitive (i.e num_nodes = 0) |
| if (expansion_edge->output_pins[i]->parent_node->pb_type->num_modes == 0) { |
| destination_pb_graph_node = expansion_edge->output_pins[i]->parent_node; |
| VTR_ASSERT(found == false); |
| /* Check assumption that each forced net has only one fan-out */ |
| /* This is the destination node */ |
| found = true; |
| |
| // the temp_scratch_pad points to the last primitive from this pb_graph_node that was added to a packing pattern. |
| const auto& destination_pb_temp = (t_pack_pattern_block*) destination_pb_graph_node->temp_scratch_pad; |
| // if this pb_graph_node (primitive) is not added to the packing pattern already, add it and expand all its edges |
| if (destination_pb_temp == nullptr || destination_pb_temp->pattern_index != curr_pattern_index) { |
| // a primitive that belongs to this pack pattern is found: 1) create a new pattern block, |
| // 2) assign an id to this pattern block, 3) increment the number of found blocks belonging to this |
| // pattern and 4) expand all its edges to find the other primitives that belong to this pattern |
| destination_block = (t_pack_pattern_block*)vtr::calloc(1, sizeof(t_pack_pattern_block)); |
| list_of_packing_patterns[curr_pattern_index].base_cost += compute_primitive_base_cost(destination_pb_graph_node); |
| destination_block->block_id = *L_num_blocks; |
| (*L_num_blocks)++; |
| destination_pb_graph_node->temp_scratch_pad = (void *) destination_block; |
| destination_block->pattern_index = curr_pattern_index; |
| destination_block->pb_type = destination_pb_graph_node->pb_type; |
| |
| // explore the inputs to this primitive |
| for (iport = 0; iport < destination_pb_graph_node->num_input_ports; iport++) { |
| for (ipin = 0; ipin < destination_pb_graph_node->num_input_pins[iport]; ipin++) { |
| for (iedge = 0; iedge < destination_pb_graph_node->input_pins[iport][ipin].num_input_edges; iedge++) { |
| backward_expand_pack_pattern_from_edge( |
| destination_pb_graph_node->input_pins[iport][ipin].input_edges[iedge], |
| list_of_packing_patterns, |
| curr_pattern_index, |
| &destination_pb_graph_node->input_pins[iport][ipin], |
| destination_block, L_num_blocks); |
| } |
| } |
| } |
| |
| // explore the outputs of this primtive |
| for (iport = 0; iport < destination_pb_graph_node->num_output_ports; iport++) { |
| for (ipin = 0; ipin < destination_pb_graph_node->num_output_pins[iport]; ipin++) { |
| for (iedge = 0; iedge < destination_pb_graph_node->output_pins[iport][ipin].num_output_edges; iedge++) { |
| forward_expand_pack_pattern_from_edge( |
| destination_pb_graph_node->output_pins[iport][ipin].output_edges[iedge], |
| list_of_packing_patterns, |
| curr_pattern_index, L_num_blocks, false); |
| } |
| } |
| } |
| |
| // explore the clock pins of this primtivie |
| for (iport = 0; iport < destination_pb_graph_node->num_clock_ports; iport++) { |
| for (ipin = 0; ipin < destination_pb_graph_node->num_clock_pins[iport]; ipin++) { |
| for (iedge = 0; iedge < destination_pb_graph_node->clock_pins[iport][ipin].num_input_edges; iedge++) { |
| backward_expand_pack_pattern_from_edge( |
| destination_pb_graph_node->clock_pins[iport][ipin].input_edges[iedge], |
| list_of_packing_patterns, |
| curr_pattern_index, |
| &destination_pb_graph_node->clock_pins[iport][ipin], |
| destination_block, L_num_blocks); |
| } |
| } |
| } |
| } |
| |
| // if this pb_graph_node (primitive) should be added to the pack pattern blocks |
| if (((t_pack_pattern_block*) destination_pb_graph_node->temp_scratch_pad)->pattern_index == curr_pattern_index) { |
| // if this pb_graph_node is known to be the root of the chain, update the root block and root pin |
| if(make_root_of_chain == true) { |
| list_of_packing_patterns[curr_pattern_index].chain_root_pin = expansion_edge->output_pins[i]; |
| list_of_packing_patterns[curr_pattern_index].root_block = destination_block; |
| } |
| } |
| |
| // the expansion_edge parent node is not a primitive |
| } else { |
| // continue expanding forward |
| for (j = 0; j < expansion_edge->output_pins[i]->num_output_edges; j++) { |
| if (expansion_edge->output_pins[i]->output_edges[j]->infer_pattern == true) { |
| forward_expand_pack_pattern_from_edge( |
| expansion_edge->output_pins[i]->output_edges[j], |
| list_of_packing_patterns, curr_pattern_index, |
| L_num_blocks, make_root_of_chain); |
| } else { |
| for (k = 0; k < expansion_edge->output_pins[i]->output_edges[j]->num_pack_patterns; k++) { |
| if (expansion_edge->output_pins[i]->output_edges[j]->pack_pattern_indices[k] == curr_pattern_index) { |
| if (found == true) { |
| /* Check assumption that each forced net has only one fan-out */ |
| vpr_throw(VPR_ERROR_PACK, __FILE__, __LINE__, |
| "Invalid packing pattern defined. Multi-fanout nets not supported when specifying pack patterns.\n" |
| "Problem on %s[%d].%s[%d] for pattern %s\n", |
| expansion_edge->output_pins[i]->parent_node->pb_type->name, |
| expansion_edge->output_pins[i]->parent_node->placement_index, |
| expansion_edge->output_pins[i]->port->name, |
| expansion_edge->output_pins[i]->pin_number, |
| list_of_packing_patterns[curr_pattern_index].name); |
| } |
| found = true; |
| forward_expand_pack_pattern_from_edge( |
| expansion_edge->output_pins[i]->output_edges[j], |
| list_of_packing_patterns, |
| curr_pattern_index, L_num_blocks, make_root_of_chain); |
| } |
| } // End for pack paterns of output edge |
| } |
| } // End for number of output edges |
| } |
| } // End for output pins of expansion edge |
| |
| } |
| |
| /** |
| * Find if driver of edge is in the same pattern, if yes, add to pattern |
| * Convention: Connections are made on backward expansion only (to make future multi- |
| * fanout support easier) so this function must update both source and |
| * destination blocks |
| */ |
| static void backward_expand_pack_pattern_from_edge( |
| const t_pb_graph_edge* expansion_edge, |
| t_pack_patterns *list_of_packing_patterns, |
| const int curr_pattern_index, t_pb_graph_pin *destination_pin, |
| t_pack_pattern_block *destination_block, int *L_num_blocks) { |
| int i, j, k; |
| int iport, ipin, iedge; |
| bool found; /* Error checking, ensure only one fan-out for each pattern net */ |
| t_pack_pattern_block *source_block = nullptr; |
| t_pb_graph_node *source_pb_graph_node = nullptr; |
| t_pack_pattern_connections *pack_pattern_connection = nullptr; |
| |
| found = expansion_edge->infer_pattern; |
| // if the pack pattern shouldn't be infered check if the expansion |
| // edge is annotated with the current pack pattern we are expanding |
| for (i = 0; !found && i < expansion_edge->num_pack_patterns; i++) { |
| if (expansion_edge->pack_pattern_indices[i] == curr_pattern_index) { |
| found = true; |
| } |
| } |
| |
| // if this edge isn't annoted with the current pack pattern |
| // no need to explore it |
| if (!found) { |
| return; |
| } |
| |
| found = false; |
| // iterate over all the drivers of this edge |
| for (i = 0; i < expansion_edge->num_input_pins; i++) { |
| // check if the expansion_edge parent node is a primitive (i.e num_modes == 0) |
| if (expansion_edge->input_pins[i]->parent_node->pb_type->num_modes == 0) { |
| source_pb_graph_node = expansion_edge->input_pins[i]->parent_node; |
| VTR_ASSERT(found == false); |
| /* Check assumption that each forced net has only one fan-out */ |
| /* This is the source node for destination */ |
| found = true; |
| |
| /* If this pb_graph_node is part not of the current pattern index, put it in and expand all its edges */ |
| source_block = (t_pack_pattern_block*) source_pb_graph_node->temp_scratch_pad; |
| if (source_block == nullptr || source_block->pattern_index != curr_pattern_index) { |
| source_block = (t_pack_pattern_block *)vtr::calloc(1, sizeof(t_pack_pattern_block)); |
| source_block->block_id = *L_num_blocks; |
| (*L_num_blocks)++; |
| list_of_packing_patterns[curr_pattern_index].base_cost += compute_primitive_base_cost(source_pb_graph_node); |
| source_pb_graph_node->temp_scratch_pad = (void *) source_block; |
| source_block->pattern_index = curr_pattern_index; |
| source_block->pb_type = source_pb_graph_node->pb_type; |
| |
| if (list_of_packing_patterns[curr_pattern_index].root_block == nullptr) { |
| list_of_packing_patterns[curr_pattern_index].root_block = source_block; |
| } |
| |
| // explore the inputs of this primitive |
| for (iport = 0; iport < source_pb_graph_node->num_input_ports; iport++) { |
| for (ipin = 0; ipin < source_pb_graph_node->num_input_pins[iport]; ipin++) { |
| for (iedge = 0; iedge < source_pb_graph_node->input_pins[iport][ipin].num_input_edges; iedge++) { |
| backward_expand_pack_pattern_from_edge( |
| source_pb_graph_node->input_pins[iport][ipin].input_edges[iedge], |
| list_of_packing_patterns, |
| curr_pattern_index, |
| &source_pb_graph_node->input_pins[iport][ipin], |
| source_block, L_num_blocks); |
| } |
| } |
| } |
| |
| // explore the outputs of this primitive |
| for (iport = 0; iport < source_pb_graph_node->num_output_ports; iport++) { |
| for (ipin = 0; ipin < source_pb_graph_node->num_output_pins[iport]; ipin++) { |
| for (iedge = 0; iedge < source_pb_graph_node->output_pins[iport][ipin].num_output_edges; iedge++) { |
| forward_expand_pack_pattern_from_edge( |
| source_pb_graph_node->output_pins[iport][ipin].output_edges[iedge], |
| list_of_packing_patterns, |
| curr_pattern_index, L_num_blocks, false); |
| } |
| } |
| } |
| |
| // explore the clock pins of thie primitive |
| for (iport = 0; iport < source_pb_graph_node->num_clock_ports; iport++) { |
| for (ipin = 0; ipin < source_pb_graph_node->num_clock_pins[iport]; ipin++) { |
| for (iedge = 0; iedge < source_pb_graph_node->clock_pins[iport][ipin].num_input_edges; iedge++) { |
| backward_expand_pack_pattern_from_edge( |
| source_pb_graph_node->clock_pins[iport][ipin].input_edges[iedge], |
| list_of_packing_patterns, |
| curr_pattern_index, |
| &source_pb_graph_node->clock_pins[iport][ipin], |
| source_block, L_num_blocks); |
| } |
| } |
| } |
| } |
| |
| if (destination_pin != nullptr) { |
| VTR_ASSERT(((t_pack_pattern_block*)source_pb_graph_node->temp_scratch_pad)->pattern_index == curr_pattern_index); |
| source_block = (t_pack_pattern_block*) source_pb_graph_node->temp_scratch_pad; |
| pack_pattern_connection = (t_pack_pattern_connections *) vtr::calloc(1, sizeof(t_pack_pattern_connections)); |
| pack_pattern_connection->from_block = source_block; |
| pack_pattern_connection->from_pin = expansion_edge->input_pins[i]; |
| pack_pattern_connection->to_block = destination_block; |
| pack_pattern_connection->to_pin = destination_pin; |
| pack_pattern_connection->next = source_block->connections; |
| source_block->connections = pack_pattern_connection; |
| |
| pack_pattern_connection = (t_pack_pattern_connections *)vtr::calloc(1, sizeof(t_pack_pattern_connections)); |
| pack_pattern_connection->from_block = source_block; |
| pack_pattern_connection->from_pin = expansion_edge->input_pins[i]; |
| pack_pattern_connection->to_block = destination_block; |
| pack_pattern_connection->to_pin = destination_pin; |
| pack_pattern_connection->next = destination_block->connections; |
| destination_block->connections = pack_pattern_connection; |
| |
| if (source_block == destination_block) { |
| vpr_throw(VPR_ERROR_PACK, __FILE__, __LINE__, |
| "Invalid packing pattern defined. Source and destination block are the same (%s).\n", |
| source_block->pb_type->name); |
| } |
| } |
| |
| // expansion edge parent is not a primitive |
| } else { |
| // check if this input pin of the expansion edge has no driving pin |
| if(expansion_edge->input_pins[i]->num_input_edges == 0) { |
| // check if this input pin of the expansion edge belongs to a root block (i.e doesn't have a parent block) |
| if(expansion_edge->input_pins[i]->parent_node->pb_type->parent_mode == nullptr) { |
| // This pack pattern extends to CLB (root pb block) input pin, |
| // thus it extends across multiple logic blocks, treat as a chain |
| list_of_packing_patterns[curr_pattern_index].is_chain = true; |
| // since this input pin has not driving nets, expand in the forward direction instead |
| forward_expand_pack_pattern_from_edge( |
| expansion_edge, |
| list_of_packing_patterns, |
| curr_pattern_index, L_num_blocks, true); |
| } |
| // this input pin of the expansion edge has a driving pin |
| } else { |
| // iterate over all the driving edges of this input pin |
| for (j = 0; j < expansion_edge->input_pins[i]->num_input_edges; j++) { |
| // if pattern should be infered for this edge continue the expansion backwards |
| if (expansion_edge->input_pins[i]->input_edges[j]->infer_pattern == true) { |
| backward_expand_pack_pattern_from_edge( |
| expansion_edge->input_pins[i]->input_edges[j], |
| list_of_packing_patterns, curr_pattern_index, |
| destination_pin, destination_block, L_num_blocks); |
| // if pattern shouldn't be infered |
| } else { |
| // check if this input pin edge is annotated with the current pattern |
| for (k = 0; k < expansion_edge->input_pins[i]->input_edges[j]->num_pack_patterns; k++) { |
| if (expansion_edge->input_pins[i]->input_edges[j]->pack_pattern_indices[k] == curr_pattern_index) { |
| VTR_ASSERT(found == false); |
| /* Check assumption that each forced net has only one fan-out */ |
| found = true; |
| backward_expand_pack_pattern_from_edge( |
| expansion_edge->input_pins[i]->input_edges[j], |
| list_of_packing_patterns, |
| curr_pattern_index, destination_pin, |
| destination_block, L_num_blocks); |
| } |
| } |
| } |
| } |
| } |
| } |
| } |
| } |
| |
| /** |
| * Pre-pack atoms in netlist to molecules |
| * 1. Single atoms are by definition a molecule. |
| * 2. Forced pack molecules are groupings of atoms that matches a t_pack_pattern definition. |
| * 3. Chained molecules are molecules that follow a carry-chain style pattern, |
| * ie. a single linear chain that can be split across multiple complex blocks |
| */ |
| t_pack_molecule *alloc_and_load_pack_molecules( |
| t_pack_patterns *list_of_pack_patterns, |
| std::multimap<AtomBlockId,t_pack_molecule*>& atom_molecules, |
| std::unordered_map<AtomBlockId,t_pb_graph_node*>& expected_lowest_cost_pb_gnode, |
| const int num_packing_patterns) { |
| int i, j, best_pattern; |
| t_pack_molecule *list_of_molecules_head; |
| t_pack_molecule *cur_molecule; |
| bool *is_used; |
| auto& atom_ctx = g_vpr_ctx.atom(); |
| |
| is_used = (bool*)vtr::calloc(num_packing_patterns, sizeof(bool)); |
| |
| cur_molecule = list_of_molecules_head = nullptr; |
| |
| /* Find forced pack patterns |
| * Simplifying assumptions: Each atom can map to at most one molecule, |
| * use first-fit mapping based on priority of pattern |
| * TODO: Need to investigate better mapping strategies than first-fit |
| */ |
| for (i = 0; i < num_packing_patterns; i++) { |
| best_pattern = 0; |
| for(j = 1; j < num_packing_patterns; j++) { |
| if(is_used[best_pattern]) { |
| best_pattern = j; |
| } else if (is_used[j] == false && compare_pack_pattern(&list_of_pack_patterns[j], &list_of_pack_patterns[best_pattern]) == 1) { |
| best_pattern = j; |
| } |
| } |
| VTR_ASSERT(is_used[best_pattern] == false); |
| is_used[best_pattern] = true; |
| |
| auto blocks = atom_ctx.nlist.blocks(); |
| for(auto blk_iter = blocks.begin(); blk_iter != blocks.end(); ++blk_iter) { |
| auto blk_id = *blk_iter; |
| |
| cur_molecule = try_create_molecule(list_of_pack_patterns, atom_molecules, best_pattern, blk_id); |
| if (cur_molecule != nullptr) { |
| cur_molecule->next = list_of_molecules_head; |
| /* In the event of multiple molecules with the same atom block pattern, |
| * bias to use the molecule with less costly physical resources first */ |
| /* TODO: Need to normalize magical number 100 */ |
| cur_molecule->base_gain = cur_molecule->num_blocks - (cur_molecule->pack_pattern->base_cost / 100); |
| list_of_molecules_head = cur_molecule; |
| |
| //Note: atom_molecules is an (ordered) multimap so the last molecule |
| // inserted for a given blk_id will be the last valid element |
| // in the equal_range |
| auto rng = atom_molecules.equal_range(blk_id); //The range of molecules matching this block |
| bool range_empty = (rng.first == rng.second); |
| bool cur_was_last_inserted = false; |
| if (!range_empty) { |
| auto last_valid_iter = --rng.second; //Iterator to last element (only valid if range is not empty) |
| cur_was_last_inserted = (last_valid_iter->second == cur_molecule); |
| } |
| if(range_empty || !cur_was_last_inserted) { |
| /* molecule did not cover current atom (possibly because molecule created is |
| * part of a long chain that extends past multiple logic blocks), try again */ |
| --blk_iter; |
| } |
| } |
| } |
| } |
| free(is_used); |
| |
| /* List all atom blocks as a molecule for blocks that do not belong to any molecules. |
| This allows the packer to be consistent as it now packs molecules only instead of atoms and molecules |
| |
| If a block belongs to a molecule, then carrying the single atoms around can make the packing problem |
| more difficult because now it needs to consider splitting molecules. |
| */ |
| for(auto blk_id : atom_ctx.nlist.blocks()) { |
| |
| expected_lowest_cost_pb_gnode[blk_id] = get_expected_lowest_cost_primitive_for_atom_block(blk_id); |
| |
| auto rng = atom_molecules.equal_range(blk_id); |
| bool rng_empty = (rng.first == rng.second); |
| if (rng_empty) { |
| cur_molecule = new t_pack_molecule; |
| cur_molecule->valid = true; |
| cur_molecule->type = MOLECULE_SINGLE_ATOM; |
| cur_molecule->num_blocks = 1; |
| cur_molecule->root = 0; |
| cur_molecule->pack_pattern = nullptr; |
| |
| cur_molecule->atom_block_ids = {blk_id}; |
| |
| cur_molecule->next = list_of_molecules_head; |
| cur_molecule->base_gain = 1; |
| list_of_molecules_head = cur_molecule; |
| |
| atom_molecules.insert({blk_id, cur_molecule}); |
| } |
| } |
| |
| if (getEchoEnabled() && isEchoFileEnabled(E_ECHO_PRE_PACKING_MOLECULES_AND_PATTERNS)) { |
| print_pack_molecules(getEchoFileName(E_ECHO_PRE_PACKING_MOLECULES_AND_PATTERNS), |
| list_of_pack_patterns, num_packing_patterns, |
| list_of_molecules_head); |
| } |
| |
| return list_of_molecules_head; |
| } |
| |
| |
| static void free_pack_pattern(t_pack_pattern_block *pattern_block, t_pack_pattern_block **pattern_block_list) { |
| t_pack_pattern_connections *connection, *next; |
| if (pattern_block == nullptr || pattern_block->block_id == OPEN) { |
| /* already traversed, return */ |
| return; |
| } |
| pattern_block_list[pattern_block->block_id] = pattern_block; |
| pattern_block->block_id = OPEN; |
| connection = pattern_block->connections; |
| while (connection) { |
| free_pack_pattern(connection->from_block, pattern_block_list); |
| free_pack_pattern(connection->to_block, pattern_block_list); |
| next = connection->next; |
| free(connection); |
| connection = next; |
| } |
| } |
| |
| /** |
| * Given a pattern and an atom block to serve as the root block, determine if |
| * the candidate atom block serving as the root node matches the pattern. |
| * If yes, return the molecule with this atom block as the root, if not, return NULL |
| * |
| * Limitations: Currently assumes that forced pack nets must be single-fanout as |
| * this covers all the reasonable architectures we wanted. More complicated |
| * structures should probably be handled either downstream (general packing) |
| * or upstream (in tech mapping). |
| * If this limitation is too constraining, code is designed so that this limitation can be removed |
| * |
| * Side Effect: If successful, link atom to molecule |
| */ |
| static t_pack_molecule *try_create_molecule( |
| t_pack_patterns *list_of_pack_patterns, |
| std::multimap<AtomBlockId,t_pack_molecule*>& atom_molecules, |
| const int pack_pattern_index, |
| AtomBlockId blk_id) { |
| int i; |
| t_pack_molecule *molecule; |
| |
| bool failed = false; |
| |
| { |
| molecule = new t_pack_molecule; |
| molecule->valid = true; |
| molecule->type = MOLECULE_FORCED_PACK; |
| molecule->pack_pattern = &list_of_pack_patterns[pack_pattern_index]; |
| if (molecule->pack_pattern == nullptr) {failed = true; goto end_prolog;} |
| |
| molecule->atom_block_ids = std::vector<AtomBlockId>(molecule->pack_pattern->num_blocks); //Initializes invalid |
| |
| molecule->num_blocks = list_of_pack_patterns[pack_pattern_index].num_blocks; |
| if (molecule->num_blocks == 0) {failed = true; goto end_prolog;} |
| |
| if (list_of_pack_patterns[pack_pattern_index].root_block == nullptr) {failed = true; goto end_prolog;} |
| molecule->root = list_of_pack_patterns[pack_pattern_index].root_block->block_id; |
| |
| if(list_of_pack_patterns[pack_pattern_index].is_chain == true) { |
| /* A chain pattern extends beyond a single logic block so we must find |
| * the blk_id that matches with the portion of a chain for this particular logic block */ |
| blk_id = find_new_root_atom_for_chain(blk_id, &list_of_pack_patterns[pack_pattern_index], atom_molecules); |
| } |
| } |
| |
| end_prolog: |
| |
| if (!failed && blk_id && try_expand_molecule(molecule, atom_molecules, blk_id, |
| molecule->pack_pattern->root_block) == true) { |
| /* Success! commit module */ |
| for (i = 0; i < molecule->pack_pattern->num_blocks; i++) { |
| auto blk_id2 = molecule->atom_block_ids[i]; |
| if(!blk_id2) { |
| VTR_ASSERT(list_of_pack_patterns[pack_pattern_index].is_block_optional[i] == true); |
| continue; |
| } |
| |
| atom_molecules.insert({blk_id2, molecule}); |
| } |
| } else { |
| failed = true; |
| } |
| |
| if (failed == true) { |
| /* Does not match pattern, free molecule */ |
| delete molecule; |
| molecule = nullptr; |
| } |
| return molecule; |
| } |
| |
| /** |
| * Determine if atom block can match with the pattern to form a molecule |
| * return true if it matches, return false otherwise |
| */ |
| static bool try_expand_molecule(t_pack_molecule *molecule, |
| const std::multimap<AtomBlockId,t_pack_molecule*>& atom_molecules, |
| const AtomBlockId blk_id, |
| const t_pack_pattern_block *current_pattern_block) { |
| int ipin; |
| bool success; |
| bool is_optional; |
| bool *is_block_optional; |
| t_pack_pattern_connections *cur_pack_pattern_connection; |
| |
| auto& atom_ctx = g_vpr_ctx.atom(); |
| |
| is_block_optional = molecule->pack_pattern->is_block_optional; |
| is_optional = is_block_optional[current_pattern_block->block_id]; |
| |
| /* If the block in the pattern has already been visited, then there is no need to revisit it */ |
| if (molecule->atom_block_ids[current_pattern_block->block_id]) { |
| if (molecule->atom_block_ids[current_pattern_block->block_id] != blk_id) { |
| /* Mismatch between the visited block and the current block implies |
| * that the current netlist structure does not match the expected pattern, |
| * return whether or not this matters */ |
| return is_optional; |
| } else { |
| return true; |
| } |
| } |
| |
| /* This node has never been visited */ |
| /* Simplifying assumption: An atom can only map to one molecule */ |
| auto rng = atom_molecules.equal_range(blk_id); |
| bool rng_empty = rng.first == rng.second; |
| if(!rng_empty) { |
| /* This block is already in a molecule, return whether or not this matters */ |
| return is_optional; |
| } |
| |
| if (primitive_type_feasible(blk_id, current_pattern_block->pb_type)) { |
| |
| success = true; |
| /* If the primitive types match, store it, expand it and explore neighbouring nodes */ |
| |
| |
| /* store that this node has been visited */ |
| molecule->atom_block_ids[current_pattern_block->block_id] = blk_id; |
| |
| cur_pack_pattern_connection = current_pattern_block->connections; |
| while (cur_pack_pattern_connection != nullptr && success == true) { |
| if (cur_pack_pattern_connection->from_block == current_pattern_block) { |
| /* find net corresponding to pattern */ |
| AtomPortId port_id = atom_ctx.nlist.find_atom_port(blk_id, cur_pack_pattern_connection->from_pin->port->model_port); |
| if(!port_id) { |
| //No matching port, we may be at the end |
| success = is_block_optional[cur_pack_pattern_connection->to_block->block_id]; |
| } else { |
| ipin = cur_pack_pattern_connection->from_pin->pin_number; |
| AtomNetId net_id = atom_ctx.nlist.port_net(port_id, ipin); |
| |
| /* Check if net is valid */ |
| if (!net_id || atom_ctx.nlist.net_sinks(net_id).size() != 1) { /* One fanout assumption */ |
| success = is_block_optional[cur_pack_pattern_connection->to_block->block_id]; |
| } else { |
| auto net_sinks = atom_ctx.nlist.net_sinks(net_id); |
| VTR_ASSERT(net_sinks.size() == 1); |
| |
| auto sink_pin_id = *net_sinks.begin(); |
| auto sink_blk_id = atom_ctx.nlist.pin_block(sink_pin_id); |
| |
| success = try_expand_molecule(molecule, atom_molecules, sink_blk_id, |
| cur_pack_pattern_connection->to_block); |
| } |
| } |
| } else { |
| VTR_ASSERT(cur_pack_pattern_connection->to_block == current_pattern_block); |
| /* find net corresponding to pattern */ |
| |
| auto port_id = atom_ctx.nlist.find_atom_port(blk_id, cur_pack_pattern_connection->to_pin->port->model_port); |
| VTR_ASSERT(port_id); |
| ipin = cur_pack_pattern_connection->to_pin->pin_number; |
| |
| AtomNetId net_id; |
| if (cur_pack_pattern_connection->to_pin->port->model_port->is_clock) { |
| VTR_ASSERT(ipin == 1); //TODO: support multi-clock primitives |
| net_id = atom_ctx.nlist.port_net(port_id, ipin); |
| } else { |
| net_id = atom_ctx.nlist.port_net(port_id, ipin); |
| } |
| /* Check if net is valid */ |
| if (!net_id || atom_ctx.nlist.net_sinks(net_id).size() != 1) { /* One fanout assumption */ |
| success = is_block_optional[cur_pack_pattern_connection->from_block->block_id]; |
| } else { |
| auto driver_blk_id = atom_ctx.nlist.net_driver_block(net_id); |
| success = try_expand_molecule(molecule, atom_molecules, driver_blk_id, |
| cur_pack_pattern_connection->from_block); |
| } |
| } |
| cur_pack_pattern_connection = cur_pack_pattern_connection->next; |
| } |
| } else { |
| success = is_optional; |
| } |
| |
| return success; |
| } |
| |
| static void print_pack_molecules(const char *fname, |
| const t_pack_patterns *list_of_pack_patterns, const int num_pack_patterns, |
| const t_pack_molecule *list_of_molecules) { |
| int i; |
| FILE *fp; |
| const t_pack_molecule *list_of_molecules_current; |
| auto& atom_ctx = g_vpr_ctx.atom(); |
| |
| fp = std::fopen(fname, "w"); |
| fprintf(fp, "# of pack patterns %d\n", num_pack_patterns); |
| |
| for (i = 0; i < num_pack_patterns; i++) { |
| VTR_ASSERT(list_of_pack_patterns[i].root_block); |
| fprintf(fp, "pack pattern index %d block count %d name %s root %s\n", |
| list_of_pack_patterns[i].index, |
| list_of_pack_patterns[i].num_blocks, |
| list_of_pack_patterns[i].name, |
| list_of_pack_patterns[i].root_block->pb_type->name); |
| } |
| |
| list_of_molecules_current = list_of_molecules; |
| while (list_of_molecules_current != nullptr) { |
| if (list_of_molecules_current->type == MOLECULE_SINGLE_ATOM) { |
| fprintf(fp, "\nmolecule type: atom\n"); |
| fprintf(fp, "\tpattern index %d: atom block %s\n", i, |
| atom_ctx.nlist.block_name(list_of_molecules_current->atom_block_ids[0]).c_str()); |
| } else if (list_of_molecules_current->type == MOLECULE_FORCED_PACK) { |
| fprintf(fp, "\nmolecule type: %s\n", |
| list_of_molecules_current->pack_pattern->name); |
| for (i = 0; i < list_of_molecules_current->pack_pattern->num_blocks; |
| i++) { |
| if(!list_of_molecules_current->atom_block_ids[i]) { |
| fprintf(fp, "\tpattern index %d: empty \n", i); |
| } else { |
| fprintf(fp, "\tpattern index %d: atom block %s", |
| i, |
| atom_ctx.nlist.block_name(list_of_molecules_current->atom_block_ids[i]).c_str()); |
| if(list_of_molecules_current->pack_pattern->root_block->block_id == i) { |
| fprintf(fp, " root node\n"); |
| } else { |
| fprintf(fp, "\n"); |
| } |
| } |
| } |
| } else { |
| VTR_ASSERT(0); |
| } |
| list_of_molecules_current = list_of_molecules_current->next; |
| } |
| |
| fclose(fp); |
| } |
| |
| /* Search through all primitives and return the lowest cost primitive that fits this atom block */ |
| static t_pb_graph_node* get_expected_lowest_cost_primitive_for_atom_block(const AtomBlockId blk_id) { |
| int i; |
| float cost, best_cost; |
| t_pb_graph_node *current, *best; |
| auto& device_ctx = g_vpr_ctx.device(); |
| |
| best_cost = UNDEFINED; |
| best = nullptr; |
| current = nullptr; |
| for(i = 0; i < device_ctx.num_block_types; i++) { |
| cost = UNDEFINED; |
| current = get_expected_lowest_cost_primitive_for_atom_block_in_pb_graph_node(blk_id, device_ctx.block_types[i].pb_graph_head, &cost); |
| if(cost != UNDEFINED) { |
| if(best_cost == UNDEFINED || best_cost > cost) { |
| best_cost = cost; |
| best = current; |
| } |
| } |
| } |
| |
| if(!best) { |
| auto& atom_ctx = g_vpr_ctx.atom(); |
| VPR_THROW(VPR_ERROR_PACK, "Failed to find any location to pack primitive of type '%s' in architecture", |
| atom_ctx.nlist.block_model(blk_id)->name); |
| } |
| |
| return best; |
| } |
| |
| static t_pb_graph_node *get_expected_lowest_cost_primitive_for_atom_block_in_pb_graph_node(const AtomBlockId blk_id, t_pb_graph_node *curr_pb_graph_node, float *cost) { |
| t_pb_graph_node *best, *cur; |
| float cur_cost, best_cost; |
| int i, j; |
| |
| best = nullptr; |
| best_cost = UNDEFINED; |
| if(curr_pb_graph_node == nullptr) { |
| return nullptr; |
| } |
| |
| if(curr_pb_graph_node->pb_type->blif_model != nullptr) { |
| if(primitive_type_feasible(blk_id, curr_pb_graph_node->pb_type)) { |
| cur_cost = compute_primitive_base_cost(curr_pb_graph_node); |
| if(best_cost == UNDEFINED || best_cost > cur_cost) { |
| best_cost = cur_cost; |
| best = curr_pb_graph_node; |
| } |
| } |
| } else { |
| for(i = 0; i < curr_pb_graph_node->pb_type->num_modes; i++) { |
| for(j = 0; j < curr_pb_graph_node->pb_type->modes[i].num_pb_type_children; j++) { |
| *cost = UNDEFINED; |
| cur = get_expected_lowest_cost_primitive_for_atom_block_in_pb_graph_node(blk_id, &curr_pb_graph_node->child_pb_graph_nodes[i][j][0], cost); |
| if(cur != nullptr) { |
| if(best == nullptr || best_cost > *cost) { |
| best = cur; |
| best_cost = *cost; |
| } |
| } |
| } |
| } |
| } |
| |
| *cost = best_cost; |
| return best; |
| } |
| |
| |
| /* Determine which of two pack pattern should take priority */ |
| static int compare_pack_pattern(const t_pack_patterns *pattern_a, const t_pack_patterns *pattern_b) { |
| float base_gain_a, base_gain_b, diff; |
| |
| /* Bigger patterns should take higher priority than smaller patterns because they are harder to fit */ |
| if (pattern_a->num_blocks > pattern_b->num_blocks) { |
| return 1; |
| } else if (pattern_a->num_blocks < pattern_b->num_blocks) { |
| return -1; |
| } |
| |
| base_gain_a = pattern_a->base_cost; |
| base_gain_b = pattern_b->base_cost; |
| diff = base_gain_a - base_gain_b; |
| |
| /* Less costly patterns should be used before more costly patterns */ |
| if (diff < 0) { |
| return 1; |
| } |
| if (diff > 0) { |
| return -1; |
| } |
| return 0; |
| } |
| |
| /* A chain can extend across multiple atom blocks. Must segment the chain to fit in an atom |
| * block by identifying the actual atom that forms the root of the new chain. |
| * Returns AtomBlockId::INVALID() if this block_index doesn't match up with any chain |
| * |
| * Assumes that the root of a chain is the primitive that starts the chain or is driven from outside the logic block |
| * block_index: index of current atom |
| * list_of_pack_pattern: ptr to current chain pattern |
| */ |
| static AtomBlockId find_new_root_atom_for_chain(const AtomBlockId blk_id, const t_pack_patterns *list_of_pack_pattern, |
| const std::multimap<AtomBlockId,t_pack_molecule*>& atom_molecules) { |
| AtomBlockId new_root_blk_id; |
| t_pb_graph_pin *root_ipin; |
| t_pb_graph_node *root_pb_graph_node; |
| t_model_ports *model_port; |
| |
| auto& atom_ctx = g_vpr_ctx.atom(); |
| |
| VTR_ASSERT(list_of_pack_pattern->is_chain == true); |
| root_ipin = list_of_pack_pattern->chain_root_pin; |
| root_pb_graph_node = root_ipin->parent_node; |
| |
| if(primitive_type_feasible(blk_id, root_pb_graph_node->pb_type) == false) { |
| return AtomBlockId::INVALID(); |
| } |
| |
| /* Assign driver furthest up the chain that matches the root node and is unassigned to a molecule as the root */ |
| model_port = root_ipin->port->model_port; |
| |
| AtomPortId port_id = atom_ctx.nlist.find_atom_port(blk_id, model_port); |
| if(!port_id) { |
| //There is no port with the chain connection on this block, it must be the furthest |
| //up the chain, so return it as root |
| return blk_id; |
| } |
| |
| AtomNetId driving_net_id = atom_ctx.nlist.port_net(port_id, root_ipin->pin_number); |
| if(!driving_net_id) { |
| //There is no net associated with the chain connection on this block, it must be the furthest |
| //up the chain, so return it as root |
| return blk_id; |
| } |
| |
| auto driver_pin_id = atom_ctx.nlist.net_driver(driving_net_id); |
| AtomBlockId driver_blk_id = atom_ctx.nlist.pin_block(driver_pin_id); |
| |
| auto rng = atom_molecules.equal_range(driver_blk_id); |
| bool rng_empty = (rng.first == rng.second); |
| if(!rng_empty) { |
| /* Driver is used/invalid, so current block is the furthest up the chain, return it */ |
| return blk_id; |
| } |
| |
| new_root_blk_id = find_new_root_atom_for_chain(driver_blk_id, list_of_pack_pattern, atom_molecules); |
| if(!new_root_blk_id) { |
| return blk_id; |
| } else { |
| return new_root_blk_id; |
| } |
| } |
| |
| |
| |
