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 (INP t_graph_type graph_type, INP int L_num_types, INP t_type_ptr types, INP int L_nx, INP int L_ny, INP struct s_grid_tile **L_grid, INP int chan_width, INP struct s_chan_width_dist *chan_capacity_inf, INP enum e_switch_block_type sb_type, INP int Fs, INP int num_seg_types, INP int num_switches, INP t_segment_inf *segment_inf, INP int global_route_switch, INP int delayless_switch, INP t_timing_inf timing_inf, INP int wire_to_ipin_switch, INP enum e_base_cost_type base_cost_type, INP t_direct_inf *directs, INP int num_directs, INP boolean ignore_Fc_0, OUTP int *Warnings)
void	free_rr_graph (void)
void	dump_rr_graph (INP const char *file_name)
void	print_rr_indexed_data (FILE *fp, int index)
void	load_net_rr_terminals (t_ivec ***L_rr_node_indices)
void	print_rr_node (FILE *fp, t_rr_node *L_rr_node, int inode)

Typedef Documentation

typedef enum e_graph_type t_graph_type

Definition at line 11 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 15 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 4 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	(	INP t_graph_type	graph_type,
		INP int	L_num_types,
		INP t_type_ptr	types,
		INP int	L_nx,
		INP int	L_ny,
		INP struct s_grid_tile **	L_grid,
		INP int	chan_width,
		INP struct s_chan_width_dist *	chan_capacity_inf,
		INP enum e_switch_block_type	sb_type,
		INP int	Fs,
		INP int	num_seg_types,
		INP int	num_switches,
		INP t_segment_inf *	segment_inf,
		INP int	global_route_switch,
		INP int	delayless_switch,
		INP t_timing_inf	timing_inf,
		INP int	wire_to_ipin_switch,
		INP enum e_base_cost_type	base_cost_type,
		INP t_direct_inf *	directs,
		INP int	num_directs,
		INP boolean	ignore_Fc_0,
		OUTP int *	Warnings
	)

Definition at line 192 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; /* [0..num_types-1][0..num_pins-1] */
    int **Fc_out = NULL; /* [0..num_types-1][0..num_pins-1] */

    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 *L_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] */
    t_clb_to_clb_directs *clb_to_clb_directs;

    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);

    clb_to_clb_directs = NULL;
    if(num_directs > 0) {
        clb_to_clb_directs = alloc_and_load_clb_to_clb_directs(directs, num_directs);
    }

    /* 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,
                std::max(L_nx, L_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;
        }
        if (getEchoEnabled() && isEchoFileEnabled(E_ECHO_SEG_DETAILS)) {
            dump_seg_details(seg_details, nodes_per_chan, 
                getEchoFileName(E_ECHO_SEG_DETAILS));
        } else
            ;
    }
    /* END SEG_DETAILS */

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

#ifdef VERBOSE
        for (i = 1; i < L_num_types; ++i) { /* Skip "<EMPTY>" */
            for (j = 0; j < type_descriptors[i].num_pins; ++j) { 
                if (type_descriptors[i].is_Fc_full_flex[j]) {
                    vpr_printf(TIO_MESSAGE_INFO, "Fc Actual Values: type = %s, Fc_out = full, Fc_in = %d.\n",
                            type_descriptors[i].name, Fc_in[i][j]);
                }
                else {
                    vpr_printf(TIO_MESSAGE_INFO, "Fc Actual Values: type = %s, Fc_out = %d, Fc_in = %d.\n",
                            type_descriptors[i].name, Fc_out[i][j], Fc_in[i][j]);
                }
            }
        }
