cluster_placement.c

Go to the documentation of this file.

/* 
 Given a group of logical blocks and a partially-packed complex block, find placement for group of logical blocks in complex block
 To use, keep "cluster_placement_stats" data structure throughout packing
 cluster_placement_stats undergoes these major states:
 Initialization - performed once at beginning of packing
 Reset          - reset state in between packing of clusters
 In flight      - Speculatively place
 Finalized      - Commit or revert placements
 Freed          - performed once at end of packing

 Author: Jason Luu
 March 12, 2012
 */
#include <stdio.h>
#include <assert.h>
#include <string.h>

#include "read_xml_arch_file.h"
#include "util.h"
#include "vpr_types.h"
#include "globals.h"
#include "vpr_utils.h"
#include "hash.h"
#include "cluster_placement.h"

/****************************************/
/*Local Function Declaration            */
/****************************************/
static void load_cluster_placement_stats_for_pb_graph_node(
        INOUTP t_cluster_placement_stats *cluster_placement_stats,
        INOUTP t_pb_graph_node *pb_graph_node);
static void requeue_primitive(
        INOUTP t_cluster_placement_stats *cluster_placement_stats,
        t_cluster_placement_primitive *cluster_placement_primitive);
static void update_primitive_cost_or_status(INP t_pb_graph_node *pb_graph_node,
        INP float incremental_cost, INP boolean valid);
static float try_place_molecule(INP t_pack_molecule *molecule,
        INP t_pb_graph_node *root, INOUTP t_pb_graph_node **primitives_list, INP int clb_index);
static boolean expand_forced_pack_molecule_placement(
        INP t_pack_molecule *molecule,
        INP t_pack_pattern_block *pack_pattern_block,
        INOUTP t_pb_graph_node **primitives_list, INOUTP float *cost);
static t_pb_graph_pin *expand_pack_molecule_pin_edge(INP int pattern_id,
        INP t_pb_graph_pin *cur_pin, INP boolean forward);
static void flush_intermediate_queues(
        INOUTP t_cluster_placement_stats *cluster_placement_stats);
static boolean root_passes_early_filter(INP t_pb_graph_node *root, INP t_pack_molecule *molecule, INP int clb_index);

/****************************************/
/*Function Definitions                  */
/****************************************/

/**
 * [0..num_pb_types-1] array of cluster placement stats, one for each type_descriptors 
 */
t_cluster_placement_stats *alloc_and_load_cluster_placement_stats(void) {
    t_cluster_placement_stats *cluster_placement_stats_list;
    int i;

    cluster_placement_stats_list = (t_cluster_placement_stats *) my_calloc(num_types,
            sizeof(t_cluster_placement_stats));
    for (i = 0; i < num_types; i++) {
        if (EMPTY_TYPE != &type_descriptors[i]) {
            cluster_placement_stats_list[i].valid_primitives = (t_cluster_placement_primitive **) my_calloc(
                    get_max_primitives_in_pb_type(type_descriptors[i].pb_type)
                            + 1, sizeof(t_cluster_placement_primitive*)); /* too much memory allocated but shouldn't be a problem */
            cluster_placement_stats_list[i].curr_molecule = NULL;
            load_cluster_placement_stats_for_pb_graph_node(
                    &cluster_placement_stats_list[i],
                    type_descriptors[i].pb_graph_head);
        }
    }
    return cluster_placement_stats_list;
}

/**
 * get next list of primitives for list of logical blocks
 * primitives is the list of ptrs to primitives that matches with the list of logical_blocks (by index), assumes memory is preallocated
 *   - if this is a new block, requeue tried primitives and return a in-flight primitive list to try
 *   - if this is an old block, put root primitive to tried queue, requeue rest of primitives. try another set of primitives
 *
 * return TRUE if can find next primitive, FALSE otherwise
 * 
 * cluster_placement_stats - ptr to the current cluster_placement_stats of open complex block
 * molecule - molecule to pack into open complex block
 * primitives_list - a list of primitives indexed to match logical_block_ptrs of molecule.  Expects an allocated array of primitives ptrs as inputs.  This function loads the array with the lowest cost primitives that implement molecule
 */
