rr_graph.c

VPR布局布线源码

					  nodes_per_chan, Fc, directionality);
	}
    else
	{
	    load_uniform_switch_pattern(Type,
					tracks_connected_to_pin,
					num_phys_pins,
					pin_num_ordering,
					side_ordering,
					offset_ordering,
					nodes_per_chan, Fc, directionality);
	}
    check_all_tracks_reach_pins(Type, tracks_connected_to_pin,
				nodes_per_chan, Fc, pin_type);

    /* Free all temporary storage. */
    free_matrix(num_dir, 0, Type->height - 1, 0, sizeof(int));
    free_matrix3(dir_list, 0, Type->height - 1, 0, 3, 0, sizeof(int));
    free_matrix(num_done_per_dir, 0, Type->height - 1, 0, sizeof(int));
    free(pin_num_ordering);
    free(side_ordering);
    free(offset_ordering);

    return tracks_connected_to_pin;
}




static void
load_uniform_switch_pattern(IN t_type_ptr type,
			    INOUT int ****tracks_connected_to_pin,
			    IN int num_phys_pins,
			    IN int *pin_num_ordering,
			    IN int *side_ordering,
			    IN int *offset_ordering,
			    IN int nodes_per_chan,
			    IN int Fc,
			    enum e_directionality directionality)
{

    /* Loads the tracks_connected_to_pin array with an even distribution of     *
     * switches across the tracks for each pin.  For example, each pin connects *
     * to every 4.3rd track in a channel, with exactly which tracks a pin       *
     * connects to staggered from pin to pin.                                   */

    int i, j, ipin, iside, ioff, itrack, k;
    float f_track, fc_step;
    int group_size;
    float step_size;

    /* Uni-directional drive is implemented to ensure no directional bias and this means 
     * two important comments noted below                                                */
    /* 1. Spacing should be (W/2)/(Fc/2), and step_size should be spacing/(num_phys_pins),
     *    and lay down 2 switches on an adjacent pair of tracks at a time to ensure
     *    no directional bias. Basically, treat W (even) as W/2 pairs of tracks, and
     *    assign switches to a pair at a time. Can do this because W is guaranteed to 
     *    be even-numbered; however same approach cannot be applied to Fc_out pattern
     *    when L > 1 and W <> 2L multiple. 
     *
     * 2. This generic pattern should be considered the tileable physical layout,
     *    meaning all track # here are physical #'s,
     *    so later must use vpr_to_phy conversion to find actual logical #'s to connect.
     *    This also means I will not use get_output_block_companion_track to ensure
     *    no bias, since that describes a logical # -> that would confuse people.  */

    step_size = (float)nodes_per_chan / (float)(Fc * num_phys_pins);

    if(directionality == BI_DIRECTIONAL)
	{
	    group_size = 1;
	}
    else
	{
	    assert(directionality == UNI_DIRECTIONAL);
	    group_size = 2;
	}

    assert((nodes_per_chan % group_size == 0) && (Fc % group_size == 0));

    fc_step = (float)nodes_per_chan / (float)Fc;

    for(i = 0; i < num_phys_pins; i++)
	{
	    ipin = pin_num_ordering[i];
	    iside = side_ordering[i];
	    ioff = offset_ordering[i];

	    /* Bi-directional treats each track separately, uni-directional works with pairs of tracks */
	    for(j = 0; j < (Fc / group_size); j++)
		{
		    f_track = (i * step_size) + (j * fc_step);
		    itrack = ((int)f_track) * group_size;

		    /* Catch possible floating point round error */
		    itrack = min(itrack, nodes_per_chan - group_size);

		    /* Assign the group of tracks for the Fc pattern */
		    for(k = 0; k < group_size; ++k)
			{
			    tracks_connected_to_pin[ipin][ioff][iside]
				[group_size * j + k] = itrack + k;
			}
		}
	}
}

static void
load_perturbed_switch_pattern(IN t_type_ptr type,
			      INOUT int ****tracks_connected_to_pin,
			      IN int num_phys_pins,
			      IN int *pin_num_ordering,
			      IN int *side_ordering,
			      IN int *offset_ordering,
			      IN int nodes_per_chan,
			      IN int Fc,
			      enum e_directionality directionality)
{

