rr_graph2.c

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

{

    /* Allocates and loads all the structures needed for fast lookups of the   *
     * index of an rr_node.  rr_node_indices is a matrix containing the index  *
     * of the *first* rr_node at a given (i,j) location.                       */

    int i, j, k, ofs;
    t_ivec ***indices;
    t_ivec tmp;
    t_type_ptr type;

    /* Alloc the lookup table */
    indices = (t_ivec ***) my_malloc(sizeof(t_ivec **) * NUM_RR_TYPES);
    indices[IPIN] = (t_ivec **) my_malloc(sizeof(t_ivec *) * (nx + 2));
    indices[SINK] = (t_ivec **) my_malloc(sizeof(t_ivec *) * (nx + 2));
    for(i = 0; i <= (nx + 1); ++i)
	{
	    indices[IPIN][i] =
		(t_ivec *) my_malloc(sizeof(t_ivec) * (ny + 2));
	    indices[SINK][i] =
		(t_ivec *) my_malloc(sizeof(t_ivec) * (ny + 2));
	    for(j = 0; j <= (ny + 1); ++j)
		{
		    indices[IPIN][i][j].nelem = 0;
		    indices[IPIN][i][j].list = NULL;

		    indices[SINK][i][j].nelem = 0;
		    indices[SINK][i][j].list = NULL;
		}
	}


    /* Count indices for block nodes */
    for(i = 0; i <= (nx + 1); i++)
	{
	    for(j = 0; j <= (ny + 1); j++)
		{
		    ofs = grid[i][j].offset;
		    if(0 == ofs)
			{
			    type = grid[i][j].type;

			    /* Load the pin class lookups. The ptc nums for SINK and SOURCE
			     * are disjoint so they can share the list. */
			    tmp.nelem = type->num_class;
			    tmp.list = NULL;
			    if(tmp.nelem > 0)
				{
				    tmp.list =
					(int *)my_malloc(sizeof(int) *
							 tmp.nelem);
				    for(k = 0; k < tmp.nelem; ++k)
					{
					    tmp.list[k] = *index;
					    ++(*index);
					}
				}
			    indices[SINK][i][j] = tmp;

			    /* Load the pin lookups. The ptc nums for IPIN and OPIN
			     * are disjoint so they can share the list. */
			    tmp.nelem = type->num_pins;
			    tmp.list = NULL;
			    if(tmp.nelem > 0)
				{
				    tmp.list =
					(int *)my_malloc(sizeof(int) *
							 tmp.nelem);
				    for(k = 0; k < tmp.nelem; ++k)
					{
					    tmp.list[k] = *index;
					    ++(*index);
					}
				}
			    indices[IPIN][i][j] = tmp;
			}
		}
	}

    /* Point offset blocks of a large block to base block */
    for(i = 0; i <= (nx + 1); i++)
	{
	    for(j = 0; j <= (ny + 1); j++)
		{
		    ofs = grid[i][j].offset;
		    if(ofs > 0)
			{
			    /* NOTE: this only supports vertical large blocks */
			    indices[SINK][i][j] = indices[SINK][i][j - ofs];
			    indices[IPIN][i][j] = indices[IPIN][i][j - ofs];
			}
		}
	}

    /* SOURCE and SINK have unique ptc values so their data can be shared.
     * IPIN and OPIN have unique ptc values so their data can be shared. */
    indices[SOURCE] = indices[SINK];
    indices[OPIN] = indices[IPIN];

    /* Load the data for x and y channels */
    load_chan_rr_indices(nodes_per_chan, nx + 1, ny + 1, CHANX,
			 seg_details, index, indices);
    load_chan_rr_indices(nodes_per_chan, ny + 1, nx + 1, CHANY,
			 seg_details, index, indices);

    return indices;
}


void
free_rr_node_indices(IN t_ivec *** rr_node_indices)
{
	int i, j, ofs;
    /* This function must unallocate the structure allocated in 
     * alloc_and_load_rr_node_indices. */
	for(i = 0; i <= (nx + 1); ++i)
	{
		for(j = 0; j <= (ny + 1); ++j)
		{
			ofs = grid[i][j].offset;
		    if(ofs > 0)
			{
			    /* Vertical large blocks reference is same as offset 0 */
			    rr_node_indices[SINK][i][j].list = NULL;
				rr_node_indices[IPIN][i][j].list = NULL;
				continue;
			}
			if(rr_node_indices[SINK][i][j].list != NULL) {
				free(rr_node_indices[SINK][i][j].list);
			}
			if(rr_node_indices[IPIN][i][j].list != NULL) {
				free(rr_node_indices[IPIN][i][j].list);
			}
		}
		free(rr_node_indices[SINK][i]);
		free(rr_node_indices[IPIN][i]);
	}
	free(rr_node_indices[SINK]);
	free(rr_node_indices[IPIN]);

	for(i = 0; i < (nx + 1); ++i)
	{
		for(j = 0; j < (ny + 1); ++j)
		{
			if(rr_node_indices[CHANY][i][j].list != NULL) {
				free(rr_node_indices[CHANY][i][j].list);
			}
		}
		free(rr_node_indices[CHANY][i]);
	}
	free(rr_node_indices[CHANY]);

	for(i = 0; i < (ny + 1); ++i)
	{
		for(j = 0; j < (nx + 1); ++j)
		{
			if(rr_node_indices[CHANX][i][j].list != NULL) {
				free(rr_node_indices[CHANX][i][j].list);
			}
		}
		free(rr_node_indices[CHANX][i]);
	}
	free(rr_node_indices[CHANX]);

	free(rr_node_indices);
}


