vpr/src/pack/cluster.cpp
/**
 * Given a pin and its assigned net, mark all pin classes that are affected.
 * Check if connecting this pin to it's driver pin or to all sink pins will
 * require leaving a pb_block starting from the parent pb_block of the
 * primitive till the root block (depth = 0). If leaving a pb_block is
 * required add this net to the pin class (to increment the number of used
 * pins from this class) that should be used to leave the pb_block.
 */
Given a pin and its assigned net, mark all pin classes that are affected.
Check if connecting this pin to it's driver pin or to all sink pins will
require leaving a pb_block starting from the parent pb_block of the
primitive till the root block (depth = 0). If leaving a pb_block is
required add this net to the pin class (to increment the number of used
pins from this class) that should be used to leave the pb_block.
Given a pin and its assigned net mark all pin classes that are affected . Check if connecting this pin to it ' s driver pin or to all sink pins will require leaving a pb_block starting from the parent pb_block of the primitive till the root block ( depth = 0 ) . If leaving a pb_block is required add this net to the pin class ( to increment the number of used pins from this class ) that should be used to leave the pb_block .
static void compute_and_mark_lookahead_pins_used_for_pin(const t_pb_graph_pin* pb_graph_pin, const t_pb* primitive_pb, const AtomNetId net_id) {
    auto& atom_ctx = g_vpr_ctx.atom();
    for (auto cur_pb = primitive_pb->parent_pb; cur_pb; cur_pb = cur_pb->parent_pb) {
        const auto depth = cur_pb->pb_graph_node->pb_type->depth;
        const auto pin_class = pb_graph_pin->parent_pin_class[depth];
        VTR_ASSERT(pin_class != OPEN);
        const auto driver_blk_id = atom_ctx.nlist.net_driver_block(net_id);
        if (pb_graph_pin->port->type == IN_PORT) {
            const auto driver_pin_id = atom_ctx.nlist.net_driver(net_id);
            const auto prim_blk_id = atom_ctx.lookup.pb_atom(primitive_pb);
            const auto driver_pb = atom_ctx.lookup.atom_pb(driver_blk_id);
            t_pb_graph_pin* output_pb_graph_pin = nullptr;
            if (atom_ctx.lookup.atom_clb(driver_blk_id) == atom_ctx.lookup.atom_clb(prim_blk_id)) {
                output_pb_graph_pin = get_driver_pb_graph_pin(driver_pb, driver_pin_id);
            }
            bool is_reachable = false;
            if (output_pb_graph_pin) {
                const t_pb* check_pb = driver_pb;
                while (check_pb && check_pb != cur_pb) {
                    check_pb = check_pb->parent_pb;
                }
                if (check_pb) {
                    for (int i = 0; i < output_pb_graph_pin->num_connectable_primitive_input_pins[depth]; i++) {
                        if (pb_graph_pin == output_pb_graph_pin->list_of_connectable_input_pin_ptrs[depth][i]) {
                            is_reachable = true;
                            break;
                        }
                    }
                }
            }
            if (!is_reachable) {
                auto it = std::find(cur_pb->pb_stats->lookahead_input_pins_used[pin_class].begin(),
                                    cur_pb->pb_stats->lookahead_input_pins_used[pin_class].end(), net_id);
                if (it == cur_pb->pb_stats->lookahead_input_pins_used[pin_class].end()) {
                    cur_pb->pb_stats->lookahead_input_pins_used[pin_class].push_back(net_id);
                }
            }
        } else {
            VTR_ASSERT(pb_graph_pin->port->type == OUT_PORT);
            bool net_exits_cluster = true;
            int num_net_sinks = static_cast<int>(atom_ctx.nlist.net_sinks(net_id).size());
            if (pb_graph_pin->num_connectable_primitive_input_pins[depth] >= num_net_sinks) {
                bool all_sinks_in_cur_cluster = true;
                ClusterBlockId driver_clb = atom_ctx.lookup.atom_clb(driver_blk_id);
                for (auto pin_id : atom_ctx.nlist.net_sinks(net_id)) {
                    auto sink_blk_id = atom_ctx.nlist.pin_block(pin_id);
                    if (atom_ctx.lookup.atom_clb(sink_blk_id) != driver_clb) {
                        all_sinks_in_cur_cluster = false;
                        break;
                    }
                }
                if (all_sinks_in_cur_cluster) {
                    Verify this, by counting the number of net sinks reachable from the driver pin.
                    If the count equals the number of net sinks then the net is fully absorbed and
                    the net does not exit the cluster
                    if (net_sinks_reachable_in_cluster(pb_graph_pin, depth, net_id)) {
                        All the sinks are reachable inside the cluster
                        net_exits_cluster = false;
                    }
                }
            }
            if (net_exits_cluster) {
                cur_pb->pb_stats->lookahead_output_pins_used[pin_class].push_back(net_id);
            }
        }
    }
}
static void compute_and_mark_lookahead_pins_used_for_pin ( const t_pb_graph_pin * pb_graph_pin , const t_pb * primitive_pb , const AtomNetId net_id ) { auto & atom_ctx = g_vpr_ctx . atom ( ) ; for ( auto cur_pb = primitive_pb -> parent_pb ; cur_pb ; cur_pb = cur_pb -> parent_pb ) { const auto depth = cur_pb -> pb_graph_node -> pb_type -> depth ; const auto pin_class = pb_graph_pin -> parent_pin_class [ depth ] ; VTR_ASSERT ( pin_class != OPEN ) ; const auto driver_blk_id = atom_ctx . nlist . net_driver_block ( net_id ) ; if ( pb_graph_pin -> port -> type == IN_PORT ) { const auto driver_pin_id = atom_ctx . nlist . net_driver ( net_id ) ; const auto prim_blk_id = atom_ctx . lookup . pb_atom ( primitive_pb ) ; const auto driver_pb = atom_ctx . lookup . atom_pb ( driver_blk_id ) ; t_pb_graph_pin * output_pb_graph_pin = nullptr ; if ( atom_ctx . lookup . atom_clb ( driver_blk_id ) == atom_ctx . lookup . atom_clb ( prim_blk_id ) ) { output_pb_graph_pin = get_driver_pb_graph_pin ( driver_pb , driver_pin_id ) ; } bool is_reachable = false ; if ( output_pb_graph_pin ) { const t_pb * check_pb = driver_pb ; while ( check_pb && check_pb != cur_pb ) { check_pb = check_pb -> parent_pb ; } if ( check_pb ) { for ( int i = 0 ; i < output_pb_graph_pin -> num_connectable_primitive_input_pins [ depth ] ; i ++ ) { if ( pb_graph_pin == output_pb_graph_pin -> list_of_connectable_input_pin_ptrs [ depth ] [ i ] ) { is_reachable = true ; break ; } } } } if ( ! is_reachable ) { auto it = std :: find ( cur_pb -> pb_stats -> lookahead_input_pins_used [ pin_class ] . begin ( ) , cur_pb -> pb_stats -> lookahead_input_pins_used [ pin_class ] . end ( ) , net_id ) ; if ( it == cur_pb -> pb_stats -> lookahead_input_pins_used [ pin_class ] . end ( ) ) { cur_pb -> pb_stats -> lookahead_input_pins_used [ pin_class ] . push_back ( net_id ) ; } } } else { VTR_ASSERT ( pb_graph_pin -> port -> type == OUT_PORT ) ; bool net_exits_cluster = true ; int num_net_sinks = static_cast < int > ( atom_ctx . nlist . net_sinks ( net_id ) . size ( ) ) ; if ( pb_graph_pin -> num_connectable_primitive_input_pins [ depth ] >= num_net_sinks ) { bool all_sinks_in_cur_cluster = true ; ClusterBlockId driver_clb = atom_ctx . lookup . atom_clb ( driver_blk_id ) ; for ( auto pin_id : atom_ctx . nlist . net_sinks ( net_id ) ) { auto sink_blk_id = atom_ctx . nlist . pin_block ( pin_id ) ; if ( atom_ctx . lookup . atom_clb ( sink_blk_id ) != driver_clb ) { all_sinks_in_cur_cluster = false ; break ; } } if ( all_sinks_in_cur_cluster ) { if ( net_sinks_reachable_in_cluster ( pb_graph_pin , depth , net_id ) ) { net_exits_cluster = false ; } } } if ( net_exits_cluster ) { cur_pb -> pb_stats -> lookahead_output_pins_used [ pin_class ] . push_back ( net_id ) ; } } } }
Given a pin and its assigned net, mark all pin classes that are affected.
Given a pin and its assigned net mark all pin classes that are affected .
// starting from the parent pb of the input primitive go up in the hierarchy till the root block // if this primitive pin is an input pin /* find location of net driver if exist in clb, NULL otherwise */ // find the driver of the input net connected to the pin being studied // find the id of the atom occupying the input primitive_pb // find the pb block occupied by the driving atom // pb_graph_pin driving net_id in the driver pb block // if the driver block is in the same clb as the input primitive block // get pb_graph_pin driving the given net // if the driver pin is within the cluster // find if the driver pin can reach the input pin of the primitive or not // Must use an input pin to connect the driver to the input pin of the given primitive, either the // driver atom is not contained in the cluster or is contained but cannot reach the primitive pin // add net to lookahead_input_pins_used if not already added /*
             * Determine if this net (which is driven from within this cluster) leaves this cluster
             * (and hence uses an output pin).
             */ //It is possible the net is completely absorbed in the cluster, //since this pin could (potentially) drive all the net's sinks /* Important: This runtime penalty looks a lot scarier than it really is.
                 * For high fan-out nets, I at most look at the number of pins within the
                 * cluster which limits runtime.
                 *
                 * DO NOT REMOVE THIS INITIAL FILTER WITHOUT CAREFUL ANALYSIS ON RUNTIME!!!
                 *
                 * Key Observation:
                 * For LUT-based designs it is impossible for the average fanout to exceed
                 * the number of LUT inputs so it's usually around 4-5 (pigeon-hole argument,
                 * if the average fanout is greater than the number of LUT inputs, where do
                 * the extra connections go?  Therefore, average fanout must be capped to a
                 * small constant where the constant is equal to the number of LUT inputs).
                 * The real danger to runtime is when the number of sinks of a net gets doubled
                 */ //Check if all the net sinks are, in fact, inside this cluster //All the sinks are part of this cluster, so the net may be fully absorbed. // //Verify this, by counting the number of net sinks reachable from the driver pin. //If the count equals the number of net sinks then the net is fully absorbed and //the net does not exit the cluster /* TODO: I should cache the absorbed outputs, once net is absorbed,
                     *       net is forever absorbed, no point in rechecking every time */ //All the sinks are reachable inside the cluster /* This output must exit this cluster */