rr_graph.c

用c＋＋写的用于FPGA设计中布图布线的工具源码

static void build_rr_xchan (int **rr_node_indices, enum e_route_type 
      route_type, struct s_ivec **tracks_to_clb_ipin, struct s_ivec *
      tracks_to_pads, int i, int j, int nodes_per_chan, enum 
      e_switch_block_type switch_block_type, int wire_to_ipin_switch, 
      t_seg_details *seg_details_x, t_seg_details *seg_details_y,
      int cost_index_offset) {

/* Loads up all the routing resource nodes in the x-directed channel      *
 * segments starting at (i,j).                                            */

 int itrack, num_edges, inode, istart, iend, length, seg_index;
 t_linked_edge *edge_list_head;

 for (itrack=0;itrack<nodes_per_chan;itrack++) {
    istart = get_closest_seg_start (seg_details_x, itrack, i, j);
    if (istart != i)
       continue;        /* Not the start of this segment. */

    iend = get_seg_end (seg_details_x, itrack, istart, j, nx);
    edge_list_head = NULL;

/* First count number of edges and put the edges in a linked list. */

    if (j == 0) {                   /* Between bottom pads and clbs.  */
       num_edges = get_xtrack_to_clb_ipin_edges (istart, iend, j, itrack, TOP, 
                   &edge_list_head, tracks_to_clb_ipin, nodes_per_chan, 
                   rr_node_indices, seg_details_x, wire_to_ipin_switch);

       num_edges += get_xtrack_to_pad_edges (istart, iend, j, j, itrack, 
                    &edge_list_head, tracks_to_pads, nodes_per_chan, 
                    rr_node_indices, seg_details_x, wire_to_ipin_switch);

       /* Only channels above exist. */

       num_edges += get_xtrack_to_ytracks (istart, iend, j, itrack, j+1,
                    &edge_list_head, nodes_per_chan, rr_node_indices, 
                    seg_details_x,  seg_details_y, switch_block_type); 
    }

    else if (j == ny) {           /* Between top clbs and pads. */
       num_edges = get_xtrack_to_clb_ipin_edges (istart, iend, j, itrack, 
                   BOTTOM, &edge_list_head, tracks_to_clb_ipin, nodes_per_chan, 
                   rr_node_indices, seg_details_x, wire_to_ipin_switch);

       num_edges += get_xtrack_to_pad_edges (istart, iend, j, j+1, itrack, 
                    &edge_list_head, tracks_to_pads, nodes_per_chan, 
                    rr_node_indices, seg_details_x, wire_to_ipin_switch);

       /* Only channels below exist. */

       num_edges += get_xtrack_to_ytracks (istart, iend, j, itrack, j,
                    &edge_list_head, nodes_per_chan, rr_node_indices, 
                    seg_details_x,  seg_details_y, switch_block_type); 
    }

    else {                          /* Between two rows of clbs. */
       num_edges = get_xtrack_to_clb_ipin_edges (istart, iend, j, itrack, 
                   BOTTOM, &edge_list_head, tracks_to_clb_ipin, nodes_per_chan, 
                   rr_node_indices, seg_details_x, wire_to_ipin_switch);

       num_edges += get_xtrack_to_clb_ipin_edges (istart, iend, j, itrack, 
                    TOP, &edge_list_head, tracks_to_clb_ipin, nodes_per_chan, 
                    rr_node_indices, seg_details_x, wire_to_ipin_switch);

       /* Channels above and below both exist. */

       num_edges += get_xtrack_to_ytracks (istart, iend, j, itrack, j+1,
                    &edge_list_head, nodes_per_chan, rr_node_indices, 
                    seg_details_x,  seg_details_y, switch_block_type); 

       num_edges += get_xtrack_to_ytracks (istart, iend, j, itrack, j,
                    &edge_list_head, nodes_per_chan, rr_node_indices, 
                    seg_details_x,  seg_details_y, switch_block_type); 

    }
    
    if (istart != 1) {   /* x-chan to left exists. */
       num_edges += get_xtrack_to_xtrack (istart, j, itrack, istart - 1, 
                    &edge_list_head, nodes_per_chan, rr_node_indices, 
                    seg_details_x, switch_block_type); 
    }

    if (iend != nx) {      /* x-chan to right exists. */
       num_edges += get_xtrack_to_xtrack (iend, j, itrack, iend + 1, 
                    &edge_list_head, nodes_per_chan, rr_node_indices, 
                    seg_details_x, switch_block_type); 
    }


    inode = get_rr_node_index (i, j, CHANX, itrack, nodes_per_chan, 
             rr_node_indices);

    alloc_and_load_edges_and_switches (inode, num_edges, edge_list_head);

/* Edge arrays have now been built up.  Do everything else.  */

    seg_index = seg_details_x[itrack].index;
    rr_node[inode].cost_index = cost_index_offset + seg_index;
    rr_node[inode].occ = 0;

    if (route_type == DETAILED) 
       rr_node[inode].capacity = 1;
    else                                    /* GLOBAL routing */
       rr_node[inode].capacity = chan_width_x[j];
 
    rr_node[inode].xlow = istart;
    rr_node[inode].xhigh = iend;
    rr_node[inode].ylow = j;
    rr_node[inode].yhigh = j;

    length = iend - istart + 1;
    rr_node[inode].R = length * seg_details_x[itrack].Rmetal;
    rr_node[inode].C = length * seg_details_y[itrack].Cmetal;

    rr_node[inode].ptc_num = itrack;
    rr_node[inode].type = CHANX;
 }
}