boolean get_next_primitive_list(
        INOUTP t_cluster_placement_stats *cluster_placement_stats,
        INP t_pack_molecule *molecule, INOUTP t_pb_graph_node **primitives_list, INP int clb_index) {
    t_cluster_placement_primitive *cur, *next, *best, *before_best, *prev;
    int i;
    float cost, lowest_cost;
    best = NULL;
    before_best = NULL;

    if (cluster_placement_stats->curr_molecule != molecule) {
        /* New block, requeue tried primitives and in-flight primitives */
        flush_intermediate_queues(cluster_placement_stats);

        cluster_placement_stats->curr_molecule = molecule;
    } else {
        /* Hack! Same failed molecule may re-enter if upper stream functions suck, I'm going to make the molecule selector more intelligent, TODO: Remove later */
        if (cluster_placement_stats->in_flight != NULL) {
            /* Hack end */

            /* old block, put root primitive currently inflight to tried queue  */
            cur = cluster_placement_stats->in_flight;
            next = cur->next_primitive;
            cur->next_primitive = cluster_placement_stats->tried;
            cluster_placement_stats->tried = cur;
            /* should have only one block in flight at any point in time */
            assert(next == NULL);
            cluster_placement_stats->in_flight = NULL;
        }
    }

    /* find next set of blocks 
     1. Remove invalid blocks to invalid queue
     2. Find lowest cost array of primitives that implements blocks
     3. When found, move current blocks to in-flight, return lowest cost array of primitives
     4. Return NULL if not found
     */
    lowest_cost = HUGE_POSITIVE_FLOAT;
    for (i = 0; i < cluster_placement_stats->num_pb_types; i++) {
        if (cluster_placement_stats->valid_primitives[i]->next_primitive == NULL) {
            continue; /* no more primitives of this type available */
        }
        if (primitive_type_feasible(
                molecule->logical_block_ptrs[molecule->root]->index,
                cluster_placement_stats->valid_primitives[i]->next_primitive->pb_graph_node->pb_type)) {
            prev = cluster_placement_stats->valid_primitives[i];
            cur = cluster_placement_stats->valid_primitives[i]->next_primitive;
            while (cur) {
                /* remove invalid nodes lazily when encountered */
                while (cur && cur->valid == FALSE) {
                    prev->next_primitive = cur->next_primitive;
                    cur->next_primitive = cluster_placement_stats->invalid;
                    cluster_placement_stats->invalid = cur;
                    cur = prev->next_primitive;
                }
                if (cur == NULL) {
                    break;
                }
                /* try place molecule at root location cur */
                cost = try_place_molecule(molecule, cur->pb_graph_node,
                        primitives_list, clb_index);
                if (cost < lowest_cost) {
                    lowest_cost = cost;
                    best = cur;
                    before_best = prev;
                }
                prev = cur;
                cur = cur->next_primitive;
            }
        }
    }
    if (best == NULL) {
        /* failed to find a placement */
        for (i = 0; i < molecule->num_blocks; i++) {
            primitives_list[i] = NULL;
        }
    } else {
        /* populate primitive list with best */
        cost = try_place_molecule(molecule, best->pb_graph_node, primitives_list, clb_index);
        assert(cost == lowest_cost);

        /* take out best node and put it in flight */
        cluster_placement_stats->in_flight = best;
        before_best->next_primitive = best->next_primitive;
        best->next_primitive = NULL;
    }

    if (best == NULL) {
        return FALSE;
    }
    return TRUE;
}

/**
 * Resets one cluster placement stats by clearing incremental costs and returning all primitives to valid queue
 */
void reset_cluster_placement_stats(
        INOUTP t_cluster_placement_stats *cluster_placement_stats) {
    t_cluster_placement_primitive *cur, *next;
    int i;

    /* Requeue primitives */
    flush_intermediate_queues(cluster_placement_stats);
    cur = cluster_placement_stats->invalid;
    while (cur != NULL) {
        next = cur->next_primitive;
        requeue_primitive(cluster_placement_stats, cur);
        cur = next;
    }
    cur = cluster_placement_stats->invalid = NULL;
    /* reset flags and cost */
    for (i = 0; i < cluster_placement_stats->num_pb_types; i++) {
        assert(
                cluster_placement_stats->valid_primitives[i] != NULL && cluster_placement_stats->valid_primitives[i]->next_primitive != NULL);
        cur = cluster_placement_stats->valid_primitives[i]->next_primitive;
        while (cur != NULL) {
            cur->incremental_cost = 0;
            cur->valid = TRUE;
            cur = cur->next_primitive;
        }
    }
    cluster_placement_stats->curr_molecule = NULL;
}