#endif /* VERBOSE */
    }

    perturb_ipins = alloc_and_load_perturb_ipins(nodes_per_chan, L_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, L_nx, L_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);
    L_rr_edge_done = (boolean *) my_malloc(sizeof(boolean) * num_rr_nodes);
    memset(L_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, L_ny, 0, L_nx, sizeof(int));
        Fc_yofs = (int **) alloc_matrix(0, L_nx, 0, L_ny, sizeof(int));
        for (i = 0; i <= L_nx; ++i) {
            for (j = 0; j <= L_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(L_nx, L_ny,
                nodes_per_chan);
        for (i = 0; i <= L_nx; i++) {
            for (j = 0; j <= L_ny; j++) {
                load_sblock_pattern_lookup(i, j, nodes_per_chan, seg_details,
                        Fs, sb_type, unidir_sb_pattern);
            }
        }
    }
    /* END SB LOOKUP */

    /* START IPINP MAP */
    /* Create ipin map lookups */
    ipin_to_track_map = (int *****) my_malloc(sizeof(int ****) * L_num_types);
    track_to_ipin_lookup = (struct s_ivec ****) my_malloc(
            sizeof(struct s_ivec ***) * L_num_types);
    for (i = 0; i < L_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 IPINP MAP */

    /* START OPINP MAP */
    /* Create opin map lookups */
    if (BI_DIRECTIONAL == directionality) {
        opin_to_track_map = (int *****) my_malloc(
                sizeof(int ****) * L_num_types);
        for (i = 0; i < L_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 OPINP 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,
            L_rr_edge_done, track_to_ipin_lookup, opin_to_track_map,
            switch_block_conn, L_grid, L_nx, L_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, directs, num_directs, clb_to_clb_directs);

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

    /* Update rr_nodes capacities if global routing */
    if (graph_type == GRAPH_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);
    if (getEchoEnabled() && isEchoFileEnabled(E_ECHO_RR_GRAPH)) {
        dump_rr_graph(getEchoFileName(E_ECHO_RR_GRAPH));
    } else
        ;

    check_rr_graph(graph_type, types, L_nx, L_ny, 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,
            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_matrix(Fc_in,0, L_num_types, 0, sizeof(int));
        Fc_in = NULL;
    }
    if (Fc_out) {
        free_matrix(Fc_out,0, L_num_types, 0, sizeof(int));
        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 (L_rr_edge_done) {
        free(L_rr_edge_done);
        L_rr_edge_done = NULL;
    }
    if (Fc_xofs) {
        free_matrix(Fc_xofs, 0, L_ny, 0, sizeof(int));
        Fc_xofs = NULL;
    }
    if (Fc_yofs) {
        free_matrix(Fc_yofs, 0, L_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 < L_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);
    free_type_track_to_ipin_map(track_to_ipin_lookup, types, nodes_per_chan);
    if(clb_to_clb_directs != NULL) {
        free(clb_to_clb_directs);
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

void dump_rr_graph

(

INP const char *

file_name

)

Definition at line 1788 of file rr_graph.c.

                                              {

    int inode;
    FILE *fp;

    fp = my_fopen(file_name, "w", 0);

    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 798 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_ch.chunk_ptr_head == NULL) /* Nothing to free. */
        return;

    free_chunk_memory(&rr_mem_ch); /* Frees ALL "chunked" data */

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

    if(net_rr_terminals != NULL) {
        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;
    num_rr_nodes = 0;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void load_net_rr_terminals

(

t_ivec ***

L_rr_node_indices

)

Definition at line 855 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, node_block_pin, iclass;
    t_type_ptr type;

    for (inet = 0; inet < num_nets; inet++) {
        for (ipin = 0; ipin <= clb_net[inet].num_sinks; ipin++) {
            iblk = clb_net[inet].node_block[ipin];
            i = block[iblk].x;
            j = block[iblk].y;
            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 = clb_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, L_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 1868 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:

void print_rr_node	(	FILE *	fp,
		t_rr_node *	L_rr_node,
		int	inode
	)

Definition at line 1814 of file rr_graph.c.

                                                                {

    static const char *name_type[] = { "SOURCE", "SINK", "IPIN", "OPIN",
            "CHANX", "CHANY", "INTRA_CLUSTER_EDGE" };
    static const char *direction_name[] = { "OPEN", "INC_DIRECTION",
            "DEC_DIRECTION", "BI_DIRECTION" };
    static const char *drivers_name[] = { "OPEN", "MULTI_BUFFER", "SINGLE" };

    t_rr_type rr_type;
    int iconn;

    rr_type = L_rr_node[inode].type;

    /* Make sure we don't overrun const arrays */
    assert((int)rr_type < (int)(sizeof(name_type) / sizeof(char *)));
    assert(
            (L_rr_node[inode].direction + 1) < (int)(sizeof(direction_name) / sizeof(char *)));
    assert(
            (L_rr_node[inode].drivers + 1) < (int)(sizeof(drivers_name) / sizeof(char *)));

    fprintf(fp, "Node: %d %s ", inode, name_type[rr_type]);
    if ((L_rr_node[inode].xlow == L_rr_node[inode].xhigh)
            && (L_rr_node[inode].ylow == L_rr_node[inode].yhigh)) {
        fprintf(fp, "(%d, %d) ", L_rr_node[inode].xlow, L_rr_node[inode].ylow);
    } else {
        fprintf(fp, "(%d, %d) to (%d, %d) ", L_rr_node[inode].xlow,
                L_rr_node[inode].ylow, L_rr_node[inode].xhigh,
                L_rr_node[inode].yhigh);
    }
    fprintf(fp, "Ptc_num: %d ", L_rr_node[inode].ptc_num);
    fprintf(fp, "Direction: %s ",
            direction_name[L_rr_node[inode].direction + 1]);
    fprintf(fp, "Drivers: %s ", drivers_name[L_rr_node[inode].drivers + 1]);
    fprintf(fp, "\n");

    fprintf(fp, "%d edge(s):", L_rr_node[inode].num_edges);
    for (iconn = 0; iconn < L_rr_node[inode].num_edges; iconn++)
        fprintf(fp, " %d", L_rr_node[inode].edges[iconn]);
    fprintf(fp, "\n");

    fprintf(fp, "Switch types:");
    for (iconn = 0; iconn < L_rr_node[inode].num_edges; iconn++)
        fprintf(fp, " %d", L_rr_node[inode].switches[iconn]);
    fprintf(fp, "\n");

    fprintf(fp, "Occ: %d  Capacity: %d\n", L_rr_node[inode].occ,
            L_rr_node[inode].capacity);
    if (rr_type != INTRA_CLUSTER_EDGE) {
        fprintf(fp, "R: %g  C: %g\n", L_rr_node[inode].R, L_rr_node[inode].C);
    }
    fprintf(fp, "Cost_index: %d\n", L_rr_node[inode].cost_index);
}

Here is the caller graph for this function: