route_tree_timing.c

fpga设计评估软件

 rr_node_to_rt_node[inode] = sink_rt_node;

/* In the code below I'm marking SINKs and IPINs as not to be re-expanded.  *
 * Undefine NO_ROUTE_THROUGHS if you want route-throughs or ipin doglegs.   *
 * It makes the code more efficient (though not vastly) to prune this way   *
 * when there aren't route-throughs or ipin doglegs.                        */
 
#define NO_ROUTE_THROUGHS 1  /* Can't route through unused CLB outputs */

#ifdef NO_ROUTE_THROUGHS
 sink_rt_node->re_expand = FALSE;
#else
 if (remaining_connections_to_sink == 0) {   /* Usual case */
    sink_rt_node->re_expand = TRUE;  
 }
 
 /* Weird case.  This net connects several times to the same SINK.  Thus I   *
  * can't re_expand this node as part of the partial routing for subsequent  *
  * connections, since I need to reach it again via another path.            */
 
 else {
    sink_rt_node->re_expand = FALSE;
 }
#endif
 
 
/* Now do it's predecessor. */
 
 downstream_rt_node = sink_rt_node;
 inode = hptr->u.prev_node;
 iedge = hptr->prev_edge;
 iswitch = rr_node[inode].switches[iedge];
 
/* For all "new" nodes in the path */
 
 while (rr_node_route_inf[inode].prev_node != NO_PREVIOUS) {
    linked_rt_edge = alloc_linked_rt_edge ();
    linked_rt_edge->child = downstream_rt_node;
    linked_rt_edge->iswitch = iswitch;
    linked_rt_edge->next = NULL;
 
    rt_node = alloc_rt_node ();
    downstream_rt_node->parent_node = rt_node;
    downstream_rt_node->parent_switch = iswitch;
 
    rt_node->u.child_list = linked_rt_edge;
    rt_node->inode = inode;
 
    if (switch_inf[iswitch].buffered == FALSE)
       C_downstream += rr_node[inode].C;
    else
       C_downstream = rr_node[inode].C;
 
    rt_node->C_downstream = C_downstream;
    rr_node_to_rt_node[inode] = rt_node;
 
#ifdef NO_ROUTE_THROUGHS
    if (rr_node[inode].type == IPIN) 
       rt_node->re_expand = FALSE;
    else
       rt_node->re_expand = TRUE;

#else
    if (remaining_connections_to_sink == 0) {  /* Normal case */
       rt_node->re_expand = TRUE;
    }
    else {   /* This is the IPIN before a multiply-connected SINK */
       rt_node->re_expand = FALSE;

      /* Reset flag so wire segments get reused */

       remaining_connections_to_sink = 0;
    }
#endif

    downstream_rt_node = rt_node;
    iedge = rr_node_route_inf[inode].prev_edge;
    inode = rr_node_route_inf[inode].prev_node;
    iswitch = rr_node[inode].switches[iedge];
 }

/* Inode is the join point to the old routing */

 rt_node = rr_node_to_rt_node[inode];

 linked_rt_edge = alloc_linked_rt_edge ();
 linked_rt_edge->child = downstream_rt_node;
 linked_rt_edge->iswitch = iswitch;
 linked_rt_edge->next = rt_node->u.child_list;
 rt_node->u.child_list = linked_rt_edge;

 downstream_rt_node->parent_node = rt_node;
 downstream_rt_node->parent_switch = iswitch;

 *sink_rt_node_ptr = sink_rt_node;
 return (downstream_rt_node);
}


static void load_new_path_R_upstream (t_rt_node *start_of_new_path_rt_node) {

/* Sets the R_upstream values of all the nodes in the new path to the       *
 * correct value.                                                           */

 float R_upstream;
 int inode;
 short iswitch;
 t_rt_node *rt_node, *parent_rt_node;
 t_linked_rt_edge *linked_rt_edge;

 rt_node = start_of_new_path_rt_node;
 iswitch = rt_node->parent_switch;
 inode = rt_node->inode;
 parent_rt_node = rt_node->parent_node;
 
 R_upstream = switch_inf[iswitch].R + rr_node[inode].R;

 if (switch_inf[iswitch].buffered == FALSE)
    R_upstream += parent_rt_node->R_upstream;
 
 rt_node->R_upstream = R_upstream;

/* Note:  the traversal below makes use of the fact that this new path      *
 * really is a path (not a tree with branches) to do a traversal without    *
 * recursion, etc.                                                          */

 linked_rt_edge = rt_node->u.child_list;
 
 while (linked_rt_edge != NULL) {   /* While SINK not reached. */

#ifdef DEBUG
    if (linked_rt_edge->next != NULL) {
       printf ("Error in load_new_path_R_upstream: new routing addition is\n"
               "a tree (not a path).\n");
       exit (1);
    }
#endif

    rt_node = linked_rt_edge->child;
    iswitch = linked_rt_edge->iswitch;
    inode = rt_node->inode;
    
    if (switch_inf[iswitch].buffered) 
       R_upstream = switch_inf[iswitch].R + rr_node[inode].R;
    else
       R_upstream += switch_inf[iswitch].R + rr_node[inode].R;

    rt_node->R_upstream = R_upstream;
    linked_rt_edge = rt_node->u.child_list;
 }
}