/** 
 * Free linked lists found in cluster_placement_stats_list 
 */
void free_cluster_placement_stats(
        INOUTP t_cluster_placement_stats *cluster_placement_stats_list) {
    t_cluster_placement_primitive *cur, *next;
    int i, j;
    for (i = 0; i < num_types; i++) {
        cur = cluster_placement_stats_list[i].tried;
        while (cur != NULL) {
            next = cur->next_primitive;
            free(cur);
            cur = next;
        }
        cur = cluster_placement_stats_list[i].in_flight;
        while (cur != NULL) {
            next = cur->next_primitive;
            free(cur);
            cur = next;
        }
        cur = cluster_placement_stats_list[i].invalid;
        while (cur != NULL) {
            next = cur->next_primitive;
            free(cur);
            cur = next;
        }
        for (j = 0; j < cluster_placement_stats_list[i].num_pb_types; j++) {
            cur =
                    cluster_placement_stats_list[i].valid_primitives[j]->next_primitive;
            while (cur != NULL) {
                next = cur->next_primitive;
                free(cur);
                cur = next;
            }
            free(cluster_placement_stats_list[i].valid_primitives[j]);
        }
        free(cluster_placement_stats_list[i].valid_primitives);
    }
    free(cluster_placement_stats_list);
}

/**
 * Put primitive back on queue of valid primitives
 *  Note that valid status is not changed because if the primitive is not valid, it will get properly collected later
 */
static void requeue_primitive(
        INOUTP t_cluster_placement_stats *cluster_placement_stats,
        t_cluster_placement_primitive *cluster_placement_primitive) {
    int i;
    int null_index;
    boolean success;
    null_index = OPEN;

    success = FALSE;
    for (i = 0; i < cluster_placement_stats->num_pb_types; i++) {
        if (cluster_placement_stats->valid_primitives[i]->next_primitive == NULL) {
            null_index = i;
            continue;
        }
        if (cluster_placement_primitive->pb_graph_node->pb_type
                == cluster_placement_stats->valid_primitives[i]->next_primitive->pb_graph_node->pb_type) {
            success = TRUE;
            cluster_placement_primitive->next_primitive =
                    cluster_placement_stats->valid_primitives[i]->next_primitive;
            cluster_placement_stats->valid_primitives[i]->next_primitive =
                    cluster_placement_primitive;
        }
    }
    if (success == FALSE) {
        assert(null_index != OPEN);
        cluster_placement_primitive->next_primitive =
                cluster_placement_stats->valid_primitives[null_index]->next_primitive;
        cluster_placement_stats->valid_primitives[null_index]->next_primitive =
                cluster_placement_primitive;
    }
}

/** 
 * Add any primitives found in pb_graph_nodes to cluster_placement_stats
 * Adds backward link from pb_graph_node to cluster_placement_primitive
 */
static void load_cluster_placement_stats_for_pb_graph_node(
        INOUTP t_cluster_placement_stats *cluster_placement_stats,
        INOUTP t_pb_graph_node *pb_graph_node) {
    int i, j, k;
    t_cluster_placement_primitive *placement_primitive;
    const t_pb_type *pb_type = pb_graph_node->pb_type;
    boolean success;
    if (pb_type->modes == 0) {
        placement_primitive = (t_cluster_placement_primitive *) my_calloc(1,
                sizeof(t_cluster_placement_primitive));
        placement_primitive->pb_graph_node = pb_graph_node;
        placement_primitive->valid = TRUE;
        pb_graph_node->cluster_placement_primitive = placement_primitive;
        placement_primitive->base_cost = compute_primitive_base_cost(
                pb_graph_node);
        success = FALSE;
        i = 0;
        while (success == FALSE) {
            if (cluster_placement_stats->valid_primitives[i] == NULL
                    || cluster_placement_stats->valid_primitives[i]->next_primitive->pb_graph_node->pb_type
                            == pb_graph_node->pb_type) {
                if (cluster_placement_stats->valid_primitives[i] == NULL) {
                    cluster_placement_stats->valid_primitives[i] = (t_cluster_placement_primitive *) my_calloc(1,
                            sizeof(t_cluster_placement_primitive)); /* head of linked list is empty, makes it easier to remove nodes later */
                    cluster_placement_stats->num_pb_types++;
                }
                success = TRUE;
                placement_primitive->next_primitive =
                        cluster_placement_stats->valid_primitives[i]->next_primitive;
                cluster_placement_stats->valid_primitives[i]->next_primitive =
                        placement_primitive;
            }
            i++;
        }
    } else {
        for (i = 0; i < pb_type->num_modes; i++) {
            for (j = 0; j < pb_type->modes[i].num_pb_type_children; j++) {
                for (k = 0; k < pb_type->modes[i].pb_type_children[j].num_pb;
                        k++) {
                    load_cluster_placement_stats_for_pb_graph_node(
                            cluster_placement_stats,
                            &pb_graph_node->child_pb_graph_nodes[i][j][k]);
                }
            }
        }
    }
}

/**
 * Commit primitive, invalidate primitives blocked by mode assignment and update costs for primitives in same cluster as current
 * Costing is done to try to pack blocks closer to existing primitives
 *  actual value based on closest common ancestor to committed placement, the farther the ancestor, the less reduction in cost there is
 * Side effects: All cluster_placement_primitives may be invalidated/costed in this algorithm
 *               Al intermediate queues are requeued
 */
void commit_primitive(INOUTP t_cluster_placement_stats *cluster_placement_stats,
        INP t_pb_graph_node *primitive) {
    t_pb_graph_node *pb_graph_node, *skip;
    float incr_cost;
    int i, j, k;
    int valid_mode;
    t_cluster_placement_primitive *cur;

    /* Clear out intermediate queues */
    flush_intermediate_queues(cluster_placement_stats);

    /* commit primitive as used, invalidate it */
    cur = primitive->cluster_placement_primitive;
    assert(cur->valid == TRUE);

    cur->valid = FALSE;
    incr_cost = -0.01; /* cost of using a node drops as its neighbours are used, this drop should be small compared to scarcity values */

    pb_graph_node = cur->pb_graph_node;
    /* walk up pb_graph_node and update primitives of children */
    while (pb_graph_node->parent_pb_graph_node != NULL) {
        skip = pb_graph_node; /* do not traverse stuff that's already traversed */
        valid_mode = pb_graph_node->pb_type->parent_mode->index;
        pb_graph_node = pb_graph_node->parent_pb_graph_node;
        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++) {
                    if (&pb_graph_node->child_pb_graph_nodes[i][j][k] != skip) {
                        update_primitive_cost_or_status(
                                &pb_graph_node->child_pb_graph_nodes[i][j][k],
                                incr_cost, (boolean)(i == valid_mode));
                    }
                }
            }
        }
        incr_cost /= 10; /* blocks whose ancestor is further away in tree should be affected less than blocks closer in tree */
    }
}

/**
 * Set mode of cluster
 */
void set_mode_cluster_placement_stats(INP t_pb_graph_node *pb_graph_node,
        int mode) {
    int i, j, k;
    for (i = 0; i < pb_graph_node->pb_type->num_modes; i++) {
        if (i != mode) {
            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++) {
                    update_primitive_cost_or_status(
                            &pb_graph_node->child_pb_graph_nodes[i][j][k], 0,
                            FALSE);
                }
            }
        }
    }
}

/**
 * For sibling primitives of pb_graph node, decrease cost
 * For modes invalidated by pb_graph_node, invalidate primitive
 * int distance is the distance of current pb_graph_node from original
 */
static void update_primitive_cost_or_status(INP t_pb_graph_node *pb_graph_node,
        INP float incremental_cost, INP boolean valid) {
    int i, j, k;
    t_cluster_placement_primitive *placement_primitive;
    if (pb_graph_node->pb_type->num_modes == 0) {
        /* is primitive */
        placement_primitive =
                (t_cluster_placement_primitive*) pb_graph_node->cluster_placement_primitive;
        if (valid) {
            placement_primitive->incremental_cost += incremental_cost;
        } else {
            placement_primitive->valid = FALSE;
        }
    } else {
        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++) {
                    update_primitive_cost_or_status(
                            &pb_graph_node->child_pb_graph_nodes[i][j][k],
                            incremental_cost, valid);
                }
            }
        }
    }
}

/**
 * Try place molecule at root location, populate primitives list with locations of placement if successful
 */
