SRC/rr_graph.h File Reference

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

Go to the source code of this file.

Typedefs
typedef enum e_graph_type	t_graph_type
Enumerations
enum	e_graph_type { GRAPH_GLOBAL, GRAPH_BIDIR, GRAPH_UNIDIR, GRAPH_UNIDIR_TILEABLE }
enum	{ RR_GRAPH_NO_WARN = 0x00, RR_GRAPH_WARN_FC_CLIPPED = 0x01, RR_GRAPH_WARN_CHAN_WIDTH_CHANGED = 0x02 }
Functions
void	build_rr_graph (IN t_graph_type graph_type, IN int num_types, IN t_type_ptr types, IN int nx, IN int ny, IN struct s_grid_tile **grid, IN int chan_width, IN struct s_chan_width_dist *chan_capacity_inf, IN enum e_switch_block_type sb_type, IN int Fs, IN int num_seg_types, IN int num_switches, IN t_segment_inf *segment_inf, IN int global_route_switch, IN int delayless_switch, IN t_timing_inf timing_inf, IN int wire_to_ipin_switch, IN enum e_base_cost_type base_cost_type, OUT int *Warnings)
void	free_rr_graph (void)
void	dump_rr_graph (IN const char *file_name)
void	print_rr_indexed_data (FILE *fp, int index)
void	load_net_rr_terminals (t_ivec ***rr_node_indices)

---

Typedef Documentation

typedef enum e_graph_type t_graph_type

Definition at line 9 of file rr_graph.h.

---

Enumeration Type Documentation

anonymous enum

Enumerator:

RR_GRAPH_NO_WARN
RR_GRAPH_WARN_FC_CLIPPED
RR_GRAPH_WARN_CHAN_WIDTH_CHANGED

Definition at line 13 of file rr_graph.h.

{
    RR_GRAPH_NO_WARN = 0x00,
    RR_GRAPH_WARN_FC_CLIPPED = 0x01,
    RR_GRAPH_WARN_CHAN_WIDTH_CHANGED = 0x02
};

enum e_graph_type

Enumerator:

GRAPH_GLOBAL
GRAPH_BIDIR
GRAPH_UNIDIR
GRAPH_UNIDIR_TILEABLE

Definition at line 1 of file rr_graph.h.

{
    GRAPH_GLOBAL,               /* One node per channel with wire capacity > 1 and full connectivity */
    GRAPH_BIDIR,                /* Detailed bidirectional graph */
    GRAPH_UNIDIR,               /* Detailed unidir graph, untilable */
    /* RESEARCH TODO: Get this option debugged */
    GRAPH_UNIDIR_TILEABLE       /* Detail unidir graph with wire groups multiples of 2*L */
};

---

Function Documentation

void build_rr_graph	(	IN t_graph_type	graph_type,
		IN int	num_types,
		IN t_type_ptr	types,
		IN int	nx,
		IN int	ny,
		IN struct s_grid_tile **	grid,
		IN int	chan_width,
		IN struct s_chan_width_dist *	chan_capacity_inf,
		IN enum e_switch_block_type	sb_type,
		IN int	Fs,
		IN int	num_seg_types,
		IN int	num_switches,
		IN t_segment_inf *	segment_inf,
		IN int	global_route_switch,
		IN int	delayless_switch,
		IN t_timing_inf	timing_inf,
		IN int	wire_to_ipin_switch,
		IN enum e_base_cost_type	base_cost_type,
		OUT int *	Warnings
	)

Definition at line 280 of file rr_graph.c.

