place.c

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

       place_algorithm == PATH_TIMING_DRIVEN_PLACE)
	{
	    /*in this case we redefine delta_c as a combination of timing and bb.  *
	     *additionally, we normalize all values, therefore delta_c is in       *
	     *relation to 1*/

	    comp_delta_td_cost(b_from, b_to, num_of_pins, &timing_delta_c,
			       &delay_delta_c);

	    delta_c =
		(1 - timing_tradeoff) * bb_delta_c * inverse_prev_bb_cost +
		timing_tradeoff * timing_delta_c * inverse_prev_timing_cost;
	}
    else
	{
	    delta_c = bb_delta_c;
	}


    keep_switch = assess_swap(delta_c, t);

    /* 1 -> move accepted, 0 -> rejected. */

    if(keep_switch)
	{
	    *cost = *cost + delta_c;
	    *bb_cost = *bb_cost + bb_delta_c;


	    if(place_algorithm == NET_TIMING_DRIVEN_PLACE ||
	       place_algorithm == PATH_TIMING_DRIVEN_PLACE)
		{
		    /*update the point_to_point_timing_cost and point_to_point_delay_cost 
		     * values from the temporary values */
		    *timing_cost = *timing_cost + timing_delta_c;
		    *delay_cost = *delay_cost + delay_delta_c;

		    update_td_cost(b_from, b_to, num_of_pins);
		}

	    /* update net cost functions and reset flags. */

	    bb_index = 0;

	    for(k = 0; k < num_nets_affected; k++)
		{
		    inet = nets_to_update[k];

		    /* If we swapped two blocks connected to the same net, its bounding box *
		     * doesn't change.                                                      */

		    if(net_block_moved[k] == FROM_AND_TO)
			{
			    temp_net_cost[inet] = -1;
			    continue;
			}

		    bb_coords[inet] = bb_coord_new[bb_index];
		    if(net[inet].num_sinks >= SMALL_NET)
			bb_num_on_edges[inet] = bb_edge_new[bb_index];

		    bb_index++;

		    net_cost[inet] = temp_net_cost[inet];
		    temp_net_cost[inet] = -1;
		}

	    /* Update fb data structures since we kept the move. */
	    /* Swap physical location */
	    grid[x_to][y_to].blocks[z_to] = b_from;
	    grid[x_from][y_from].blocks[z_from] = b_to;

	    if(EMPTY == b_to)
		{		/* Moved to an empty location */
		    grid[x_to][y_to].usage++;
		    grid[x_from][y_from].usage--;
		}
	}

    else
	{			/* Move was rejected.  */

	    /* Reset the net cost function flags first. */
	    for(k = 0; k < num_nets_affected; k++)
		{
		    inet = nets_to_update[k];
		    temp_net_cost[inet] = -1;
		}

	    /* Restore the block data structures to their state before the move. */
	    block[b_from].x = x_from;
	    block[b_from].y = y_from;
	    block[b_from].z = z_from;
	    if(b_to != EMPTY)
		{
		    block[b_to].x = x_to;
		    block[b_to].y = y_to;
		    block[b_to].z = z_to;
		}

	    /* Restore the region occupancies to their state before the move. */
	    if(place_cost_type == NONLINEAR_CONG)
		{
		    restore_region_occ(old_region_occ_x, old_region_occ_y,
				       num_regions);
		}
	}

    return (keep_switch);
}


static void
save_region_occ(float **old_region_occ_x,
		float **old_region_occ_y,
		int num_regions)
{

    /* Saves the old occupancies of the placement subregions in case the  *
     * current move is not accepted.  Used only for NONLINEAR_CONG.       */

    int i, j;

    for(i = 0; i < num_regions; i++)
	{
	    for(j = 0; j < num_regions; j++)
		{
		    old_region_occ_x[i][j] = place_region_x[i][j].occupancy;
		    old_region_occ_y[i][j] = place_region_y[i][j].occupancy;
		}
	}
}


