rr_graph.c

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

 free_matrix (dir_list, 0, 3, 0, sizeof(int));
 free (num_done_per_dir);
 free (pin_num_ordering);
 free (side_ordering);

 return (tracks_connected_to_pin);
}


static void load_uniform_switch_pattern (int ***tracks_connected_to_pin, 
       int num_phys_pins, int *pin_num_ordering, int *side_ordering, 
       int nodes_per_chan, int Fc, float step_size) {

/* Loads the tracks_connected_to_pin array with an even distribution of     *
 * switches across the tracks for each pin.  For example, each pin connects *
 * to every 4.3rd track in a channel, with exactly which tracks a pin       *
 * connects to staggered from pin to pin.                                   */

 int i, j, ipin, iside, itrack;
 float f_track;


 for (i=0;i<num_phys_pins;i++) {
    ipin = pin_num_ordering[i];
    iside = side_ordering[i];
    for (j=0;j<Fc;j++) {
       f_track = i*step_size + j * (float) nodes_per_chan / (float) Fc;
       itrack = (int) f_track;

  /* In case of weird roundoff effects */
       itrack = min(itrack, nodes_per_chan-1);
       tracks_connected_to_pin[ipin][iside][j] = itrack;
    }
 }
}


static void load_perturbed_switch_pattern (int ***tracks_connected_to_pin, 
       int num_phys_pins, int *pin_num_ordering, int *side_ordering, 
       int nodes_per_chan, int Fc, float step_size) {

/* Loads the tracks_connected_to_pin array with an unevenly distributed     *
 * set of switches across the channel.  This is done for inputs when        *
 * Fc_input = Fc_output to avoid creating "pin domains" -- certain output   *
 * pins being able to talk only to certain input pins because their switch  *
 * patterns exactly line up.  Distribute Fc/2 + 1 switches over half the    *
 * channel and Fc/2 - 1 switches over the other half to make the switch     * 
 * pattern different from the uniform one of the outputs.  Also, have half  *
 * the pins put the "dense" part of their connections in the first half of  *
 * the channel and the other half put the "dense" part in the second half,  *
 * to make sure each track can connect to about the same number of ipins.   */

 int i, j, ipin, iside, itrack, ihalf, iconn;
 int Fc_dense, Fc_sparse, Fc_half[2];
 float f_track, spacing_dense, spacing_sparse, spacing[2];
 
 Fc_dense = Fc/2 + 1;
 Fc_sparse = Fc - Fc_dense;  /* Works for even or odd Fc */

 spacing_dense = (float) nodes_per_chan / (float) (2 * Fc_dense);
 spacing_sparse = (float) nodes_per_chan / (float) (2 * Fc_sparse);

 for (i=0;i<num_phys_pins;i++) {
    ipin = pin_num_ordering[i];
    iside = side_ordering[i];

    /* Flip every pin to balance switch density */

    spacing[i%2] = spacing_dense;
    Fc_half[i%2] = Fc_dense;
    spacing[(i+1)%2] = spacing_sparse;
    Fc_half[(i+1)%2] = Fc_sparse;

    f_track = i * step_size;    /* Start point.  Staggered from pin to pin */
    iconn = 0;

    for (ihalf=0;ihalf<2;ihalf++) {  /* For both dense and sparse halves. */

       for (j=0;j<Fc_half[ihalf];j++) {
          itrack = (int) f_track;

     /* Can occasionally get wraparound. */
          itrack = itrack%nodes_per_chan;
          tracks_connected_to_pin[ipin][iside][iconn] = itrack;

          f_track += spacing[ihalf];
          iconn++;
       }

    }
 }   /* End for all physical pins. */
}


static void check_all_tracks_reach_pins (int ***tracks_connected_to_pin,
         int nodes_per_chan, int Fc, enum e_pin_type ipin_or_opin) {

/* Checks that all tracks can be reached by some pin.   */

 int iconn, iside, itrack, ipin;
 int *num_conns_to_track;  /* [0..nodes_per_chan-1] */

 num_conns_to_track = (int *) my_calloc (nodes_per_chan, sizeof(int));
 
 for (ipin=0;ipin<pins_per_clb;ipin++) {
    for (iside=0;iside<=3;iside++) {
       if (tracks_connected_to_pin[ipin][iside][0] != OPEN) { /* Pin exists */
          for (iconn=0;iconn<Fc;iconn++) {
             itrack = tracks_connected_to_pin[ipin][iside][iconn];
             num_conns_to_track[itrack]++;
          }
       }
    }
 }

 for (itrack=0;itrack<nodes_per_chan;itrack++) {
    if (num_conns_to_track[itrack] <= 0) {
       printf ("Warning (check_all_tracks_reach_pins):  track %d does not \n"
               "\tconnect to any CLB ", itrack);

       if (ipin_or_opin == DRIVER)
          printf ("OPINs.\n");
       else
          printf ("IPINs.\n");
    }
 }
 
 free (num_conns_to_track);
}
 

