place.c

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

static float
recompute_bb_cost(int place_cost_type,
		  int num_regions)
{

    /* Recomputes the cost to eliminate roundoff that may have accrued.  *
     * This routine does as little work as possible to compute this new  *
     * cost.                                                             */

    int i, j, inet;
    float cost;

    cost = 0;

    /* Initialize occupancies to zero if regions are being used. */

    if(place_cost_type == NONLINEAR_CONG)
	{
	    for(i = 0; i < num_regions; i++)
		{
		    for(j = 0; j < num_regions; j++)
			{
			    place_region_x[i][j].occupancy = 0.;
			    place_region_y[i][j].occupancy = 0.;
			}
		}
	}

    for(inet = 0; inet < num_nets; inet++)
	{			/* for each net ... */

	    if(net[inet].is_global == FALSE)
		{		/* Do only if not global. */

		    /* Bounding boxes don't have to be recomputed; they're correct. */

		    if(place_cost_type != NONLINEAR_CONG)
			{
			    cost += net_cost[inet];
			}
		    else
			{	/* Must be nonlinear_cong case. */
			    update_region_occ(inet, &bb_coords[inet], 1,
					      num_regions);
			}
		}
	}

    if(place_cost_type == NONLINEAR_CONG)
	{
	    cost = nonlinear_cong_cost(num_regions);
	}

    return (cost);
}


static float
comp_td_point_to_point_delay(int inet,
			     int ipin)
{

    /*returns the delay of one point to point connection */

    int source_block, sink_block;
    int delta_x, delta_y;
    t_type_ptr source_type, sink_type;
    float delay_source_to_sink;

    delay_source_to_sink = 0.;

    source_block = net[inet].node_block[0];
    source_type = block[source_block].type;

    sink_block = net[inet].node_block[ipin];
    sink_type = block[sink_block].type;

    assert(source_type != NULL);
    assert(sink_type != NULL);

    delta_x = abs(block[sink_block].x - block[source_block].x);
    delta_y = abs(block[sink_block].y - block[source_block].y);

    /* TODO low priority: Could be merged into one look-up table */
    /* Note: This heuristic is terrible on Quality of Results.  
     * A much better heuristic is to create a more comprehensive lookup table but
     * it's too late in the release cycle to do this.  Pushing until the next release */
    if(source_type == IO_TYPE)
	{
	    if(sink_type == IO_TYPE)
		delay_source_to_sink = delta_io_to_io[delta_x][delta_y];
	    else
		delay_source_to_sink = delta_io_to_fb[delta_x][delta_y];
	}
    else
	{
	    if(sink_type == IO_TYPE)
		delay_source_to_sink = delta_fb_to_io[delta_x][delta_y];
	    else
		delay_source_to_sink = delta_fb_to_fb[delta_x][delta_y];
	}
    if(delay_source_to_sink < 0)
	{
	    printf
		("Error in comp_td_point_to_point_delay in place.c, bad delay_source_to_sink value\n");
	    exit(1);
	}

    if(delay_source_to_sink < 0.)
	{
	    printf
		("Error in comp_td_point_to_point_delay in place.c, delay is less than 0\n");
	    exit(1);
	}

    return (delay_source_to_sink);
}



