route_tree_timing.c

fpga设计评估软件

#include <stdio.h>
#include "util.h"
#include "vpr_types.h"
#include "globals.h"
#include "route_common.h"
#include "route_tree_timing.h"

/* This module keeps track of the partial routing tree for timing-driven     *
 * routing.  The normal traceback structure doesn't provide enough info      *
 * about the partial routing during timing-driven routing, so the routines   *
 * in this module are used to keep a tree representation of the partial      *
 * routing during timing-driven routing.  This allows rapid incremental      *
 * timing analysis.  The net_delay module does timing analysis in one step   *
 * (not incrementally as pieces of the routing are added).  I could probably *
 * one day remove a lot of net_delay.c and call the corresponding routines   *
 * here, but it's useful to have a from-scratch delay calculator to check    *
 * the results of this one.                                                  */


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

/* Array below allows mapping from any rr_node to any rt_node currently in   *
 * the rt_tree.                                                              */

static t_rt_node **rr_node_to_rt_node = NULL;   /* [0..num_rr_nodes-1] */

/* Frees lists for fast addition and deletion of nodes and edges. */

static t_rt_node *rt_node_free_list = NULL;
static t_linked_rt_edge *rt_edge_free_list = NULL;



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

static t_rt_node *alloc_rt_node (void); 

static void free_rt_node (t_rt_node *rt_node);

static t_linked_rt_edge *alloc_linked_rt_edge (void);

static void free_linked_rt_edge (t_linked_rt_edge *rt_edge);

static t_rt_node *add_path_to_route_tree (struct s_heap *hptr, t_rt_node
        **sink_rt_node_ptr);

static void load_new_path_R_upstream (t_rt_node *start_of_new_path_rt_node);

static t_rt_node *update_unbuffered_ancestors_C_downstream (t_rt_node
            *start_of_new_path_rt_node);

static void load_rt_subtree_Tdel (t_rt_node *subtree_rt_root, float Tarrival); 



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

void alloc_route_tree_timing_structs (void) {

/* Allocates any structures needed to build the routing trees. */

 if (rr_node_to_rt_node != NULL || rt_node_free_list != NULL ||
          rt_node_free_list != NULL) {
    printf ("Error in alloc_route_tree_timing_structs: old structures "
            "already exist.\n");
    exit (1);
 }

 rr_node_to_rt_node = (t_rt_node **) my_malloc (num_rr_nodes * 
                          sizeof (t_rt_node *));
}


void free_route_tree_timing_structs (void) {

/* Frees the structures needed to build routing trees, and really frees      *
 * (i.e. calls free) all the data on the free lists.                         */
 
 t_rt_node *rt_node, *next_node;
 t_linked_rt_edge *rt_edge, *next_edge;

 free (rr_node_to_rt_node);
 rr_node_to_rt_node = NULL;

 rt_node = rt_node_free_list;

 while (rt_node != NULL) {
    next_node = rt_node->u.next;
    free (rt_node);
    rt_node = next_node;
 }

 rt_node_free_list = NULL;

 rt_edge = rt_edge_free_list;
 
 while (rt_edge != NULL) {
    next_edge = rt_edge->next;
    free (rt_edge);
    rt_edge = next_edge;
 }

 rt_edge_free_list = NULL;
}


static t_rt_node *alloc_rt_node (void) {
 
/* Allocates a new rt_node, from the free list if possible, from the free   *
 * store otherwise.                                                         */
 
 t_rt_node *rt_node;
 
 rt_node = rt_node_free_list;
 
 if (rt_node != NULL) {
    rt_node_free_list = rt_node->u.next;
 }
 else {
    rt_node = (t_rt_node *) my_malloc (sizeof (t_rt_node));
 }    
 
 return (rt_node);
}