    /* Loads the tracks_connected_to_pin array with an unevenly distributed     *
     * set of switches across the channel.  This is done for inputs when        *
     * Fc_input = Fc_output to avoid creating "pin domains" -- certain output   *
     * pins being able to talk only to certain input pins because their switch  *
     * patterns exactly line up.  Distribute Fc/2 + 1 switches over half the    *
     * channel and Fc/2 - 1 switches over the other half to make the switch     * 
     * pattern different from the uniform one of the outputs.  Also, have half  *
     * the pins put the "dense" part of their connections in the first half of  *
     * the channel and the other half put the "dense" part in the second half,  *
     * to make sure each track can connect to about the same number of ipins.   */

    int i, j, ipin, iside, itrack, ihalf, iconn, ioff;
    int Fc_dense, Fc_sparse, Fc_half[2];
    float f_track, spacing_dense, spacing_sparse, spacing[2];
    float step_size;

    assert(directionality == BI_DIRECTIONAL);

    step_size = (float)nodes_per_chan / (float)(Fc * num_phys_pins);

    Fc_dense = (Fc / 2) + 1;
    Fc_sparse = Fc - Fc_dense;	/* Works for even or odd Fc */

    spacing_dense = (float)nodes_per_chan / (float)(2 * Fc_dense);
    spacing_sparse = (float)nodes_per_chan / (float)(2 * Fc_sparse);

    for(i = 0; i < num_phys_pins; i++)
	{
	    ipin = pin_num_ordering[i];
	    iside = side_ordering[i];
	    ioff = offset_ordering[i];

	    /* Flip every pin to balance switch density */
	    spacing[i % 2] = spacing_dense;
	    Fc_half[i % 2] = Fc_dense;
	    spacing[(i + 1) % 2] = spacing_sparse;
	    Fc_half[(i + 1) % 2] = Fc_sparse;

	    f_track = i * step_size;	/* Start point.  Staggered from pin to pin */
	    iconn = 0;

	    for(ihalf = 0; ihalf < 2; ihalf++)
		{		/* For both dense and sparse halves. */
		    for(j = 0; j < Fc_half[ihalf]; ++j)
			{
			    itrack = (int)f_track;

			    /* Can occasionally get wraparound due to floating point rounding. 
				   This is okay because the starting position > 0 when this occurs
				   so connection is valid and fine */
			    itrack = itrack % nodes_per_chan;
			    tracks_connected_to_pin[ipin][ioff][iside][iconn]
				= itrack;

			    f_track += spacing[ihalf];
			    iconn++;
			}
		}
	}			/* End for all physical pins. */
}


static void
check_all_tracks_reach_pins(t_type_ptr type,
			    int ****tracks_connected_to_pin,
			    int nodes_per_chan,
			    int Fc,
			    enum e_pin_type ipin_or_opin)
{

    /* Checks that all tracks can be reached by some pin.   */

    int iconn, iside, itrack, ipin, ioff;
    int *num_conns_to_track;	/* [0..nodes_per_chan-1] */

	assert(nodes_per_chan > 0);    

    num_conns_to_track = (int *)my_calloc(nodes_per_chan, sizeof(int));

    for(ipin = 0; ipin < type->num_pins; ipin++)
	{
	    for(ioff = 0; ioff < type->height; ioff++)
		{
		    for(iside = 0; iside < 4; iside++)
			{
			    if(tracks_connected_to_pin[ipin][ioff][iside][0]
			       != OPEN)
				{	/* Pin exists */
				    for(iconn = 0; iconn < Fc; iconn++)
					{
					    itrack =
						tracks_connected_to_pin[ipin]
						[ioff][iside][iconn];
					    num_conns_to_track[itrack]++;
					}
				}
			}
		}
	}

	for(itrack = 0; itrack < nodes_per_chan; itrack++)
	{
	    if(num_conns_to_track[itrack] <= 0)
		{
		    printf
			("Warning (check_all_tracks_reach_pins):  track %d does not \n"
			 "\tconnect to any FB ", itrack);

		    if(ipin_or_opin == DRIVER)
			printf("OPINs.\n");
		    else
			printf("IPINs.\n");
		}
	}

