rr_graph.c

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

 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);
 free (rr_node);
 free (rr_indexed_data);
 free_matrix (rr_clb_source, 0, num_blocks-1, 0, sizeof(int));

 net_rr_terminals = NULL;
 rr_node = NULL;
 rr_indexed_data = NULL;
 rr_clb_source = NULL;
}


static void alloc_net_rr_terminals (void) {

  int inet;

 net_rr_terminals = (int **) my_malloc (num_nets * sizeof(int *));

 for (inet=0;inet<num_nets;inet++) {
    net_rr_terminals[inet] = (int *) my_chunk_malloc (net[inet].num_pins * 
              sizeof (int), &rr_mem_chunk_list_head, &chunk_bytes_avail,
	     &chunk_next_avail_mem);
 }

}


void load_net_rr_terminals (int **rr_node_indices, 
        int nodes_per_chan) {

/* 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, blk_pin, iclass;
 t_rr_type rr_type;


 for (inet=0;inet<num_nets;inet++) {
    
    rr_type = SOURCE;     /* First pin only */
    for (ipin=0;ipin<net[inet].num_pins;ipin++) {
       iblk = net[inet].blocks[ipin];
       i = block[iblk].x;
       j = block[iblk].y;

       if (clb[i][j].type == CLB) {
          blk_pin = net[inet].blk_pin[ipin];
          iclass = clb_pin_class[blk_pin];
       }
       else {
          iclass = which_io_block (iblk);
       }

       inode = get_rr_node_index (i, j, rr_type, iclass, nodes_per_chan, 
                  rr_node_indices);
       net_rr_terminals[inet][ipin] = inode;
 
       rr_type = SINK;    /* All pins after first are SINKs. */
    }
 }
}

static void alloc_and_load_rr_clb_source (int **rr_node_indices,
          int nodes_per_chan) {

/* Saves the rr_node corresponding to each SOURCE and SINK in each CLB      *
 * in the FPGA.  Currently only the SOURCE rr_node values are used, and     *
 * they are used only to reserve pins for locally used OPINs in the router. *
 * [0..num_blocks-1][0..num_class-1].  The values for blocks that are pads  *
 * are NOT valid.                                                           */

 int iblk, i, j, iclass, inode;
 t_rr_type rr_type;

 rr_clb_source = (int **) alloc_matrix (0, num_blocks-1, 0, num_class-1,
                  sizeof(int));

 for (iblk=0;iblk<num_blocks;iblk++) {
    for (iclass=0;iclass<num_class;iclass++) {
       if (block[iblk].type == CLB) {
          i = block[iblk].x;
          j = block[iblk].y;

          if (class_inf[iclass].type == DRIVER)
             rr_type = SOURCE;
          else
             rr_type = SINK;
 
          inode = get_rr_node_index (i, j, rr_type, iclass, nodes_per_chan,
               rr_node_indices);
          rr_clb_source[iblk][iclass] = inode;
       }
       else {  /* IO Pad; don't need any data so set to OPEN (invalid) */
          rr_clb_source[iblk][iclass] = OPEN;
       }
    }
 }
}



static int which_io_block (int iblk) {

/* Returns the subblock (pad) number at which this block was placed.  iblk *
 * must be an IO block.                                                    */

 int i, j, ipad, ifound, test_blk;

 ifound = -1;
 i = block[iblk].x;
 j = block[iblk].y;
 

 if (block[iblk].type != INPAD && block[iblk].type != OUTPAD) {
    printf ("Error in which_io_block:  block %d is not an IO block.\n", iblk);
    exit (1);
 }

 for (ipad=0;ipad<clb[i][j].occ;ipad++) {
    test_blk = clb[i][j].u.io_blocks[ipad];
    if (test_blk == iblk) {
       ifound = ipad;
       break;
    }
 }

 if (ifound < 0) {
    printf ("Error in which_io_block:  block %d not found in clb array.\n",
             iblk);
    exit (1);
 }

 return (ifound);
}