int
get_rr_node_index(int x,
		  int y,
		  t_rr_type rr_type,
		  int ptc,
		  t_ivec *** rr_node_indices)
{
    /* Returns the index of the specified routing resource node.  (x,y) are     *
     * the location within the FPGA, rr_type specifies the type of resource,    *
     * and ptc gives the number of this resource.  ptc is the class number,   *
     * pin number or track number, depending on what type of resource this      *
     * is.  All ptcs start at 0 and go up to pins_per_clb-1 or the equivalent. *
     * The order within a clb is:  SOURCEs + SINKs (type->num_class of them); IPINs,  *
     * and OPINs (pins_per_clb of them); CHANX; and CHANY (nodes_per_chan of    *
     * each).  For (x,y) locations that point at pads the order is:  type->capacity     *
     * occurances of SOURCE, SINK, OPIN, IPIN (one for each pad), then one      *
     * associated channel (if there is a channel at (x,y)).  All IO pads are    *
     * bidirectional, so while each will be used only as an INPAD or as an      *
     * OUTPAD, all the switches necessary to do both must be in each pad.       *
     *                                                                          *
     * Note that for segments (CHANX and CHANY) of length > 1, the segment is   *
     * given an rr_index based on the (x,y) location at which it starts (i.e.   *
     * lowest (x,y) location at which this segment exists).                     *
     * This routine also performs error checking to make sure the node in       *
     * question exists.                                                         */

    int iclass, tmp;
    t_type_ptr type;
    t_ivec lookup;

    assert(ptc >= 0);
    assert(x >= 0 && x <= (nx + 1));
    assert(y >= 0 && y <= (ny + 1));

    type = grid[x][y].type;

    /* Currently need to swap x and y for CHANX because of chan, seg convention */
    if(CHANX == rr_type)
	{
	    tmp = x;
	    x = y;
	    y = tmp;
	}

    /* Start of that block.  */
    lookup = rr_node_indices[rr_type][x][y];

    /* Check valid ptc num */
    assert(ptc >= 0);
    assert(ptc < lookup.nelem);

#ifdef DEBUG
    switch (rr_type)
	{
	case SOURCE:
	    assert(ptc < type->num_class);
	    assert(type->class_inf[ptc].type == DRIVER);
	    break;

	case SINK:
	    assert(ptc < type->num_class);
	    assert(type->class_inf[ptc].type == RECEIVER);
	    break;

	case OPIN:
	    assert(ptc < type->num_pins);
	    iclass = type->pin_class[ptc];
	    assert(type->class_inf[iclass].type == DRIVER);
	    break;

	case IPIN:
	    assert(ptc < type->num_pins);
	    iclass = type->pin_class[ptc];
	    assert(type->class_inf[iclass].type == RECEIVER);
	    break;

	case CHANX:
	case CHANY:
	    break;

	default:
	    printf("Error:  Bad rr_node passed to get_rr_node_index.\n"
		   "Request for type=%d ptc=%d at (%d, %d).\n",
		   rr_type, ptc, x, y);
	    exit(1);
	}
#endif

    return lookup.list[ptc];
}


int
get_track_to_ipins(int seg,
		   int chan,
		   int track,
		   t_linked_edge ** edge_list_ptr,
		   t_ivec *** rr_node_indices,
		   struct s_ivec ****track_to_ipin_lookup,
		   t_seg_details * seg_details,
		   enum e_rr_type chan_type,
		   int chan_length,
		   int wire_to_ipin_switch,
		   enum e_directionality directionality)
{

    /* This counts the fan-out from wire segment (chan, seg, track) to blocks on either side */

    t_linked_edge *edge_list_head;
    int j, pass, iconn, phy_track, end, to_node, max_conn, ipin, side, x,
	y, num_conn;
    t_type_ptr type;
    int off;

    /* End of this wire */
    end = get_seg_end(seg_details, track, seg, chan, chan_length);

    edge_list_head = *edge_list_ptr;
    num_conn = 0;

