rr_graph2.c

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

	{
	    start = (is_behind ? end : start);
	    end = start;
	}

    /* Iterate over the SBs */
    num_conn = 0;
    for(from_sb = start; from_sb <= end; ++from_sb)
	{
	    /* Figure out if we are at a sbox */
	    from_is_sbox = is_sbox(from_chan, from_seg, from_sb, from_track,
				   seg_details, directionality);
	    /* end of wire must be an sbox */
	    if(from_sb == from_end || from_sb == from_first)
		{
		    from_is_sbox = TRUE;	/* Endpoints always default to true */
		}

	    /* to_chan is the current segment if different directions,
	     * otherwise to_chan is the from_chan */
	    to_chan = from_sb;
	    to_sb = from_chan;
	    if(from_type == to_type)
		{
		    to_chan = from_chan;
		    to_sb = from_sb;
		}

	    /* Do the edges going to the left or down */
	    if(from_sb < from_end)
		{
		    if(BI_DIRECTIONAL == directionality)
			{
			    conn_tracks =
				switch_block_conn[from_side_a][to_side]
				[from_track];
			    num_conn +=
				get_bidir_track_to_chan_seg(conn_tracks,
							    rr_node_indices,
							    to_chan, to_seg,
							    to_sb, to_type,
							    seg_details,
							    from_is_sbox,
							    from_switch,
							    rr_edge_done,
							    directionality,
							    edge_list);
			}
		    if(UNI_DIRECTIONAL == directionality)
			{
			    /* No fanout if no SB. */
			    /* We are connecting from the top or right of SB so it
			     * makes the most sense to only there from DEC_DIRECTION wires. */
			    if((from_is_sbox) &&
			       (DEC_DIRECTION ==
				seg_details[from_track].direction))
				{
				    num_conn +=
					get_unidir_track_to_chan_seg((from_sb
								      ==
								      from_first),
								     from_track,
								     to_chan,
								     to_seg,
								     to_sb,
								     to_type,
								     nodes_per_chan,
								     nx, ny,
								     from_side_a,
								     to_side,
								     Fs_per_side,
								     opin_mux_size,
								     sblock_pattern,
								     rr_node_indices,
								     seg_details,
								     rr_edge_done,
								     &Fs_clipped,
								     edge_list);
				}
			}
		}

	    /* Do the edges going to the right or up */
	    if(from_sb > from_first)
		{
		    if(BI_DIRECTIONAL == directionality)
			{
			    conn_tracks =
				switch_block_conn[from_side_b][to_side]
				[from_track];
			    num_conn +=
				get_bidir_track_to_chan_seg(conn_tracks,
							    rr_node_indices,
							    to_chan, to_seg,
							    to_sb, to_type,
							    seg_details,
							    from_is_sbox,
							    from_switch,
							    rr_edge_done,
							    directionality,
							    edge_list);
			}
		    if(UNI_DIRECTIONAL == directionality)
			{
			    /* No fanout if no SB. */
			    /* We are connecting from the bottom or left of SB so it
			     * makes the most sense to only there from INC_DIRECTION wires. */
			    if((from_is_sbox) &&
			       (INC_DIRECTION ==
				seg_details[from_track].direction))
				{
				    num_conn +=
					get_unidir_track_to_chan_seg((from_sb
								      ==
								      from_end),
								     from_track,
								     to_chan,
								     to_seg,
								     to_sb,
								     to_type,
								     nodes_per_chan,
								     nx, ny,
								     from_side_b,
								     to_side,
								     Fs_per_side,
								     opin_mux_size,
								     sblock_pattern,
								     rr_node_indices,
								     seg_details,
								     rr_edge_done,
								     &Fs_clipped,
								     edge_list);
				}
			}
		}
	}

    return num_conn;
}



static int
get_bidir_track_to_chan_seg(IN struct s_ivec conn_tracks,
			    IN t_ivec *** rr_node_indices,
			    IN int to_chan,
			    IN int to_seg,
			    IN int to_sb,
			    IN t_rr_type to_type,
			    IN t_seg_details * seg_details,
			    IN boolean from_is_sbox,
			    IN int from_switch,
			    INOUT boolean * rr_edge_done,
			    IN enum e_directionality directionality,
			    INOUT struct s_linked_edge **edge_list)
{
    int iconn, to_track, to_node, to_switch, num_conn, to_x, to_y, i;
    boolean to_is_sbox;
    short switch_types[2];

    /* x, y coords for get_rr_node lookups */
    if(CHANX == to_type)
	{
	    to_x = to_seg;
	    to_y = to_chan;
	}
    else
	{
	    assert(CHANY == to_type);
	    to_x = to_chan;
	    to_y = to_seg;
	}

    /* Go through the list of tracks we can connect to */
    num_conn = 0;
    for(iconn = 0; iconn < conn_tracks.nelem; ++iconn)
	{
	    to_track = conn_tracks.list[iconn];
	    to_node = get_rr_node_index(to_x, to_y, to_type, to_track,
					rr_node_indices);

	    /* Skip edge if already done */
	    if(rr_edge_done[to_node])
		{
		    continue;
		}

	    /* Get the switches for any edges between the two tracks */
	    to_switch = seg_details[to_track].wire_switch;

	    to_is_sbox = is_sbox(to_chan, to_seg, to_sb, to_track,
				 seg_details, directionality);
	    get_switch_type(from_is_sbox, to_is_sbox,
			    from_switch, to_switch, switch_types);

	    /* There are up to two switch edges allowed from track to track */
	    for(i = 0; i < 2; ++i)
		{
		    /* If the switch_type entry is empty, skip it */
		    if(OPEN == switch_types[i])
			{
			    continue;
			}

		    /* Add the edge to the list */
		    *edge_list = insert_in_edge_list(*edge_list,
						     to_node,
						     switch_types[i]);
		    /* Mark the edge as now done */
		    rr_edge_done[to_node] = TRUE;
		    ++num_conn;
		}
	}

    return num_conn;
}

static int
get_unidir_track_to_chan_seg(IN boolean is_end_sb,
			     IN int from_track,
			     IN int to_chan,
			     IN int to_seg,
			     IN int to_sb,
			     IN t_rr_type to_type,
			     IN int nodes_per_chan,
			     IN int nx,
			     IN int ny,
			     IN enum e_side from_side,
			     IN enum e_side to_side,
			     IN int Fs_per_side,
			     IN int *opin_mux_size,
			     IN short *****sblock_pattern,
			     IN t_ivec *** rr_node_indices,
			     IN t_seg_details * seg_details,
			     INOUT boolean * rr_edge_done,
			     OUT boolean * Fs_clipped,
			     INOUT struct s_linked_edge **edge_list)
{
    int to_track, to_mux, to_node, to_x, to_y, i, max_len, num_labels;
    int sb_x, sb_y, count;
    int *mux_labels = NULL;
    enum e_direction to_dir;
    boolean is_fringe, is_core, is_corner, is_straight;

    /* x, y coords for get_rr_node lookups */
    if(CHANX == to_type)
	{
	    to_x = to_seg;
	    to_y = to_chan;
	    sb_x = to_sb;
	    sb_y = to_chan;
	    max_len = nx;
	}
    else
	{
	    assert(CHANY == to_type);
	    to_x = to_chan;
	    to_y = to_seg;
	    sb_x = to_chan;
	    sb_y = to_sb;
	    max_len = ny;
	}


    to_dir = DEC_DIRECTION;
    if(to_sb < to_seg)
	{
	    to_dir = INC_DIRECTION;
	}

    *Fs_clipped = FALSE;

    /* SBs go from (0, 0) to (nx, ny) */
    is_corner = ((sb_x < 1) || (sb_x >= nx)) && ((sb_y < 1) || (sb_y >= ny));
    is_fringe = (FALSE == is_corner) && ((sb_x < 1) || (sb_y < 1)
					 || (sb_x >= nx) || (sb_y >= ny));
    is_core = (FALSE == is_corner) && (FALSE == is_fringe);
    is_straight = (from_side == RIGHT && to_side == LEFT) ||
	(from_side == LEFT && to_side == RIGHT) ||
	(from_side == TOP && to_side == BOTTOM) ||
	(from_side == BOTTOM && to_side == TOP);

    /* Ending wires use N-to-N mapping if not fringe or if goes straight */
    if(is_end_sb && (is_core || is_corner || is_straight))
	{
	    /* Get the list of possible muxes for the N-to-N mapping. */
	    mux_labels = label_wire_muxes(to_chan, to_seg, seg_details,
					  max_len, to_dir, nodes_per_chan,
					  &num_labels);
	}
    else
	{
	    assert(is_fringe || !is_end_sb);

	    mux_labels = label_wire_muxes_for_balance(to_chan, to_seg,
						      seg_details, max_len,
						      to_dir, nodes_per_chan,
						      &num_labels, to_type,
						      opin_mux_size,
						      rr_node_indices);
	}

    /* Can't connect if no muxes. */
    if(num_labels < 1)
	{
	    if(mux_labels)
		{
		    free(mux_labels);
		    mux_labels = NULL;
		}
	    return 0;
	}

    /* Check if Fs demand was too high. */
    if(Fs_per_side > num_labels)
	{
	    *Fs_clipped = TRUE;
	}

    /* Get the target label */
    to_mux = sblock_pattern[sb_x][sb_y][from_side][to_side][from_track];
    assert(to_mux != UN_SET);

    /* Handle Fs > 3 but assigning consecutive muxes. */
    count = 0;
    for(i = 0; i < Fs_per_side; ++i)
	{
	    /* Use the balanced labeling for passing and fringe wires */
	    to_track = mux_labels[(to_mux + i) % num_labels];
	    to_node =
		get_rr_node_index(to_x, to_y, to_type, to_track,
				  rr_node_indices);

	    /* Add edge to list. */
	    if(FALSE == rr_edge_done[to_node])
		{
		    rr_edge_done[to_node] = TRUE;
		    *edge_list =
			insert_in_edge_list(*edge_list, to_node,
					    seg_details[to_track].
					    wire_switch);
		    ++count;
		}
	}

    if(mux_labels)
	{
	    free(mux_labels);
	    mux_labels = NULL;
	}

    return count;
}