static void build_rr_ychan (int **rr_node_indices, enum e_route_type 
      route_type, struct s_ivec **tracks_to_clb_ipin, struct s_ivec *
      tracks_to_pads, int i, int j, int nodes_per_chan, enum 
      e_switch_block_type switch_block_type, int wire_to_ipin_switch,
      t_seg_details *seg_details_x, t_seg_details *seg_details_y,
      int cost_index_offset) {

/* Loads up all the routing resource nodes in the y-directed channel      *
 * segments starting at (i,j).                                            */

 int itrack, num_edges, inode, jstart, jend, length, seg_index;
 t_linked_edge *edge_list_head;

 for (itrack=0;itrack<nodes_per_chan;itrack++) {
    jstart = get_closest_seg_start (seg_details_y, itrack, j, i);
    if (jstart != j)
       continue;        /* Not the start of this segment. */

    jend = get_seg_end (seg_details_y, itrack, jstart, i, ny);
    edge_list_head = NULL;

/* First count number of edges and put the edges in a linked list. */

    if (i == 0) {                   /* Between leftmost pads and clbs.  */
       num_edges = get_ytrack_to_clb_ipin_edges (jstart, jend, i, itrack, 
                   RIGHT, &edge_list_head, tracks_to_clb_ipin, nodes_per_chan, 
                   rr_node_indices, seg_details_y, wire_to_ipin_switch);

       num_edges += get_ytrack_to_pad_edges (jstart, jend, i, i, itrack, 
                    &edge_list_head, tracks_to_pads, nodes_per_chan, 
                    rr_node_indices, seg_details_y, wire_to_ipin_switch);

       /* Only channel to right exists. */

       num_edges += get_ytrack_to_xtracks (jstart, jend, i, itrack, i+1, 
                    &edge_list_head, nodes_per_chan, rr_node_indices, 
                    seg_details_x, seg_details_y, switch_block_type);
    }

    else if (i == nx) {           /* Between rightmost clbs and pads. */
       num_edges = get_ytrack_to_clb_ipin_edges (jstart, jend, i, itrack, 
                   LEFT, &edge_list_head, tracks_to_clb_ipin, nodes_per_chan, 
                   rr_node_indices, seg_details_y, wire_to_ipin_switch);

       num_edges += get_ytrack_to_pad_edges (jstart, jend, i, i+1, itrack, 
                    &edge_list_head, tracks_to_pads, nodes_per_chan, 
                    rr_node_indices, seg_details_y, wire_to_ipin_switch);

       /* Only channel to left exists. */

       num_edges += get_ytrack_to_xtracks (jstart, jend, i, itrack, i, 
                    &edge_list_head, nodes_per_chan, rr_node_indices, 
                    seg_details_x, seg_details_y, switch_block_type);
    }

    else {                          /* Between two rows of clbs. */
       num_edges = get_ytrack_to_clb_ipin_edges (jstart, jend, i, itrack, 
                   LEFT, &edge_list_head, tracks_to_clb_ipin, nodes_per_chan, 
                   rr_node_indices, seg_details_y, wire_to_ipin_switch);

       num_edges += get_ytrack_to_clb_ipin_edges (jstart, jend, i, itrack, 
                    RIGHT, &edge_list_head, tracks_to_clb_ipin, nodes_per_chan, 
                    rr_node_indices, seg_details_y, wire_to_ipin_switch);

       /* Channels on both sides. */

       num_edges += get_ytrack_to_xtracks (jstart, jend, i, itrack, i+1, 
                    &edge_list_head, nodes_per_chan, rr_node_indices, 
                    seg_details_x, seg_details_y, switch_block_type);

       num_edges += get_ytrack_to_xtracks (jstart, jend, i, itrack, i,
                    &edge_list_head, nodes_per_chan, rr_node_indices, 
                    seg_details_x, seg_details_y, switch_block_type);
    }

    if (jstart != 1) {   /* y-chan below exists. */
       num_edges += get_ytrack_to_ytrack (i, jstart, itrack, jstart - 1, 
                    &edge_list_head, nodes_per_chan, rr_node_indices, 
                    seg_details_y, switch_block_type); 
    }

    if (jend != ny) {      /* y-chan above exists. */
       num_edges += get_ytrack_to_ytrack (i, jend, itrack, jend + 1, 
                    &edge_list_head, nodes_per_chan, rr_node_indices, 
                    seg_details_y, switch_block_type); 
    }


    inode = get_rr_node_index (i, j, CHANY, itrack, nodes_per_chan, 
             rr_node_indices);

    alloc_and_load_edges_and_switches (inode, num_edges, edge_list_head);

/* Edge arrays have now been built up.  Do everything else.  */

    seg_index = seg_details_y[itrack].index;
    rr_node[inode].cost_index = cost_index_offset + seg_index;
    rr_node[inode].occ = 0;

    if (route_type == DETAILED) 
       rr_node[inode].capacity = 1;
    else                                    /* GLOBAL routing */
       rr_node[inode].capacity = chan_width_y[i];
 
    rr_node[inode].xlow = i;
    rr_node[inode].xhigh = i;
    rr_node[inode].ylow = jstart;
    rr_node[inode].yhigh = jend;

    length = jend - jstart + 1;
    rr_node[inode].R = length * seg_details_y[itrack].Rmetal;
    rr_node[inode].C = length * seg_details_y[itrack].Cmetal;
 
    rr_node[inode].ptc_num = itrack;
    rr_node[inode].type = CHANY;
 }
}