    free(num_conns_to_track);
}

/* Allocates and loads the track to ipin lookup for each physical grid type. This
 * is the same information as the ipin_to_track map but accessed in a different way. */

static struct s_ivec ***
alloc_and_load_track_to_pin_lookup(IN int ****pin_to_track_map,
				   IN int Fc,
				   IN int height,
				   IN int num_pins,
				   IN int nodes_per_chan)
{
    int ipin, iside, itrack, iconn, ioff, pin_counter;
    struct s_ivec ***track_to_pin_lookup;

    /* [0..nodes_per_chan-1][0..height][0..3].  For each track number it stores a vector  
     * for each of the four sides.  x-directed channels will use the TOP and   
     * BOTTOM vectors to figure out what clb input pins they connect to above  
     * and below them, respectively, while y-directed channels use the LEFT    
     * and RIGHT vectors.  Each vector contains an nelem field saying how many 
     * ipins it connects to.  The list[0..nelem-1] array then gives the pin    
     * numbers.                                                                */

    /* Note that a clb pin that connects to a channel on its RIGHT means that  *
     * that channel connects to a clb pin on its LEFT.  The convention used    *
     * here is always in the perspective of the CLB                            */

    if(num_pins < 1)
	{
	    return NULL;
	}

    /* Alloc and zero the the lookup table */
    track_to_pin_lookup =
	(struct s_ivec ***)alloc_matrix3(0, nodes_per_chan - 1, 0,
					 height - 1, 0, 3,
					 sizeof(struct s_ivec));
    for(itrack = 0; itrack < nodes_per_chan; itrack++)
	{
	    for(ioff = 0; ioff < height; ioff++)
		{
		    for(iside = 0; iside < 4; iside++)
			{
			    track_to_pin_lookup[itrack][ioff][iside].nelem =
				0;
			    track_to_pin_lookup[itrack][ioff][iside].list =
				NULL;
			}
		}
	}

    /* Counting pass.  */
    for(ipin = 0; ipin < num_pins; ipin++)
	{
	    for(ioff = 0; ioff < height; ioff++)
		{
		    for(iside = 0; iside < 4; iside++)
			{
			    if(pin_to_track_map[ipin][ioff][iside][0] == OPEN)
				continue;

			    for(iconn = 0; iconn < Fc; iconn++)
				{
				    itrack =
					pin_to_track_map[ipin][ioff][iside]
					[iconn];
				    track_to_pin_lookup[itrack][ioff][iside].
					nelem++;
				}
			}
		}
	}

    /* Allocate space.  */
    for(itrack = 0; itrack < nodes_per_chan; itrack++)
	{
	    for(ioff = 0; ioff < height; ioff++)
		{
		    for(iside = 0; iside < 4; iside++)
			{
			    track_to_pin_lookup[itrack][ioff][iside].list = NULL;	/* Defensive code */
			    if(track_to_pin_lookup[itrack][ioff][iside].
			       nelem != 0)
				{
				    track_to_pin_lookup[itrack][ioff][iside].
					list =
					(int *)
					my_malloc(track_to_pin_lookup[itrack]
						  [ioff][iside].nelem *
						  sizeof(int));
				    track_to_pin_lookup[itrack][ioff][iside].
					nelem = 0;
				}
			}
		}
	}

    /* Loading pass. */
    for(ipin = 0; ipin < num_pins; ipin++)
	{
	    for(ioff = 0; ioff < height; ioff++)
		{
		    for(iside = 0; iside < 4; iside++)
			{
			    if(pin_to_track_map[ipin][ioff][iside][0] == OPEN)
				continue;

			    for(iconn = 0; iconn < Fc; iconn++)
				{
				    itrack =
					pin_to_track_map[ipin][ioff][iside]
					[iconn];
				    pin_counter =
					track_to_pin_lookup[itrack][ioff]
					[iside].nelem;
				    track_to_pin_lookup[itrack][ioff][iside].
					list[pin_counter] = ipin;
				    track_to_pin_lookup[itrack][ioff][iside].
					nelem++;
				}
			}
		}
	}

    return track_to_pin_lookup;
}