static void
restore_region_occ(float **old_region_occ_x,
		   float **old_region_occ_y,
		   int num_regions)
{

    /* Restores the old occupancies of the placement subregions when the  *
     * current move is not accepted.  Used only for NONLINEAR_CONG.       */

    int i, j;

    for(i = 0; i < num_regions; i++)
	{
	    for(j = 0; j < num_regions; j++)
		{
		    place_region_x[i][j].occupancy = old_region_occ_x[i][j];
		    place_region_y[i][j].occupancy = old_region_occ_y[i][j];
		}
	}
}


static int
find_affected_nets(int *nets_to_update,
		   int *net_block_moved,
		   int b_from,
		   int b_to,
		   int num_of_pins)
{

    /* Puts a list of all the nets connected to b_from and b_to into          *
     * nets_to_update.  Returns the number of affected nets.  Net_block_moved *
     * is either FROM, TO or FROM_AND_TO -- the block connected to this net   *
     * that has moved.                                                        */

    int k, inet, affected_index, count;

    affected_index = 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;

	    /* This is here in case the same block connects to a net twice. */

	    if(temp_net_cost[inet] > 0.)
		continue;

	    nets_to_update[affected_index] = inet;
	    net_block_moved[affected_index] = FROM;
	    affected_index++;
	    temp_net_cost[inet] = 1.;	/* Flag to say we've marked this net. */
	}

    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;

		    if(temp_net_cost[inet] > 0.)
			{	/* Net already marked. */
			    for(count = 0; count < affected_index; count++)
				{
				    if(nets_to_update[count] == inet)
					{
					    if(net_block_moved[count] == FROM)
						net_block_moved[count] =
						    FROM_AND_TO;
					    break;
					}
				}

#ifdef DEBUG
			    if(count > affected_index)
				{
				    printf
					("Error in find_affected_nets -- count = %d,"
					 " affected index = %d.\n", count,
					 affected_index);
				    exit(1);
				}
#endif
			}

		    else
			{	/* Net not marked yet. */

			    nets_to_update[affected_index] = inet;
			    net_block_moved[affected_index] = TO;
			    affected_index++;
			    temp_net_cost[inet] = 1.;	/* Flag means we've  marked net. */
			}
		}
	}

    return (affected_index);
}


