rr_graph2.c

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

    for(i = 0; i < nodes_per_chan; i++)
	{
	    free(seg_details[i].cb);
	    free(seg_details[i].sb);
	}
    free(seg_details);
}


/* Dumps out an array of seg_details structures to file fname.  Used only   *
 * for debugging.                                                           */
void
dump_seg_details(t_seg_details * seg_details,
		 int nodes_per_chan,
		 char *fname)
{

    FILE *fp;
    int i, j;
    const char *drivers_names[] = { "multi_buffered",
	"multi_muxed",
	"multi_merged",
	"single"
    };
    const char *direction_names[] = { "inc_direction",
	"dec_direction",
	"bi_direction"
    };

    fp = my_fopen(fname, "w");

    for(i = 0; i < nodes_per_chan; i++)
	{
	    fprintf(fp, "Track: %d.\n", i);
	    fprintf(fp, "Length: %d,  Start: %d,  Long line: %d  "
		    "wire_switch: %d  opin_switch: %d.\n",
		    seg_details[i].length,
		    seg_details[i].start,
		    seg_details[i].longline,
		    seg_details[i].wire_switch, seg_details[i].opin_switch);

	    fprintf(fp, "Rmetal: %g  Cmetal: %g\n",
		    seg_details[i].Rmetal, seg_details[i].Cmetal);

	    fprintf(fp, "Direction: %s  Drivers: %s\n",
		    direction_names[seg_details[i].direction],
		    drivers_names[seg_details[i].drivers]);

	    fprintf(fp, "Start Track: %d  End Track: %d\n",
		    seg_details[i].start_track, seg_details[i].end_track);

	    fprintf(fp, "cb list:  ");
	    for(j = 0; j < seg_details[i].length; j++)
		fprintf(fp, "%d ", seg_details[i].cb[j]);
	    fprintf(fp, "\n");

	    fprintf(fp, "sb list: ");
	    for(j = 0; j <= seg_details[i].length; j++)
		fprintf(fp, "%d ", seg_details[i].sb[j]);
	    fprintf(fp, "\n");

	    fprintf(fp, "\n");
	}

    fclose(fp);
}



/* Returns the segment number at which the segment this track lies on        *
 * started.                                                                  */
int
get_seg_start(IN t_seg_details * seg_details,
	      IN int itrack,
	      IN int chan_num,
	      IN int seg_num)
{

    int seg_start, length, start;

    seg_start = 1;
    if(FALSE == seg_details[itrack].longline)
	{

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

	    /* Start is guaranteed to be between 1 and length.  Hence adding length to *
	     * the quantity in brackets below guarantees it will be nonnegative.       */

	    assert(start > 0);
	    assert(start <= length);

	    /* NOTE: Start points are staggered between different channels.
	     * The start point must stagger backwards as chan_num increases.
	     * Unidirectional routing expects this to allow the N-to-N 
	     * assumption to be made with respect to ending wires in the core. */
	    seg_start =
		seg_num - (seg_num + length + chan_num - start) % length;
	    if(seg_start < 1)
		{
		    seg_start = 1;
		}
	}

    return seg_start;
}

int
get_seg_end(IN t_seg_details * seg_details,
	    IN int itrack,
	    IN int istart,
	    IN int chan_num,
	    IN int seg_max)
{
    int len, ofs, end, first_full;

    len = seg_details[itrack].length;
    ofs = seg_details[itrack].start;

    /* Normal endpoint */
    end = istart + len - 1;

    /* If start is against edge it may have been clipped */
    if(1 == istart)
	{
	    /* If the (staggered) startpoint of first full wire wasn't
	     * also 1, we must be the clipped wire */
	    first_full = (len - (chan_num % len) + ofs - 1) % len + 1;
	    if(first_full > 1)
		{
		    /* then we stop just before the first full seg */
		    end = first_full - 1;
		}
	}

    /* Clip against far edge */
    if(end > seg_max)
	{
	    end = seg_max;
	}

    return end;
}




/* Returns the number of tracks to which clb opin #ipin at (i,j) connects.   *
 * Also stores the nodes to which this pin connects in the linked list       *
 * pointed to by *edge_list_ptr.                                             */