void alloc_and_load_edges_and_switches (int inode, int num_edges, 
        t_linked_edge *edge_list_head) {
 
/* Sets up all the edge related information for rr_node inode (num_edges,  * 
 * the edges array and the switches array).  The edge_list_head points to  *
 * a list of the num_edges edges and switches to put in the arrays.  This  *
 * linked list is freed by this routine. This routine also resets the      *
 * rr_edge_done array for the next rr_node (i.e. set it so that no edges   *
 * are marked as having been seen before).                                 */
 
 t_linked_edge *list_ptr, *next_ptr;
 int i, to_node;


 rr_node[inode].num_edges = num_edges; 
 
 rr_node[inode].edges = (int *) my_chunk_malloc (num_edges * sizeof(int), 
       &rr_mem_chunk_list_head, &chunk_bytes_avail, &chunk_next_avail_mem); 
 
 rr_node[inode].switches = (short *) my_chunk_malloc (num_edges * 
       sizeof(short), &rr_mem_chunk_list_head, &chunk_bytes_avail, 
       &chunk_next_avail_mem); 
     
/* Load the edge and switch arrays, deallocate the linked list and reset   *
 * the rr_edge_done flags.                                                 */ 
  
 list_ptr = edge_list_head;
 i = 0;

 while (list_ptr != NULL) {
    to_node = list_ptr->edge;
    rr_node[inode].edges[i] = to_node;
    rr_edge_done[to_node] = FALSE;
    rr_node[inode].switches[i] = list_ptr->iswitch;
    next_ptr = list_ptr->next;

    /* Add to free list */
    free_linked_edge_soft (list_ptr, &free_edge_list_head); 

    list_ptr = next_ptr;
    i++;
 }
}
 

