cluster.h File Reference

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Functions
void	do_clustering (const t_arch *arch, t_pack_molecule *molecule_head, int num_models, boolean global_clocks, boolean *is_clock, boolean hill_climbing_flag, char *out_fname, boolean timing_driven, enum e_cluster_seed cluster_seed_type, float alpha, float beta, int recompute_timing_after, float block_delay, float intra_cluster_net_delay, float inter_cluster_net_delay, float aspect, boolean allow_unrelated_clustering, boolean allow_early_exit, boolean connection_driven, enum e_packer_algorithm packer_algorithm, t_timing_inf timing_inf)
int	get_cluster_of_block (int blkidx)

Function Documentation

void do_clustering	(	const t_arch *	arch,
		t_pack_molecule *	molecule_head,
		int	num_models,
		boolean	global_clocks,
		boolean *	is_clock,
		boolean	hill_climbing_flag,
		char *	out_fname,
		boolean	timing_driven,
		enum e_cluster_seed	cluster_seed_type,
		float	alpha,
		float	beta,
		int	recompute_timing_after,
		float	block_delay,
		float	intra_cluster_net_delay,
		float	inter_cluster_net_delay,
		float	aspect,
		boolean	allow_unrelated_clustering,
		boolean	allow_early_exit,
		boolean	connection_driven,
		enum e_packer_algorithm	packer_algorithm,
		t_timing_inf	timing_inf
	)