int
get_bidir_opin_connections(IN int i,
			   IN int j,
			   IN int ipin,
			   IN struct s_linked_edge **edge_list,
			   IN int *****opin_to_track_map,
			   IN int Fc,
			   IN boolean * rr_edge_done,
			   IN t_ivec *** rr_node_indices,
			   IN t_seg_details * seg_details)
{

    int iside, num_conn, ofs, tr_i, tr_j, chan, seg;
    int to_track, to_switch, to_node, iconn;
	int is_connected_track;
    t_type_ptr type;
    t_rr_type to_type;

    type = grid[i][j].type;
    ofs = grid[i][j].offset;

    num_conn = 0;

    /* [0..num_types-1][0..num_pins-1][0..height][0..3][0..Fc-1] */
    for(iside = 0; iside < 4; iside++)
	{

	    /* Figure out coords of channel segment based on side */
	    tr_i = ((iside == LEFT) ? (i - 1) : i);
	    tr_j = ((iside == BOTTOM) ? (j - 1) : j);

	    to_type = ((iside == LEFT) || (iside == RIGHT)) ? CHANY : CHANX;

	    chan = ((to_type == CHANX) ? tr_j : tr_i);
	    seg = ((to_type == CHANX) ? tr_i : tr_j);

	    /* Don't connect where no tracks on fringes */
	    if((tr_i < 0) || (tr_i > nx))
		{
		    continue;
		}
	    if((tr_j < 0) || (tr_j > ny))
		{
		    continue;
		}
	    if((CHANX == to_type) && (tr_i < 1))
		{
		    continue;
		}
	    if((CHANY == to_type) && (tr_j < 1))
		{
		    continue;
		}

		is_connected_track = FALSE;

	    /* Itterate of the opin to track connections */
	    for(iconn = 0; iconn < Fc; ++iconn)
		{
		    to_track =
			opin_to_track_map[type->
					  index][ipin][ofs][iside][iconn];

		    /* Skip unconnected connections */
		    if(OPEN == to_track || is_connected_track)
			{
				is_connected_track = TRUE;
			    assert(OPEN ==
				   opin_to_track_map[type->
						     index][ipin][ofs][iside]
				   [0]);
			    continue;
			}

		    /* Only connect to wire if there is a CB */
		    if(is_cbox
		       (chan, seg, to_track, seg_details, BI_DIRECTIONAL))
			{
			    to_switch = seg_details[to_track].wire_switch;
			    to_node =
				get_rr_node_index(tr_i, tr_j, to_type,
						  to_track, rr_node_indices);

			    *edge_list =
				insert_in_edge_list(*edge_list, to_node,
						    to_switch);
			    rr_edge_done[to_node] = TRUE;
			    ++num_conn;
			}
		}
	}

    return num_conn;
}



int
get_unidir_opin_connections(IN int chan,
			    IN int seg,
			    IN int Fc,
			    IN t_rr_type chan_type,
			    IN t_seg_details * seg_details,
			    INOUT t_linked_edge ** edge_list_ptr,
			    INOUT int **Fc_ofs,
			    INOUT boolean * rr_edge_done,
			    IN int max_len,
			    IN int nodes_per_chan,
			    IN t_ivec *** rr_node_indices,
			    OUT boolean * Fc_clipped)
{
    /* Gets a linked list of Fc nodes to connect to in given
     * chan seg.  Fc_ofs is used for the for the opin staggering
     * pattern. */

    int *inc_muxes = NULL;
    int *dec_muxes = NULL;
    int num_inc_muxes, num_dec_muxes, iconn;
    int inc_inode, dec_inode;
    int inc_mux, dec_mux;
    int inc_track, dec_track;
    int x, y;
    int num_edges;

    *Fc_clipped = FALSE;

    /* Fc is assigned in pairs so check it is even. */
    assert(Fc % 2 == 0);

    /* get_rr_node_indices needs x and y coords. */
    x = ((CHANX == chan_type) ? seg : chan);
    y = ((CHANX == chan_type) ? chan : seg);

    /* Get the lists of possible muxes. */
    inc_muxes = label_wire_muxes(chan, seg, seg_details, max_len,
				 INC_DIRECTION, nodes_per_chan,
				 &num_inc_muxes);
    dec_muxes =
	label_wire_muxes(chan, seg, seg_details, max_len, DEC_DIRECTION,
			 nodes_per_chan, &num_dec_muxes);

    /* Clip Fc to the number of muxes. */
    if(((Fc / 2) > num_inc_muxes) || ((Fc / 2) > num_dec_muxes))
	{
	    *Fc_clipped = TRUE;
	    Fc = 2 * min(num_inc_muxes, num_dec_muxes);
	}

    /* Assign tracks to meet Fc demand */
    num_edges = 0;
    for(iconn = 0; iconn < (Fc / 2); ++iconn)
	{
	    /* Figure of the next mux to use */
	    inc_mux = Fc_ofs[chan][seg] % num_inc_muxes;
	    dec_mux = Fc_ofs[chan][seg] % num_dec_muxes;
	    ++Fc_ofs[chan][seg];

	    /* Figure out the track it corresponds to. */
	    inc_track = inc_muxes[inc_mux];
	    dec_track = dec_muxes[dec_mux];

	    /* Figure the inodes of those muxes */
	    inc_inode =
		get_rr_node_index(x, y, chan_type, inc_track,
				  rr_node_indices);
	    dec_inode =
		get_rr_node_index(x, y, chan_type, dec_track,
				  rr_node_indices);

	    /* Add to the list. */
	    if(FALSE == rr_edge_done[inc_inode])
		{
		    rr_edge_done[inc_inode] = TRUE;
		    *edge_list_ptr = insert_in_edge_list(*edge_list_ptr,
							 inc_inode,
							 seg_details
							 [inc_track].
							 opin_switch);
		    ++num_edges;
		}
	    if(FALSE == rr_edge_done[dec_inode])
		{
		    rr_edge_done[dec_inode] = TRUE;
		    *edge_list_ptr = insert_in_edge_list(*edge_list_ptr,
							 dec_inode,
							 seg_details
							 [dec_track].
							 opin_switch);
		    ++num_edges;
		}
	}

    if(inc_muxes)
	{
	    free(inc_muxes);
	    inc_muxes = NULL;
	}
    if(dec_muxes)
	{
	    free(dec_muxes);
	    dec_muxes = NULL;
	}

    return num_edges;
}