static float try_place_molecule(INP t_pack_molecule *molecule,
        INP t_pb_graph_node *root, INOUTP t_pb_graph_node **primitives_list, INP int clb_index) {
    int list_size, i;
    float cost = HUGE_POSITIVE_FLOAT;
    list_size = get_array_size_of_molecule(molecule);

    if (primitive_type_feasible(
            molecule->logical_block_ptrs[molecule->root]->index,
            root->pb_type)) {
        if (root->cluster_placement_primitive->valid == TRUE) {
            if(root_passes_early_filter(root, molecule, clb_index)) {
                for (i = 0; i < list_size; i++) {
                    primitives_list[i] = NULL;
                }
                cost = root->cluster_placement_primitive->base_cost
                        + root->cluster_placement_primitive->incremental_cost;
                primitives_list[molecule->root] = root;
                if (molecule->type == MOLECULE_FORCED_PACK) {
                    if (!expand_forced_pack_molecule_placement(molecule,
                            molecule->pack_pattern->root_block, primitives_list,
                            &cost)) {
                        return HUGE_POSITIVE_FLOAT;
                    }
                }
                for (i = 0; i < list_size; i++) {
                    assert(
                            (primitives_list[i] == NULL) == (molecule->logical_block_ptrs[i] == NULL));
                }
            }
        }
    }
    return cost;
}

/**
 * Expand molecule at pb_graph_node
 * Assumes molecule and pack pattern connections have fan-out 1
 */
static boolean expand_forced_pack_molecule_placement(
        INP t_pack_molecule *molecule,
        INP t_pack_pattern_block *pack_pattern_block,
        INOUTP t_pb_graph_node **primitives_list, INOUTP float *cost) {
    t_pb_graph_node *pb_graph_node =
            primitives_list[pack_pattern_block->block_id];
    t_pb_graph_node *next_primitive;
    t_pack_pattern_connections *cur;
    int from_pin, from_port;
    t_pb_graph_pin *cur_pin, *next_pin;
    t_pack_pattern_block *next_block;

    cur = pack_pattern_block->connections;
    while (cur) {
        if (cur->from_block == pack_pattern_block) {
            next_block = cur->to_block;
        } else {
            next_block = cur->from_block;
        }
        if (primitives_list[next_block->block_id] == NULL && molecule->logical_block_ptrs[next_block->block_id] != NULL) {
            /* first time visiting location */

            /* find next primitive based on pattern connections, expand next primitive if not visited */
            from_pin = cur->from_pin->pin_number;
            from_port = cur->from_pin->port->port_index_by_type;
            if (cur->from_block == pack_pattern_block) {
                /* forward expand to find next block */
                cur_pin = &pb_graph_node->output_pins[from_port][from_pin];
                next_pin = expand_pack_molecule_pin_edge(
                        pack_pattern_block->pattern_index, cur_pin, TRUE);
            } else {
                /* backward expand to find next block */
                assert(cur->to_block == pack_pattern_block);
                if (cur->from_pin->port->is_clock) {
                    cur_pin = &pb_graph_node->clock_pins[from_port][from_pin];
                } else {
                    cur_pin = &pb_graph_node->input_pins[from_port][from_pin];
                }
                next_pin = expand_pack_molecule_pin_edge(
                        pack_pattern_block->pattern_index, cur_pin, FALSE);
            }
            /* found next primitive */
            if (next_pin != NULL) {
                next_primitive = next_pin->parent_node;
                /* Check for legality of placement, if legal, expand from legal placement, if not, return FALSE */
                if (molecule->logical_block_ptrs[next_block->block_id] != NULL
                        && primitives_list[next_block->block_id] == NULL) {
                    if (next_primitive->cluster_placement_primitive->valid
                            == TRUE
                            && primitive_type_feasible(
                                    molecule->logical_block_ptrs[next_block->block_id]->index,
                                    next_primitive->pb_type)) {
                        primitives_list[next_block->block_id] = next_primitive;
                        *cost +=
                                next_primitive->cluster_placement_primitive->base_cost
                                        + next_primitive->cluster_placement_primitive->incremental_cost;
                        if (!expand_forced_pack_molecule_placement(molecule,
                                next_block, primitives_list, cost)) {
                            return FALSE;
                        }
                    } else {
                        return FALSE;
                    }
                }
            } else {
                return FALSE;
            }
        }
        cur = cur->next;
    }

    return TRUE;
}

/**
 * Find next primitive pb_graph_pin
 */
