route_directed_search.c

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

 * the same logic block, so the hack will never execute.  If your logic     *
 * block is an and-gate, however, nets might connect to two and-inputs on   *
 * the same logic block, and since the and-inputs are logically-equivalent, *
 * this means two connections to the same SINK.                             */

    struct s_trace *tptr;
    int inode, backward_path_cost, tot_cost;

    tptr = start_ptr;

    if(remaining_connections_to_sink == 0)
	{			/* Usual case. */
	    while(tptr != NULL)
		{
		    /* WMF: partial routing is added to the heap with path cost of 0, because
		     * new extension to the next sink can start at any point on current partial 
		     * routing. However, for directed search the total cost must be made to favor
		     * the points of current partial routing that are NEAR the next sink (target sink) */

		    /* WMF: IPINs and SINKs should be excluded from the heap in this
		     * since they NEVER connect TO any rr_node (no to_edges), but since they have
		     * no to_edges, it's ok (ROUTE_THROUGHS are disabled). To clarify, see 
		     * rr_graph.c to find out rr_node[inode].num_edges = 0 for SINKs and
		     * rr_node[inode].num_edges = 1 for INPINs */

		    inode = tptr->index;

		    if(!
		       (rr_node[inode].type == IPIN
			|| rr_node[inode].type == SINK))
			{

			    backward_path_cost = 0;
			    tot_cost =
				backward_path_cost +
				astar_fac *
				get_directed_search_expected_cost(inode,
								  target_node);
			    node_to_heap(inode, tot_cost, NO_PREVIOUS,
					 NO_PREVIOUS, backward_path_cost,
					 OPEN);
			}

		    tptr = tptr->next;
		}
	}

    else
	{			/* This case never executes for most logic blocks. */
	    printf("Warning: Multiple connections from net to the same sink. "
		   "This should not happen for LUT/Cluster based logic blocks. Aborting.\n");
	    exit(1);
	}
}

static void
directed_search_expand_neighbours(struct s_heap *current,
				  int inet,
				  float bend_cost,
				  int target_node,
				  float astar_fac)
{

/* Puts all the rr_nodes adjacent to current on the heap.  rr_nodes outside   *
 * the expanded bounding box specified in route_bb are not added to the     *
 * heap.  back_cost is the path_cost to get to inode. total cost i.e.
 * tot_cost is path_cost + (expected_cost to target sink) */

    int iconn, to_node, num_edges, inode, target_x, target_y;
    t_rr_type from_type, to_type;
    float new_tot_cost, old_back_pcost, new_back_pcost;

    inode = current->index;
    old_back_pcost = current->backward_path_cost;
    num_edges = rr_node[inode].num_edges;

    target_x = rr_node[target_node].xhigh;
    target_y = rr_node[target_node].yhigh;

    for(iconn = 0; iconn < num_edges; iconn++)
	{
	    to_node = rr_node[inode].edges[iconn];

	    if(rr_node[to_node].xhigh < route_bb[inet].xmin ||
	       rr_node[to_node].xlow > route_bb[inet].xmax ||
	       rr_node[to_node].yhigh < route_bb[inet].ymin ||
	       rr_node[to_node].ylow > route_bb[inet].ymax)
		continue;	/* Node is outside (expanded) bounding box. */

/* Prune away IPINs that lead to blocks other than the target one.  Avoids  *
 * the issue of how to cost them properly so they don't get expanded before *
 * more promising routes, but makes route-throughs (via CLBs) impossible.   *
 * Change this if you want to investigate route-throughs.                   */

	    to_type = rr_node[to_node].type;
	    if(to_type == IPIN && (rr_node[to_node].xhigh != target_x ||
				   rr_node[to_node].yhigh != target_y))
		continue;

/* new_back_pcost stores the "known" part of the cost to this node -- the   *
 * congestion cost of all the routing resources back to the existing route  *
 * new_tot_cost 
 * is this "known" backward cost + an expected cost to get to the target.   */

	    new_back_pcost = old_back_pcost + get_rr_cong_cost(to_node);

	    if(bend_cost != 0.)
		{
		    from_type = rr_node[inode].type;
		    to_type = rr_node[to_node].type;
		    if((from_type == CHANX && to_type == CHANY) ||
		       (from_type == CHANY && to_type == CHANX))
			new_back_pcost += bend_cost;
		}

	    /* Calculate the new total cost = path cost + astar_fac * remaining distance to target */
	    new_tot_cost = new_back_pcost + astar_fac *
		get_directed_search_expected_cost(to_node, target_node);

	    node_to_heap(to_node, new_tot_cost, inode, iconn, new_back_pcost,
			 OPEN);
	}
}


static void
directed_search_add_source_to_heap(int inet,
				   int target_node,
				   float astar_fac)
{

/* Adds the SOURCE of this net to the heap.  Used to start a net's routing. */

    int inode;
    float back_cost, tot_cost;

    inode = net_rr_terminals[inet][0];	/* SOURCE */
    back_cost = 0.0 + get_rr_cong_cost(inode);

    /* setting the total cost to 0 because it's the only element on the heap */
    if(!is_empty_heap())
	{
	    printf
		("Error: Wrong Assumption: in directed_search_add_source_to_heap "
		 "the heap is not empty. Need to properly calculate source node's cost.\n");
	    exit(1);
	}

    /* WMF: path cost is 0. could use tot_cost = 0 to save some computation time, but
     * for consistency, I chose to do the expected cost calculation. */
    tot_cost =
	back_cost + astar_fac * get_directed_search_expected_cost(inode,
								  target_node);
    node_to_heap(inode, tot_cost, NO_PREVIOUS, NO_PREVIOUS, back_cost, OPEN);

}