{
    /* Temp structures used to build graph */
    int nodes_per_chan, i, j;
    t_seg_details *seg_details = NULL;
    int *Fc_in = NULL;
    int *Fc_out = NULL;
   
    int *****opin_to_track_map = NULL;  /* [0..num_types-1][0..num_pins-1][0..height][0..3][0..Fc-1] */
    int *****ipin_to_track_map = NULL;  /* [0..num_types-1][0..num_pins-1][0..height][0..3][0..Fc-1] */
    t_ivec ****track_to_ipin_lookup = NULL;     /* [0..num_types-1][0..nodes_per_chan-1][0..height][0..3] */
    t_ivec ***switch_block_conn = NULL;
    short *****unidir_sb_pattern = NULL;
    boolean *rr_edge_done = NULL;
    boolean is_global_graph;
    boolean Fc_clipped;
    boolean use_full_seg_groups;
    boolean *perturb_ipins = NULL;
    enum e_directionality directionality;
    int **Fc_xofs = NULL;       /* [0..ny-1][0..nx-1] */
    int **Fc_yofs = NULL;       /* [0..nx-1][0..ny-1] */

        rr_node_indices = NULL;
        rr_node = NULL;
        num_rr_nodes = 0;

    /* Reset warning flag */
    *Warnings = RR_GRAPH_NO_WARN;

    /* Decode the graph_type */
    is_global_graph = FALSE;
    if(GRAPH_GLOBAL == graph_type)
        {
            is_global_graph = TRUE;
        }
    use_full_seg_groups = FALSE;
    if(GRAPH_UNIDIR_TILEABLE == graph_type)
        {
            use_full_seg_groups = TRUE;
        }
    directionality = UNI_DIRECTIONAL;
    if(GRAPH_BIDIR == graph_type)
        {
            directionality = BI_DIRECTIONAL;
        }
    if(is_global_graph)
        {
            directionality = BI_DIRECTIONAL;
        }


    /* Global routing uses a single longwire track */
    nodes_per_chan = (is_global_graph ? 1 : chan_width);
    assert(nodes_per_chan > 0);



    /* START SEG_DETAILS */
    if(is_global_graph)
        {
            /* Sets up a single unit length segment type for global routing. */
            seg_details =
                alloc_and_load_global_route_seg_details(nodes_per_chan,
                                                        global_route_switch);
        }
    else
        {
            /* Setup segments including distrubuting tracks and staggering.
             * If use_full_seg_groups is specified, nodes_per_chan may be 
             * changed. Warning should be singled to caller if this happens. */
            seg_details = alloc_and_load_seg_details(&nodes_per_chan,
                                                     max(nx, ny),
                                                     num_seg_types,
                                                     segment_inf,
                                                     use_full_seg_groups,
                                                     is_global_graph,
                                                     directionality);
            if((is_global_graph ? 1 : chan_width) != nodes_per_chan)
                {
                    *Warnings |= RR_GRAPH_WARN_CHAN_WIDTH_CHANGED;
                }
#ifdef CREATE_ECHO_FILES
            dump_seg_details(seg_details, nodes_per_chan, "seg_details.txt");
#endif /* CREATE_ECHO_FILES */
        }
    /* END SEG_DETAILS */



    /* START FC */
    /* Determine the actual value of Fc */
    if(is_global_graph)
        {
            Fc_in = (int *)my_malloc(sizeof(int) * num_types);
            Fc_out = (int *)my_malloc(sizeof(int) * num_types);
            for(i = 0; i < num_types; ++i)
                {
                    Fc_in[i] = 1;
                    Fc_out[i] = 1;
                }
        }
    else
        {
            Fc_clipped = FALSE;
            Fc_in =
                alloc_and_load_actual_fc(num_types, types, nodes_per_chan,
                                         FALSE, directionality, &Fc_clipped);
            if(Fc_clipped)
                {
                    *Warnings |= RR_GRAPH_WARN_FC_CLIPPED;
                }
            Fc_clipped = FALSE;
            Fc_out =
                alloc_and_load_actual_fc(num_types, types, nodes_per_chan,
                                         TRUE, directionality, &Fc_clipped);
            if(Fc_clipped)
                {
                    *Warnings |= RR_GRAPH_WARN_FC_CLIPPED;
                }


#ifdef VERBOSE
            for(i = 1; i < num_types; ++i)
                {               /* Skip "<EMPTY>" */
                    if(type_descriptors[i].is_Fc_out_full_flex)
                        {
                            printf
                                ("Fc Actual Values: Type = %s, Fc_out = full, Fc_in = %d.\n",
                                 type_descriptors[i].name, Fc_input[i]);
                        }
                    else
                        {
                            printf
                                ("Fc Actual Values: Type = %s, Fc_out = %d, Fc_in = %d.\n",
                                 type_descriptors[i].name, Fc_output[i],
                                 Fc_input[i]);
                        }
                }
#endif /* VERBOSE */
        }
        
        perturb_ipins =
                alloc_and_load_perturb_ipins(nodes_per_chan, num_types, Fc_in,
                                             Fc_out, directionality);
    /* END FC */


    /* Alloc node lookups, count nodes, alloc rr nodes */
    num_rr_nodes = 0;
    rr_node_indices =
        alloc_and_load_rr_node_indices(nodes_per_chan, nx, ny, &num_rr_nodes,
                                       seg_details);
    rr_node = (t_rr_node *) my_malloc(sizeof(t_rr_node) * num_rr_nodes);
    memset(rr_node, 0, sizeof(t_rr_node) * num_rr_nodes);
    rr_edge_done = (boolean *) my_malloc(sizeof(boolean) * num_rr_nodes);
    memset(rr_edge_done, 0, sizeof(boolean) * num_rr_nodes);

    /* These are data structures used by the the unidir opin mapping. */
    if(UNI_DIRECTIONAL == directionality)
        {
            Fc_xofs = (int **)alloc_matrix(0, ny, 0, nx, sizeof(int));
            Fc_yofs = (int **)alloc_matrix(0, nx, 0, ny, sizeof(int));
            for(i = 0; i <= nx; ++i)
                {
                    for(j = 0; j <= ny; ++j)
                        {
                            Fc_xofs[j][i] = 0;
                            Fc_yofs[i][j] = 0;
                        }
                }
        }



    /* START SB LOOKUP */
    /* Alloc and load the switch block lookup */
    if(is_global_graph)
        {
            assert(nodes_per_chan == 1);
            switch_block_conn =
                alloc_and_load_switch_block_conn(1, SUBSET, 3);
        }
    else if(BI_DIRECTIONAL == directionality)
        {
            switch_block_conn =
                alloc_and_load_switch_block_conn(nodes_per_chan, sb_type, Fs);
        }
    else
        {
            assert(UNI_DIRECTIONAL == directionality);

            unidir_sb_pattern =
                alloc_sblock_pattern_lookup(nx, ny, nodes_per_chan);
            for(i = 0; i <= nx; i++)
                {
                    for(j = 0; j <= ny; j++)
                        {
                            load_sblock_pattern_lookup(i, j, nodes_per_chan,
                                                       seg_details, Fs,
                                                       sb_type,
                                                       unidir_sb_pattern);
                        }
                }
        }
    /* END SB LOOKUP */



    /* START IPIN MAP */
    /* Create ipin map lookups */
    ipin_to_track_map = (int *****)my_malloc(sizeof(int ****) * num_types);
    track_to_ipin_lookup =
        (struct s_ivec ****)my_malloc(sizeof(struct s_ivec ***) * num_types);
    for(i = 0; i < num_types; ++i)
        {
            ipin_to_track_map[i] = alloc_and_load_pin_to_track_map(RECEIVER,
                                                                   nodes_per_chan,
                                                                   Fc_in[i],
                                                                   &types[i],
                                                                   perturb_ipins
                                                                   [i],
                                                                   directionality);
            track_to_ipin_lookup[i] =
                alloc_and_load_track_to_pin_lookup(ipin_to_track_map[i],
                                                   Fc_in[i], types[i].height,
                                                   types[i].num_pins,
                                                   nodes_per_chan);
        }
    /* END IPIN MAP */



    /* START OPIN MAP */
    /* Create opin map lookups */
    if(BI_DIRECTIONAL == directionality)
        {
            opin_to_track_map =
                (int *****)my_malloc(sizeof(int ****) * num_types);
            for(i = 0; i < num_types; ++i)
                {
                    opin_to_track_map[i] =
                        alloc_and_load_pin_to_track_map(DRIVER,
                                                        nodes_per_chan,
                                                        Fc_out[i], &types[i],
                                                        FALSE,
                                                        directionality);
                }
        }
    /* END OPIN MAP */

    /* UDSD Modifications by WMF begin */
    /* I'm adding 2 new fields to t_rr_node, and I want them initialized to 0. */
    for(i = 0; i < num_rr_nodes; i++)
        {
            rr_node[i].num_wire_drivers = 0;
            rr_node[i].num_opin_drivers = 0;
        }


    alloc_and_load_rr_graph(num_rr_nodes, rr_node, num_seg_types,
                            seg_details, rr_edge_done,
                            track_to_ipin_lookup, opin_to_track_map,
                            switch_block_conn, grid, nx,
                            ny, Fs, unidir_sb_pattern, Fc_out, Fc_xofs,
                            Fc_yofs, rr_node_indices, nodes_per_chan,
                            sb_type, delayless_switch, directionality,
                            wire_to_ipin_switch, &Fc_clipped);


#if 0
#ifdef MUX_SIZE_DIST_DISPLAY
    if(UNI_DIRECTIONAL == directionality)
        {
            view_mux_size_distribution(rr_node_indices, nodes_per_chan,
                                       seg_details, seg_details);
        }
#endif
#endif

        /* Update rr_nodes capacities if global routing */
        if(graph_type == GLOBAL) {
                for(i = 0; i < num_rr_nodes; i++) {
                        if(rr_node[i].type == CHANX || rr_node[i].type == CHANY) {
                                rr_node[i].capacity = chan_width;
                        }
                }
        }

    rr_graph_externals(timing_inf, segment_inf, num_seg_types,
                       nodes_per_chan, wire_to_ipin_switch, base_cost_type);

#ifdef CREATE_ECHO_FILES
    dump_rr_graph("rr_graph.echo");
#endif /* CREATE_ECHO_FILES */

    check_rr_graph(graph_type, num_types, types, nx, ny,
                   grid, nodes_per_chan, Fs, num_seg_types, num_switches, segment_inf,
                   global_route_switch, delayless_switch,
                   wire_to_ipin_switch, seg_details, Fc_in, Fc_out,
                   rr_node_indices, opin_to_track_map, ipin_to_track_map,
                   track_to_ipin_lookup, switch_block_conn, perturb_ipins);

    /* Free all temp structs */
    if(seg_details)
        {
            free_seg_details(seg_details, nodes_per_chan);
            seg_details = NULL;
        }
    if(Fc_in)
        {
            free(Fc_in);
            Fc_in = NULL;
        }
    if(Fc_out)
        {
            free(Fc_out);
            Fc_out = NULL;
        }
    if(perturb_ipins)
        {
            free(perturb_ipins);
            perturb_ipins = NULL;
        }
    if(switch_block_conn)
        {
            free_switch_block_conn(switch_block_conn, nodes_per_chan);
            switch_block_conn = NULL;
        }
    if(rr_edge_done)
        {
            free(rr_edge_done);
            rr_edge_done = NULL;
        }
    if(Fc_xofs)
        {
            free_matrix(Fc_xofs, 0, ny, 0, sizeof(int));
                Fc_xofs = NULL;
        }
    if(Fc_yofs)
        {
            free_matrix(Fc_yofs, 0, nx, 0, sizeof(int));
                Fc_yofs = NULL;
        }
        if(unidir_sb_pattern)
        {
                free_sblock_pattern_lookup(unidir_sb_pattern);
                unidir_sb_pattern = NULL;
        }
        if(opin_to_track_map) {
            for(i = 0; i < num_types; ++i)
                {
                    free_matrix4(opin_to_track_map[i], 0, types[i].num_pins - 1,
                      0, types[i].height - 1, 0, 3, 0, sizeof(int));
                }
                free(opin_to_track_map);
        }
        
    free_type_pin_to_track_map(ipin_to_track_map, types, Fc_in);
    free_type_track_to_ipin_map(track_to_ipin_lookup, types, nodes_per_chan);
}