static t_pb_graph_pin *expand_pack_molecule_pin_edge(INP int pattern_id,
        INP t_pb_graph_pin *cur_pin, INP boolean forward) {
    int i, j, k;
    t_pb_graph_pin *temp_pin, *dest_pin;
    temp_pin = NULL;
    dest_pin = NULL;
    if (forward) {
        for (i = 0; i < cur_pin->num_output_edges; i++) {
            /* one fanout assumption */
            if (cur_pin->output_edges[i]->infer_pattern) {
                for (k = 0; k < cur_pin->output_edges[i]->num_output_pins;
                        k++) {
                    if (cur_pin->output_edges[i]->output_pins[k]->parent_node->pb_type->num_modes
                            == 0) {
                        temp_pin = cur_pin->output_edges[i]->output_pins[k];
                    } else {
                        temp_pin = expand_pack_molecule_pin_edge(pattern_id,
                                cur_pin->output_edges[i]->output_pins[k],
                                forward);
                    }
                }
                if (temp_pin != NULL) {
                    assert(dest_pin == NULL || dest_pin == temp_pin);
                    dest_pin = temp_pin;
                }
            } else {
                for (j = 0; j < cur_pin->output_edges[i]->num_pack_patterns;
                        j++) {
                    if (cur_pin->output_edges[i]->pack_pattern_indices[j]
                            == pattern_id) {
                        for (k = 0;
                                k < cur_pin->output_edges[i]->num_output_pins;
                                k++) {
                            if (cur_pin->output_edges[i]->output_pins[k]->parent_node->pb_type->num_modes
                                    == 0) {
                                temp_pin =
                                        cur_pin->output_edges[i]->output_pins[k];
                            } else {
                                temp_pin =
                                        expand_pack_molecule_pin_edge(
                                                pattern_id,
                                                cur_pin->output_edges[i]->output_pins[k],
                                                forward);
                            }
                        }
                        if (temp_pin != NULL) {
                            assert(dest_pin == NULL || dest_pin == temp_pin);
                            dest_pin = temp_pin;
                        }
                    }
                }
            }
        }
    } else {
        for (i = 0; i < cur_pin->num_input_edges; i++) {
            /* one fanout assumption */
            if (cur_pin->input_edges[i]->infer_pattern) {
                for (k = 0; k < cur_pin->input_edges[i]->num_input_pins; k++) {
                    if (cur_pin->input_edges[i]->input_pins[k]->parent_node->pb_type->num_modes
                            == 0) {
                        temp_pin = cur_pin->input_edges[i]->input_pins[k];
                    } else {
                        temp_pin = expand_pack_molecule_pin_edge(pattern_id,
                                cur_pin->input_edges[i]->input_pins[k],
                                forward);
                    }
                }
                if (temp_pin != NULL) {
                    assert(dest_pin == NULL || dest_pin == temp_pin);
                    dest_pin = temp_pin;
                }
            } else {
                for (j = 0; j < cur_pin->input_edges[i]->num_pack_patterns;
                        j++) {
                    if (cur_pin->input_edges[i]->pack_pattern_indices[j]
                            == pattern_id) {
                        for (k = 0; k < cur_pin->input_edges[i]->num_input_pins;
                                k++) {
                            if (cur_pin->input_edges[i]->input_pins[k]->parent_node->pb_type->num_modes
                                    == 0) {
                                temp_pin =
                                        cur_pin->input_edges[i]->input_pins[k];
                            } else {
                                temp_pin = expand_pack_molecule_pin_edge(
                                        pattern_id,
                                        cur_pin->input_edges[i]->input_pins[k],
                                        forward);
                            }
                        }
                        if (temp_pin != NULL) {
                            assert(dest_pin == NULL || dest_pin == temp_pin);
                            dest_pin = temp_pin;
                        }
                    }
                }
            }
        }
    }
    return dest_pin;
}

static void flush_intermediate_queues(
        INOUTP t_cluster_placement_stats *cluster_placement_stats) {
    t_cluster_placement_primitive *cur, *next;
    cur = cluster_placement_stats->tried;
    while (cur != NULL) {
        next = cur->next_primitive;
        requeue_primitive(cluster_placement_stats, cur);
        cur = next;
    }
    cluster_placement_stats->tried = NULL;

    cur = cluster_placement_stats->in_flight;
    if (cur != NULL) {
        next = cur->next_primitive;
        requeue_primitive(cluster_placement_stats, cur);
        /* should have at most one block in flight at any point in time */
        assert(next == NULL);
    }
    cluster_placement_stats->in_flight = NULL;
}

