rr_graph2.c

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

    int group_start, group_size;
    int vpr_offset_for_first_phy_track;
    int vpr_offset, phy_offset;
    int phy_track;
    int fac;

    /* Assign in pairs if unidir. */
    fac = 1;
    if(UNI_DIRECTIONAL == directionality)
	{
	    fac = 2;
	}

    group_start = seg_details[itrack].group_start;
    group_size = seg_details[itrack].group_size;

    vpr_offset_for_first_phy_track =
	(chan_num + seg_num - 1) % (group_size / fac);
    vpr_offset = (itrack - group_start) / fac;
    phy_offset =
	(vpr_offset_for_first_phy_track + vpr_offset) % (group_size / fac);
    phy_track =
	group_start + (fac * phy_offset) + (itrack - group_start) % fac;

    return phy_track;
}



short *****
alloc_sblock_pattern_lookup(IN int nx,
			    IN int ny,
			    IN int nodes_per_chan)
{
    int i, j, from_side, to_side, itrack, items;
    short *****result;
    short *****i_list;
    short ****j_list;
    short ***from_list;
    short **to_list;
    short *track_list;

    /* loading up the sblock connection pattern matrix. It's a huge matrix because
     * for nonquantized W, it's impossible to make simple permutations to figure out
     * where muxes are and how to connect to them such that their sizes are balanced */

    /* Do chunked allocations to make freeing easier, speed up malloc and free, and
     * reduce some of the memory overhead. Could use fewer malloc's but this way
     * avoids all considerations of pointer sizes and allignment. */

    /* Alloc each list of pointers in one go. items is a running product that increases
     * with each new dimension of the matrix. */
    items = 1;
    items *= (nx + 1);
    i_list = (short *****)my_malloc(sizeof(short ****) * items);
    items *= (ny + 1);
    j_list = (short ****)my_malloc(sizeof(short ***) * items);
    items *= (4);
    from_list = (short ***)my_malloc(sizeof(short **) * items);
    items *= (4);
    to_list = (short **)my_malloc(sizeof(short *) * items);
    items *= (nodes_per_chan);
    track_list = (short *)my_malloc(sizeof(short) * items);

    /* Build the pointer lists to form the multidimensional array */
    result = i_list;
    i_list += (nx + 1);		/* Skip forward nx+1 items */
    for(i = 0; i < (nx + 1); ++i)
	{

	    result[i] = j_list;
	    j_list += (ny + 1);	/* Skip forward ny+1 items */
	    for(j = 0; j < (ny + 1); ++j)
		{

		    result[i][j] = from_list;
		    from_list += (4);	/* Skip forward 4 items */
		    for(from_side = 0; from_side < 4; ++from_side)
			{

			    result[i][j][from_side] = to_list;
			    to_list += (4);	/* Skip forward 4 items */
			    for(to_side = 0; to_side < 4; ++to_side)
				{

				    result[i][j][from_side][to_side] =
					track_list;
				    track_list += (nodes_per_chan);	/* Skip forward nodes_per_chan items */
				    for(itrack = 0; itrack < nodes_per_chan;
					itrack++)
					{

					    /* Set initial value to be unset */
					    result[i][j][from_side][to_side]
						[itrack] = UN_SET;
					}
				}
			}
		}
	}

    /* This is the outer pointer to the full matrix */
    return result;
}


void
free_sblock_pattern_lookup(INOUT short *****sblock_pattern)
{
    /* This free function corresponds to the chunked matrix 
     * allocation above and there should only be one free
     * call for each dimension. */

    /* Free dimensions from the inner one, outwards so
     * we can still access them. The comments beside
     * each one indicate the corresponding name used when
     * allocating them. */
    free(****sblock_pattern);	/* track_list */
    free(***sblock_pattern);	/* to_list */
    free(**sblock_pattern);	/* from_list */
    free(*sblock_pattern);	/* j_list */
    free(sblock_pattern);	/* i_list */
}


void
load_sblock_pattern_lookup(IN int i,
			   IN int j,
			   IN int nodes_per_chan,
			   IN t_seg_details * seg_details,
			   IN int Fs,
			   IN enum e_switch_block_type switch_block_type,
			   INOUT short *****sblock_pattern)
{

    /* This routine loads a lookup table for sblock topology. The lookup table is huge
     * because the sblock varies from location to location. The i, j means the owning
     * location of the sblock under investigation. */

    int side_cw_incoming_wire_count, side_ccw_incoming_wire_count,
	opp_incoming_wire_count;
    int to_side, side, side_cw, side_ccw, side_opp, itrack;
    int Fs_per_side, chan, seg, chan_len, sb_seg;
    boolean is_core_sblock, is_corner_sblock, x_edge, y_edge;
    int *incoming_wire_label[4];
    int *wire_mux_on_track[4];
    int num_incoming_wires[4];
    int num_ending_wires[4];
    int num_wire_muxes[4];
    boolean skip, vert, pos_dir;
    enum e_direction dir;

    Fs_per_side = 1;
    if(Fs != -1)
	{
	    Fs_per_side = Fs / 3;
	}

    /* SB's have coords from (0, 0) to (nx, ny) */
    assert(i >= 0);
    assert(i <= nx);
    assert(j >= 0);
    assert(j <= ny);

    /* May 12 - 15, 2007
     *
     * I identify three types of sblocks in the chip: 1) The core sblock, whose special
     * property is that the number of muxes (and ending wires) on each side is the same (very useful
     * property, since it leads to a N-to-N assignment problem with ending wires). 2) The corner sblock
     * which is same as a L=1 core sblock with 2 sides only (again N-to-N assignment problem). 3) The
     * fringe / chip edge sblock which is most troublesome, as balance in each side of muxes is 
     * attainable but balance in the entire sblock is not. The following code first identifies the
     * incoming wires, which can be classified into incoming passing wires with sbox and incoming
     * ending wires (the word "incoming" is sometimes dropped for ease of discussion). It appropriately 
     * labels all the wires on each side by the following order: By the call to label_incoming_wires, 
     * which labels for one side, the order is such that the incoming ending wires (always with sbox) 
     * are labelled first 0,1,2,... p-1, then the incoming passing wires with sbox are labelled 
     * p,p+1,p+2,... k-1 (for total of k). By this convention, one can easily distinguish the ending
     * wires from the passing wires by checking a label against num_ending_wires variable. 
     *
     * After labelling all the incoming wires, this routine labels the muxes on the side we're currently
     * connecting to (iterated for four sides of the sblock), called the to_side. The label scheme is
     * the natural order of the muxes by their track #. Also we find the number of muxes.
     *
     * For each to_side, the total incoming wires that connect to the muxes on to_side 
     * come from three sides: side_1 (to_side's right), side_2 (to_side's left) and opp_side.
     * The problem of balancing mux size is then: considering all incoming passing wires
     * with sbox on side_1, side_2 and opp_side, how to assign them to the muxes on to_side
     * (with specified Fs) in a way that mux size is imbalanced by at most 1. I solve this
     * problem by this approach: the first incoming passing wire will connect to 0, 1, 2, 
     * ..., Fs_per_side - 1, then the next incoming passing wire will connect to 
     * Fs_per_side, Fs_per_side+1, ..., Fs_per_side*2-1, and so on. This consistent STAGGERING
     * ensures N-to-N assignment is perfectly balanced and M-to-N assignment is imbalanced by no
     * more than 1.
     *
     * For the sblock_pattern_init_mux_lookup lookup table, I will only need the lookup
     * table to remember the first/init mux to connect, since the convention is Fs_per_side consecutive
     * muxes to connect. Then how do I determine the order of the incoming wires? I use the labels
     * on side_1, then labels on side_2, then labels on opp_side. Effectively I listed all
     * incoming passing wires from the three sides, and order them to each make Fs_per_side
     * consecutive connections to muxes, and use % to rotate to keep imbalance at most 1. 
     */

    /* SB's range from (0, 0) to (nx, ny) */
    /* First find all four sides' incoming wires */
    x_edge = ((i < 1) || (i >= nx));
    y_edge = ((j < 1) || (j >= ny));

    is_corner_sblock = (x_edge && y_edge);
    is_core_sblock = (!x_edge && !y_edge);

    /* "Label" the wires around the switch block by connectivity. */
    for(side = 0; side < 4; ++side)
	{
	    /* Assume the channel segment doesn't exist. */
	    wire_mux_on_track[side] = NULL;
	    incoming_wire_label[side] = NULL;
	    num_incoming_wires[side] = 0;
	    num_ending_wires[side] = 0;
	    num_wire_muxes[side] = 0;

	    /* Skip the side and leave the zero'd value if the
	     * channel segment doesn't exist. */
	    skip = TRUE;
	    switch (side)
		{
		case TOP:
		    if(j < ny)
			{
			    skip = FALSE;
			};
		    break;
		case RIGHT:
		    if(i < nx)
			{
			    skip = FALSE;
			}
		    break;
		case BOTTOM:
		    if(j > 0)
			{
			    skip = FALSE;
			}
		    break;
		case LEFT:
		    if(i > 0)
			{
			    skip = FALSE;
			}
		    break;
		}
	    if(skip)
		{
		    continue;
		}

	    /* Figure out the channel and segment for a certain direction */
	    vert = ((side == TOP) || (side == BOTTOM));
	    pos_dir = ((side == TOP) || (side == RIGHT));
	    chan = (vert ? i : j);
	    sb_seg = (vert ? j : i);
	    seg = (pos_dir ? (sb_seg + 1) : sb_seg);
	    chan_len = (vert ? ny : nx);

	    /* Figure out all the tracks on a side that are ending and the
	     * ones that are passing through and have a SB. */
	    dir = (pos_dir ? DEC_DIRECTION : INC_DIRECTION);
	    incoming_wire_label[side] =
		label_incoming_wires(chan, seg, sb_seg, seg_details, chan_len,
				     dir, nodes_per_chan,
				     &num_incoming_wires[side],
				     &num_ending_wires[side]);

	    /* Figure out all the tracks on a side that are starting. */
	    dir = (pos_dir ? INC_DIRECTION : DEC_DIRECTION);
	    wire_mux_on_track[side] = label_wire_muxes(chan, seg,
						       seg_details, chan_len,
						       dir, nodes_per_chan,
						       &num_wire_muxes[side]);
	}

    for(to_side = 0; to_side < 4; to_side++)
	{
	    /* Can't do anything if no muxes on this side. */
	    if(0 == num_wire_muxes[to_side])
		{
		    continue;
		}

	    /* Figure out side rotations */
	    assert((TOP == 0) && (RIGHT == 1) && (BOTTOM == 2)
		   && (LEFT == 3));
	    side_cw = (to_side + 1) % 4;
	    side_opp = (to_side + 2) % 4;
	    side_ccw = (to_side + 3) % 4;

	    /* For the core sblock:
	     * The new order for passing wires should appear as
	     * 0,1,2..,scw-1, for passing wires with sbox on side_cw 
	     * scw,scw+1,...,sccw-1, for passing wires with sbox on side_ccw
	     * sccw,sccw+1,... for passing wires with sbox on side_opp.
	     * This way, I can keep the imbalance to at most 1.
	     *
	     * For the fringe sblocks, I don't distinguish between
	     * passing and ending wires so the above statement still holds
	     * if you replace "passing" by "incoming" */

	    side_cw_incoming_wire_count = 0;
	    if(incoming_wire_label[side_cw])
		{
		    for(itrack = 0; itrack < nodes_per_chan; itrack++)
			{
			    /* Ending wire, or passing wire with sbox. */
			    if(incoming_wire_label[side_cw][itrack] != UN_SET)
				{

				    if((is_corner_sblock || is_core_sblock) &&
				       (incoming_wire_label[side_cw][itrack] <
					num_ending_wires[side_cw]))
					{
					    /* The ending wires in core sblocks form N-to-N assignment 
					     * problem, so can use any pattern such as Wilton. This N-to-N 
					     * mapping depends on the fact that start points stagger across
					     * channels. */
					    assert(num_ending_wires[side_cw]
						   ==
						   num_wire_muxes[to_side]);
					    sblock_pattern[i][j][side_cw]
						[to_side][itrack] =
						get_simple_switch_block_track
						(side_cw, to_side,
						 incoming_wire_label[side_cw]
						 [itrack], switch_block_type,
						 num_wire_muxes[to_side]);

					}
				    else
					{

					    /* These are passing wires with sbox only for core sblocks
					     * or passing and ending wires (for fringe cases). */
					    sblock_pattern[i][j][side_cw]
						[to_side][itrack] =
						(side_cw_incoming_wire_count *
						 Fs_per_side) %
						num_wire_muxes[to_side];
					    side_cw_incoming_wire_count++;
					}
				}
			}
		}


	    side_ccw_incoming_wire_count = 0;
	    for(itrack = 0; itrack < nodes_per_chan; itrack++)
		{

		    /* if that side has no channel segment skip it */
		    if(incoming_wire_label[side_ccw] == NULL)
			break;

		    /* not ending wire nor passing wire with sbox */
		    if(incoming_wire_label[side_ccw][itrack] != UN_SET)
			{

			    if((is_corner_sblock || is_core_sblock) &&
			       (incoming_wire_label[side_ccw][itrack] <
				num_ending_wires[side_ccw]))
				{
				    /* The ending wires in core sblocks form N-to-N assignment problem, so can
				     * use any pattern such as Wilton */
				    assert(incoming_wire_label[side_ccw]
					   [itrack] <
					   num_wire_muxes[to_side]);
				    sblock_pattern[i][j][side_ccw][to_side]
					[itrack] =
					get_simple_switch_block_track
					(side_ccw, to_side,
					 incoming_wire_label[side_ccw]
					 [itrack], switch_block_type,
					 num_wire_muxes[to_side]);
				}
			    else
				{

				    /* These are passing wires with sbox only for core sblocks
				     * or passing and ending wires (for fringe cases). */
				    sblock_pattern[i][j][side_ccw][to_side]
					[itrack] =
					((side_ccw_incoming_wire_count +
					  side_cw_incoming_wire_count) *
					 Fs_per_side) %
					num_wire_muxes[to_side];
				    side_ccw_incoming_wire_count++;
				}
			}
		}


	    opp_incoming_wire_count = 0;
	    if(incoming_wire_label[side_opp])
		{
		    for(itrack = 0; itrack < nodes_per_chan; itrack++)
			{
			    /* not ending wire nor passing wire with sbox */
			    if(incoming_wire_label[side_opp][itrack] !=
			       UN_SET)
				{

				    /* corner sblocks for sure have no opposite channel segments so don't care about them */
				    if(is_core_sblock)
					{
					    if(incoming_wire_label[side_opp]
					       [itrack] <
					       num_ending_wires[side_opp])
						{
						    /* The ending wires in core sblocks form N-to-N assignment problem, so can
						     * use any pattern such as Wilton */
						    /* In the direct connect case, I know for sure the init mux is at the same track #
						     * as this ending wire, but still need to find the init mux label for Fs > 3 */
						    sblock_pattern[i][j]
							[side_opp][to_side]
							[itrack] =
							find_label_of_track
							(wire_mux_on_track
							 [to_side],
							 num_wire_muxes
							 [to_side], itrack);
						}
					    else
						{
						    /* These are passing wires with sbox for core sblocks */
						    sblock_pattern[i][j]
							[side_opp][to_side]
							[itrack] =
							((side_ccw_incoming_wire_count + side_cw_incoming_wire_count) * Fs_per_side + opp_incoming_wire_count * (Fs_per_side - 1)) % num_wire_muxes[to_side];
						    opp_incoming_wire_count++;
						}
					}
				    else
					{
					    if(incoming_wire_label[side_opp]
					       [itrack] <
					       num_ending_wires[side_opp])
						{
						    sblock_pattern[i][j]
							[side_opp][to_side]
							[itrack] =
							find_label_of_track
							(wire_mux_on_track
							 [to_side],
							 num_wire_muxes
							 [to_side], itrack);
						}
					    else
						{
						    /* These are passing wires with sbox for fringe sblocks */
						    sblock_pattern[i][j]
							[side_opp][to_side]
							[itrack] =
							((side_ccw_incoming_wire_count + side_cw_incoming_wire_count) * Fs_per_side + opp_incoming_wire_count * (Fs_per_side - 1)) % num_wire_muxes[to_side];
						    opp_incoming_wire