Here is the call graph for this function:

Here is the caller graph for this function:

void dump_rr_graph

(

IN const char *

file_name

)

Definition at line 2259 of file rr_graph.c.

{

    int inode;
    FILE *fp;

    fp = my_fopen(file_name, "w");

    for(inode = 0; inode < num_rr_nodes; inode++)
        {
            print_rr_node(fp, rr_node, inode);
            fprintf(fp, "\n");
        }

#if 0
    fprintf(fp, "\n\n%d rr_indexed_data entries.\n\n", num_rr_indexed_data);

    for(index = 0; index < num_rr_indexed_data; index++)
        {
            print_rr_indexed_data(fp, index);
            fprintf(fp, "\n");
        }
#endif

    fclose(fp);
}

Here is the call graph for this function:

Here is the caller graph for this function:

void free_rr_graph

(

void

)

Definition at line 1045 of file rr_graph.c.

{
    int i;

    /* Frees all the routing graph data structures, if they have been       *
     * allocated.  I use rr_mem_chunk_list_head as a flag to indicate       *
     * whether or not the graph has been allocated -- if it is not NULL,    *
     * a routing graph exists and can be freed.  Hence, you can call this   *
     * routine even if you're not sure of whether a rr_graph exists or not. */

    if(rr_mem_chunk_list_head == NULL)  /* Nothing to free. */
        return;

    free_chunk_memory(rr_mem_chunk_list_head);  /* Frees ALL "chunked" data */
    rr_mem_chunk_list_head = NULL;      /* No chunks allocated now. */
    chunk_bytes_avail = 0;      /* 0 bytes left in current "chunk". */
    chunk_next_avail_mem = NULL;        /* No current chunk.                */

    /* Before adding any more free calls here, be sure the data is NOT chunk *
     * allocated, as ALL the chunk allocated data is already free!           */

    free(net_rr_terminals);

        for(i = 0; i < num_rr_nodes; i++) {
                if(rr_node[i].edges != NULL) {
                        free(rr_node[i].edges);
                }
                if(rr_node[i].switches != NULL) {
                        free(rr_node[i].switches);
                }
        }

        assert(rr_node_indices);
    free_rr_node_indices(rr_node_indices);
    free(rr_node);
    free(rr_indexed_data);
    for(i = 0; i < num_blocks; i++)
        {
            free(rr_blk_source[i]);
        }
    free(rr_blk_source);
    rr_blk_source = NULL;
    net_rr_terminals = NULL;
    rr_node = NULL;
        rr_node_indices = NULL;
    rr_indexed_data = NULL;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void load_net_rr_terminals

(

t_ivec ***

rr_node_indices

)

Definition at line 1113 of file rr_graph.c.

{

    /* Allocates and loads the net_rr_terminals data structure.  For each net   *
     * it stores the rr_node index of the SOURCE of the net and all the SINKs   *
     * of the net.  [0..num_nets-1][0..num_pins-1].  Entry [inet][pnum] stores  *
     * the rr index corresponding to the SOURCE (opin) or SINK (ipin) of pnum.  */

    int inet, ipin, inode, iblk, i, j, k, node_block_pin, iclass;
    t_type_ptr type;

    for(inet = 0; inet < num_nets; inet++)
        {
            for(ipin = 0; ipin <= net[inet].num_sinks; ipin++)
                {
                    iblk = net[inet].node_block[ipin];
                    i = block[iblk].x;
                    j = block[iblk].y;
                    k = block[iblk].z;
                    type = block[iblk].type;

                    /* In the routing graph, each (x, y) location has unique pins on it
                     * so when there is capacity, blocks are packed and their pin numbers
                     * are offset to get their actual rr_node */
                    node_block_pin = net[inet].node_block_pin[ipin];

                    iclass = type->pin_class[node_block_pin];

                    inode = get_rr_node_index(i, j, (ipin == 0 ? SOURCE : SINK),        /* First pin is driver */
                                              iclass, rr_node_indices);
                    net_rr_terminals[inet][ipin] = inode;
                }
        }
}

Here is the call graph for this function:

Here is the caller graph for this function:

void print_rr_indexed_data	(	FILE *	fp,
		int	index
	)

Definition at line 2354 of file rr_graph.c.

{

    fprintf(fp, "Index: %d\n", index);

    fprintf(fp, "ortho_cost_index: %d  ",
            rr_indexed_data[index].ortho_cost_index);
    fprintf(fp, "base_cost: %g  ", rr_indexed_data[index].saved_base_cost);
    fprintf(fp, "saved_base_cost: %g\n",
            rr_indexed_data[index].saved_base_cost);

    fprintf(fp, "Seg_index: %d  ", rr_indexed_data[index].seg_index);
    fprintf(fp, "inv_length: %g\n", rr_indexed_data[index].inv_length);

    fprintf(fp, "T_linear: %g  ", rr_indexed_data[index].T_linear);
    fprintf(fp, "T_quadratic: %g  ", rr_indexed_data[index].T_quadratic);
    fprintf(fp, "C_load: %g\n", rr_indexed_data[index].C_load);
}

Here is the caller graph for this function: