route_common.c

fpga设计评估软件

      exit(1);
   }
#endif
 
 tptr = alloc_trace_data ();   /* SINK on the end of the connection */ 
 tptr->index = inode;
 tptr->iswitch = OPEN;
 tptr->next = NULL;
 temptail = tptr;              /* This will become the new tail at the end */
                               /* of the routine.                          */

/* Now do it's predecessor. */

 inode = hptr->u.prev_node;
 iedge = hptr->prev_edge;

 while (inode != NO_PREVIOUS) {
    prevptr = alloc_trace_data();
    prevptr->index = inode;
    prevptr->iswitch = rr_node[inode].switches[iedge];
    prevptr->next = tptr;
    tptr = prevptr;

    iedge = rr_node_route_inf[inode].prev_edge;
    inode = rr_node_route_inf[inode].prev_node;
 }

 if (trace_tail[inet] != NULL) {
    trace_tail[inet]->next = tptr;     /* Traceback ends with tptr */
    ret_ptr = tptr->next;              /* First new segment.       */
 }
 else {                /* This was the first "chunk" of the net's routing */
    trace_head[inet] = tptr;
    ret_ptr = tptr;                    /* Whole traceback is new. */
 }

 trace_tail[inet] = temptail;
 return (ret_ptr);
}


void reset_path_costs (void) {

/* The routine sets the path_cost to HUGE_FLOAT for all channel segments   *
 * touched by previous routing phases.                                     */

 struct s_linked_f_pointer *mod_ptr;
#ifdef DEBUG
 int num_mod_ptrs;
#endif

/* The traversal method below is slightly painful to make it faster. */

 if (rr_modified_head != NULL) {
    mod_ptr = rr_modified_head;

#ifdef DEBUG 
    num_mod_ptrs = 1;
#endif

    while (mod_ptr->next != NULL) {
       *(mod_ptr->fptr) = HUGE_FLOAT;
       mod_ptr = mod_ptr->next;
#ifdef DEBUG 
       num_mod_ptrs++;
#endif
    }
    *(mod_ptr->fptr) = HUGE_FLOAT;   /* Do last one. */
    
/* Reset the modified list and put all the elements back in the free   *
 * list.                                                               */

    mod_ptr->next = linked_f_pointer_free_head;
    linked_f_pointer_free_head = rr_modified_head; 
    rr_modified_head = NULL;

#ifdef DEBUG 
    num_linked_f_pointer_allocated -= num_mod_ptrs;
#endif
 }
}


float get_rr_cong_cost (int inode) {

/* Returns the *congestion* cost of using this rr_node. */

 short cost_index;
 float cost;

 cost_index = rr_node[inode].cost_index;
 cost = rr_indexed_data[cost_index].base_cost * 
                 rr_node_route_inf[inode].acc_cost * 
                rr_node_route_inf[inode].pres_cost;
 return (cost);
}


void mark_ends (int inet) {

/* Mark all the SINKs of this net as targets by setting their target flags  *
 * to the number of times the net must connect to each SINK.  Note that     *
 * this number can occassionally be greater than 1 -- think of connecting   *
 * the same net to two inputs of an and-gate (and-gate inputs are logically *
 * equivalent, so both will connect to the same SINK).                      */

 int ipin, inode;

 for (ipin=1;ipin<net[inet].num_pins;ipin++) {
    inode = net_rr_terminals[inet][ipin];
    rr_node_route_inf[inode].target_flag++;
 }
}


void node_to_heap (int inode, float cost, int prev_node, int prev_edge,
                   float backward_path_cost, float R_upstream) {

/* Puts an rr_node on the heap, if the new cost given is lower than the     *
 * current path_cost to this channel segment.  The index of its predecessor *
 * is stored to make traceback easy.  The index of the edge used to get     *
 * from its predecessor to it is also stored to make timing analysis, etc.  *
 * easy.  The backward_path_cost and R_upstream values are used only by the *
 * timing-driven router -- the breadth-first router ignores them.           */

 struct s_heap *hptr;

 if (cost >= rr_node_route_inf[inode].path_cost)
     return;

 hptr = alloc_heap_data();
 hptr->index = inode; 
 hptr->cost = cost;
 hptr->u.prev_node = prev_node;
 hptr->prev_edge = prev_edge;
 hptr->backward_path_cost = backward_path_cost;
 hptr->R_upstream = R_upstream;
 add_to_heap (hptr);
}


void free_traceback (int inet) {

/* Puts the entire traceback (old routing) for this net on the free list *
 * and sets the trace_head pointers etc. for the net to NULL.            */

 struct s_trace *tptr, *tempptr;

 tptr = trace_head[inet];

 while (tptr != NULL) {
    tempptr = tptr->next; 
    free_trace_data (tptr);
    tptr = tempptr;
 }
 
 trace_head[inet] = NULL; 
 trace_tail[inet] = NULL;
}


t_ivec **alloc_route_structs (t_subblock_data subblock_data) {

/* Allocates the data structures needed for routing.    */

 t_ivec **clb_opins_used_locally;

 trace_head = (struct s_trace **) my_calloc (num_nets,  
    sizeof(struct s_trace *));
 trace_tail = (struct s_trace **) my_malloc (num_nets * 
    sizeof(struct s_trace *));

 heap_size = nx*ny;
 heap = (struct s_heap **) my_malloc (heap_size * 
    sizeof (struct s_heap *));
 heap--;   /* heap stores from [1..heap_size] */
 heap_tail = 1;

 route_bb = (struct s_bb *) my_malloc (num_nets * sizeof (struct s_bb));

 clb_opins_used_locally = alloc_and_load_clb_opins_used_locally (
              subblock_data);
 
 return (clb_opins_used_locally);
}


struct s_trace **alloc_saved_routing (t_ivec **clb_opins_used_locally,
         t_ivec ***saved_clb_opins_used_locally_ptr) {

/* Allocates data structures into which the key routing data can be saved,   *
 * allowing the routing to be recovered later (e.g. after a another routing  *
 * is attempted).                                                            */

 struct s_trace **best_routing;
 t_ivec **saved_clb_opins_used_locally;
 int iblk, iclass, num_local_opins;

 best_routing = (struct s_trace **) my_calloc (num_nets, 
     sizeof (struct s_trace *));

 saved_clb_opins_used_locally = (t_ivec **) alloc_matrix (0, num_blocks-1, 0,
       num_class-1, sizeof (t_ivec));

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

       if (num_local_opins == 0) {
          saved_clb_opins_used_locally[iblk][iclass].list = NULL;
       }
       else {
          saved_clb_opins_used_locally[iblk][iclass].list = (int *) 
               my_malloc (num_local_opins * sizeof (int));
       }
    }
 }
 
 *saved_clb_opins_used_locally_ptr = saved_clb_opins_used_locally;
 return (best_routing);
}


static t_ivec **alloc_and_load_clb_opins_used_locally (t_subblock_data 
          subblock_data) {

/* Allocates and loads the data needed to make the router reserve some CLB  *
 * output pins for connections made locally within a CLB (if the netlist    *
 * specifies that this is necessary).                                       */

 t_ivec **clb_opins_used_locally;
 int *num_subblocks_per_block;
 t_subblock **subblock_inf;
 int iblk, isub, clb_pin, iclass, num_local_opins;

 clb_opins_used_locally = (t_ivec **) alloc_matrix (0, num_blocks-1, 0, 
                    num_class-1, sizeof (t_ivec));
 num_subblocks_per_block = subblock_data.num_subblocks_per_block;
 subblock_inf = subblock_data.subblock_inf;

 for (iblk=0;iblk<num_blocks;iblk++) {
    if (block[iblk].type != CLB) {
       for (iclass=0;iclass<num_class;iclass++) {
          clb_opins_used_locally[iblk][iclass].nelem = 0;
          clb_opins_used_locally[iblk][iclass].list = NULL;
       }
    }
    
    else {  /* CLB */
       for (iclass=0;iclass<num_class;iclass++) 
          clb_opins_used_locally[iblk][iclass].nelem = 0;

       for (isub=0;isub<num_subblocks_per_block[iblk];isub++) {
          clb_pin = subblock_inf[iblk][isub].output;

     /* Subblock output used only locally, but must connect to a CLB OPIN?  */
          if (clb_pin != OPEN && block[iblk].nets[clb_pin] == OPEN) {
             iclass = clb_pin_class[clb_pin];
             clb_opins_used_locally[iblk][iclass].nelem++;
          }
       }

       for (iclass=0;iclass<num_class;iclass++) {
          num_local_opins = 
                  clb_opins_used_locally[iblk][iclass].nelem;

          if (num_local_opins == 0) 
             clb_opins_used_locally[iblk][iclass].list = NULL;
          else 
             clb_opins_used_locally[iblk][iclass].list = 
                 (int *) my_malloc (num_local_opins * sizeof (int));
       }
    }
 }
 
 return (clb_opins_used_locally);
}