Definition at line 232 of file cluster.c.

                                                                           {

    /* Does the actual work of clustering multiple netlist blocks *
     * into clusters.                                                  */

    /* Algorithm employed
     1.  Find type that can legally hold block and create cluster with pb info
     2.  Populate started cluster
     3.  Repeat 1 until no more blocks need to be clustered
     
     */

    int i, iblk, num_molecules, blocks_since_last_analysis, num_clb, max_nets_in_pb_type,  
        cur_nets_in_pb_type, num_blocks_hill_added, max_cluster_size, cur_cluster_size, 
        max_molecule_inputs, max_pb_depth, cur_pb_depth, num_unrelated_clustering_attempts,
        indexofcrit, savedindexofcrit /* index of next most timing critical block */,
        detailed_routing_stage, *hill_climbing_inputs_avail;

    int *num_used_instances_type, *num_instances_type; 
    /* [0..num_types] Holds array for total number of each cluster_type available */

    boolean early_exit, is_cluster_legal;
    enum e_block_pack_status block_pack_status;
    float crit;

    t_cluster_placement_stats *cluster_placement_stats, *cur_cluster_placement_stats_ptr;
    t_pb_graph_node **primitives_list;
    t_block *clb;
    t_slack * slacks = NULL;
    t_pack_molecule *istart, *next_molecule, *prev_molecule, *cur_molecule;
    
#ifdef PATH_COUNTING
    int inet, ipin;
#else
    int inode;
    float num_paths_scaling, distance_scaling;
#endif

    /* TODO: This is memory inefficient, fix if causes problems */
    clb = (t_block*)my_calloc(num_logical_blocks, sizeof(t_block));
    num_clb = 0;
    istart = NULL;

    /* determine bound on cluster size and primitive input size */
    max_cluster_size = 0;
    max_molecule_inputs = 0;
    max_pb_depth = 0;
    max_nets_in_pb_type = 0;

    indexofcrit = 0;

    cur_molecule = molecule_head;
    num_molecules = 0;
    while (cur_molecule != NULL) {
        cur_molecule->valid = TRUE;
        if (cur_molecule->num_ext_inputs > max_molecule_inputs) {
            max_molecule_inputs = cur_molecule->num_ext_inputs;
        }
        num_molecules++;
        cur_molecule = cur_molecule->next;
    }

    for (i = 0; i < num_types; i++) {
        if (EMPTY_TYPE == &type_descriptors[i])
            continue;
        cur_cluster_size = get_max_primitives_in_pb_type(
                type_descriptors[i].pb_type);
        cur_pb_depth = get_max_depth_of_pb_type(type_descriptors[i].pb_type);
        cur_nets_in_pb_type = get_max_nets_in_pb_type(
                type_descriptors[i].pb_type);
        if (cur_cluster_size > max_cluster_size) {
            max_cluster_size = cur_cluster_size;
        }
        if (cur_pb_depth > max_pb_depth) {
            max_pb_depth = cur_pb_depth;
        }
        if (cur_nets_in_pb_type > max_nets_in_pb_type) {
            max_nets_in_pb_type = cur_nets_in_pb_type;
        }
    }

    if (hill_climbing_flag) {
        hill_climbing_inputs_avail = (int *) my_calloc(max_cluster_size + 1,
                sizeof(int));
    } else {
        hill_climbing_inputs_avail = NULL; /* if used, die hard */
    }

    /* TODO: make better estimate for nx and ny */
    nx = ny = 1;

    check_clocks(is_clock);
#if 0
    check_for_duplicate_inputs ();
#endif
    alloc_and_init_clustering(global_clocks, alpha, beta, max_cluster_size,
            max_molecule_inputs, max_pb_depth, num_models,
            &cluster_placement_stats, &primitives_list, molecule_head,
            num_molecules);

    blocks_since_last_analysis = 0;
    early_exit = FALSE;
    num_blocks_hill_added = 0;
    num_used_instances_type = (int*) my_calloc(num_types, sizeof(int));
    num_instances_type = (int*) my_calloc(num_types, sizeof(int));

    assert(max_cluster_size < MAX_SHORT);
    /* Limit maximum number of elements for each cluster */

    if (timing_driven) {
        slacks = alloc_and_load_pre_packing_timing_graph(block_delay,
                inter_cluster_net_delay, arch->models, timing_inf);
        do_timing_analysis(slacks, TRUE, FALSE, FALSE);

        if (getEchoEnabled()) {
            if(isEchoFileEnabled(E_ECHO_PRE_PACKING_TIMING_GRAPH))
                print_timing_graph(getEchoFileName(E_ECHO_PRE_PACKING_TIMING_GRAPH));
#ifndef PATH_COUNTING
            if(isEchoFileEnabled(E_ECHO_CLUSTERING_TIMING_INFO))
                print_clustering_timing_info(getEchoFileName(E_ECHO_CLUSTERING_TIMING_INFO));
#endif
            if(isEchoFileEnabled(E_ECHO_PRE_PACKING_SLACK))
                print_slack(slacks->slack, FALSE, getEchoFileName(E_ECHO_PRE_PACKING_SLACK));
            if(isEchoFileEnabled(E_ECHO_PRE_PACKING_CRITICALITY))
                print_criticality(slacks, FALSE, getEchoFileName(E_ECHO_PRE_PACKING_CRITICALITY));
        }

        block_criticality = (float*) my_calloc(num_logical_blocks, sizeof(float));

        critindexarray = (int*) my_malloc(num_logical_blocks * sizeof(int));

        for (i = 0; i < num_logical_blocks; i++) {
            assert(logical_block[i].index == i);
            critindexarray[i] = i;
        }

#ifdef PATH_COUNTING
        /* Calculate block criticality from a weighted sum of timing and path criticalities. */
        for (inet = 0; inet < num_logical_nets; inet++) { 
            for (ipin = 1; ipin <= vpack_net[inet].num_sinks; ipin++) { 
            
                /* Find the logical block iblk which this pin is a sink on. */
                iblk = vpack_net[inet].node_block[ipin];
                    
                /* The criticality of this pin is a sum of its timing and path criticalities. */
                crit =      PACK_PATH_WEIGHT  * slacks->path_criticality[inet][ipin] 
                     + (1 - PACK_PATH_WEIGHT) * slacks->timing_criticality[inet][ipin]; 

                /* The criticality of each block is the maximum of the criticalities of all its pins. */
                if (block_criticality[iblk] < crit) {
                    block_criticality[iblk] = crit;
                }
            }
        }

#else
        /* Calculate criticality based on slacks and tie breakers (# paths, distance from source) */
        for (inode = 0; inode < num_tnodes; inode++) {
            /* Only calculate for tnodes which have valid normalized values.
            Either all values will be accurate or none will, so we only have
            to check whether one particular value (normalized_T_arr) is valid 
            Tnodes that do not have both times valid were not part of the analysis. 
            Because we calloc-ed the array criticality, such nodes will have criticality 0, the lowest possible value. */
            if (has_valid_normalized_T_arr(inode)) {
                iblk = tnode[inode].block;
                num_paths_scaling = SCALE_NUM_PATHS
                        * (float) tnode[inode].prepacked_data->normalized_total_critical_paths;
                distance_scaling = SCALE_DISTANCE_VAL
                        * (float) tnode[inode].prepacked_data->normalized_T_arr;
                crit = (1 - tnode[inode].prepacked_data->normalized_slack) + num_paths_scaling
                        + distance_scaling;
                if (block_criticality[iblk] < crit) {
                    block_criticality[iblk] = crit;
                }
            }
        }
#endif
        heapsort(critindexarray, block_criticality, num_logical_blocks, 1);
        
        if (getEchoEnabled() && isEchoFileEnabled(E_ECHO_CLUSTERING_BLOCK_CRITICALITIES)) {
            print_block_criticalities(getEchoFileName(E_ECHO_CLUSTERING_BLOCK_CRITICALITIES));
        }


        if (cluster_seed_type == VPACK_TIMING) {
            istart = get_most_critical_seed_molecule(&indexofcrit);
        } else {/*max input seed*/
            istart = get_seed_logical_molecule_with_most_ext_inputs(
                    max_molecule_inputs);
        }

    } else /*cluster seed is max input (since there is no timing information)*/ {
        istart = get_seed_logical_molecule_with_most_ext_inputs(
                max_molecule_inputs);
    }


    while (istart != NULL) {
        is_cluster_legal = FALSE;
        savedindexofcrit = indexofcrit;
        for (detailed_routing_stage = (int)E_DETAILED_ROUTE_AT_END_ONLY; !is_cluster_legal && detailed_routing_stage != (int)E_DETAILED_ROUTE_END; detailed_routing_stage++) {
            reset_legalizer_for_cluster(&clb[num_clb]);

            /* start a new cluster and reset all stats */
            start_new_cluster(cluster_placement_stats, primitives_list, arch,
                    &clb[num_clb], num_clb, istart, aspect, num_used_instances_type,
                    num_instances_type, num_models, max_cluster_size,
                    max_nets_in_pb_type, detailed_routing_stage);
            vpr_printf(TIO_MESSAGE_INFO, "Complex block %d: %s, type: %s\n", 
                    num_clb, clb[num_clb].name, clb[num_clb].type->name);
            vpr_printf(TIO_MESSAGE_INFO, "\t");
            fflush(stdout);
            update_cluster_stats(istart, num_clb, is_clock, global_clocks, alpha,
                    beta, timing_driven, connection_driven, slacks);
            num_clb++;

            if (timing_driven && !early_exit) {
                blocks_since_last_analysis++;
                /*it doesn't make sense to do a timing analysis here since there*
                 *is only one logical_block clustered it would not change anything      */
            }
            cur_cluster_placement_stats_ptr = &cluster_placement_stats[clb[num_clb
                    - 1].type->index];
            num_unrelated_clustering_attempts = 0;
            next_molecule = get_molecule_for_cluster(PACK_BRUTE_FORCE,
                    clb[num_clb - 1].pb, allow_unrelated_clustering,
                    &num_unrelated_clustering_attempts,
                    cur_cluster_placement_stats_ptr);
            prev_molecule = istart;
            while (next_molecule != NULL && prev_molecule != next_molecule) {
                block_pack_status = try_pack_molecule(
                        cur_cluster_placement_stats_ptr, next_molecule,
                        primitives_list, clb[num_clb - 1].pb, num_models,
                        max_cluster_size, num_clb - 1, max_nets_in_pb_type, detailed_routing_stage);
                prev_molecule = next_molecule;
                if (block_pack_status != BLK_PASSED) {
                    if (next_molecule != NULL) {
                        if (block_pack_status == BLK_FAILED_ROUTE) {
#ifdef DEBUG_FAILED_PACKING_CANDIDATES
                            vpr_printf(TIO_MESSAGE_DIRECT, "\tNO_ROUTE:%s type %s/n", 
                                    next_molecule->logical_block_ptrs[next_molecule->root]->name, 
                                    next_molecule->logical_block_ptrs[next_molecule->root]->model->name);
                            fflush(stdout);
    #else
                            vpr_printf(TIO_MESSAGE_DIRECT, ".");
    #endif
                        } else {
    #ifdef DEBUG_FAILED_PACKING_CANDIDATES
                            vpr_printf(TIO_MESSAGE_DIRECT, "\tFAILED_CHECK:%s type %s check %d\n", 
                                    next_molecule->logical_block_ptrs[next_molecule->root]->name, 
                                    next_molecule->logical_block_ptrs[next_molecule->root]->model->name, 
                                    block_pack_status);
                            fflush(stdout);
    #else
                            vpr_printf(TIO_MESSAGE_DIRECT, ".");
    #endif
                        }
                    }

                    next_molecule = get_molecule_for_cluster(PACK_BRUTE_FORCE,
                            clb[num_clb - 1].pb, allow_unrelated_clustering,
                            &num_unrelated_clustering_attempts,
                            cur_cluster_placement_stats_ptr);
                    continue;
                } else {
                    /* Continue packing by filling smallest cluster */
    #ifdef DEBUG_FAILED_PACKING_CANDIDATES          
                    vpr_printf(TIO_MESSAGE_DIRECT, "\tPASSED:%s type %s\n", 
                            next_molecule->logical_block_ptrs[next_molecule->root]->name, 
                            next_molecule->logical_block_ptrs[next_molecule->root]->model->name);
                    fflush(stdout);
    #else
                    vpr_printf(TIO_MESSAGE_DIRECT, ".");
    #endif
                }
                update_cluster_stats(next_molecule, num_clb - 1, is_clock,
                        global_clocks, alpha, beta, timing_driven,
                        connection_driven, slacks);
                num_unrelated_clustering_attempts = 0;

                if (timing_driven && !early_exit) {
                    blocks_since_last_analysis++; /* historically, timing slacks were recomputed after X number of blocks were packed, but this doesn't significantly alter results so I (jluu) did not port the code */
                }
                next_molecule = get_molecule_for_cluster(PACK_BRUTE_FORCE,
                        clb[num_clb - 1].pb, allow_unrelated_clustering,
                        &num_unrelated_clustering_attempts,
                        cur_cluster_placement_stats_ptr);
            }
            vpr_printf(TIO_MESSAGE_DIRECT, "\n");
            if (detailed_routing_stage == (int)E_DETAILED_ROUTE_AT_END_ONLY) {
                is_cluster_legal = try_breadth_first_route_cluster();
                if (is_cluster_legal == TRUE) {
                    vpr_printf(TIO_MESSAGE_INFO, "Passed route at end.\n");
                } else {
                    vpr_printf(TIO_MESSAGE_INFO, "Failed route at end, repack cluster trying detailed routing at each stage.\n");
                }
            } else {
                is_cluster_legal = TRUE;
            }
            if (is_cluster_legal == TRUE) {
                save_cluster_solution();
                if (timing_driven) {
                    if (num_blocks_hill_added > 0 && !early_exit) {
                        blocks_since_last_analysis += num_blocks_hill_added;
                    }
                    if (cluster_seed_type == VPACK_TIMING) {
                        istart = get_most_critical_seed_molecule(&indexofcrit);
                    } else { /*max input seed*/
                        istart = get_seed_logical_molecule_with_most_ext_inputs(
                                max_molecule_inputs);
                    }
                } else
                    /*cluster seed is max input (since there is no timing information)*/
                    istart = get_seed_logical_molecule_with_most_ext_inputs(
                            max_molecule_inputs);
                
                free_pb_stats_recursive(clb[num_clb - 1].pb);
            } else {
                /* Free up data structures and requeue used molecules */
                num_used_instances_type[clb[num_clb - 1].type->index]--;
                free_cb(clb[num_clb - 1].pb);
                free(clb[num_clb - 1].pb);
                free(clb[num_clb - 1].name);
                clb[num_clb - 1].name = NULL;
                clb[num_clb - 1].pb = NULL;
                num_clb--;
                indexofcrit = savedindexofcrit;
            }
        }
    }

    free_cluster_legality_checker();

    alloc_and_load_cluster_info(num_clb, clb);

    check_clustering(num_clb, clb, is_clock);

    output_clustering(clb, num_clb, global_clocks, is_clock, out_fname, FALSE);
    if (getEchoEnabled() && isEchoFileEnabled(E_ECHO_POST_PACK_NETLIST)) {
        output_blif (clb, num_clb, global_clocks, is_clock,
            getEchoFileName(E_ECHO_POST_PACK_NETLIST), FALSE);
    }

    if (hill_climbing_flag) {
        free(hill_climbing_inputs_avail);
    }
    free_cluster_placement_stats(cluster_placement_stats);

    for (i = 0; i < num_clb; i++) {
        free_cb(clb[i].pb);
        free(clb[i].name);
        free(clb[i].nets);
        free(clb[i].pb);
    }
    free(clb);

    free(num_used_instances_type);
    free(num_instances_type);
    free(unclustered_list_head);
    free(memory_pool);
    free(net_output_feeds_driving_block_input);

    if (timing_driven) {
        free(block_criticality);
        free(critindexarray);

        block_criticality = NULL;
        critindexarray = NULL;
    }

    if (timing_driven) {
        free_timing_graph(slacks);
    }

 free (primitives_list);

}

Here is the call graph for this function:

Here is the caller graph for this function:

int get_cluster_of_block

(

int

blkidx

)