rr_graph2.c

fpga设计评估软件

#include <stdio.h>
#include "util.h"
#include "vpr_types.h"
#include "globals.h"
#include "rr_graph2.h"
#include "rr_graph_sbox.h"
#include <assert.h>


/* Variables below are the global variables shared only amongst the rr_graph *
 ************************************ routines. ******************************/

/* [0..num_rr_nodes-1].  TRUE if a node is already listed in the edges array *
 * that's being constructed.  This allows me to ensure that there are never  *
 *  duplicate edges (two edges between the same thing).                      */

boolean *rr_edge_done; 


/* Used to keep my own list of free linked integers, for speed reasons.     */

t_linked_edge *free_edge_list_head = NULL;



/*************************** Variables local to this module *****************/

/* Two arrays below give the rr_node_index of the channel segment at        *
 * (i,j,track) for fast index lookup.                                       */

static int ***chanx_rr_indices;  /* [1..nx][0..ny][0..nodes_per_chan-1] */
static int ***chany_rr_indices;  /* [0..nx][1..ny][0..nodes_per_chan-1] */
  


/************************** Subroutines local to this module ****************/

static int load_chanx_rr_indices (t_seg_details *seg_details_x, int 
           nodes_per_chan, int start_index, int i, int j); 

static int load_chany_rr_indices (t_seg_details *seg_details_y, int 
           nodes_per_chan, int start_index, int i, int j); 

static void get_switch_type (boolean is_from_sbox, boolean is_to_sbox, 
         short from_node_switch, short to_node_switch, short switch_types[2]); 


/******************** Subroutine definitions *******************************/