void free_trace_structs (void) {
  /*the trace lists are only freed after use by the timing-driven placer*/
  /*Do not  free them after use by the router, since stats, and draw  */
  /*routines use the trace values */
  int i;

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

  free(trace_head);
  free(trace_tail);
  trace_head = NULL;
  trace_tail = NULL;
}

void free_route_structs (t_ivec **clb_opins_used_locally) {

/* Frees the temporary storage needed only during the routing.  The  *
 * final routing result is not freed.                                */

 free (heap + 1);
 free (route_bb);

 heap = NULL;         /* Defensive coding:  crash hard if I use these. */
 route_bb = NULL;

 free_ivec_matrix (clb_opins_used_locally, 0, num_blocks-1, 0, num_class-1);

/* NB:  Should use my chunk_malloc for tptr, hptr, and mod_ptr structures. *
 * I could free everything except the tptrs at the end then.               */

}


void free_saved_routing (struct s_trace **best_routing, t_ivec
        **saved_clb_opins_used_locally) {

/* Frees the data structures needed to save a routing.                     */

 free (best_routing);
 free_ivec_matrix (saved_clb_opins_used_locally, 0, num_blocks-1, 0, 
                   num_class-1);
}


void alloc_and_load_rr_node_route_structs (void) {

/* Allocates some extra information about each rr_node that is used only   *
 * during routing.                                                         */

 int inode;

 if (rr_node_route_inf != NULL) {
    printf ("Error in alloc_and_load_rr_node_route_structs:  \n"
            "old rr_node_route_inf array exists.\n");
    exit (1);
 }

 rr_node_route_inf = my_malloc (num_rr_nodes * sizeof (t_rr_node_route_inf));

 for (inode=0;inode<num_rr_nodes;inode++) {
    rr_node_route_inf[inode].prev_node = NO_PREVIOUS;
    rr_node_route_inf[inode].prev_edge = NO_PREVIOUS;
    rr_node_route_inf[inode].pres_cost = 1.;
    rr_node_route_inf[inode].acc_cost = 1.;
    rr_node_route_inf[inode].path_cost = HUGE_FLOAT;
    rr_node_route_inf[inode].target_flag = 0;
 }
}


void free_rr_node_route_structs (void) {

/* Frees the extra information about each rr_node that is needed only      *
 * during routing.                                                         */

 free (rr_node_route_inf);
 rr_node_route_inf = NULL;   /* Mark as free */
}


static void load_route_bb (int bb_factor) {

/* This routine loads the bounding box arrays used to limit the space  *
 * searched by the maze router when routing each net.  The search is   *
 * limited to channels contained with the net bounding box expanded    *
 * by bb_factor channels on each side.  For example, if bb_factor is   *
 * 0, the maze router must route each net within its bounding box.     *
 * If bb_factor = nx, the maze router will search every channel in     *
 * the FPGA if necessary.  The bounding boxes returned by this routine *
 * are different from the ones used by the placer in that they are     * 
 * clipped to lie within (0,0) and (nx+1,ny+1) rather than (1,1) and   *
 * (nx,ny).                                                            */

 int k, xmax, ymax, xmin, ymin, x, y, inet;

 for (inet=0;inet<num_nets;inet++) {
    x = block[net[inet].blocks[0]].x;
    y = block[net[inet].blocks[0]].y;

    xmin = x;
    ymin = y;
    xmax = x;
    ymax = y;

    for (k=1;k<net[inet].num_pins;k++) {
       x = block[net[inet].blocks[k]].x;
       y = block[net[inet].blocks[k]].y;

       if (x < xmin) {
          xmin = x;
       }
       else if (x > xmax) {
          xmax = x;
       }

       if (y < ymin) {
          ymin = y;
       }
       else if (y > ymax ) {
          ymax = y;
       }
    }   

   /* Want the channels on all 4 sides to be usuable, even if bb_factor = 0. */

    xmin -= 1;
    ymin -= 1;

   /* Expand the net bounding box by bb_factor, then clip to the physical *
    * chip area.                                                          */

    route_bb[inet].xmin = max (xmin - bb_factor, 0);
    route_bb[inet].xmax = min (xmax + bb_factor, nx+1);
    route_bb[inet].ymin = max (ymin - bb_factor, 0);
    route_bb[inet].ymax = min (ymax + bb_factor, ny+1);
 }
}