static struct s_ivec **alloc_and_load_tracks_to_clb_ipin (int nodes_per_chan,
      int Fc, int ***clb_ipin_to_tracks) {

/* The routing graph will connect tracks to input pins on the clbs.   *
 * This routine converts the list of which tracks each ipin connects  *
 * to into a list of the ipins each track connects to.                */

 int ipin, iside, itrack, iconn, ioff, tr_side;

/* [0..nodes_per_chan-1][0..3].  For each track number it stores a vector  *
 * for each of the four sides.  x-directed channels will use the TOP and   *
 * BOTTOM vectors to figure out what clb input pins they connect to above  *
 * and below them, respectively, while y-directed channels use the LEFT    *
 * and RIGHT vectors.  Each vector contains an nelem field saying how many *
 * ipins it connects to.  The list[0..nelem-1] array then gives the pin    *
 * numbers.                                                                */

/* Note that a clb pin that connects to a channel on its RIGHT means that  *
 * that channel connects to a clb pin on its LEFT.  I have to convert the  *
 * sides so that the new structure lists the sides of pins from the        *
 * perspective of the track.                                               */

 struct s_ivec **tracks_to_clb_ipin;
 
 tracks_to_clb_ipin = (struct s_ivec **) alloc_matrix (0, nodes_per_chan-1, 0,
      3, sizeof(struct s_ivec));

 for (itrack=0;itrack<nodes_per_chan;itrack++)
    for (iside=0;iside<=3;iside++) 
       tracks_to_clb_ipin[itrack][iside].nelem = 0;

/* Counting pass.  */

 for (ipin=0;ipin<pins_per_clb;ipin++) {
    for (iside=0;iside<=3;iside++) {
       if (clb_ipin_to_tracks[ipin][iside][0] == OPEN) 
          continue;
       
       tr_side = track_side (iside);
       for (iconn=0;iconn<Fc;iconn++) {
          itrack = clb_ipin_to_tracks[ipin][iside][iconn];
          tracks_to_clb_ipin[itrack][tr_side].nelem++;
       }
    }
 }

/* Allocate space.  */

 for (itrack=0;itrack<nodes_per_chan;itrack++) {
    for (iside=0;iside<=3;iside++) {
       if (tracks_to_clb_ipin[itrack][iside].nelem != 0) {
          tracks_to_clb_ipin[itrack][iside].list = (int *) my_malloc (
                    tracks_to_clb_ipin[itrack][iside].nelem * sizeof (int));
          tracks_to_clb_ipin[itrack][iside].nelem = 0;
       }
       else {
          tracks_to_clb_ipin[itrack][iside].list = NULL;  /* Defensive code */
       }
    }
 } 

/* Loading pass. */

 for (ipin=0;ipin<pins_per_clb;ipin++) {
    for (iside=0;iside<=3;iside++) {
       if (clb_ipin_to_tracks[ipin][iside][0] == OPEN) 
          continue;
       
       tr_side = track_side (iside);
       for (iconn=0;iconn<Fc;iconn++) {
          itrack = clb_ipin_to_tracks[ipin][iside][iconn];
          ioff = tracks_to_clb_ipin[itrack][tr_side].nelem;
          tracks_to_clb_ipin[itrack][tr_side].list[ioff] = ipin;
          tracks_to_clb_ipin[itrack][tr_side].nelem++;
       }
    }
 }
 
 return (tracks_to_clb_ipin);
}


static int track_side (int clb_side) {

/* Converts a side from referring to the world from a clb's perspective *
 * to a channel's perspective.  That is, a connection from a clb to the *
 * track above (TOP) it, is to the clb below (BOTTOM) the track.        */
 
 switch (clb_side) {
 
 case TOP:
    return (BOTTOM);

 case BOTTOM:
    return (TOP);
 
 case LEFT:
    return (RIGHT);

 case RIGHT:
    return (LEFT);

 default:
    printf("Error:  unexpected clb_side (%d) in track_side.\n", clb_side);
    exit (1);
 }
}


static int **alloc_and_load_pads_to_tracks (int nodes_per_chan, int Fc_pad) {

/* Allocates and loads up a 2D array ([0..io_rat-1][0..Fc_pad-1]) where *
 * each entry gives a track number to which that pad connects if it is  *
 * an INPUT pad.  Code below should work for both GLOBAL and DETAILED.  */

 int **pads_to_tracks;
 float step_size;
 int ipad, iconn, itrack;

 pads_to_tracks = (int **) alloc_matrix (0, io_rat-1, 0, Fc_pad-1, sizeof(int));
 step_size = (float) nodes_per_chan / (float) (Fc_pad * io_rat);
 
 for (ipad=0;ipad<io_rat;ipad++) {
    for (iconn=0;iconn<Fc_pad;iconn++) {

       itrack = (int) (ipad * step_size + iconn * (float) nodes_per_chan / 
                 (float) Fc_pad);

/* Watch for weird round off effects.  */
       itrack = min(itrack, nodes_per_chan-1);
       pads_to_tracks[ipad][iconn] = itrack;
    }
 }

 return (pads_to_tracks);
}