t_seg_details *alloc_and_load_seg_details (int nodes_per_chan, t_segment_inf 
              *segment_inf, int num_seg_types, int max_len) {
 
/* Allocates and loads the seg_details data structure.  Max_len gives the   *
 * maximum length of a segment (dimension of array).  The code below tries  *
 * to:                                                                      *
 * (1) stagger the start points of segments of the same type evenly;        *
 * (2) spread out the limited number of connection boxes or switch boxes    *
 *     evenly along the length of a segment, starting at the segment ends;  *
 * (3) stagger the connection and switch boxes on different long lines,     *
 *     as they will not be staggered by different segment start points.     */
 
 int tracks_left, i, next_track, ntracks, itrack, length, j, index;
 int wire_switch, opin_switch, num_cb, num_sb;
 float frac_left, start_step, sb_step, cb_step;
 float cb_off_step, sb_off_step;
 t_seg_details *seg_details;
 boolean longline;

 seg_details = (t_seg_details *) my_malloc (nodes_per_chan * sizeof 
                    (t_seg_details));

 tracks_left = nodes_per_chan;
 next_track = 0;
 frac_left = 1.;

 for (i=0;i<num_seg_types;i++) {
    if (frac_left <= 0.) {
       ntracks = 0;
    }
    else {
       ntracks = nint (segment_inf[i].frequency / frac_left * tracks_left);
    }
    frac_left -= segment_inf[i].frequency;
    tracks_left -= ntracks;

    if (ntracks == 0) 
       continue;      /* No tracks of this length.  Avoid divide by 0, etc. */

    longline = segment_inf[i].longline;
 
    if (!longline) {  
       length = min (segment_inf[i].length, max_len);
       start_step = (float) length / (float) ntracks;
    }
    else {                                 /* Is a long line. */
       length = max_len;
       start_step = 0.;
    }

    num_cb = nint (length * segment_inf[i].frac_cb);
    num_sb = nint ((length + 1.) * segment_inf[i].frac_sb);

/* Distribute connection boxes, with two endpoints covered first.           */

    if (!longline) {
       if (num_cb > 1) 
          cb_step = (float) (length-1) / (float) (num_cb - 1);
       else
          cb_step = 0.;
    }

/* Treat longlines differently.  Distribute C and S blocks as if the        *
 * longlines were circular (i.e., don't cover both endpoints first).  This  *
 * is important, as the rotation of the C and S blocks from line to line    *
 * would cause stupidities otherwise.                                       */

    else {   
       if (num_cb > 0)
          cb_step = (float) length / (float) num_cb;
       else
          cb_step = 0.;
    }


/* Now spead out switch boxes in the same way.     */

    if (!longline) {
       if (num_sb > 1) 
          sb_step = (float) length / (float) (num_sb - 1);
       else
          sb_step = 0.;
    }

    else {    /* Is a longline */
       if (num_sb > 0) 
          sb_step = (float) (length + 1) / (float) num_sb;
       else
          sb_step = 0;
    }

    if (!longline) {
       cb_off_step = 0.;
       sb_off_step = 0.;
    }

    else {                                 /* Is a long line. */
       cb_off_step = cb_step / (float) ntracks;
       sb_off_step = sb_step / (float) ntracks;
    }

    wire_switch = segment_inf[i].wire_switch;
    opin_switch = segment_inf[i].opin_switch;
 
    for (itrack=0;itrack<ntracks;itrack++) {
       seg_details[next_track].length = length;
       seg_details[next_track].longline = longline;
 
       seg_details[next_track].start = nint (itrack * start_step) % length + 1;
 
       seg_details[next_track].cb = (boolean *) my_calloc (length, 
                           sizeof (boolean));

       seg_details[next_track].sb = (boolean *) my_calloc ((length+1),
                            sizeof (boolean));

       for (j=0;j<num_cb;j++) {
          index = nint (j * cb_step + itrack * cb_off_step) % length;
          seg_details[next_track].cb[index] = TRUE;
       }    

       for (j=0;j<num_sb;j++) {
          index = nint (j * sb_step + itrack * sb_off_step) % (length + 1);
          seg_details[next_track].sb[index] = TRUE;
       }    
 
       seg_details[next_track].Rmetal = segment_inf[i].Rmetal;
       seg_details[next_track].Cmetal = segment_inf[i].Cmetal;

       seg_details[next_track].wire_switch = wire_switch;
       seg_details[next_track].opin_switch = opin_switch;

       seg_details[next_track].index = i;

       next_track++;
    }
 }   /* End for each segment type. */
 
 assert (tracks_left == 0);
 assert (next_track == nodes_per_chan);
 return (seg_details);
}
 
 
void free_seg_details (t_seg_details *seg_details, int nodes_per_chan) {
 
/* Frees all the memory allocated to an array of seg_details structures. */
 
 int i;
 
 for (i=0;i<nodes_per_chan;i++) {
    free (seg_details[i].cb);
    free (seg_details[i].sb);
 }
 free (seg_details);
}


void dump_seg_details (t_seg_details *seg_details, int nodes_per_chan, char 
           *fname) {

/* Dumps out an array of seg_details structures to file fname.  Used only   *
 * for debugging.                                                           */

 FILE *fp;
 int i, j;

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

 for (i=0;i<nodes_per_chan;i++) {
    fprintf (fp, "Track: %d.\n", i);
    fprintf (fp, "Length: %d,  Start: %d,  Long line: %d  wire_switch: %d  "
        "opin_switch: %d.\n", seg_details[i].length, seg_details[i].start, 
        seg_details[i].longline, seg_details[i].wire_switch, 
        seg_details[i].opin_switch);

    fprintf (fp, "Rmetal: %g  Cmetal: %g\n", seg_details[i].Rmetal, 
        seg_details[i].Cmetal);

    fprintf (fp, "cb list: ");
    for (j=0;j<seg_details[i].length;j++)
       fprintf (fp, "%d ", seg_details[i].cb[j]);

    fprintf (fp, "\nsb list: ");
    for (j=0;j<=seg_details[i].length;j++)
       fprintf (fp, "%d ", seg_details[i].sb[j]);

    fprintf (fp, "\n\n");
 } 

 fclose (fp);
}