static int ***alloc_and_load_clb_pin_to_tracks (enum e_pin_type pin_type, 
          int nodes_per_chan, int Fc, boolean perturb_switch_pattern) {

/* Allocates and loads an array that contains a list of which tracks each  *
 * output or input pin of a clb should connect to on each side of the clb. *
 * The pin_type flag is either DRIVER or RECEIVER, and determines whether  *
 * information for output C blocks or input C blocks is generated.         *
 * Set Fc and nodes_per_chan to 1 if you're doing a global routing graph.  */


 int *num_dir;   /* [0..3] Number of *physical* pins on each clb side.      */
 int **dir_list; /* [0..3][0..pins_per_clb-1] list of pins of correct type  *
                  * on each side. Max possible space alloced for simplicity */

 int i, j, iside, ipin, iclass, num_phys_pins, pindex;
 int *num_done_per_dir, *pin_num_ordering, *side_ordering;
 int ***tracks_connected_to_pin;  /* [0..pins_per_clb-1][0..3][0..Fc-1] */
 float step_size;

/* NB:  This wastes some space.  Could set tracks_..._pin[ipin][iside] =   *
 * NULL if there is no pin on that side, or that pin is of the wrong type. *
 * Probably not enough memory to worry about, esp. as it's temporary.      *
 * If pin ipin on side iside does not exist or is of the wrong type,       *
 * tracks_connected_to_pin[ipin][iside][0] = OPEN.                         */

 tracks_connected_to_pin = (int ***) alloc_matrix3 (0, pins_per_clb-1, 0, 3,
                  0, Fc-1, sizeof(int));

 for (ipin=0;ipin<pins_per_clb;ipin++) 
    for (iside=0;iside<=3;iside++)
       tracks_connected_to_pin[ipin][iside][0] = OPEN;  /* Unconnected. */


 num_dir = (int *) my_calloc (4, sizeof(int));
 dir_list = (int **) alloc_matrix (0, 3, 0, pins_per_clb-1, sizeof(int));

/* Defensive coding.  Try to crash hard if I use an unset entry.  */
 
 for (i=0;i<4;i++) 
    for (j=0;j<pins_per_clb;j++) 
       dir_list[i][j] = -1;
 

 for (ipin=0;ipin<pins_per_clb;ipin++) {
    iclass = clb_pin_class[ipin];
    if (class_inf[iclass].type != pin_type) /* Doing either ipins OR opins */
       continue;
     
/* Pins connecting only to global resources get no switches -> keeps the    *
 * area model accurate.                                                     */

    if (is_global_clb_pin[ipin])   
       continue;
    
    for (iside=0;iside<=3;iside++) {
       if (pinloc[iside][ipin] == 1) {
          dir_list[iside][num_dir[iside]] = ipin;
          num_dir[iside]++;
       }
    }
 }

 num_phys_pins = 0;
 for (iside=0;iside<4;iside++) 
    num_phys_pins += num_dir[iside];  /* Num. physical output pins per clb */

 num_done_per_dir = (int *) my_calloc (4, sizeof(int));
 pin_num_ordering = (int *) my_malloc (num_phys_pins * sizeof(int));
 side_ordering = (int *) my_malloc (num_phys_pins * sizeof(int));

/* Connection block I use distributes pins evenly across the tracks      *
 * of ALL sides of the clb at once.  Ensures that each pin connects      *
 * to spaced out tracks in its connection block, and that the other      *
 * pins (potentially in other C blocks) connect to the remaining tracks  *
 * first.  Doesn't matter for large Fc, but should make a fairly         *
 * good low Fc block that leverages the fact that usually lots of pins   *
 * are logically equivalent.                                             */

 iside = -1;
 ipin = 0;
 pindex = 0;

 while (ipin < num_phys_pins) {
    iside = (iside + 1);
    if (iside > 3) {
       pindex++;
       iside = 0;
    }
    if (num_done_per_dir[iside] >= num_dir[iside])
       continue;
    pin_num_ordering[ipin] = dir_list[iside][pindex]; 
    side_ordering[ipin] = iside;
    num_done_per_dir[iside]++;
    ipin++;
 }


 step_size = (float) nodes_per_chan / (float) (Fc * num_phys_pins);
 if (step_size > 1.) {
    if (pin_type == DRIVER) 
       printf("Warning:  some tracks are never driven by clb outputs.\n");
    else 
       printf("Warning:  some tracks cannot reach any inputs.\n");
 }

 if (perturb_switch_pattern) {
    load_perturbed_switch_pattern (tracks_connected_to_pin, num_phys_pins, 
          pin_num_ordering, side_ordering, nodes_per_chan, Fc, step_size);

    check_all_tracks_reach_pins (tracks_connected_to_pin, nodes_per_chan, Fc, 
          RECEIVER);
 }
 else {
    load_uniform_switch_pattern (tracks_connected_to_pin, num_phys_pins, 
          pin_num_ordering, side_ordering, nodes_per_chan, Fc, step_size);
 }

/* Free all temporary storage. */

 free (num_dir);