static void free_rt_node (t_rt_node *rt_node) {
 
/* Adds rt_node to the proper free list.          */
 
 rt_node->u.next = rt_node_free_list;
 rt_node_free_list = rt_node;
}
 
 
static t_linked_rt_edge *alloc_linked_rt_edge (void) {
 
/* Allocates a new linked_rt_edge, from the free list if possible, from the  *
 * free store otherwise.                                                     */
 
 t_linked_rt_edge *linked_rt_edge;
 
 linked_rt_edge = rt_edge_free_list;
 
 if (linked_rt_edge != NULL) {
    rt_edge_free_list = linked_rt_edge->next;
 }
 else {
    linked_rt_edge = (t_linked_rt_edge *) my_malloc (sizeof
                      (t_linked_rt_edge));
 }
 
 return (linked_rt_edge);
}
 
 
static void free_linked_rt_edge (t_linked_rt_edge *rt_edge) {
 
/* Adds the rt_edge to the rt_edge free list.                       */
 
 rt_edge->next = rt_edge_free_list;
 rt_edge_free_list = rt_edge;
}


t_rt_node *init_route_tree_to_source (int inet) {

/* Initializes the routing tree to just the net source, and returns the root *
 * node of the rt_tree (which is just the net source).                       */

 t_rt_node *rt_root;
 int inode;

 rt_root = alloc_rt_node ();
 rt_root->u.child_list = NULL;
 rt_root->parent_node = NULL;
 rt_root->parent_switch = OPEN;
 rt_root->re_expand = TRUE;
 
 inode = net_rr_terminals[inet][0];  /* Net source */
 
 rt_root->inode = inode;
 rt_root->C_downstream = rr_node[inode].C;
 rt_root->R_upstream = rr_node[inode].R;
 rt_root->Tdel = 0.5 * rr_node[inode].R * rr_node[inode].C;
 rr_node_to_rt_node[inode] = rt_root;

 return (rt_root);
}


t_rt_node *update_route_tree (struct s_heap *hptr) {

/* Adds the most recently finished wire segment to the routing tree, and    *
 * updates the Tdel, etc. numbers for the rest of the routing tree.  hptr   *
 * is the heap pointer of the SINK that was reached.  This routine returns  *
 * a pointer to the rt_node of the SINK that it adds to the routing.        */

 t_rt_node *start_of_new_path_rt_node, *sink_rt_node;
 t_rt_node *unbuffered_subtree_rt_root, *subtree_parent_rt_node;
 float Tdel_start;
 short iswitch;

 start_of_new_path_rt_node = add_path_to_route_tree (hptr, &sink_rt_node);
 load_new_path_R_upstream (start_of_new_path_rt_node);
 unbuffered_subtree_rt_root = update_unbuffered_ancestors_C_downstream (
                                      start_of_new_path_rt_node);
 
 subtree_parent_rt_node = unbuffered_subtree_rt_root->parent_node;

 if (subtree_parent_rt_node != NULL) {  /* Parent exists. */
    Tdel_start = subtree_parent_rt_node->Tdel;
    iswitch = unbuffered_subtree_rt_root->parent_switch;
    Tdel_start += switch_inf[iswitch].R * 
                   unbuffered_subtree_rt_root->C_downstream;
    Tdel_start += switch_inf[iswitch].Tdel;
 } 
 else {                                 /* Subtree starts at SOURCE */
    Tdel_start = 0.;
 }

 load_rt_subtree_Tdel (unbuffered_subtree_rt_root, Tdel_start);
 
 return (sink_rt_node);
}


static t_rt_node *add_path_to_route_tree (struct s_heap *hptr, t_rt_node 
        **sink_rt_node_ptr) {

/* Adds the most recent wire segment, ending at the SINK indicated by hptr, *
 * to the routing tree.  It returns the first (most upstream) new rt_node,  *
 * and (via a pointer) the rt_node of the new SINK.                         */

 int inode, remaining_connections_to_sink;
 short iedge, iswitch;
 float C_downstream;
 t_rt_node *rt_node, *downstream_rt_node, *sink_rt_node;
 t_linked_rt_edge *linked_rt_edge;

 
 inode = hptr->index;
 
#ifdef DEBUG
 if (rr_node[inode].type != SINK) {
    printf ("Error in add_path_to_route_tree.  Expected type = SINK (%d).\n", 
             SINK);
    printf ("Got type = %d.", rr_node[inode].type);
    exit (1);
 }
#endif
 
 remaining_connections_to_sink = rr_node_route_inf[inode].target_flag;
 sink_rt_node = alloc_rt_node ();
 sink_rt_node->u.child_list = NULL;
 sink_rt_node->inode = inode;
 C_downstream = rr_node[inode].C;
 sink_rt_node->C_downstream = C_downstream;