/* Determine max index + 1 of molecule */
int get_array_size_of_molecule(t_pack_molecule *molecule) {
    if (molecule->type == MOLECULE_FORCED_PACK) {
        return molecule->pack_pattern->num_blocks;
    } else {
        return molecule->num_blocks;
    }
}

/* Given logical block, determines if a free primitive exists for it */
boolean exists_free_primitive_for_logical_block(
        INOUTP t_cluster_placement_stats *cluster_placement_stats,
        INP int ilogical_block) {
    int i;
    t_cluster_placement_primitive *cur, *prev;

    /* might have a primitive in flight that's still valid */
    if (cluster_placement_stats->in_flight) {
        if (primitive_type_feasible(ilogical_block,
                cluster_placement_stats->in_flight->pb_graph_node->pb_type)) {
            return TRUE;
        }
    }

    /* Look through list of available primitives to see if any valid */
    for (i = 0; i < cluster_placement_stats->num_pb_types; i++) {
        if (cluster_placement_stats->valid_primitives[i]->next_primitive == NULL) {
            continue; /* no more primitives of this type available */
        }
        if (primitive_type_feasible(ilogical_block,
                cluster_placement_stats->valid_primitives[i]->next_primitive->pb_graph_node->pb_type)) {
            prev = cluster_placement_stats->valid_primitives[i];
            cur = cluster_placement_stats->valid_primitives[i]->next_primitive;
            while (cur) {
                /* remove invalid nodes lazily when encountered */
                while (cur && cur->valid == FALSE) {
                    prev->next_primitive = cur->next_primitive;
                    cur->next_primitive = cluster_placement_stats->invalid;
                    cluster_placement_stats->invalid = cur;
                    cur = prev->next_primitive;
                }
                if (cur == NULL) {
                    break;
                }
                return TRUE;
            }
        }
    }

    return FALSE;
}


void reset_tried_but_unused_cluster_placements(
        INOUTP t_cluster_placement_stats *cluster_placement_stats) {
    flush_intermediate_queues(cluster_placement_stats);
}


/* Quick, additional filter to see if root is feasible for molecule 

   Limitation: This code can absorb a single atom by a "forced connection".  A forced connection is one where there is no interconnect flexibility connecting
               two primitives so if one primitive is used, then the other must also be used.

               TODO: jluu - Many ways to make this either more efficient or more robust.
                            1.  For forced connections, I can get the packer to try forced connections first thus avoid trying out other locations that 
                                I know are bad thus saving runtime and potentially improving robustness because the placement cost function is not always 100%.
                            2.  I need to extend this so that molecules can be pulled in instead of just atoms.
*/
static boolean root_passes_early_filter(INP t_pb_graph_node *root, INP t_pack_molecule *molecule, INP int clb_index) {
    int i, j;
    boolean feasible;
    t_logical_block *root_block;
    t_model_ports *model_port;
    int inet;
    int isink;
    t_pb_graph_pin *sink_pb_graph_pin;

    feasible = TRUE;
    root_block = molecule->logical_block_ptrs[molecule->root];
    for(i = 0; feasible && i < root->num_output_ports; i++) {
        for(j = 0; feasible && j < root->num_output_pins[i]; j++) {
            if(root->output_pins[i][j].is_forced_connection) {
                model_port = root->output_pins[i][j].port->model_port;
                inet = root_block->output_nets[model_port->index][j];
                if(inet != OPEN) {
                    /* This output pin has a dedicated connection to one output, make sure that molecule works */
                    if(molecule->type == MOLECULE_SINGLE_ATOM) {
                        feasible = FALSE; /* There is only one case where an atom can fit in here, so by default, feasibility is false unless proven otherwise */
                        if(vpack_net[inet].num_sinks == 1) {
                            isink = vpack_net[inet].node_block[1];
                            if(logical_block[isink].clb_index == clb_index) {
                                sink_pb_graph_pin = &root->output_pins[i][j];
                                while(sink_pb_graph_pin->num_output_edges != 0) {
                                    assert(sink_pb_graph_pin->num_output_edges == 1);
                                    assert(sink_pb_graph_pin->output_edges[0]->num_output_pins == 1);
                                    sink_pb_graph_pin = sink_pb_graph_pin->output_edges[0]->output_pins[0];
                                }
                                if(sink_pb_graph_pin->parent_node == logical_block[isink].pb->pb_graph_node) {
                                    /* There is a logical block mapped to the physical position that pulls in the atom in question */
                                    feasible = TRUE;
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    return feasible;
}