static t_rt_node *update_unbuffered_ancestors_C_downstream (t_rt_node 
            *start_of_new_path_rt_node) {

/* Updates the C_downstream values for the ancestors of the new path.  Once *
 * a buffered switch is found amongst the ancestors, no more ancestors are  *
 * affected.  Returns the root of the "unbuffered subtree" whose Tdel       *
 * values are affected by the new path's addition.                          */

 t_rt_node *rt_node, *parent_rt_node;
 short iswitch;
 float C_downstream_addition;

 rt_node = start_of_new_path_rt_node;
 C_downstream_addition = rt_node->C_downstream;
 parent_rt_node = rt_node->parent_node;
 iswitch = rt_node->parent_switch;
 
 while (parent_rt_node != NULL && switch_inf[iswitch].buffered == FALSE) {
    rt_node = parent_rt_node;
    rt_node->C_downstream += C_downstream_addition;
    parent_rt_node = rt_node->parent_node;
    iswitch = rt_node->parent_switch;
 }
 
 return (rt_node);
}


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

/* Updates the Tdel values of the subtree rooted at subtree_rt_root by      *
 * by calling itself recursively.  The C_downstream values of all the nodes *
 * must be correct before this routine is called.  Tarrival is the time at  *
 * at which the signal arrives at this node's *input*.                      */

 int inode;
 short iswitch;
 t_rt_node *child_node;
 t_linked_rt_edge *linked_rt_edge;
 float Tdel, Tchild;

 inode = subtree_rt_root->inode;

/* Assuming the downstream connections are, on average, connected halfway    *
 * along a wire segment's length.  See discussion in net_delay.c if you want *
 * to change this.                                                           */

 Tdel = Tarrival + 0.5 * subtree_rt_root->C_downstream * rr_node[inode].R;
 subtree_rt_root->Tdel = Tdel;

/* Now expand the children of this node to load their Tdel values (depth-   *
 * first pre-order traversal).                                              */

 linked_rt_edge = subtree_rt_root->u.child_list;
 
 while (linked_rt_edge != NULL) {
    iswitch = linked_rt_edge->iswitch;
    child_node = linked_rt_edge->child;
    
    Tchild = Tdel + switch_inf[iswitch].R * child_node->C_downstream;
    Tchild += switch_inf[iswitch].Tdel;     /* Intrinsic switch delay. */
    load_rt_subtree_Tdel (child_node, Tchild);

    linked_rt_edge = linked_rt_edge->next;
 }
}


void free_route_tree (t_rt_node *rt_node) {

/* Puts the rt_nodes and edges in the tree rooted at rt_node back on the    *
 * free lists.  Recursive, depth-first post-order traversal.                */

 t_rt_node *child_node;
 t_linked_rt_edge *rt_edge, *next_edge;

 rt_edge = rt_node->u.child_list;

 while (rt_edge != NULL) {     /* For all children */
    child_node = rt_edge->child;
    free_route_tree (child_node);
    next_edge = rt_edge->next;
    free_linked_rt_edge (rt_edge);
    rt_edge = next_edge;
 }

 free_rt_node (rt_node);
}


void update_net_delays_from_route_tree (float *net_delay, t_rt_node 
           **rt_node_of_sink, int inet) {

/* Goes through all the sinks of this net and copies their delay values from *
 * the route_tree to the net_delay array.                                    */

 int isink;
 t_rt_node *sink_rt_node;
 
 for (isink=1;isink<net[inet].num_pins;isink++) {
    sink_rt_node = rt_node_of_sink[isink];
    net_delay[isink] = sink_rt_node->Tdel;
 }
}