static void
update_td_cost(int b_from,
	       int b_to,
	       int num_of_pins)
{
    /*update the point_to_point_timing_cost values from the temporary */
    /*values for all connections that have changed */

    int blkpin, net_pin, inet, ipin;

    for(blkpin = 0; blkpin < num_of_pins; blkpin++)
	{

	    inet = block[b_from].nets[blkpin];

	    if(inet == OPEN)
		continue;

	    if(net[inet].is_global)
		continue;

	    net_pin = net_pin_index[b_from][blkpin];

	    if(net_pin != 0)
		{

		    /*the following "if" prevents the value from being updated twice */
		    if(net[inet].node_block[0] != b_to
		       && net[inet].node_block[0] != b_from)
			{

			    point_to_point_delay_cost[inet][net_pin] =
				temp_point_to_point_delay_cost[inet][net_pin];
			    temp_point_to_point_delay_cost[inet][net_pin] =
				-1;

			    point_to_point_timing_cost[inet][net_pin] =
				temp_point_to_point_timing_cost[inet]
				[net_pin];
			    temp_point_to_point_timing_cost[inet][net_pin] =
				-1;
			}
		}
	    else
		{		/*this net is being driven by a moved block, recompute */
		    /*all point to point connections on this net. */
		    for(ipin = 1; ipin <= net[inet].num_sinks; ipin++)
			{

			    point_to_point_delay_cost[inet][ipin] =
				temp_point_to_point_delay_cost[inet][ipin];
			    temp_point_to_point_delay_cost[inet][ipin] = -1;

			    point_to_point_timing_cost[inet][ipin] =
				temp_point_to_point_timing_cost[inet][ipin];
			    temp_point_to_point_timing_cost[inet][ipin] = -1;
			}
		}
	}

    if(b_to != EMPTY)
	{
	    for(blkpin = 0; blkpin < num_of_pins; blkpin++)
		{

		    inet = block[b_to].nets[blkpin];

		    if(inet == OPEN)
			continue;

		    if(net[inet].is_global)
			continue;

		    net_pin = net_pin_index[b_to][blkpin];

		    if(net_pin != 0)
			{

			    /*the following "if" prevents the value from being updated 2x */
			    if(net[inet].node_block[0] != b_to
			       && net[inet].node_block[0] != b_from)
				{

				    point_to_point_delay_cost[inet][net_pin] =
					temp_point_to_point_delay_cost[inet]
					[net_pin];
				    temp_point_to_point_delay_cost[inet]
					[net_pin] = -1;

				    point_to_point_timing_cost[inet][net_pin]
					=
					temp_point_to_point_timing_cost[inet]
					[net_pin];
				    temp_point_to_point_timing_cost[inet]
					[net_pin] = -1;
				}
			}
		    else
			{	/*this net is being driven by a moved block, recompute */
			    /*all point to point connections on this net. */
			    for(ipin = 1; ipin <= net[inet].num_sinks; ipin++)
				{

				    point_to_point_delay_cost[inet][ipin] =
					temp_point_to_point_delay_cost[inet]
					[ipin];
				    temp_point_to_point_delay_cost[inet][ipin]
					= -1;

				    point_to_point_timing_cost[inet][ipin] =
					temp_point_to_point_timing_cost[inet]
					[ipin];
				    temp_point_to_point_timing_cost[inet]
					[ipin] = -1;
				}
			}
		}
	}
}


static void
comp_delta_td_cost(int b_from,
		   int b_to,
		   int num_of_pins,
		   float *delta_timing,
		   float *delta_delay)
{

    /*a net that is being driven by a moved block must have all of its  */
    /*sink timing costs recomputed. A net that is driving a moved block */
    /*must only have the timing cost on the connection driving the input */
    /*pin computed */

    int inet, k, net_pin, ipin;
    float delta_timing_cost, delta_delay_cost, temp_delay;

    delta_timing_cost = 0.;
    delta_delay_cost = 0.;


    for(k = 0; k < num_of_pins; k++)
	{
	    inet = block[b_from].nets[k];

	    if(inet == OPEN)
		continue;

	    if(net[inet].is_global)
		continue;

	    net_pin = net_pin_index[b_from][k];

	    if(net_pin != 0)
		{		/*this net is driving a moved block               */

		    /*if this net is being driven by a block that has moved, we do not  */
		    /*need to compute the change in the timing cost (here) since it will */
		    /*be computed in the fanout of the net on  the driving block, also  */
		    /*computing it here would double count the change, and mess up the  */
		    /*delta_timing_cost value */
		    if(net[inet].node_block[0] != b_to
		       && net[inet].node_block[0] != b_from)
			{
			    temp_delay =
				comp_td_point_to_point_delay(inet, net_pin);

			    temp_point_to_point_delay_cost[inet][net_pin] =
				temp_delay;
			    temp_point_to_point_timing_cost[inet][net_pin] =
				timing_place_crit[inet][net_pin] * temp_delay;

			    delta_delay_cost +=
				temp_point_to_point_delay_cost[inet][net_pin]
				- point_to_point_delay_cost[inet][net_pin];

			    delta_timing_cost +=
				temp_point_to_point_timing_cost[inet][net_pin]
				- point_to_point_timing_cost[inet][net_pin];
			}
		}
	    else
		{		/*this net is being driven by a moved block, recompute */
		    /*all point to point connections on this net. */
		    for(ipin = 1; ipin <= net[inet].num_sinks; ipin++)
			{
			    temp_delay =
				comp_td_point_to_point_delay(inet, ipin);

			    temp_point_to_point_delay_cost[inet][ipin] =
				temp_delay;
			    temp_point_to_point_timing_cost[inet][ipin] =
				timing_place_crit[inet][ipin] * temp_delay;

			    delta_delay_cost +=
				temp_point_to_point_delay_cost[inet][ipin] -
				point_to_point_delay_cost[inet][ipin];

			    delta_timing_cost +=
				temp_point_to_point_timing_cost[inet][ipin] -
				point_to_point_timing_cost[inet][ipin];
			}
		}
	}

    if(b_to != EMPTY)
	{
	    for(k = 0; k < num_of_pins; k++)
		{
		    inet = block[b_to].nets[k];

		    if(inet == OPEN)
			continue;

		    if(net[inet].is_global)
			continue;

		    net_pin = net_pin_index[b_to][k];

		    if(net_pin != 0)
			{	/*this net is driving a moved block */

			    /*if this net is being driven by a block that has moved, we do not */
			    /*need to compute the change in the timing cost (here) since it was */
			    /*computed in the fanout of the net on  the driving block, also    */
			    /*computing it here would double count the change, and mess up the */
			    /*delta_timing_cost value */
			    if(net[inet].node_block[0] != b_to
			       && net[inet].node_block[0] != b_from)
				{
				    temp_delay =
					comp_td_point_to_point_delay(inet,
								     net_pin);

				    temp_point_to_point_delay_cost[inet]
					[net_pin] = temp_delay;
				    temp_point_to_point_timing_cost[inet]
					[net_pin] =
					timing_place_crit[inet][net_pin] *
					temp_delay;

				    delta_delay_cost +=
					temp_point_to_point_delay_cost[inet]
					[net_pin] -
					point_to_point_delay_cost[inet]
					[net_pin];
				    delta_timing_cost +=
					temp_point_to_point_timing_cost[inet]
					[net_pin] -
					point_to_point_timing_cost[inet]
					[net_pin];
				}
			}
		    else
			{	/*this net is being driven by a moved block, recompute */
			    /*all point to point connections on this net. */
			    for(ipin = 1; ipin <= net[inet].num_sinks; ipin++)
				{

				    temp_delay =
					comp_td_point_to_point_delay(inet,
								     ipin);

				    temp_point_to_point_delay_cost[inet][ipin]
					= temp_delay;
				    temp_point_to_point_timing_cost[inet]
					[ipin] =
					timing_place_crit[inet][ipin] *
					temp_delay;


				    delta_delay_cost +=
					temp_point_to_point_delay_cost[inet]
					[ipin] -
					point_to_point_delay_cost[inet][ipin];
				    delta_timing_cost +=
					temp_point_to_point_timing_cost[inet]
					[ipin] -
					point_to_point_timing_cost[inet]
					[ipin];
				}
			}
		}
	}

    *delta_timing = delta_timing_cost;
    *delta_delay = delta_delay_cost;
}