static boolean
find_to(int x_from,
	int y_from,
	t_type_ptr type,
	float rlim,
	int *x_lookup,
	int *x_to,
	int *y_to)
{

    /* Returns the point to which I want to swap, properly range limited. 
     * rlim must always be between 1 and nx (inclusive) for this routine  
     * to work.  Assumes that a column only contains blocks of the same type.
     */

    int x_rel, y_rel, iside, iplace, rlx, rly, min_x, max_x, min_y, max_y;
    int num_col_same_type, i, j;

    rlx = min(nx, rlim);	/* Only needed when nx < ny. */
    rly = min(ny, rlim);	/* Added rly for aspect_ratio != 1 case. */

    min_x = max(1, x_from - rlx);
    max_x = min(nx, x_from + rlx);
    min_y = max(1, y_from - rly);
    max_y = min(ny, y_from + rly);

    num_col_same_type = 0;
    j = 0;
    if(type != IO_TYPE)
	{
	    for(i = min_x; i <= max_x; i++)
		{
		    if(grid[i][1].type == type)
			{
			    num_col_same_type++;
			    x_lookup[j] = i;
			    j++;
			}
		}
	    assert(num_col_same_type != 0);
	    if(num_col_same_type == 1 &&
	       ((((max_y - min_y) / type->height) - 1) <= 0
		|| type->height > (ny / 2)))
		return FALSE;
	}

#ifdef DEBUG
    if(rlx < 1 || rlx > nx)
	{
	    printf("Error in find_to: rlx = %d\n", rlx);
	    exit(1);
	}
#endif

    do
	{			/* Until (x_to, y_to) different from (x_from, y_from) */
	    if(type == IO_TYPE)
		{		/* io_block to be moved. */
		    if(rlx >= nx)
			{
			    iside = my_irand(3);
			    /*                              *
			     *       +-----1----+           *
			     *       |          |           *
			     *       |          |           *
			     *       0          2           *
			     *       |          |           *
			     *       |          |           *
			     *       +-----3----+           *
			     *                              */
			    switch (iside)
				{
				case 0:
				    iplace = my_irand(ny - 1) + 1;
				    *x_to = 0;
				    *y_to = iplace;
				    break;
				case 1:
				    iplace = my_irand(nx - 1) + 1;
				    *x_to = iplace;
				    *y_to = ny + 1;
				    break;
				case 2:
				    iplace = my_irand(ny - 1) + 1;
				    *x_to = nx + 1;
				    *y_to = iplace;
				    break;
				case 3:
				    iplace = my_irand(nx - 1) + 1;
				    *x_to = iplace;
				    *y_to = 0;
				    break;
				default:
				    printf
					("Error in find_to.  Unexpected io swap location.\n");
				    exit(1);
				}
			}
		    else
			{	/* rlx is less than whole chip */
			    if(x_from == 0)
				{
				    iplace = my_irand(2 * rly);
				    *y_to = y_from - rly + iplace;
				    *x_to = x_from;
				    if(*y_to > ny)
					{
					    *y_to = ny + 1;
					    *x_to = my_irand(rlx - 1) + 1;
					}
				    else if(*y_to < 1)
					{
					    *y_to = 0;
					    *x_to = my_irand(rlx - 1) + 1;
					}
				}
			    else if(x_from == nx + 1)
				{
				    iplace = my_irand(2 * rly);
				    *y_to = y_from - rly + iplace;
				    *x_to = x_from;
				    if(*y_to > ny)
					{
					    *y_to = ny + 1;
					    *x_to = nx - my_irand(rlx - 1);
					}
				    else if(*y_to < 1)
					{
					    *y_to = 0;
					    *x_to = nx - my_irand(rlx - 1);
					}
				}
			    else if(y_from == 0)
				{
				    iplace = my_irand(2 * rlx);
				    *x_to = x_from - rlx + iplace;
				    *y_to = y_from;
				    if(*x_to > nx)
					{
					    *x_to = nx + 1;
					    *y_to = my_irand(rly - 1) + 1;
					}
				    else if(*x_to < 1)
					{
					    *x_to = 0;
					    *y_to = my_irand(rly - 1) + 1;
					}
				}
			    else
				{	/* *y_from == ny + 1 */
				    iplace = my_irand(2 * rlx);
				    *x_to = x_from - rlx + iplace;
				    *y_to = y_from;
				    if(*x_to > nx)
					{
					    *x_to = nx + 1;
					    *y_to = ny - my_irand(rly - 1);
					}
				    else if(*x_to < 1)
					{
					    *x_to = 0;
					    *y_to = ny - my_irand(rly - 1);
					}
				}
			}	/* End rlx if */
		}		/* end type if */
	    else
		{
		    x_rel = my_irand(num_col_same_type - 1);
		    y_rel =
			my_irand(max
				 (0, ((max_y - min_y) / type->height) - 1));
		    *x_to = x_lookup[x_rel];
		    *y_to = min_y + y_rel * type->height;
		    *y_to = (*y_to) - grid[*x_to][*y_to].offset;	/* align it */
		    assert(*x_to >= 1 && *x_to <= nx);
		    assert(*y_to >= 1 && *y_to <= ny);
		}
	}
    while((x_from == *x_to) && (y_from == *y_to));

#ifdef DEBUG
    if(*x_to < 0 || *x_to > nx + 1 || *y_to < 0 || *y_to > ny + 1)
	{
	    printf("Error in routine find_to:  (x_to,y_to) = (%d,%d)\n",
		   *x_to, *y_to);
	    exit(1);
	}
#endif
    assert(type == grid[*x_to][*y_to].type);
    return TRUE;
}


static int
assess_swap(float delta_c,
	    float t)
{

    /* Returns: 1 -> move accepted, 0 -> rejected. */

    int accept;
    float prob_fac, fnum;

    if(delta_c <= 0)
	{

#ifdef SPEC			/* Reduce variation in final solution due to round off */
	    fnum = my_frand();
#endif

	    accept = 1;
	    return (accept);
	}

    if(t == 0.)
	return (0);

    fnum = my_frand();
    prob_fac = exp(-delta_c / t);
    if(prob_fac > fnum)
	{
	    accept = 1;
	}
    else
	{
	    accept = 0;
	}
    return (accept);
}