static void build_rr_clb (int **rr_node_indices, int Fc_output, int ***
       clb_opin_to_tracks, int nodes_per_chan, int i, int j, int 
       delayless_switch, t_seg_details *seg_details_x, t_seg_details 
       *seg_details_y) {

/* Load up the rr_node structures for the clb at location (i,j).  I both  *
 * fill in fields that shouldn't change during the entire routing and     *
 * initialize fields that will change to the proper starting value.       */

 int ipin, iclass, inode, pin_num, to_node, num_edges;
 t_linked_edge *edge_list_head;

/* SOURCES and SINKS first.   */

 for (iclass=0;iclass<num_class;iclass++) {
    if (class_inf[iclass].type == DRIVER) {    /* SOURCE */
       inode = get_rr_node_index (i, j, SOURCE, iclass, nodes_per_chan,
                 rr_node_indices);

       num_edges = class_inf[iclass].num_pins;
       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);

       for (ipin=0;ipin<class_inf[iclass].num_pins;ipin++) {
          pin_num = class_inf[iclass].pinlist[ipin];
          to_node = get_rr_node_index (i, j, OPIN, pin_num, nodes_per_chan,
                  rr_node_indices);
          rr_node[inode].edges[ipin] = to_node;
          rr_node[inode].switches[ipin] = delayless_switch;
       }

       rr_node[inode].capacity = class_inf[iclass].num_pins;
       rr_node[inode].cost_index = SOURCE_COST_INDEX;
       rr_node[inode].type = SOURCE;
    }

    else {    /* SINK */
       inode = get_rr_node_index (i, j, SINK, iclass, nodes_per_chan,
                 rr_node_indices);

/* Note:  To allow route throughs through clbs, change the lines below to  *
 * make an edge from the input SINK to the output SOURCE.  Do for just the *
 * special case of INPUTS = class 0 and OUTPUTS = class 1 and see what it  *
 * leads to.  If route throughs are allowed, you may want to increase the  *
 * base cost of OPINs and/or SOURCES so they aren't used excessively.      */

       rr_node[inode].num_edges = 0; 
       rr_node[inode].edges = NULL;
       rr_node[inode].switches = NULL;
       rr_node[inode].capacity = class_inf[iclass].num_pins;
       rr_node[inode].cost_index = SINK_COST_INDEX;
       rr_node[inode].type = SINK;
    }

/* Things common to both SOURCEs and SINKs.   */

    rr_node[inode].occ = 0;

    rr_node[inode].xlow = i;
    rr_node[inode].xhigh = i;
    rr_node[inode].ylow = j;
    rr_node[inode].yhigh = j;
    rr_node[inode].R = 0;
    rr_node[inode].C = 0;

    rr_node[inode].ptc_num = iclass;
 }

/* Now do the pins.  */

 for (ipin=0;ipin<pins_per_clb;ipin++) {
    iclass = clb_pin_class[ipin];
    if (class_inf[iclass].type == DRIVER) {  /* OPIN */
       inode = get_rr_node_index (i, j, OPIN, ipin, nodes_per_chan,
                 rr_node_indices);

       edge_list_head = NULL;
       num_edges = get_clb_opin_connections (clb_opin_to_tracks, ipin, i, j,
                   Fc_output, seg_details_x, seg_details_y, &edge_list_head, 
                   nodes_per_chan, rr_node_indices);

       alloc_and_load_edges_and_switches (inode, num_edges, edge_list_head);

       rr_node[inode].cost_index = OPIN_COST_INDEX;
       rr_node[inode].type = OPIN;
    }
    else {                                   /* IPIN */
       inode = get_rr_node_index (i, j, IPIN, ipin, nodes_per_chan,
                 rr_node_indices);

       rr_node[inode].num_edges = 1;
       rr_node[inode].edges = (int *) my_chunk_malloc (sizeof(int), 
          &rr_mem_chunk_list_head, &chunk_bytes_avail, &chunk_next_avail_mem);

       rr_node[inode].switches = (short *) my_chunk_malloc (sizeof(short), 
          &rr_mem_chunk_list_head, &chunk_bytes_avail, &chunk_next_avail_mem);

       to_node = get_rr_node_index (i, j, SINK, iclass, nodes_per_chan,
                  rr_node_indices);
       rr_node[inode].edges[0] = to_node;
       rr_node[inode].switches[0] = delayless_switch;

       rr_node[inode].cost_index = IPIN_COST_INDEX;
       rr_node[inode].type = IPIN;
    }

/* Things that are common to both OPINs and IPINs.  */

    rr_node[inode].capacity = 1;
    rr_node[inode].occ = 0;
 
    rr_node[inode].xlow = i;
    rr_node[inode].xhigh = i;
    rr_node[inode].ylow = j;
    rr_node[inode].yhigh = j;
    rr_node[inode].C = 0;
    rr_node[inode].R = 0;
 
    rr_node[inode].ptc_num = ipin;
 }
}


