route_common.c

fpga设计评估软件

#include <math.h>
#include <stdio.h>
#include "util.h"
#include "vpr_types.h"
#include "globals.h" 
#include "route_export.h"
#include "route_common.h"
#include "route_tree_timing.h"
#include "route_timing.h"
#include "route_breadth_first.h"
#include "place_and_route.h"
#include "rr_graph.h"

/***************** Variables shared only by route modules *******************/

t_rr_node_route_inf *rr_node_route_inf = NULL;       /* [0..num_rr_nodes-1] */

struct s_bb *route_bb = NULL; /* [0..num_nets-1]. Limits area in which each  */
                              /* net must be routed.                         */


/**************** Static variables local to route_common.c ******************/

static struct s_heap **heap;  /* Indexed from [1..heap_size] */
static int heap_size;   /* Number of slots in the heap array */
static int heap_tail;   /* Index of first unused slot in the heap array */

/* For managing my own list of currently free heap data structures.     */
static struct s_heap *heap_free_head = NULL; 

/* For managing my own list of currently free trace data structures.    */
static struct s_trace *trace_free_head = NULL;

#ifdef DEBUG
 static int num_trace_allocated = 0;   /* To watch for memory leaks. */
 static int num_heap_allocated = 0;
 static int num_linked_f_pointer_allocated = 0;
#endif

static struct s_linked_f_pointer *rr_modified_head = NULL;
static struct s_linked_f_pointer *linked_f_pointer_free_head = NULL;



/*  The numbering relation between the channels and clbs is:               *
 *                                                                         *
 *  |   IO    | chan_   |   CLB      | chan_   |   CLB     |               *
 *  |clb[0][2]| y[0][2] | clb[1][2]  | y[1][2] |  clb[2][2]|               *
 *  +-------- +         +------------+         +-----------+               *
 *                                                           } capacity in *
 *   No channel          chan_x[1][1]          chan_x[2][1]  } chan_width  *
 *                                                           } _x[1]       *
 *  +---------+         +------------+         +-----------+               *
 *  |         | chan_   |            | chan_   |           |               *
 *  |  IO     | y[0][1] |    CLB     | y[1][1] |   CLB     |               *
 *  |clb[0][1]|         |  clb[1][1] |         | clb[2][1] |               *
 *  |         |         |            |         |           |               *
 *  +---------+         +------------+         +-----------+               *
 *                                                           } capacity in *
 *                      chan_x[1][0]           chan_x[2][0]  } chan_width  * 
 *                                                           } _x[0]       *
 *                      +------------+         +-----------+               *
 *              No      |            | No      |           |               *
 *            Channel   |    IO      | Channel |   IO      |               *
 *                      |  clb[1][0] |         | clb[2][0] |               *
 *                      |            |         |           |               *
 *                      +------------+         +-----------+               *
 *                                                                         *
 *             {=======}              {=======}                            *
 *            Capacity in            Capacity in                           *
 *          chan_width_y[0]        chan_width_y[1]                         *
 *                                                                         */


/******************** Subroutines local to route_common.c *******************/

static void free_trace_data (struct s_trace *tptr);
static void load_route_bb (int bb_factor); 

static struct s_trace *alloc_trace_data (void); 
static void add_to_heap (struct s_heap *hptr);
static struct s_heap *alloc_heap_data (void);
static struct s_linked_f_pointer *alloc_linked_f_pointer (void);

static t_ivec **alloc_and_load_clb_opins_used_locally (t_subblock_data 
        subblock_data);
static void adjust_one_rr_occ_and_pcost (int inode, int add_or_sub, float
            pres_fac);



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

void save_routing (struct s_trace **best_routing, t_ivec 
        **clb_opins_used_locally, t_ivec **saved_clb_opins_used_locally) {

/* This routing frees any routing currently held in best routing,       *
 * then copies over the current routing (held in trace_head), and       *
 * finally sets trace_head and trace_tail to all NULLs so that the      *
 * connection to the saved routing is broken.  This is necessary so     *
 * that the next iteration of the router does not free the saved        *
 * routing elements.  Also saves any data about locally used clb_opins, *
 * since this is also part of the routing.                              */

 int inet, iblk, iclass, ipin, num_local_opins;
 struct s_trace *tptr, *tempptr;

 for (inet=0;inet<num_nets;inet++) {

/* Free any previously saved routing.  It is no longer best. */
    tptr = best_routing[inet];
    while (tptr != NULL) {
       tempptr = tptr->next;
       free_trace_data (tptr);
       tptr = tempptr;
    }

/* Save a pointer to the current routing in best_routing. */
    best_routing[inet] = trace_head[inet];

/* Set the current (working) routing to NULL so the current trace       *
 * elements won't be reused by the memory allocator.                    */

    trace_head[inet] = NULL;
    trace_tail[inet] = NULL;
 }

/* Save which OPINs are locally used.                           */
 
 for (iblk=0;iblk<num_blocks;iblk++) {
    for (iclass=0;iclass<num_class;iclass++) {
       num_local_opins = clb_opins_used_locally[iblk][iclass].nelem;
       for (ipin=0;ipin<num_local_opins;ipin++) {
          saved_clb_opins_used_locally[iblk][iclass].list[ipin] = 
              clb_opins_used_locally[iblk][iclass].list[ipin];
       }
    }

 }
}