    for(j = seg; j <= end; j++)
	{
	    if(is_cbox(chan, j, track, seg_details, directionality))
		{
		    for(pass = 0; pass < 2; ++pass)
			{
			    if(CHANX == chan_type)
				{
				    x = j;
				    y = chan + pass;
				    side = (0 == pass ? TOP : BOTTOM);
				}
			    else
				{
				    assert(CHANY == chan_type);
				    x = chan + pass;
				    y = j;
				    side = (0 == pass ? RIGHT : LEFT);
				}

			    /* PAJ - if the pointed to is an EMPTY then shouldn't look for ipins */
			    if(grid[x][y].type == EMPTY_TYPE)
				continue;

			    /* Move from logical (straight) to physical (twisted) track index 
			     * - algorithm assigns ipin connections to same physical track index
			     * so that the logical track gets distributed uniformly */
			    phy_track =
				vpr_to_phy_track(track, chan, j, seg_details,
						 directionality);

			    /* We need the type to find the ipin map for this type */
			    type = grid[x][y].type;
			    off = grid[x][y].offset;

			    max_conn =
				track_to_ipin_lookup[type->
						     index][phy_track][off]
				[side].nelem;
			    for(iconn = 0; iconn < max_conn; iconn++)
				{
				    ipin =
					track_to_ipin_lookup[type->
							     index][phy_track]
					[off][side].list[iconn];

				    /* Check there is a connection and Fc map isn't wrong */
				    assert(type->pinloc[off][side][ipin]);
				    assert(type->is_global_pin[ipin] ==
					   FALSE);

				    to_node =
					get_rr_node_index(x, y, IPIN, ipin,
							  rr_node_indices);
				    edge_list_head =
					insert_in_edge_list(edge_list_head,
							    to_node,
							    wire_to_ipin_switch);
				}
			    num_conn += max_conn;
			}
		}
	}

    *edge_list_ptr = edge_list_head;
    return (num_conn);
}


/* Counts how many connections should be made from this segment to the y-   *
 * segments in the adjacent channels at to_j.  It returns the number of     *
 * connections, and updates edge_list_ptr to point at the head of the       *
 * (extended) linked list giving the nodes to which this segment connects   *
 * and the switch type used to connect to each.                             *
 *                                                                          *
 * An edge is added from this segment to a y-segment if:                    *
 * (1) this segment should have a switch box at that location, or           *
 * (2) the y-segment to which it would connect has a switch box, and the    *
 *     switch type of that y-segment is unbuffered (bidirectional pass      *
 *     transistor).                                                         *
 *                                                                          *
 * For bidirectional:                                                       *
 * If the switch in each direction is a pass transistor (unbuffered), both  *
 * switches are marked as being of the types of the larger (lower R) pass   *
 * transistor.                                                              */
int
get_track_to_tracks(IN int from_chan,
		    IN int from_seg,
		    IN int from_track,
		    IN t_rr_type from_type,
		    IN int to_seg,
		    IN t_rr_type to_type,
		    IN int chan_len,
		    IN int nodes_per_chan,
		    IN int *opin_mux_size,
		    IN int Fs_per_side,
		    IN short *****sblock_pattern,
		    INOUT struct s_linked_edge **edge_list,
		    IN t_seg_details * seg_details,
		    IN enum e_directionality directionality,
		    IN t_ivec *** rr_node_indices,
		    INOUT boolean * rr_edge_done,
		    IN struct s_ivec ***switch_block_conn)
{
    int num_conn;
    int from_switch, from_end, from_sb, from_first;
    int to_chan, to_sb;
    int start, end;
    struct s_ivec conn_tracks;
    boolean from_is_sbox, is_behind, Fs_clipped;
    enum e_side from_side_a, from_side_b, to_side;

    assert(from_seg ==
	   get_seg_start(seg_details, from_track, from_chan, from_seg));

    from_switch = seg_details[from_track].wire_switch;
    from_end =
	get_seg_end(seg_details, from_track, from_seg, from_chan, chan_len);
    from_first = from_seg - 1;

    /* Figure out the sides of SB the from_wire will use */
    if(CHANX == from_type)
	{
	    from_side_a = RIGHT;
	    from_side_b = LEFT;
	}
    else
	{
	    assert(CHANY == from_type);
	    from_side_a = TOP;
	    from_side_b = BOTTOM;
	}

    /* Figure out if the to_wire is connecting to a SB 
     * that is behind it. */
    is_behind = FALSE;
    if(to_type == from_type)
	{
	    /* If inline, check that they only are trying
	     * to connect at endpoints. */
	    assert((to_seg == (from_end + 1)) || (to_seg == (from_seg - 1)));
	    if(to_seg > from_end)
		{
		    is_behind = TRUE;
		}
	}
    else
	{
	    /* If bending, check that they are adjacent to
	     * our channel. */
	    assert((to_seg == from_chan) || (to_seg == (from_chan + 1)));
	    if(to_seg > from_chan)
		{
		    is_behind = TRUE;
		}
	}

    /* Figure out the side of SB the to_wires will use.
     * The to_seg and from_chan are in same direction. */
    if(CHANX == to_type)
	{
	    to_side = (is_behind ? RIGHT : LEFT);
	}
    else
	{
	    assert(CHANY == to_type);
	    to_side = (is_behind ? TOP : BOTTOM);
	}

    /* Set the loop bounds */
    start = from_first;
    end = from_end;

    /* If we are connecting in same direction the connection is 
     * on one of the two sides so clip the bounds to the SB of
     * interest and proceed normally. */
    if(to_type == from_type)