static void build_rr_pads (int **rr_node_indices, int Fc_pad, int 
        **pads_to_tracks, int nodes_per_chan, int i, int j, int 
        delayless_switch, t_seg_details *seg_details_x, t_seg_details 
        *seg_details_y) {

/* Load up the rr_node structures for the pads at location (i,j).  I both *
 * fill in fields that shouldn't change during the entire routing and     *
 * initialize fields that will change to the proper starting value.       *
 * Empty pad locations have their type set to EMPTY.                      */

 int s_node, p_node, ipad, iloop;
 int inode, num_edges;
 t_linked_edge *edge_list_head;


/* Each pad contains both a SOURCE + OPIN, and a SINK + IPIN, since each  *
 * pad is bidirectional.  The fact that it will only be used as either an *
 * input or an output makes no difference.                                */

 for (ipad=0;ipad<io_rat;ipad++) {   /* For each pad at this (i,j) */

   /* Do SOURCE first.   */

    s_node = get_rr_node_index (i, j, SOURCE, ipad, nodes_per_chan,
             rr_node_indices);
       
    rr_node[s_node].num_edges = 1;
    p_node = get_rr_node_index (i, j, OPIN, ipad, nodes_per_chan, 
              rr_node_indices);

    rr_node[s_node].edges = (int *) my_chunk_malloc (sizeof(int), 
          &rr_mem_chunk_list_head, &chunk_bytes_avail, &chunk_next_avail_mem);
    rr_node[s_node].edges[0] = p_node;

    rr_node[s_node].switches = (short *) my_chunk_malloc (sizeof(short),
          &rr_mem_chunk_list_head, &chunk_bytes_avail, &chunk_next_avail_mem);
    rr_node[s_node].switches[0] = delayless_switch;
    
    rr_node[s_node].cost_index = SOURCE_COST_INDEX;
    rr_node[s_node].type = SOURCE;


   /* Now do OPIN */
       
    edge_list_head = NULL;
    num_edges = get_pad_opin_connections (pads_to_tracks, ipad, i, j, 
              Fc_pad, seg_details_x, seg_details_y, &edge_list_head, 
              nodes_per_chan, rr_node_indices);

    alloc_and_load_edges_and_switches (p_node, num_edges, edge_list_head);
 
    rr_node[p_node].cost_index = OPIN_COST_INDEX;
    rr_node[p_node].type = OPIN;

   /* Code common to both SOURCE and OPIN. */

    inode = s_node;
    for (iloop=1;iloop<=2;iloop++) {    /* for both SOURCE or SINK and pin */
       rr_node[inode].occ = 0;
       rr_node[inode].capacity = 1;

       rr_node[inode].xlow = i;
       rr_node[inode].xhigh = i;
       rr_node[inode].ylow = j;
       rr_node[inode].yhigh = j;
       rr_node[inode].R = 0.;
       rr_node[inode].C = 0.;

       rr_node[inode].ptc_num = ipad;

       inode = p_node;
    }


   /* Now do SINK */

    s_node = get_rr_node_index (i, j, SINK, ipad, nodes_per_chan,
             rr_node_indices);

    rr_node[s_node].num_edges = 0;
    rr_node[s_node].edges = NULL;
    rr_node[s_node].switches = NULL;

    rr_node[s_node].cost_index = SINK_COST_INDEX;
    rr_node[s_node].type = SINK;


    /* Now do IPIN */
    
    p_node = get_rr_node_index (i, j, IPIN, ipad, nodes_per_chan,
             rr_node_indices);

    rr_node[p_node].num_edges = 1;
    rr_node[p_node].edges = (int *) my_chunk_malloc (sizeof(int), 
          &rr_mem_chunk_list_head, &chunk_bytes_avail, &chunk_next_avail_mem);
    rr_node[p_node].edges[0] = s_node;

    rr_node[p_node].switches = (short *) my_chunk_malloc (sizeof(short), 
          &rr_mem_chunk_list_head, &chunk_bytes_avail, &chunk_next_avail_mem);
    rr_node[p_node].switches[0] = delayless_switch;

    rr_node[p_node].cost_index = IPIN_COST_INDEX;
    rr_node[p_node].type = IPIN;

  /* Code common to both SINK and IPIN. */

    inode = s_node;
    for (iloop=1;iloop<=2;iloop++) {    /* for both SOURCE or SINK and pin */
       rr_node[inode].occ = 0;
       rr_node[inode].capacity = 1;

       rr_node[inode].xlow = i;
       rr_node[inode].xhigh = i;
       rr_node[inode].ylow = j;
       rr_node[inode].yhigh = j;
       rr_node[inode].R = 0.;
       rr_node[inode].C = 0.;

       rr_node[inode].ptc_num = ipad;

       inode = p_node;
    }

 }   /* End for each pad. */
}