Google Git
Sign in
foss-fpga-tools / third_party / vtr-verilog-to-routing / 954be24355ace41670a508749ecb955c19f86471 / . / vpr / SRC / route / build_switchblocks.c
blob: bdc7943e7ceefceeeb92628e2b8920a38dc2ae87 [file] [log] [blame]
/*
Author(s): Oleg Petelin
Last revised: May, 2015
************ NEW SWITCH BLOCK HIGH-LEVEL DESCRIPTION ************
The new switch block description format allows a much finer level of control over the switch blocks generated by VPR.
Whereas a user previously only had the choice of 'wilton', 'universal', 'subset', or 'full' switch blocks, the new
format allows a user to specify a small set of mathematical formulas that describe the switch block connections. This format
allows the specification of all the switch blocks previously available in VPR as well as a great number of new switch block patterns.
The new switch block description format is loosely based on chapter 7 of Lemieux' and Lewis' "Design of Interconnection Networks
for Programmable Logic" book (2004).
************ FILES AND THEIR PURPOSE ************
The overall flow of parsing and building the new switch blocks involves reading switch block descriptions from the VPR
architecture file and then building the switch blocks according to these descriptions in build_rr_graph (rr_graph.c).
This functionality is split across different files which are described below:
* read_xml_arch_file.c (under libarchfpga):
* calls ProcessSwitchblocks which fills s_arch-->switchblocks with info about each user-defined switch blocks
* calls functions from parse_switchblocks.c to build switch block data structures (reads-in permutation functions
and wire segment source-point/dest-point connection info)
* ProcessSegments has been modified to give a string name to each segment type (in t_segment_inf).
* parse_switchblocks.c (under libarchfpga):
* provides functions to help load switch block data structures during XML parsing of VPR architecture file
* provides functions to evaluate switch block permutation formulas and return a numeric result
* SetupVPR.c:
* SetupRoutingArch copies switch block information from s_arch to s_det_routing_arch
* physical_types.h (under libarchfpga):
* defines classes, structs and typedefs for parsing switch blocks from XML architecture file
* vpr_types.h
* defines classes, structs and typedefs for building switch blocks
* build_switchblocks.c (this file):
* builds t_sb_connection_map sparse array containing target connections for each track in each horizontal/vertical channel segment.
'compute_track_connections' is the most important function here -- it computes the set of track segments that a given track at
(x, y, from_side, to_side, from_track) should connect to.
* rr_graph.c:
* calls alloc_and_load_switchblock_permutations (from build_switchblocks.c) which creates the t_sb_connection_map
* rr_graph2.c:
* get_track_to_chan_seg is called within get_track_to_tracks which looks at t_sb_connection_map to create the edges that
connect a source track segment into a destination channel segment
************ DESCRIPTION OF SWITCH BLOCK SPECIFICATION ************
Some terminology:
* Wire segment type: a named collection of wires. Assigned a particular length and fraction of total channel width in VPR's architecture file
* Wire segment group: a number assigned to a particular wire segment's sub-segment (sub-segments separated by switch blocks). Used to define
a collection of wire segments within a channel segment that all go in the same direction and have the same start point.
* Wire segment point: a number assigned to a specific switch block along a wire segment
Ex: for a length-4 wire segment (belonging to some named segment type):
wire segment point 0-------1-------2-------3-------0
wire segment group 0 1 2 3
The new switch block format allows a user to specify mathematical permutation functions that prescribe how a set of from_type/from_group/from_point wire segments in one channel segment (the source set) should connect to a set of to_type/to_group/to_point wire segments in an adjacent channel segment (the destination set). This provides for an abstract but very flexible way of specifying different switch block patterns.
An example from the XML VPR architecture file is given below. The 'wireconn' entries define ordered source/destination sets of wire segments that should be connected with the specified permutation functions. The wireconn entries essentially "re-index" the channel so that a permutation function of 't/2' means that the t'th wire segment in the source wireconn set should connect to the [(t/2)%W]'th wire segment in the destination set where W is the size, or effective channel width, of the destination set (note that permutation functions are implicitly modulo W so that all functions evaluate to a number that indexes into the destination set).
<switch_block type="custom"/> <-- backwards-compatible with VPR's previous wilton/subset/universal/full specification
...
...
<switchblocklist> <-- XML node that defines custom switch blocks
<switchblock name="my_switchblock" type="unidir"> <-- switch block name/type. type is either unidirectional or bidirectional
<switchblock_location type="EVERYWHERE"/> <-- location to implement switch block (EVERYWHERE/CORE/PERIMETER/CORNER/FRINGE)
<switchfuncs> <-- list of permutation functions
<func type="lr" formula="t+1"/> <-- left-to-right switch block connection
<func type="lt" formula="W-t"/> <-- formula supports different operators; discussed below
<func type="lb" formula="W+t-1"/>
<func type="rt" formula="W+t-1"/>
<func type="br" formula="W-t-2"/>
<func type="bt" formula="t+1"/>
<func type="rl" formula="t+1"/>
<func type="tl" formula="W-t"/>
<func type="bl" formula="W+t-1"/>
<func type="tr" formula="W+t-1"/>
<func type="rb" formula="W-t-2"/>
<func type="tb" formula="t+1"/>
</switchfuncs>
<wireconn FT="my_seg" TT="my_seg" FP="0,1,2,3" TP="0"/> <-- from_type/to_type/from_point/to_point
<wireconn FT="another_seg" TT="my_seg" FP="0,1" TP="0"/> <-- subset of wire segments to connect
</switchblock>
<switchblock name="another_switch_block" type="unidir">
... switch block description ...
</switchblock>
</switchblocklist>
In the above 'wireconn' entries, FT means 'From Type', TT means 'To Type', FP means 'From Point' and TP means 'To Point'. Where 'type' and 'point' is terminology defined earlier on.
Allowed symmbols and operators for the switch block permutation functions are described below (recall
that formulas are evaluated in 'parse_switchblocks.c'):
* "+" -- addition
* "-" -- subtraction
* "/" -- division
* "*" -- multiplication
* "t" -- index of the wire segment in the source set
* "W" -- size of the destination set
*/
/* TODO TODO TODO!! in t_seg_details VPR referes to 'group' as a collection of L tracks that are consecutive and
all with different start points. I'm referring to 'group' as the collection of track segments
in a channel going in the same direction and having the same start point (going by literature,
this seems to be the more appropriate definition of 'group') */
#include <cstring>
#include <cassert>
#include <algorithm>
#include <iterator>
#include "build_switchblocks.h"
#include "physical_types.h"
#include "parse_switchblocks.h"
#include "util.h"
#include <malloc.h>
#include <iostream>
#include <forward_list>
using namespace std;
/************ Defines ************/
/* if defined, switch block patterns are loaded by first computing a row of switch blocks and then
stamping out the row throughout the FPGA */
//#define FAST_SB_COMPUTATION
/* REF_X/REF_Y set a reference coordinate; some look-up structures in this file are computed relative to
this reference */
#define REF_X 1 //constexpr int REX_X = 1; <-- basically C++11 defines; more type-safe
#define REF_Y 1
/************ Classes ************/
/* contains info about a track segment type */
class Track_Info{
public:
int length; /* the length of this type of track segment in tiles */
int num_tracks; /* total number of tracks in a channel segment (basically W) */
int start; /* the track index at which this type starts in the channel segment (0..W-1) */
void set(int len, int tracks, int st){
length = len; num_tracks = tracks; start = st;
}
Track_Info(){
this->set(0, 0, 0);
}
Track_Info(int len, int tracks, int st){
this->set(len, tracks, st);
}
};
/************ Typedefs ************/
/* Used to get info about a given track type based on the name */
typedef map< string, Track_Info > t_track_type_sizes;
/************ Function Declarations ************/
/* Counts the number of tracks in each track type in the specified channel */
static void count_track_type_sizes(INP t_seg_details *channel, INP int nodes_per_chan,
INOUTP t_track_type_sizes *track_type_sizes);
#ifdef FAST_SB_COMPUTATION
/* over all connected wire types (i,j), compute the maximum least common multiple of their track lengths,
ie max(LCM(L_i, L_J)) */
static int get_max_lcm(INP vector<t_switchblock_inf> *switchblocks, INP t_track_type_sizes *track_type_sizes);
/* compute all the switchblocks around the perimeter of the FPGA for the given switchblock and wireconn */
static void compute_perimeter_switchblocks(INP t_chan_details *chan_details_x, INP t_chan_details *chan_details_y,
INP vector<t_switchblock_inf> *switchblocks, INP int nx, INP int ny, INP int nodes_per_chan,
INP t_track_type_sizes *track_type_sizes, INP e_directionality directionality,
INOUTP t_sb_connection_map *sb_conns);
/* computes a horizontal line of switchblocks of size sb_row_size (or of nx-2, whichever is smaller), starting
at coordinate (1,1) */
static void compute_switchblock_row(INP int sb_row_size, INP t_chan_details *chan_details_x, INP t_chan_details *chan_details_y,
INP vector<t_switchblock_inf> *switchblocks, INP int nx, INP int ny, INP int nodes_per_chan,
INP t_track_type_sizes *track_type_sizes, INP e_directionality directionality,
INOUTP t_sb_connection_map *sb_row);
/* stamp out a line of horizontal switchblocks starting at coordinates (ref_x, ref_y) and
continuing on for sb_row_size */
static void stampout_switchblocks_from_row( INP int sb_row_size,
INP int nodes_per_chan,
INP int nx, INP int ny, INP t_track_type_sizes *track_type_sizes,
INP e_directionality directionality, INP t_sb_connection_map *sb_row,
INOUTP t_sb_connection_map *sb_conns );
/* compute greatest common denominator of x and y */
static int gcd(INP int x, INP int y);
/* compute least common multiple of x and y */
static int lcm(INP int x, INP int y);
#endif //FAST_SB_COMPUTATION
/* Compute the track(s) that the track at (x, y, from_side, to_side, from_track) should connect to.
sb_conns is updated with the result */
static void compute_track_connections(INP int x_coord, INP int y_coord, INP enum e_side from_side,
INP enum e_side to_side, INP int from_track, INP t_chan_details * chan_details_x,
INP t_chan_details * chan_details_y, INP t_switchblock_inf *sb,
INP int nx, INP int ny, INP int nodes_per_chan,
INP t_track_type_sizes *track_type_sizes, INP e_directionality directionality,
INOUTP t_sb_connection_map *sb_conns);
/* ... sb_conn represents the 'coordinates' of the desired switch block connections */
static void compute_track_wireconn_connections(INP int nx, INP int ny, INP e_directionality directionality, INP int nodes_per_chan,
INP t_chan_details *from_chan_details, INP t_chan_details *to_chan_details, INP Switchblock_Lookup sb_conn,
INP int from_x, INP int from_y, INP int to_x, INP int to_y, INP t_rr_type from_chan_type, INP t_rr_type to_chan_type,
INP t_track_type_sizes *track_type_sizes, INP t_switchblock_inf *sb,
INP t_wireconn_inf *wireconn_ptr, INOUTP t_sb_connection_map *sb_conns);
/* returns the track indices belonging to the types in 'track_type_vec' and wirepoint in 'points' at the given channel segment */
static void get_wirepoint_tracks( INP e_directionality directionality, INP int nx, INP int ny, INP int nodes_per_chan, t_seg_details *chan_details,
INP t_rr_type chan_type, INP int x, INP int y, INP e_side side, INP vector<string> *track_type_vec, INP vector<int> *points,
INP t_track_type_sizes *track_type_sizes, INP bool is_dest, INOUTP vector<int> *tracks);
static t_rr_type index_into_correct_chan(INP int tile_x, INP int tile_y, INP enum e_side side,
INP t_chan_details *chan_details_x, INP t_chan_details *chan_details_y,
OUTP int *chan_x, OUTP int *chan_y,
OUTP t_chan_details **chan_details);
/* checks whether the specified coordinates are out of bounds */
static bool coords_out_of_bounds(INP int nx, INP int ny, INP int x_coord, INP int y_coord,
e_rr_type chan_type);
/* returns seg coordinate based on a channel's x/y coordinates */
static int get_seg_coordinate(INP t_rr_type chan_type, INP int x_coord, INP int y_coord);
/* returns the group number of the specified track */
static int get_track_group(INP int nx, INP int ny, INP e_rr_type chan_type,
INP t_seg_details &track_details, int seg_coord);
int get_track_segment_length(INP int nx, INP int ny, INP e_rr_type chan_type, INP t_seg_details &track_details);
/* Returns the wirepoint of the track specified by track_details at a segment coordinate
of seg_coord, and connection to the sb_side of the switchblock */
static int get_wirepoint_of_track(INP int nx, INP int ny, INP e_rr_type chan_type,
INP t_seg_details &track_details, INP int seg_coord, INP e_side sb_side);
/* returns true if the coordinates x/y do not correspond to the location specified by 'location' */
static bool sb_not_here(INP int nx, INP int ny, INP int x, INP int y, INP e_sb_location location);
/* checks if the specified coordinates represent a corner of the FPGA */
static bool is_corner(INP int nx, INP int ny, INP int x, INP int y);
/* checks if the specified coordinates correspond to one of the perimeter switchblocks */
static bool is_perimeter(INP int nx, INP int ny, INP int x, INP int y);
/* checks if the specified coordinates correspond to the core of the FPGA (i.e. not perimeter) */
static bool is_core(INP int nx, INP int ny, INP int x, INP int y);
/* adjusts a negative destination track calculated from a permutation formula */
static int adjust_formula_result(INP int dest_track, INP int dest_W);
t_sb_connection_map* alloc_switchblock_permutations(int nx, int ny, int channel_width);
/************ Function Definitions ************/
/* allocate and build the switchblock permutation map */
t_sb_connection_map * alloc_and_load_switchblock_permutations( INP t_chan_details * chan_details_x,
INP t_chan_details * chan_details_y, INP int nx, INP int ny,
INP vector<t_switchblock_inf> switchblocks,
INP s_chan_width *nodes_per_chan, INP e_directionality directionality){
/* get a single number for channel width */
int channel_width = nodes_per_chan->max;
if (nodes_per_chan->max != nodes_per_chan->x_min || nodes_per_chan->max != nodes_per_chan->y_min){
vpr_throw(VPR_ERROR_ARCH, __FILE__, __LINE__, "Custom switch blocks currently support consistent channel widths only.");
}
/* sparse array that will contain switch block connections */
//t_sb_connection_map *sb_conns = new t_sb_connection_map;
t_sb_connection_map *sb_conns = alloc_switchblock_permutations(nx, ny, channel_width);
/* We assume that x & y channels have the same ratios of track types. i.e., looking at a single
channel is representative of all channels in the FPGA -- as of 3/9/2013 this is true in VPR */
t_track_type_sizes track_type_sizes;
count_track_type_sizes(chan_details_x[0][0], channel_width, &track_type_sizes);
#ifdef FAST_SB_COMPUTATION
/******** fast switch block computation method; computes a row of switchblocks then stamps it out everywhere ********/
/* figure out max(lcm(L_i, L_j)) for all wire lengths belonging to wire types i & j */
int max_lcm = get_max_lcm(&switchblocks, &track_type_sizes);
t_sb_connection_map sb_row;
/* compute the perimeter switchblocks. unfortunately we can't just compute corners and stamp out the rest because
for a unidirectional architecture corners AND perimeter switchblocks require special treatment */
compute_perimeter_switchblocks( chan_details_x, chan_details_y, &switchblocks,
nx, ny, channel_width, &track_type_sizes, directionality, sb_conns);
/* compute the switchblock row */
compute_switchblock_row( max_lcm, chan_details_x, chan_details_y, &switchblocks,
nx, ny, channel_width, &track_type_sizes, directionality, &sb_row );
/* stamp-out the switchblock row throughout the rest of the FPGA */
stampout_switchblocks_from_row( max_lcm, channel_width,
nx, ny, &track_type_sizes, directionality, &sb_row, sb_conns );
#else
/******** slow switch block computation method; computes switchblocks at each coordinate ********/
/* iterate over all the switchblocks specified in the architecture */
for (int i_sb = 0; i_sb < (int)switchblocks.size(); i_sb++){
t_switchblock_inf sb = switchblocks[i_sb];
/* verify that switchblock type matches specified directionality -- currently we have to stay consistent */
if (directionality != sb.directionality){
vpr_throw(VPR_ERROR_ARCH, __FILE__, __LINE__, "alloc_and_load_switchblock_connections: Switchblock %s does not match directionality of architecture\n", sb.name.c_str());
}
/* Iterate over the x,y coordinates spanning the FPGA. Currently, the FPGA size is set as
(0..nx+1) by (0..ny+1), so we iterate over 0..nx and 0..ny. */
for (int x_coord = 0; x_coord <= nx+1; x_coord++){
for (int y_coord = 0; y_coord <= ny+1; y_coord++){
if (sb_not_here(nx, ny, x_coord, y_coord, sb.location)){
continue;
}
/* Iterate over each track in channel */
for (int from_track = 0; from_track < channel_width; from_track++){
/* now we iterate over all the potential side1->side2 connections */
for ( e_side from_side = (e_side) 0; from_side < 4; from_side = (e_side)(from_side + 1) ){
for ( e_side to_side = (e_side) 0; to_side < 4; to_side = (e_side)(to_side + 1) ){
/* Fill appropriate entry of the sb_conns map with vector specifying the tracks
the current track will connect to */
compute_track_connections(x_coord, y_coord, from_side, to_side, from_track,
chan_details_x, chan_details_y, &sb, nx, ny, channel_width,
&track_type_sizes, directionality, sb_conns);
}
}
}
}
}
}
#endif
return sb_conns;
}
/* allocate switch block matrix */
t_sb_connection_map* alloc_switchblock_permutations(int nx, int ny, int channel_width){
t_sb_connection_map *sb_conns = new t_sb_connection_map;
forward_list< t_to_track_inf > tracks;
vector < forward_list< t_to_track_inf >> from_track_vec(channel_width, tracks);
vector < vector< forward_list < t_to_track_inf >>> to_side_vec(4, from_track_vec);
vector < vector< vector < forward_list < t_to_track_inf >>>> from_side_vec(4, to_side_vec);
vector < vector< vector < vector < forward_list < t_to_track_inf >>>>> y_vec(ny+1, from_side_vec);
sb_conns->assign(nx+1, y_vec);
//(*sb_conns) = (t_sb_connection_map) alloc_matrix5(0, nx, 0, ny, 0, 3, 0, 3, 0, channel_width-1, sizeof(forward_list<t_to_track_inf>));
return sb_conns;
}
/* deallocates switch block connections sparse array */
void free_switchblock_permutations(INOUTP t_sb_connection_map *sb_conns, int nx, int ny){
sb_conns->clear();
delete sb_conns;
//free_matrix5((void*)(*sb_conns), 0, nx, 0, ny, 0, 3, 0, 3, 0, sizeof(forward_list<t_to_track_inf>));
sb_conns = NULL;
/* the switch block unordered_map can get quite large and it doesn't seem like the program
is interested in releasing the memory back to the OS after the map is cleared.
calling malloc_trim forces the program to give unused heap space back to the OS.
this significantly reduces memory usage during the routing stage when running multiple
large benchmark circuits in parallel. */
malloc_trim(0);
return;
}
#ifdef FAST_SB_COMPUTATION
/* over all connected wire types (i,j), compute the maximum least common multiple of their track lengths,
ie max(LCM(L_i, L_J)) */
static int get_max_lcm( INP vector<t_switchblock_inf> *switchblocks, INP t_track_type_sizes *track_type_sizes){
int max_lcm = -1;
int num_sb = (int)switchblocks->size();
/* over each switchblock */
for (int isb = 0; isb < num_sb; isb++){
t_switchblock_inf *sb = &(switchblocks->at(isb));
int num_wireconns = (int)sb->wireconns.size();
/* over each wireconn */
for (int iwc = 0; iwc < num_wireconns; iwc++){
t_wireconn_inf *wc = &(sb->wireconns[iwc]);
int num_from_types = (int)wc->from_type.size();
int num_to_types = (int)wc->to_type.size();
/* over each from type */
for (int ifrom = 0; ifrom < num_from_types; ifrom++){
/* over each to type */
for (int ito = 0; ito < num_to_types; ito++){
if ((*track_type_sizes).find(wc->from_type[ifrom]) != (*track_type_sizes).end() &&
(*track_type_sizes).find(wc->to_type[ito]) != (*track_type_sizes).end()) {
// the condition can fail if freq of a seg is 0 (so it is in wc, but not in track_type_size)
int length1 = track_type_sizes->at(wc->from_type[ifrom]).length;
int length2 = track_type_sizes->at(wc->to_type[ito]).length;
int current_lcm = lcm(length1, length2);
if (current_lcm > max_lcm){
max_lcm = current_lcm;
}
}
}
}
}
}
return max_lcm;
}
/* computes a horizontal row of switchblocks of size sb_row_size (or of nx-2, whichever is smaller), starting
at coordinate (1,1) */
static void compute_switchblock_row(INP int sb_row_size, INP t_chan_details *chan_details_x, INP t_chan_details *chan_details_y,
INP vector<t_switchblock_inf> *switchblocks, INP int nx, INP int ny, INP int nodes_per_chan,
INP t_track_type_sizes *track_type_sizes, INP e_directionality directionality,
INOUTP t_sb_connection_map *sb_row){
int y = 1;
for (int isb = 0; isb < (int)switchblocks->size(); isb++){
t_switchblock_inf *sb = &(switchblocks->at(isb));
for (int x = 1; x < 1 + sb_row_size; x++){
if (sb_not_here(nx, ny, x, y, sb->location)){
continue;
}
/* Iterate over each track in channel */
for (int from_track = 0; from_track < nodes_per_chan; from_track++){
/* now we iterate over all the potential side1->side2 connections */
for ( e_side from_side = (e_side) 0; from_side < 4; from_side = (e_side)(from_side + 1) ){
for ( e_side to_side = (e_side) 0; to_side < 4; to_side = (e_side)(to_side + 1) ){
/* Fill appropriate entry of the sb_conns map with vector specifying the tracks
the current track will connect to */
compute_track_connections(x, y, from_side, to_side, from_track,
chan_details_x, chan_details_y, sb, nx, ny, nodes_per_chan,
track_type_sizes, directionality, sb_row);
}
}
}
}
}
}
/* stamp out a row of horizontal switchblocks throughout the FPGA starting at coordinates (ref_x, ref_y) and
continuing on for sb_row_size */
static void stampout_switchblocks_from_row( INP int sb_row_size,
INP int nodes_per_chan,
INP int nx, INP int ny, INP t_track_type_sizes *track_type_sizes,
INP e_directionality directionality, INP t_sb_connection_map *sb_row,
INOUTP t_sb_connection_map *sb_conns ){
/* over all x coordinates that may need stamping out */
for (int x = 1; x < nx; x++){
/* over all y coordinates that may need stamping out */
for (int y = 1; y < ny; y++){
/* perimeter has been precomputed */
if ( is_perimeter(nx, ny, x, y) ){
continue;
}
/* over each source side */
for (int from_side = 0; from_side < 4; from_side ++){
/* over each destination side */
for (int to_side = 0; to_side < 4; to_side ++){
/* can't connect a side to itself */
if (from_side == to_side){
continue;
}
/* over each source track */
for (int itrack = 0; itrack < nodes_per_chan; itrack++){
/* get the total x+y distance of the current switchblock from the reference switchblock */
int distance = (x - REF_X) + (y - REF_Y);
if (distance < 0){
distance = sb_row_size - ((-1*distance)%sb_row_size);
}
/* figure out the coordinates of the switchblock we want to copy */
int copy_y = 1;
int copy_x = 1 + (distance % sb_row_size); //TODO: based on what? explain staggering pattern
/* create the indices to key into the switchblock permutation map */
Switchblock_Lookup my_key(x, y, (e_side)from_side, (e_side)to_side, itrack);
Switchblock_Lookup copy_key(copy_x, copy_y, (e_side)from_side, (e_side)to_side, itrack);
if ( sb_row->count(copy_key) == 0 ){
continue;
}
(*sb_conns)[my_key] = sb_row->at(copy_key);
}
}
}
}
}
}
/* compute all the switchblocks around the perimeter of the FPGA for the given switchblock and wireconn */
static void compute_perimeter_switchblocks(INP t_chan_details *chan_details_x, INP t_chan_details *chan_details_y,
INP vector<t_switchblock_inf> *switchblocks, INP int nx, INP int ny, INP int nodes_per_chan,
INP t_track_type_sizes *track_type_sizes, INP e_directionality directionality,
INOUTP t_sb_connection_map *sb_conns){
int x, y;
for (int isb = 0; isb < (int)switchblocks->size(); isb++){
/* along left and right edge */
x = 0;
t_switchblock_inf *sb = &(switchblocks->at(isb));
for (int i = 0; i < 2; i++){ //TODO: can use i+=nx to make more explicit what the ranges of the loop are
for (y = 0; y <= ny+1; y++){
if (sb_not_here(nx, ny, x, y, sb->location)){
continue;
}
/* Iterate over each track in channel */
for (int from_track = 0; from_track < nodes_per_chan; from_track++){
/* now we iterate over all the potential side1->side2 connections */
for ( e_side from_side = (e_side) 0; from_side < 4; from_side = (e_side)(from_side + 1) ){
for ( e_side to_side = (e_side) 0; to_side < 4; to_side = (e_side)(to_side + 1) ){
/* Fill appropriate entry of the sb_conns map with vector specifying the tracks
the current track will connect to */
compute_track_connections(x, y, from_side, to_side, from_track,
chan_details_x, chan_details_y, sb, nx, ny, nodes_per_chan,
track_type_sizes, directionality, sb_conns);
}
}
}
}
x = nx;
}
}
for (int isb = 0; isb < (int)switchblocks->size(); isb++){
/* along bottom and top edge */
y = 0;
t_switchblock_inf *sb = &(switchblocks->at(isb));
for (int i = 0; i < 2; i++){
for (x = 0; x <= nx+1; x++){
if (sb_not_here(nx, ny, x, y, sb->location)){
continue;
}
/* Iterate over each track in channel */
for (int from_track = 0; from_track < nodes_per_chan; from_track++){
/* now we iterate over all the potential side1->side2 connections */
for ( e_side from_side = (e_side) 0; from_side < 4; from_side = (e_side)(from_side + 1) ){
for ( e_side to_side = (e_side) 0; to_side < 4; to_side = (e_side)(to_side + 1) ){
/* Fill appropriate entry of the sb_conns map with vector specifying the tracks
the current track will connect to */
compute_track_connections(x, y, from_side, to_side, from_track,
chan_details_x, chan_details_y, sb, nx, ny, nodes_per_chan,
track_type_sizes, directionality, sb_conns);
}
}
}
}
y = ny;
}
}
}
/* compute greatest common denominator of x and y */
static int gcd(INP int x, INP int y){
int result;
if (y == 0){
result = x;
} else {
result = gcd(y, x % y);
}
return result;
}
/* compute least common multiple of x and y */
static int lcm(INP int x, INP int y){
int result;
result = x / gcd(x,y) * y;
return result;
}
#endif //FAST_SB_COMPUTATION
/* returns true if the coordinates x/y do not correspond to the location specified by 'location' */
static bool sb_not_here(INP int nx, INP int ny, INP int x, INP int y, INP e_sb_location location){
bool sb_not_here = true;
switch( location ){
case E_EVERYWHERE:
sb_not_here = false;
break;
case E_PERIMETER:
if (is_perimeter(nx, ny, x, y)){
sb_not_here = false;
}
break;
case E_CORNER:
if (is_corner(nx, ny, x, y)){
sb_not_here = false;
}
break;
case E_CORE:
if (is_core(nx, ny, x, y)){
sb_not_here = false;
}
break;
case E_FRINGE:
if (is_perimeter(nx, ny, x, y) && !is_corner(nx, ny, x, y)){
sb_not_here = false;
}
break;
default:
vpr_throw(VPR_ERROR_ARCH, __FILE__, __LINE__, "sb_not_here: unrecognized location enum: %d\n", location);
break;
}
return sb_not_here;
}
/* checks if the specified coordinates represent a corner of the FPGA */
static bool is_corner(INP int nx, INP int ny, INP int x, INP int y){
bool is_corner = false;
if ((x == 0 && y == 0) ||
(x == 0 && y == ny) ||
(x == nx && y == 0) ||
(x == nx && y == ny)){
is_corner = true;
}
return is_corner;
}
/* checks if the specified coordinates correspond to one of the perimeter switchblocks */
static bool is_perimeter(INP int nx, INP int ny, INP int x, INP int y){
bool is_perimeter = false;
if (x == 0 || x == nx ||
y == 0 || y == ny){
is_perimeter = true;
}
return is_perimeter;
}
/* checks if the specified coordinates correspond to the core of the FPGA (i.e. not perimeter) */
static bool is_core(INP int nx, INP int ny, INP int x, INP int y){
bool is_core = !is_perimeter(nx, ny, x, y);
return is_core;
}
/* Counts the number of tracks in each track type in the specified channel */
static void count_track_type_sizes(INP t_seg_details *channel, INP int nodes_per_chan,
INOUTP t_track_type_sizes *track_type_sizes){
string track_type;
const char * new_type;
int new_length, length;
int new_start, start;
int num_tracks = 0;
Track_Info track_info;
track_type = channel[0].type_name_ptr;
length = channel[0].length;
start = 0;
for (int itrack = 0; itrack < nodes_per_chan; itrack++){
new_type = channel[itrack].type_name_ptr;
new_length = channel[itrack].length;
new_start = itrack;
if (strcmp(new_type, track_type.c_str()) != 0){
track_info.set(length, num_tracks, start);
(*track_type_sizes)[track_type] = track_info;
track_type = new_type;
length = new_length;
start = new_start;
num_tracks = 0;
}
num_tracks++;
}
track_info.set(length, num_tracks, start);
(*track_type_sizes)[track_type] = track_info;
return;
}
/* returns the track indices belonging to the types in 'track_type_vec' and wirepoint in 'points' at the given channel segment */
static void get_wirepoint_tracks( INP e_directionality directionality, INP int nx, INP int ny, INP int nodes_per_chan, t_seg_details *chan_details,
INP t_rr_type chan_type, INP int x, INP int y, INP e_side side, INP vector<string> *track_type_vec, INP vector<int> *points,
INP t_track_type_sizes *track_type_sizes, INP bool is_dest, INOUTP vector<int> *tracks){
tracks->clear();
int num_types = (int)track_type_vec->size();
int seg_coord = x;
if (chan_type == CHANY){
seg_coord = y;
}
for (int itype = 0; itype < num_types; itype++){
string track_type = track_type_vec->at(itype);
if ((*track_type_sizes).find(track_type) == (*track_type_sizes).end()) {
// track_type_sizes may not contain track_type if its seg freq is 0
continue;
}
/* get the number of tracks of given type */
int num_type_tracks = track_type_sizes->at(track_type).num_tracks;
/* get the last track belonging to this type */
int first_type_track = track_type_sizes->at(track_type).start;
int last_type_track = first_type_track + num_type_tracks - 1;
/* walk through each track segment of specified type and check whether it matches one
of the specified wirepoints */
for (int itrack = first_type_track; itrack <= last_type_track; itrack++){
e_direction seg_direction = chan_details[itrack].direction;
if (side == TOP || side == RIGHT){
if (seg_direction == DEC_DIRECTION && is_dest){
continue;
}
if (seg_direction == INC_DIRECTION && !is_dest){
continue;
}
} else {
assert(side == LEFT || side == BOTTOM);
if (seg_direction == DEC_DIRECTION && !is_dest){
continue;
}
if (seg_direction == INC_DIRECTION && is_dest){
continue;
}
}
int track_wirepoint = get_wirepoint_of_track(nx, ny, chan_type, chan_details[itrack], seg_coord, side);
/* check if this track belongs to one of the specified wirepoints; add it to our 'tracks' vector if so */
if ( find( points->begin(), points->end(), track_wirepoint ) != points->end() ){
tracks->push_back( itrack );
}
}
}
sort(tracks->begin(), tracks->end());
}
/* Compute the track(s) that the track at (x, y, from_side, to_side, from_track) should connect to.
sb_conns is updated with the result */
static void compute_track_connections(INP int x_coord, INP int y_coord, INP enum e_side from_side,
INP enum e_side to_side, INP int from_track, INP t_chan_details * chan_details_x,
INP t_chan_details * chan_details_y, INP t_switchblock_inf *sb,
INP int nx, INP int ny, INP int nodes_per_chan,
INP t_track_type_sizes *track_type_sizes, INP e_directionality directionality,
INOUTP t_sb_connection_map *sb_conns){
t_chan_details *from_chan_details = NULL; /* details for source channel */
t_chan_details *to_chan_details = NULL ; /* details for destination channel */
int from_x, from_y; /* index into source channel */
int to_x, to_y; /* index into destination channel */
t_rr_type from_chan_type, to_chan_type; /* the type of channel - i.e. CHANX or CHANY */
from_x = from_y = to_x = to_y = UNDEFINED;
Connect_SB_Sides side_conn(from_side, to_side); /* for indexing into this switchblock's permutation funcs */
Switchblock_Lookup sb_conn(x_coord, y_coord, from_side, to_side, from_track); /* for indexing into FPGA's switchblock map */
/* can't connect a switchblock side to itself */
if (from_side == to_side){
return;
}
/* check that the permutation map has an entry for this side combination */
if (sb->permutation_map.count(side_conn) == 0){
/* the specified switchblock does not have any permutation funcs for this side1->side2 connection */
return;
}
/* find the correct channel, and the coordinates to index into it for both the source and
destination channels. also return the channel type (ie chanx/chany) into which we are
indexing */
from_chan_type = index_into_correct_chan(x_coord, y_coord, from_side, chan_details_x, chan_details_y,
&from_x, &from_y, &from_chan_details);
to_chan_type = index_into_correct_chan(x_coord, y_coord, to_side, chan_details_x, chan_details_y,
&to_x, &to_y, &to_chan_details);
/* make sure from_x/y and to_x/y aren't out of bounds */
if (coords_out_of_bounds(nx, ny, to_x, to_y, to_chan_type) ||
coords_out_of_bounds(nx, ny, from_x, from_y, from_chan_type)){
return;
}
/* iterate over all the wire connections specified for this switch block */
for (int iconn = 0; iconn < (int)sb->wireconns.size(); iconn++){
/* pointer to a connection specification between two wire types/groups */
t_wireconn_inf *wireconn_ptr = &sb->wireconns[iconn];
/* compute the destination track segments to which the source track segment should connect based on the
current wireconn */
compute_track_wireconn_connections(nx, ny, directionality, nodes_per_chan, from_chan_details, to_chan_details,
sb_conn, from_x, from_y, to_x, to_y, from_chan_type, to_chan_type, track_type_sizes,
sb, wireconn_ptr, sb_conns);
}
from_chan_details = NULL;
to_chan_details = NULL;
return;
}
/* computes the destination track segments that a source track segment at the coordinate 'sb_conn' (in
channel segment with coordinate from_x/from_y) should connect to based on the specified 'wireconn_ptr'.
wireconn_ptr defines the source and destination sets of track segments (based on track segment type & wirepoint
as defined at the top of this file), and the indices of tracks to connect to are relative to these sets */
static void compute_track_wireconn_connections(INP int nx, INP int ny, INP e_directionality directionality, INP int nodes_per_chan,
INP t_chan_details *from_chan_details, INP t_chan_details *to_chan_details, INP Switchblock_Lookup sb_conn,
INP int from_x, INP int from_y, INP int to_x, INP int to_y, INP t_rr_type from_chan_type, INP t_rr_type to_chan_type,
INP t_track_type_sizes *track_type_sizes, INP t_switchblock_inf *sb,
INP t_wireconn_inf *wireconn_ptr, INOUTP t_sb_connection_map *sb_conns){
e_direction from_track_direction = from_chan_details[from_x][from_y][sb_conn.from_track].direction;
if ( from_track_direction == INC_DIRECTION ){
/* if this is a unidirectional track headed in the increasing direction (relative to coordinate system)
then switch block source side should be BOTTOM or LEFT */
if (sb_conn.from_side == TOP || sb_conn.from_side == RIGHT){
return;
}
} else if ( from_track_direction == DEC_DIRECTION ){
/* a track heading in the decreasing direction can only connect from the TOP or RIGHT sides of a switch block */
if (sb_conn.from_side == BOTTOM || sb_conn.from_side == LEFT){
return;
}
} else {
assert( from_track_direction = BI_DIRECTION );
}
/* name of the source track type */
const char *track_type_name = from_chan_details[from_x][from_y][sb_conn.from_track].type_name_ptr;
/* names of track types we may be connecting from/to */
vector<string> *from_track_type = &(wireconn_ptr->from_type);
vector<string> *to_track_type = &(wireconn_ptr->to_type);
/* the 'seg' coordinate of the from channel */
int from_seg = get_seg_coordinate( from_chan_type, from_x, from_y );
/* the 'from' wirepoint and 'to' wirepoints at which the connection is made */
int from_wirepoint;
vector<int> to_wirepoint;
/* the current track corresponds to a single wirepoint */
from_wirepoint = get_wirepoint_of_track(nx, ny, from_chan_type, from_chan_details[from_x][from_y][sb_conn.from_track],
from_seg, sb_conn.from_side);
/* If we're at a switch block side where *all* wires start/terminate (i.e. around the FPGA perimeter) then
the source wirepoint is 0 no matter what */
if ((TOP==sb_conn.from_side && sb_conn.y_coord==0) ||
(RIGHT==sb_conn.from_side && sb_conn.x_coord==0) ||
(LEFT==sb_conn.from_side && sb_conn.x_coord==nx) ||
(BOTTOM==sb_conn.from_side && sb_conn.y_coord==ny)){
from_wirepoint = 0;
}
/* there may be multiple destination wirepoints */
to_wirepoint = wireconn_ptr->to_point;
/* vectors that will contain indices of the tracks belonging to the source/dest wire types/points */
vector<int> potential_src_tracks;
vector<int> potential_dest_tracks;
/* the index of the source/destination track within their own wirepoint set */
int src_track_in_sp, dest_track_in_sp; //XXX: what's 'sp'???
/* the effective destination channel width is the size of the destination track set */
int dest_W;
/* check that the current track has one of the types specified by the wire connection */
bool skip = true;
for (int itype = 0; itype < (int)from_track_type->size(); itype++){
if ( strcmp(from_track_type->at(itype).c_str(), track_type_name) == 0 ){
skip = false;
break;
}
}
if (skip){
return;
}
/* check that the current track has one of the source wire points specified by the wire connection */
skip = true;
for (int ipoint = 0; ipoint < (int)wireconn_ptr->from_point.size(); ipoint++){
if (from_wirepoint == wireconn_ptr->from_point[ipoint]){
skip = false;
break;
}
}
if (skip){
return;
}
/* now we need to find all tracks in the destination channel that correspond to the
type and point specified by the current wireconn_ptr. Must also have appropriate
directionality */
/* get the indices of tracks in the destination group, as well as the effective destination
channel width (which is the number of tracks in destination group) */
get_wirepoint_tracks(directionality, nx, ny, nodes_per_chan, to_chan_details[to_x][to_y], to_chan_type, to_x, to_y, sb_conn.to_side,
to_track_type, &to_wirepoint, track_type_sizes, true, &potential_dest_tracks);
if (0 == potential_dest_tracks.size()){
return;
}
dest_W = potential_dest_tracks.size();
/* get the index of the source track relative to all the tracks specified by the wireconn */
get_wirepoint_tracks(directionality, nx, ny, nodes_per_chan, from_chan_details[from_x][from_y], from_chan_type, from_x, from_y, sb_conn.from_side,
from_track_type, &(wireconn_ptr->from_point), track_type_sizes, false, &potential_src_tracks);
if (0 == potential_src_tracks.size()){
return;
}
vector<int>::iterator it = find(potential_src_tracks.begin(), potential_src_tracks.end(), sb_conn.from_track);
if (it == potential_src_tracks.end()){
vpr_throw(VPR_ERROR_ARCH, __FILE__, __LINE__, "Could not find switch block source track in vector of potential source tracks\n");
}
src_track_in_sp = it - potential_src_tracks.begin();
/* at this point the vectors 'potential_src_tracks' and 'potential_dest_tracks' contain the indices of the from_type/from_point
and to_type/to_point track segments. now its time to compute which destination track segments our specific track segment of interest
('from_track') should connect to */
/* get a reference to the string vector containing desired side1->side2 permutations */
Connect_SB_Sides side_conn(sb_conn.from_side, sb_conn.to_side);
vector<string> &permutations_ref = sb->permutation_map[side_conn];
/* iterate over the permutation functions specified in permutations_ref */
int to_track;
s_formula_data formula_data;
for (int iperm = 0; iperm < (int)permutations_ref.size(); iperm++){
/* Convert the symbolic permutation formula to a number */
formula_data.dest_W = dest_W;
if (0 == dest_W){
return;
}
formula_data.track = src_track_in_sp;
dest_track_in_sp = get_sb_formula_result(permutations_ref[iperm].c_str(), formula_data);
dest_track_in_sp = adjust_formula_result(dest_track_in_sp, dest_W);
if(dest_track_in_sp < 0){
vpr_throw(VPR_ERROR_ARCH, __FILE__, __LINE__, "Got a negative track from switch block formula %s", permutations_ref[iperm].c_str());
}
/* the resulting track number is the *index* of the destination track in it's own
set, so we need to convert that back to the absolute index of the track in the channel */
to_track = potential_dest_tracks[dest_track_in_sp];
/* create the struct containing information about the target track segment which will be added to the
sb connections map */
t_to_track_inf to_track_inf;
to_track_inf.to_track = to_track;
to_track_inf.switch_ind = to_chan_details[to_x][to_y][to_track].arch_wire_switch;
/* and now, finally, add this switchblock connection to the switchblock connections map */
//(*sb_conns)[sb_conn.x_coord][sb_conn.y_coord][sb_conn.from_side][sb_conn.to_side][sb_conn.from_track].push_back(to_track_inf);
(*sb_conns)[sb_conn.x_coord][sb_conn.y_coord][sb_conn.from_side][sb_conn.to_side][sb_conn.from_track].push_front(to_track_inf);
/* If bidir architecture, implement the reverse connection as well */
if (BI_DIRECTIONAL == directionality){
to_track_inf.to_track = sb_conn.from_track;
Switchblock_Lookup sb_conn_reverse(sb_conn.x_coord, sb_conn.y_coord, sb_conn.to_side, sb_conn.from_side, to_track);
//(*sb_conns)[sb_conn.x_coord][sb_conn.y_coord][sb_conn.to_side][sb_conn.from_side][to_track].push_back(to_track_inf);
(*sb_conns)[sb_conn.x_coord][sb_conn.y_coord][sb_conn.to_side][sb_conn.from_side][to_track].push_front(to_track_inf);
}
}
}
/* Here we find the correct channel (x or y), and the coordinates to index into it based on the
specified tile coordinates and the switchblock side. Also returns the type of channel
that we are indexing into (ie, CHANX or CHANY */
static t_rr_type index_into_correct_chan(INP int tile_x, INP int tile_y, INP enum e_side side,
INP t_chan_details *chan_details_x, INP t_chan_details *chan_details_y,
OUTP int *set_x, OUTP int *set_y,
OUTP t_chan_details **set_chan_details){
t_rr_type chan_type = CHANX;
/* here we use the VPR convention that a tile 'owns' the channels directly to the right
and above it */
switch (side){
case TOP:
/* this is y-channel belonging to tile above */
*set_chan_details = chan_details_y;
*set_x = tile_x;
*set_y = tile_y+1;
chan_type = CHANY;
break;
case RIGHT:
/* this is x-channel belonging to tile to the right */
*set_chan_details = chan_details_x;
*set_x = tile_x+1;
*set_y = tile_y;
chan_type = CHANX;
break;
case BOTTOM:
/* this is y-channel on the right of the tile */
*set_chan_details = chan_details_y;
*set_x = tile_x;
*set_y = tile_y;
chan_type = CHANY;
break;
case LEFT:
/* this is x-channel on top of the tile */
*set_chan_details = chan_details_x;
*set_x = tile_x;
*set_y = tile_y;
chan_type = CHANX;
break;
default:
vpr_throw(VPR_ERROR_ARCH, __FILE__, __LINE__, "index_into_correct_chan: unknown side specified: %d\n", side);
break;
}
return chan_type;
}
/* checks whether the specified coordinates are out of bounds */
static bool coords_out_of_bounds(INP int nx, INP int ny, INP int x_coord, INP int y_coord,
e_rr_type chan_type){
bool result = true;
if (CHANX == chan_type){
if (x_coord <=0 || x_coord >= nx+1 || /* there is no x-channel at x=0 */
y_coord < 0 || y_coord >= ny+1){
result = true;
} else {
result = false;
}
} else if (CHANY == chan_type){
if (x_coord < 0 || x_coord >= nx+1 ||
y_coord <= 0 || y_coord >= ny+1){ /* there is no y-channel at y=0 */
result = true;
} else {
result = false;
}
} else {
vpr_throw(VPR_ERROR_ARCH, __FILE__, __LINE__, "coords_out_of_bounds(): illegal channel type %d\n", chan_type);
}
return result;
}
/* We can look at a channel as either having an x and y coordinate, or as having a
'seg' and 'chan' coordinate. Here we return the seg coordinate based on the
channel type and channel x/y coordinates */
static int get_seg_coordinate(INP t_rr_type chan_type, INP int x_coord, INP int y_coord){
int seg = -1;
switch (chan_type){
case CHANX:
seg = x_coord;
break;
case CHANY:
seg = y_coord;
break;
default:
vpr_throw(VPR_ERROR_ARCH, __FILE__, __LINE__, "get_seg_coordinate: 'chan_type' %d is not a channel\n", chan_type);
break;
}
return seg;
}
/* returns the group number of the specified track */
static int get_track_group(INP int nx, INP int ny, INP e_rr_type chan_type,
INP t_seg_details &track_details, int seg_coord){
/* We get track group by comparing the track's seg_coord to the seg_start of the track.
The offset between seg_start (or seg_end) and seg_coord is the group number
Cases:
seg starts at bottom but does not extend all the way to the top -- look at seg_end
seg starts > bottom and does not extend all the way to top -- look at seg_start
seg starts > bottom but terminates all the way at the top -- look at seg_start
seg starts at bottom and extends all the way to the top -- look at seg end
*/
int group;
int seg_start = track_details.seg_start;
int seg_end = track_details.seg_end;
int track_length = get_track_segment_length(nx, ny, chan_type, track_details);
int min_seg;
/* determine the minimum and maximum values that the 'seg' coordinate
of a track can take */
min_seg = 1;
if (seg_start != min_seg){
group = seg_coord - seg_start;
} else {
group = (track_length-1) - (seg_end - seg_coord);
}
return group;
}
/* returns track segment length based on either:
1) the track length specified in the segment details variable for this track (if this track segment doesn't span entire FPGA)
2) the seg_start and seg_end coordinates in the segment details for this track (if this track segment spans entire FPGA, as might happen for very long wires)
Computing the track segment length in this way help to classify short vs long track segments according to wirepoint. */
int get_track_segment_length(INP int nx, INP int ny, INP e_rr_type chan_type, INP t_seg_details &track_details){
int track_length;
int min_seg = 1;
int max_seg = nx;
if (chan_type == CHANY){
max_seg = ny;
}
int seg_start = track_details.seg_start;
int seg_end = track_details.seg_end;
if (seg_start == min_seg && seg_end == max_seg){
track_length = seg_end - seg_start + 1;
} else {
track_length = track_details.length;
}
return track_length;
}
/* Returns the wirepoint of the track specified by track_details at a segment coordinate
of seg_coord, and connection to the sb_side of the switchblock */
static int get_wirepoint_of_track(INP int nx, INP int ny, INP e_rr_type chan_type,
INP t_seg_details &track_details, INP int seg_coord, INP e_side sb_side){
/* this function calculates the wirepoint of a given track by first calculating
the group of the specified track. For instance, for a track with L=4:
wirepoint: 0-------1-------2-------3-------0
group: 0 1 2 3
So knowing the track's group and which switchblock side it connects to is
enough to calculate the wirepoint
*/
int wirepoint;
/* get the minimum and maximum segment coordinate which a track in this channel type can take */
int min_seg = 1;
int max_seg = nx;
if (chan_type == CHANY){
max_seg = ny;
}
/* check whether the current seg_coord/sb_side coordinate specifies a perimeter switch block side at which all track segments terminate/start.
in this case only segments with wirepoints = 0 can exist */
bool perimeter_connection = false;
if ((seg_coord == min_seg && (sb_side == RIGHT || sb_side == TOP)) ||
(seg_coord == max_seg && (sb_side == LEFT || sb_side == BOTTOM))){
perimeter_connection = true;
}
if (perimeter_connection){
wirepoint = 0;
} else {
int track_length = get_track_segment_length(nx, ny, chan_type, track_details);
int group = get_track_group(nx, ny, chan_type, track_details, seg_coord);
if (LEFT == sb_side || BOTTOM == sb_side){
wirepoint = (group + 1) % track_length;
} else {
assert(RIGHT == sb_side || TOP == sb_side);
wirepoint = group;
}
}
return wirepoint;
}
/* adjusts a negative destination track calculated from a permutation formula */
static int adjust_formula_result(INP int dest_track, INP int dest_W){
int result = dest_track;
if (dest_track < 0){
int mult = (-1*dest_track) / dest_W + 1;
result = dest_track + mult*dest_W;
}
result = (result + dest_W) % dest_W;
return result;
}