boolean
is_sbox(IN int chan,
	IN int wire_seg,
	IN int sb_seg,
	IN int track,
	IN t_seg_details * seg_details,
	IN enum e_directionality directionality)
{

    int start, length, ofs, fac;

    fac = 1;
    if(UNI_DIRECTIONAL == directionality)
	{
	    fac = 2;
	}

    start = seg_details[track].start;
    length = seg_details[track].length;

    /* Make sure they gave us correct start */
    wire_seg = get_seg_start(seg_details, track, chan, wire_seg);

    ofs = sb_seg - wire_seg + 1;	/* Ofset 0 is behind us, so add 1 */

    assert(ofs >= 0);
    assert(ofs < (length + 1));

    /* If unidir segment that is going backwards, we need to flip the ofs */
    if((ofs % fac) > 0)
	{
	    ofs = length - ofs;
	}

    return seg_details[track].sb[ofs];
}



static void
get_switch_type(boolean is_from_sbox,
		boolean is_to_sbox,
		short from_node_switch,
		short to_node_switch,
		short switch_types[2])
{
    /* This routine looks at whether the from_node and to_node want a switch,  *
     * and what type of switch is used to connect *to* each type of node       *
     * (from_node_switch and to_node_switch).  It decides what type of switch, *
     * if any, should be used to go from from_node to to_node.  If no switch   *
     * should be inserted (i.e. no connection), it returns OPEN.  Its returned *
     * values are in the switch_types array.  It needs to return an array      *
     * because one topology (a buffer in the forward direction and a pass      *
     * transistor in the backward direction) results in *two* switches.        */

    boolean forward_pass_trans;
    boolean backward_pass_trans;
    int used, min, max;

    switch_types[0] = OPEN;	/* No switch */
    switch_types[1] = OPEN;
    used = 0;
    forward_pass_trans = FALSE;
    backward_pass_trans = FALSE;

    /* Connect forward if we are a sbox */
    if(is_from_sbox)
	{
	    switch_types[used] = to_node_switch;
	    if(FALSE == switch_inf[to_node_switch].buffered)
		{
		    forward_pass_trans = TRUE;
		}
	    ++used;
	}

    /* Check for pass_trans coming backwards */
    if(is_to_sbox)
	{
	    if(FALSE == switch_inf[from_node_switch].buffered)
		{
		    switch_types[used] = from_node_switch;
		    backward_pass_trans = TRUE;
		    ++used;
		}
	}

    /* Take the larger pass trans if there are two */
    if(forward_pass_trans && backward_pass_trans)
	{
	    min = min(to_node_switch, from_node_switch);
	    max = max(to_node_switch, from_node_switch);

	    /* Take the smaller index unless the other 
	     * pass_trans is bigger (smaller R). */
	    switch_types[used] = min;
	    if(switch_inf[max].R < switch_inf[min].R)
		{
		    switch_types[used] = max;
		}
	    ++used;
	}
}

static int
vpr_to_phy_track(IN int itrack,
		 IN int chan_num,
		 IN int seg_num,
		 IN t_seg_details * seg_details,
		 IN enum e_directionality directionality)
{