static struct s_ivec *alloc_and_load_tracks_to_pads (int **pads_to_tracks, 
          int nodes_per_chan, int Fc_pad) {

/* Converts the list of tracks each IO pad connects to into a list of  *
 * pads each track should connect to.  Allocates and fills in an array *
 * of vectors [0..nodes_per_chan-1].  Each vector specifies the number *
 * of pads to which that track connects and gives a list of the pads.  */

 int itrack, ipad, i, iconn, ioff;
 struct s_ivec *tracks_to_pads;

 tracks_to_pads = (struct s_ivec *) my_malloc (nodes_per_chan * sizeof (
           struct s_ivec));
 
/* Counting pass. */

 for (i=0;i<nodes_per_chan;i++) 
    tracks_to_pads[i].nelem = 0;

 for (ipad=0;ipad<io_rat;ipad++) {
    for (iconn=0;iconn<Fc_pad;iconn++) {
       itrack = pads_to_tracks[ipad][iconn];
       tracks_to_pads[itrack].nelem++;
    }
 }

 for (i=0;i<nodes_per_chan;i++) {
    if (tracks_to_pads[i].nelem != 0) {
       tracks_to_pads[i].list = (int *) my_malloc (tracks_to_pads[i].nelem *
                        sizeof(int));
       tracks_to_pads[i].nelem = 0;
    }
    else {
       tracks_to_pads[i].list = NULL;  /* For safety only. */
    }
 }

/* Load pass. */

 for (ipad=0;ipad<io_rat;ipad++) {
    for (iconn=0;iconn<Fc_pad;iconn++) {
       itrack = pads_to_tracks[ipad][iconn];
       ioff = tracks_to_pads[itrack].nelem;
       tracks_to_pads[itrack].list[ioff] = ipad;
       tracks_to_pads[itrack].nelem++;
    }
 }

 return (tracks_to_pads);
}


void dump_rr_graph (char *file_name) {

/* A utility routine to dump the contents of the routing resource graph   *
 * (everything -- connectivity, occupancy, cost, etc.) into a file.  Used *
 * only for debugging.                                                    */

 int inode, index;
 FILE *fp;

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

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

 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");
 }
     
 fclose (fp);
}


void print_rr_node (FILE *fp, int inode) {

/* Prints all the data about node inode to file fp.                    */

 static char *name_type[] = {"SOURCE", "SINK", "IPIN", "OPIN", "CHANX",
       "CHANY"};
 t_rr_type rr_type;
 int iconn;

 rr_type = rr_node[inode].type;
 if (rr_node[inode].xlow == rr_node[inode].xhigh && rr_node[inode].ylow ==
            rr_node[inode].yhigh) {
    fprintf (fp, "Node: %d.  %s (%d, %d)  Ptc_num: %d\n", inode,
       name_type[rr_type], rr_node[inode].xlow, rr_node[inode].ylow,
       rr_node[inode].ptc_num);
 }
 else {
    fprintf (fp, "Node: %d.  %s (%d, %d) to (%d, %d)  Ptc_num: %d\n", inode,
       name_type[rr_type], rr_node[inode].xlow, rr_node[inode].ylow,
       rr_node[inode].xhigh, rr_node[inode].yhigh,
       rr_node[inode].ptc_num);
 }
 
 fprintf (fp, "%4d edge(s):", rr_node[inode].num_edges);
 
 for (iconn=0;iconn<rr_node[inode].num_edges;iconn++)
    fprintf (fp," %d", rr_node[inode].edges[iconn]);

 fprintf (fp,"\nSwitch types:");

 for (iconn=0;iconn<rr_node[inode].num_edges;iconn++)
    fprintf (fp, " %d", rr_node[inode].switches[iconn]);
     
 fprintf (fp, "\n");
 fprintf (fp, "Occ: %d  Capacity: %d.\n", rr_node[inode].occ,
     rr_node[inode].capacity);
 fprintf (fp,"R: %g  C: %g\n", rr_node[inode].R, rr_node[inode].C);
 fprintf (fp, "Cost_index: %d\n", rr_node[inode].cost_index);
}


void print_rr_indexed_data (FILE *fp, int index) {

/* Prints all the rr_indexed_data of index to file fp.   */

 fprintf (fp, "Index: %d\n", index);
 fprintf (fp, "ortho_cost_index: %d  base_cost: %g  saved_base_cost: %g\n",
               rr_indexed_data[index].ortho_cost_index, 
               rr_indexed_data[index].base_cost,
               rr_indexed_data[index].saved_base_cost);
 fprintf (fp, "Seg_index: %d  inv_length: %g\n", 
       rr_indexed_data[index].seg_index, rr_indexed_data[index].inv_length);
 fprintf (fp, "T_linear: %g  T_quadratic: %g  C_load: %g\n", 
       rr_indexed_data[index].T_linear, rr_indexed_data[index].T_quadratic,
       rr_indexed_data[index].C_load);
}