void restore_routing (struct s_trace **best_routing, t_ivec 
       **clb_opins_used_locally, t_ivec **saved_clb_opins_used_locally) {

/* Deallocates any current routing in trace_head, and replaces it with    *
 * the routing in best_routing.  Best_routing is set to NULL to show that *
 * it no longer points to a valid routing.  NOTE:  trace_tail is not      *
 * restored -- it is set to all NULLs since it is only used in            *
 * update_traceback.  If you need trace_tail restored, modify this        *
 * routine.  Also restores the locally used opin data.                    */

 int inet, iblk, ipin, iclass, num_local_opins;

 for (inet=0;inet<num_nets;inet++) {

   /* Free any current routing. */
    free_traceback (inet);

  /* Set the current routing to the saved one. */
   trace_head[inet] = best_routing[inet];
   best_routing[inet] = NULL;          /* No stored routing. */
 }

/* Save which OPINs are locally used.                           */

 for (iblk=0;iblk<num_blocks;iblk++) {
    for (iclass=0;iclass<num_class;iclass++) {
       num_local_opins = clb_opins_used_locally[iblk][iclass].nelem;
       for (ipin=0;ipin<num_local_opins;ipin++) {
          clb_opins_used_locally[iblk][iclass].list[ipin] =  
              saved_clb_opins_used_locally[iblk][iclass].list[ipin];
       } 
    }

 }
}


void get_serial_num (void) {

/* This routine finds a "magic cookie" for the routing and prints it.    *
 * Use this number as a routing serial number to ensure that programming *
 * changes do not break the router.                                      */

 int inet, serial_num, inode;
 struct s_trace *tptr;
 serial_num = 0;

 for (inet=0;inet<num_nets;inet++) {

/* Global nets will have null trace_heads (never routed) so they *
 * are not included in the serial number calculation.            */

    tptr = trace_head[inet];
    while (tptr != NULL) {
       inode = tptr->index;
       serial_num += (inet+1) * (rr_node[inode].xlow * (nx+1) - 
                      rr_node[inode].yhigh);

       serial_num -= rr_node[inode].ptc_num * (inet+1) * 10;

       serial_num -= rr_node[inode].type * (inet+1) * 100;
       serial_num %= 2000000000;  /* Prevent overflow */
       tptr = tptr->next;
    }
 }
 printf ("Serial number (magic cookie) for the routing is: %d\n",
    serial_num);
}


boolean try_route (int width_fac, struct s_router_opts router_opts, struct
        s_det_routing_arch det_routing_arch, t_segment_inf *segment_inf, 
        t_timing_inf timing_inf, float **net_slack, float **net_delay,
        t_chan_width_dist chan_width_dist, t_ivec **clb_opins_used_locally) {

/* Attempts a routing via an iterated maze router algorithm.  Width_fac *
 * specifies the relative width of the channels, while the members of   *
 * router_opts determine the value of the costs assigned to routing     *
 * resource node, etc.  det_routing_arch describes the detailed routing *
 * architecture (connection and switch boxes) of the FPGA; it is used   *
 * only if a DETAILED routing has been selected.                        */

 boolean success;

 printf("\nAttempting routing with a width factor (usually maximum channel ");
 printf("width) of %d.\n",width_fac);

/* Set the channel widths */

 init_chan (width_fac, chan_width_dist);

/* Free any old routing graph, if one exists. */

 free_rr_graph ();

/* Set up the routing resource graph defined by this FPGA architecture. */

 build_rr_graph (router_opts.route_type, det_routing_arch, segment_inf,
                 timing_inf, router_opts.base_cost_type);
 free_rr_graph_internals (router_opts.route_type, det_routing_arch, segment_inf,
                 timing_inf, router_opts.base_cost_type);

/* Allocate and load some additional rr_graph information needed only by *
 * the router.                                                           */

 alloc_and_load_rr_node_route_structs ();

 init_route_structs (router_opts.bb_factor);

 if (router_opts.router_algorithm == BREADTH_FIRST) 
    success = try_breadth_first_route (router_opts, clb_opins_used_locally); 

 else    /* TIMING_DRIVEN route */
    success = try_timing_driven_route (router_opts, net_slack, net_delay, 
                clb_opins_used_locally);

 free_rr_node_route_structs ();
 return (success);
}


boolean feasible_routing (void) {

/* This routine checks to see if this is a resource-feasible routing.      *
 * That is, are all rr_node capacity limitations respected?  It assumes    *
 * that the occupancy arrays are up to date when it is called.             */

 int inode;

 for (inode=0;inode<num_rr_nodes;inode++) 
    if (rr_node[inode].occ > rr_node[inode].capacity)
       return (FALSE);

 return (TRUE);
}