/* A utility routine to dump the contents of the routing resource graph   *
 * (everything -- connectivity, occupancy, cost, etc.) into a file.  Used *
 * only for debugging.                                                    */
void
dump_rr_graph(IN const char *file_name)
{

    int inode;
    FILE *fp;

    fp = my_fopen(file_name, "w");

    for(inode = 0; inode < num_rr_nodes; inode++)
	{
	    print_rr_node(fp, rr_node, inode);
	    fprintf(fp, "\n");
	}

#if 0
    fprintf(fp, "\n\n%d rr_indexed_data entries.\n\n", num_rr_indexed_data);

    for(index = 0; index < num_rr_indexed_data; index++)
	{
	    print_rr_indexed_data(fp, index);
	    fprintf(fp, "\n");
	}
#endif

    fclose(fp);
}


/* Prints all the data about node inode to file fp.                    */
static void
print_rr_node(FILE * fp,
	      t_rr_node * rr_node,
	      int inode)
{

    static const char *name_type[] = {
	"SOURCE", "SINK", "IPIN", "OPIN", "CHANX", "CHANY"
    };
    static const char *direction_name[] = {
	"OPEN", "INC_DIRECTION", "DEC_DIRECTION", "BI_DIRECTION"
    };
    static const char *drivers_name[] = {
	"OPEN", "MULTI_BUFFER", "MULTI_MUXED", "MULTI_MERGED", "SINGLE"
    };

    t_rr_type rr_type;
    int iconn;

    rr_type = rr_node[inode].type;

    /* Make sure we don't overrun const arrays */
    assert(rr_type < (sizeof(name_type) / sizeof(char *)));
    assert((rr_node[inode].direction + 1) <
	   (sizeof(direction_name) / sizeof(char *)));
    assert((rr_node[inode].drivers + 1) <
	   (sizeof(drivers_name) / sizeof(char *)));

    fprintf(fp, "Node: %d %s ", inode, name_type[rr_type]);
    if((rr_node[inode].xlow == rr_node[inode].xhigh) &&
       (rr_node[inode].ylow == rr_node[inode].yhigh))
	{
	    fprintf(fp, "(%d, %d) ", rr_node[inode].xlow,
		    rr_node[inode].ylow);
	}
    else
	{
	    fprintf(fp, "(%d, %d) to (%d, %d) ", rr_node[inode].xlow,
		    rr_node[inode].ylow, rr_node[inode].xhigh,
		    rr_node[inode].yhigh);
	}
    fprintf(fp, "Ptc_num: %d ", rr_node[inode].ptc_num);
    fprintf(fp, "Direction: %s ",
	    direction_name[rr_node[inode].direction + 1]);
    fprintf(fp, "Drivers: %s ", drivers_name[rr_node[inode].drivers + 1]);
    fprintf(fp, "\n");

    fprintf(fp, "%d edge(s):", rr_node[inode].num_edges);
    for(iconn = 0; iconn < rr_node[inode].num_edges; iconn++)
	fprintf(fp, " %d", rr_node[inode].edges[iconn]);
    fprintf(fp, "\n");

    fprintf(fp, "Switch types:");
    for(iconn = 0; iconn < rr_node[inode].num_edges; iconn++)
	fprintf(fp, " %d", rr_node[inode].switches[iconn]);
    fprintf(fp, "\n");

    fprintf(fp, "Occ: %d  Capacity: %d\n", rr_node[inode].occ,
	    rr_node[inode].capacity);
    fprintf(fp, "R: %g  C: %g\n", rr_node[inode].R, rr_node[inode].C);
    fprintf(fp, "Cost_index: %d\n", rr_node[inode].cost_index);
}


/* Prints all the rr_indexed_data of index to file fp.   */
void
print_rr_indexed_data(FILE * fp,
		      int index)
{

    fprintf(fp, "Index: %d\n", index);

    fprintf(fp, "ortho_cost_index: %d  ",
	    rr_indexed_data[index].ortho_cost_index);
    fprintf(fp, "base_cost: %g  ", rr_indexed_data[index].saved_base_cost);
    fprintf(fp, "saved_base_cost: %g\n",
	    rr_indexed_data[index].save