static float
get_directed_search_expected_cost(int inode,
				  int target_node)
{

/* Determines the expected cost (due to resouce cost i.e. distance) to reach  *
 * the target node from inode.  It doesn't include the cost of inode --       *
 * that's already in the "known" path_cost.                                   */

    t_rr_type rr_type;
    int cost_index, ortho_cost_index, num_segs_same_dir, num_segs_ortho_dir;
    float cong_cost;

    rr_type = rr_node[inode].type;

    if(rr_type == CHANX || rr_type == CHANY)
	{
	    num_segs_same_dir =
		get_expected_segs_to_target(inode, target_node,
					    &num_segs_ortho_dir);
	    cost_index = rr_node[inode].cost_index;
	    ortho_cost_index = rr_indexed_data[cost_index].ortho_cost_index;

	    cong_cost =
		num_segs_same_dir * rr_indexed_data[cost_index].base_cost +
		num_segs_ortho_dir *
		rr_indexed_data[ortho_cost_index].base_cost;
	    cong_cost +=
		rr_indexed_data[IPIN_COST_INDEX].base_cost +
		rr_indexed_data[SINK_COST_INDEX].base_cost;

	    return (cong_cost);
	}

    else if(rr_type == IPIN)
	{			/* Change if you're allowing route-throughs */
	    return (rr_indexed_data[SINK_COST_INDEX].base_cost);
	}

    else
	{			/* Change this if you want to investigate route-throughs */
	    return (0.);
	}
}


/* Macro used below to ensure that fractions are rounded up, but floating   *
 * point values very close to an integer are rounded to that integer.       */

#define ROUND_UP(x) (ceil (x - 0.001))


static int
get_expected_segs_to_target(int inode,
			    int target_node,
			    int *num_segs_ortho_dir_ptr)
{

/* Returns the number of segments the same type as inode that will be needed *
 * to reach target_node (not including inode) in each direction (the same    *
 * direction (horizontal or vertical) as inode and the orthogonal direction).*/

    t_rr_type rr_type;
    int target_x, target_y, num_segs_same_dir, cost_index, ortho_cost_index;
    int no_need_to_pass_by_clb;
    float inv_length, ortho_inv_length, ylow, yhigh, xlow, xhigh;

    target_x = rr_node[target_node].xlow;
    target_y = rr_node[target_node].ylow;
    cost_index = rr_node[inode].cost_index;
    inv_length = rr_indexed_data[cost_index].inv_length;
    ortho_cost_index = rr_indexed_data[cost_index].ortho_cost_index;
    ortho_inv_length = rr_indexed_data[ortho_cost_index].inv_length;
    rr_type = rr_node[inode].type;

    if(rr_type == CHANX)
	{
	    ylow = rr_node[inode].ylow;
	    xhigh = rr_node[inode].xhigh;
	    xlow = rr_node[inode].xlow;

	    /* Count vertical (orthogonal to inode) segs first. */

	    if(ylow > target_y)
		{		/* Coming from a row above target? */
		    *num_segs_ortho_dir_ptr =
			ROUND_UP((ylow - target_y + 1.) * ortho_inv_length);
		    no_need_to_pass_by_clb = 1;
		}
	    else if(ylow < target_y - 1)
		{		/* Below the FB bottom? */
		    *num_segs_ortho_dir_ptr = ROUND_UP((target_y - ylow) *
						       ortho_inv_length);
		    no_need_to_pass_by_clb = 1;
		}
	    else
		{		/* In a row that passes by target FB */
		    *num_segs_ortho_dir_ptr = 0;
		    no_need_to_pass_by_clb = 0;
		}

	    /* Now count horizontal (same dir. as inode) segs. */

	    if(xlow > target_x + no_need_to_pass_by_clb)
		{
		    num_segs_same_dir =
			ROUND_UP((xlow - no_need_to_pass_by_clb -
				  target_x) * inv_length);
		}
	    else if(xhigh < target_x - no_need_to_pass_by_clb)
		{
		    num_segs_same_dir =
			ROUND_UP((target_x - no_need_to_pass_by_clb -
				  xhigh) * inv_length);
		}
	    else
		{
		    num_segs_same_dir = 0;
		}
	}

    else
	{			/* inode is a CHANY */
	    ylow = rr_node[inode].ylow;
	    yhigh = rr_node[inode].yhigh;
	    xlow = rr_node[inode].xlow;

	    /* Count horizontal (orthogonal to inode) segs first. */

	    if(xlow > target_x)
		{		/* Coming from a column right of target? */
		    *num_segs_ortho_dir_ptr =
			ROUND_UP((xlow - target_x + 1.) * ortho_inv_length);
		    no_need_to_pass_by_clb = 1;
		}
	    else if(xlow < target_x - 1)
		{		/* Left of and not adjacent to the FB? */
		    *num_segs_ortho_dir_ptr = ROUND_UP((target_x - xlow) *
						       ortho_inv_length);
		    no_need_to_pass_by_clb = 1;
		}
	    else
		{		/* In a column that passes by target FB */
		    *num_segs_ortho_dir_ptr = 0;
		    no_need_to_pass_by_clb = 0;
		}

	    /* Now count vertical (same dir. as inode) segs. */

	    if(ylow > target_y + no_need_to_pass_by_clb)
		{
		    num_segs_same_dir =
			ROUND_UP((ylow - no_need_to_pass_by_clb -
				  target_y) * inv_length);
		}
	    else if(yhigh < target_y - no_need_to_pass_by_clb)
		{
		    num_segs_same_dir =
			ROUND_UP((target_y - no_need_to_pass_by_clb -
				  yhigh) * inv_length);
		}
	    else
		{
		    num_segs_same_dir = 0;
		}
	}

    return (num_segs_same_dir);
}