int get_closest_seg_start (t_seg_details *seg_details, int itrack, int seg_num,
        int chan_num) {

/* Returns the segment number at which the segment this track lies on        *
 * started.                                                                  */

 int closest_start, length, start;

 if (seg_details[itrack].longline) {
    closest_start = 1;
 }
 else {
    length = seg_details[itrack].length;
    start = seg_details[itrack].start;

/* Start is guaranteed to be between 1 and length.  Hence adding length to *
 * the quantity in brackets below guarantees it will be nonnegative.       */

    closest_start = seg_num - (seg_num + chan_num - start + length) % length;
    closest_start = max (closest_start, 1);
 }

 return (closest_start);
}


int get_clb_opin_connections (int ***clb_opin_to_tracks, int ipin, int i, int 
        j, int Fc_output, t_seg_details *seg_details_x, t_seg_details 
        *seg_details_y, t_linked_edge **edge_list_ptr, int nodes_per_chan, int 
        **rr_node_indices) {

/* Returns the number of tracks to which clb opin #ipin at (i,j) connects.   *
 * Also stores the nodes to which this pin connects in the linked list       *
 * pointed to by *edge_list_ptr.                                             */

 int iside, num_conn, iconn, itrack, tr_j, tr_i, to_node;
 t_rr_type to_rr_type;
 boolean cbox_exists;
 t_linked_edge *edge_list_head;
 t_seg_details *seg_details;

 edge_list_head = *edge_list_ptr;
 num_conn = 0;

 for (iside=0;iside<=3;iside++) {  
    if (clb_opin_to_tracks[ipin][iside][0] != OPEN) {
 
/* This track may be at a different (i,j) location than the clb.  Tracks *
 * above and to the right of a clb are at the same (i,j) -- the channels *
 * on the other two sides "belong" to different clbs.                    */
 
       if (iside == BOTTOM)
          tr_j = j-1;
       else
          tr_j = j;
 
       if (iside == LEFT)
          tr_i = i-1;
       else
          tr_i = i;
 
       if (iside == LEFT || iside == RIGHT) {
          to_rr_type = CHANY;
          seg_details = seg_details_y;
       }
       else {
          to_rr_type = CHANX;
          seg_details = seg_details_x;
       }
                 
       for (iconn=0;iconn<Fc_output;iconn++) {
          itrack = clb_opin_to_tracks[ipin][iside][iconn]; 
 
          if (to_rr_type == CHANX) 
             cbox_exists = is_cbox (tr_i, tr_j, itrack, seg_details);
          else
             cbox_exists = is_cbox (tr_j, tr_i, itrack, seg_details);

          if (cbox_exists) {
             to_node = get_rr_node_index (tr_i, tr_j, to_rr_type, itrack,
                           nodes_per_chan, rr_node_indices);
             edge_list_head = insert_in_edge_list (edge_list_head, to_node,
                       seg_details[itrack].opin_switch, &free_edge_list_head);
             num_conn++;
          }
       }
           
    }
 }

 if (num_conn == 0) {
    printf ("Error:  clb output pin %d at (%d,%d) does not connect to any "
            "tracks.\n", ipin, i, j);
    exit (1);
 }

 *edge_list_ptr = edge_list_head;
 return (num_conn);
}


int get_pad_opin_connections (int **pads_to_tracks, int ipad, int i, int j, 
        int Fc_pad, t_seg_details *seg_details_x, t_seg_details *seg_details_y, 
        t_linked_edge **edge_list_ptr, int nodes_per_chan, int 
        **rr_node_indices) {

/* Returns the number of tracks to which the pad opin at (i,j) connects.     *
 * If edge_ptr isn't NULL, it also loads the edge array.                     */

 int chan_i, chan_j, iconn, itrack, num_conn, to_node;