static void
comp_td_costs(float *timing_cost,
	      float *connection_delay_sum)
{
    /*computes the cost (from scratch) due to the delays and criticalities*
     *on all point to point connections, we define the timing cost of     *
     *each connection as criticality*delay */

    int inet, ipin;
    float loc_timing_cost, loc_connection_delay_sum, temp_delay_cost,
	temp_timing_cost;

    loc_timing_cost = 0.;
    loc_connection_delay_sum = 0.;

    for(inet = 0; inet < num_nets; inet++)
	{			/* for each net ... */
	    if(net[inet].is_global == FALSE)
		{		/* Do only if not global. */

		    for(ipin = 1; ipin <= net[inet].num_sinks; ipin++)
			{

			    temp_delay_cost =
				comp_td_point_to_point_delay(inet, ipin);
			    temp_timing_cost =
				temp_delay_cost *
				timing_place_crit[inet][ipin];

			    loc_connection_delay_sum += temp_delay_cost;
			    point_to_point_delay_cost[inet][ipin] =
				temp_delay_cost;
			    temp_point_to_point_delay_cost[inet][ipin] = -1;	/*undefined */

			    point_to_point_timing_cost[inet][ipin] =
				temp_timing_cost;
			    temp_point_to_point_timing_cost[inet][ipin] = -1;	/*undefined */
			    loc_timing_cost += temp_timing_cost;
			}
		}
	}
    *timing_cost = loc_timing_cost;
    *connection_delay_sum = loc_connection_delay_sum;
}


static float
comp_bb_cost(int method,
	     int place_cost_type,
	     int num_regions)
{

    /* Finds the cost from scratch.  Done only when the placement   *
     * has been radically changed (i.e. after initial placement).   *
     * Otherwise find the cost change incrementally.  If method     *
     * check is NORMAL, we find bounding boxes that are updateable  *
     * for the larger nets.  If method is CHECK, all bounding boxes *
     * are found via the non_updateable_bb routine, to provide a    *
     * cost which can be used to check the correctness of the       *
     * other routine.                                               */

    int i, j, k;
    float cost;