boolean
is_cbox(IN int chan,
	IN int seg,
	IN int track,
	IN t_seg_details * seg_details,
	IN enum e_directionality directionality)
{

    int start, length, ofs, fac, start_seg;

    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 */
    start_seg = get_seg_start(seg_details, track, chan, seg);

    ofs = seg - start_seg;

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

    /* If unidir segment that is going backwards, we need to flip the ofs */
    if(DEC_DIRECTION == seg_details[track].direction)
	{
	    ofs = (length - 1) - ofs;
	}

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


static void
load_chan_rr_indices(IN int nodes_per_chan,
		     IN int chan_len,
		     IN int num_chans,
		     IN t_rr_type type,
		     IN t_seg_details * seg_details,
		     INOUT int *index,
		     INOUT t_ivec *** indices)
{
    int chan, seg, track, start, inode;

    indices[type] = (t_ivec **) my_malloc(sizeof(t_ivec *) * num_chans);
    for(chan = 0; chan < num_chans; ++chan)
	{
	    indices[type][chan] =
		(t_ivec *) my_malloc(sizeof(t_ivec) * chan_len);

	    indices[type][chan][0].nelem = 0;
	    indices[type][chan][0].list = NULL;

	    for(seg = 1; seg < chan_len; ++seg)
		{
		    /* Alloc the track inode lookup list */
		    indices[type][chan][seg].nelem = nodes_per_chan;
		    indices[type][chan][seg].list =
			(int *)my_malloc(sizeof(int) * nodes_per_chan);
		    for(track = 0; track < nodes_per_chan; ++track)
			{
			    indices[type][chan][seg].list[track] = OPEN;
			}
		}
	}

    for(chan = 0; chan < num_chans; ++chan)
	{
	    for(seg = 1; seg < chan_len; ++seg)
		{
		    /* Assign an inode to the starts of tracks */
		    for(track = 0; track < indices[type][chan][seg].nelem;
			++track)
			{
			    start =
				get_seg_start(seg_details, track, chan, seg);

			    /* If the start of the wire doesn't have a inode, 
			     * assign one to it. */
			    inode = indices[type][chan][start].list[track];
			    if(OPEN == inode)
				{
				    inode = *index;
				    ++(*index);

				    indices[type][chan][start].list[track] =
					inode;
				}

			    /* Assign inode of start of wire to current position */
			    indices[type][chan][seg].list[track] = inode;
			}
		}
	}
}


struct s_ivec ***
alloc_and_load_rr_node_indices(IN int nodes_per_chan,
			       IN int nx,
			       IN int ny,
			       INOUT int *index,
			       IN t_seg_details * seg_details)