route_tree_timing.c

用于学术研究的FPGA布局布线软件VPR

    sink_rt_node->inode = inode;
    C_downstream = rr_node[inode].C;
    sink_rt_node->C_downstream = C_downstream;
    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 FB 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_sinks; isink++)
	{
	    sink_rt_node = rt_node_of_sink[isink];
	    net_delay[isink] = sink_rt_node->Tdel;
	}
}