void pathfinder_update_one_cost (struct s_trace *route_segment_start,
      int add_or_sub, float pres_fac) {

/* This routine updates the occupancy and pres_cost of the rr_nodes that are *
 * affected by the portion of the routing of one net that starts at          *
 * route_segment_start.  If route_segment_start is trace_head[inet], the     *
 * cost of all the nodes in the routing of net inet are updated.  If         *
 * add_or_sub is -1 the net (or net portion) is ripped up, if it is 1 the    *
 * net is added to the routing.  The size of pres_fac determines how severly *
 * oversubscribed rr_nodes are penalized.                                    */

 struct s_trace *tptr;
 int inode, occ, capacity;

 tptr = route_segment_start;
 if (tptr == NULL)        /* No routing yet. */
    return;

 while (1) {
    inode = tptr->index;

    occ = rr_node[inode].occ + add_or_sub;
    capacity = rr_node[inode].capacity;

    rr_node[inode].occ = occ;

/* pres_cost is Pn in the Pathfinder paper. I set my pres_cost according to *
 * the overuse that would result from having ONE MORE net use this routing  *
 * node.                                                                    */

    if (occ < capacity) {
       rr_node_route_inf[inode].pres_cost = 1.;
    }
    else {
       rr_node_route_inf[inode].pres_cost = 1. + (occ + 1 - capacity) * 
                                                pres_fac;
    }

    if (rr_node[inode].type == SINK) {
       tptr = tptr->next;             /* Skip next segment. */
       if (tptr == NULL)
          break;
    }

    tptr = tptr->next;
 
 }   /* End while loop -- did an entire traceback. */
}


void pathfinder_update_cost (float pres_fac, float acc_fac) {

/* This routine recomputes the pres_cost and acc_cost of each routing        *
 * resource for the pathfinder algorithm after all nets have been routed.    *
 * It updates the accumulated cost to by adding in the number of extra       *
 * signals sharing a resource right now (i.e. after each complete iteration) *
 * times acc_fac.  It also updates pres_cost, since pres_fac may have        *
 * changed.  THIS ROUTINE ASSUMES THE OCCUPANCY VALUES IN RR_NODE ARE UP TO  *
 * DATE.                                                                     */

 int inode, occ, capacity;
 
 for (inode=0;inode<num_rr_nodes;inode++) {
    occ = rr_node[inode].occ;
    capacity = rr_node[inode].capacity;
    
    if (occ > capacity) {
       rr_node_route_inf[inode].acc_cost += (occ - capacity) * acc_fac;
       rr_node_route_inf[inode].pres_cost = 1. + (occ + 1 - capacity) * 
                                            pres_fac;
    }

/* If occ == capacity, we don't need to increase acc_cost, but a change    *
 * in pres_fac could have made it necessary to recompute the cost anyway.  */

    else if (occ == capacity) {
       rr_node_route_inf[inode].pres_cost = 1. + pres_fac;
    }
 }
}    


void init_route_structs (int bb_factor) {

/* Call this before you route any nets.  It frees any old traceback and   *
 * sets the list of rr_nodes touched to empty.                            */

 int i;

 for (i=0;i<num_nets;i++)
    free_traceback (i);

 load_route_bb (bb_factor);

/* Check that things that should have been emptied after the last routing *
 * really were.                                                           */
 
 if (rr_modified_head != NULL) {
    printf ("Error in init_route_structs.  List of modified rr nodes is \n"
            "not empty.\n");
    exit (1);
 }

 if (heap_tail != 1) {
    printf ("Error in init_route_structs.  Heap is not empty.\n");
    exit (1);
 }
}


struct s_trace *update_traceback (struct s_heap *hptr, int inet) {

/* This routine adds the most recently finished wire segment to the         *
 * traceback linked list.  The first connection starts with the net SOURCE  *
 * and begins at the structure pointed to by trace_head[inet]. Each         *
 * connection ends with a SINK.  After each SINK, the next connection       *
 * begins (if the net has more than 2 pins).  The first element after the   *
 * SINK gives the routing node on a previous piece of the routing, which is *
 * the link from the existing net to this new piece of the net.             *
 * In each traceback I start at the end of a path and trace back through    *
 * its predecessors to the beginning.  I have stored information on the     *
 * predecesser of each node to make traceback easy -- this sacrificies some *
 * memory for easier code maintenance.  This routine returns a pointer to   *
 * the first "new" node in the traceback (node not previously in trace).    */ 

 struct s_trace *tptr, *prevptr, *temptail, *ret_ptr;
 int inode;
 short iedge;
#ifdef DEBUG
 t_rr_type rr_type;
#endif

 inode = hptr->index;

#ifdef DEBUG
   rr_type = rr_node[inode].type;
   if (rr_type != SINK) {
      printf("Error in update_traceback.  Expected type = SINK (%d).\n",
         SINK);
      printf("Got type = %d while tracing back net %d.\n", rr_type, inet);