| /* |
| * Author(s): Oleg Petelin |
| * Last revised: September, 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/dest 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 |
| * s_det_routing_arch carries info about custom switch blocks |
| * build_switchblocks.c (this file): |
| * builds t_sb_connection_map sparse array containing target connections for each wire in each horizontal/vertical channel segment. |
| * 'compute_wire_connections' is the most important function here -- it computes the set of wire segments that a given wire at |
| * (x, y, from_side, to_side, from_wire) 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_wire_to_chan_seg is called within get_wire_to_wires which looks at t_sb_connection_map to create the edges that |
| * connect a source wire segment into a destination channel segment |
| * |
| * |
| ************ DESCRIPTION OF SWITCH BLOCK SPECIFICATION ************ |
| * Some terminology: |
| * |
| * Wire segment type: a named group of wires defined in the architecture file. |
| * Wire subsegment number: a number assigned to a wire subsegment relative to the wire's start coordinate (see diagram below). |
| * Used to define a collection of wire segments that have a start point in the same column (or row) of the FPGA. |
| * Wire switch point: a number assigned to a specific switch block along a wire segment |
| * |
| * Ex: for a length-4 unidirectional wire segment going in the decreasing direction: |
| * wire switch point 0<-------3<-------2<-------1<-------0 |
| * wire subsegment # 3 2 1 0 |
| * |
| * The new switch block format allows a user to specify mathematical permutation functions that describe how different types of wires will connect at different switchpoinnts. One or more wire types *and* one or more switch points define a set of wires, and each switch block connection is specified in terms of a source and destination set. Specifically, the permutation functions prescribe how a set of from_type/from_switchpoint wires (the source set) in one channel segment should connect to a set of to_type/to_switchpoint wires (the destination set) in an adjacent channel segment. This provides for an abstract but very flexible way of specifying different switch block patterns. |
| * |
| * An example from an 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). |
| * |
| * <!-- Specify that custom switch blocks will be used. This is backwards compatible with VPR's previous wilton/subset/univeral specification, |
| * but "custom" is specified instead. --> |
| * <switch_block type="custom"/> <-- backwards-compatible with VPR's previous wilton/subset/universal/full specification |
| * ... |
| * ... |
| * <!-- Segment specification is as before, except that a "name" is also specified for each segment. Each segment defines a type of wire. --> |
| * <segmentlist> |
| * <segment freq="0.85" name="l4" length="4" type="unidir" Rmetal="232" Cmetal="0.0"> |
| * <mux name="l4_mux"/> |
| * <sb type="pattern">1 1 1 1 1</sb> |
| * <cb type="pattern">1 1 1 1</cb> |
| * </segment> |
| * <segment freq="0.15" name="l8_global" length="8" type="unidir" Rmetal="33.8" Cmetal="0.0"> |
| * <mux name="l8_mux"/> |
| * <sb type="pattern">1 1 1 1 1 1 1 1 1</sb> |
| * <cb type="pattern">1 1 1 1 1 1 1 1</cb> |
| * </segment> |
| * </segmentlist> |
| * ... |
| * ... |
| * <!-- Custom switch blocks are declared here --> |
| * <switchblocklist> |
| * <!-- Each "switchblock" entry is given a name. Type specifies either a unidirectional or bidirectional switch block --> |
| * <switchblock name="my_switchblock" type="unidir"> |
| * <!-- Location to implement this switch block (EVERYWHERE/CORE/PERIMETER/CORNER/FRINGE) --> |
| * <switchblock_location type="EVERYWHERE"/> |
| * <!-- A list of permutation functions. Any number can be specified (for instance two "lt" entries can be specified to increase |
| * Fs of connections from the left to the top switch block sides --> |
| * <switchfuncs> |
| * <!-- "lr" means left-to-right, "lt" means left to top, etc. Formulas support different operators which are discussed later --> |
| * <func type="lr" formula="t"/> |
| * <func type="lt" formula="W-t"/> |
| * <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"/> |
| * <func type="rl" formula="t"/> |
| * <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"/> |
| * </switchfuncs> |
| * <!-- Wireconn entries define the sets of wires that should be connected with the above permutation functions --> |
| * <wireconn from_type="l4" to_type="l4" from_switchpoint="0,1,2,3" to_switchpoint="0"/> |
| * <wireconn from_type="l8_global" to_type="l8_global" from_switchpoint="0,4" to_switchpoint="0"/> |
| * <wireconn from_type="l8_global" to_type="l4" from_switchpoint="0,4" to_switchpoint="0"/> |
| * </switchblock> |
| * |
| * <switchblock name="another_switch_block" type="unidir"> |
| * ... switch block description ... |
| * </switchblock> |
| * </switchblocklist> |
| * |
| * 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 |
| * |
| */ |
| |
| #include <cstring> |
| #include <algorithm> |
| #include <iterator> |
| #include <iostream> |
| |
| #include "vtr_assert.h" |
| #include "vtr_memory.h" |
| #include "vtr_log.h" |
| |
| #include "vpr_error.h" |
| |
| #include "build_switchblocks.h" |
| #include "physical_types.h" |
| #include "parse_switchblocks.h" |
| #include "expr_eval.h" |
| |
| /************ 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 wire segment type */ |
| class Wire_Info { |
| public: |
| int length; /* the length of this type of wire segment in tiles */ |
| int num_wires; /* total number of wires in a channel segment (basically W) */ |
| int start; /* the wire index at which this type starts in the channel segment (0..W-1) */ |
| |
| void set(int len, int wires, int st) { |
| length = len; |
| num_wires = wires; |
| start = st; |
| } |
| Wire_Info() { |
| this->set(0, 0, 0); |
| } |
| Wire_Info(int len, int wires, int st) { |
| this->set(len, wires, st); |
| } |
| }; |
| |
| struct t_wire_switchpoint { |
| int wire; //Wire index within the channel |
| int switchpoint; //Switchpoint of the wire |
| }; |
| |
| /************ Typedefs ************/ |
| /* Used to get info about a given wire type based on the name */ |
| typedef std::map<std::string, Wire_Info> t_wire_type_sizes; |
| |
| /************ Function Declarations ************/ |
| /* Counts the number of wires in each wire type in the specified channel */ |
| static void count_wire_type_sizes(const t_chan_seg_details* channel, int nodes_per_chan, t_wire_type_sizes* wire_type_sizes); |
| |
| #ifdef FAST_SB_COMPUTATION |
| /* over all connected wire types (i,j), compute the maximum least common multiple of their wire lengths, |
| * ie max(LCM(L_i, L_J)) */ |
| static int get_max_lcm(vector<t_switchblock_inf>* switchblocks, t_wire_type_sizes* wire_type_sizes); |
| |
| /* compute all the switchblocks around the perimeter of the FPGA for the given switchblock and wireconn */ |
| static void compute_perimeter_switchblocks(t_chan_details* chan_details_x, t_chan_details* chan_details_y, vector<t_switchblock_inf>* switchblocks, const DeviceGrid& grid, int nodes_per_chan, t_wire_type_sizes* wire_type_sizes, e_directionality directionality, t_sb_connection_map* sb_conns); |
| |
| /* computes a horizontal line of switchblocks of size sb_row_size (or of grid.width()-4, whichever is smaller), starting |
| * at coordinate (1,1) */ |
| static void compute_switchblock_row(int sb_row_size, t_chan_details* chan_details_x, t_chan_details* chan_details_y, vector<t_switchblock_inf>* switchblocks, const DeviceGrid& grid, int nodes_per_chan, t_wire_type_sizes* wire_type_sizes, e_directionality directionality, 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(int sb_row_size, |
| int nodes_per_chan, |
| const DeviceGrid& grid, |
| t_wire_type_sizes* wire_type_sizes, |
| e_directionality directionality, |
| t_sb_connection_map* sb_row, |
| t_sb_connection_map* sb_conns); |
| |
| #endif //FAST_SB_COMPUTATION |
| |
| /* Compute the wire(s) that the wire at (x, y, from_side, to_side, from_wire) should connect to. |
| * sb_conns is updated with the result */ |
| static void compute_wire_connections(int x_coord, int y_coord, enum e_side from_side, enum e_side to_side, const t_chan_details& chan_details_x, const t_chan_details& chan_details_y, t_switchblock_inf* sb, const DeviceGrid& grid, t_wire_type_sizes* wire_type_sizes, e_directionality directionality, t_sb_connection_map* sb_conns, vtr::RandState& rand_state); |
| |
| /* ... sb_conn represents the 'coordinates' of the desired switch block connections */ |
| static void compute_wireconn_connections(const DeviceGrid& grid, e_directionality directionality, const t_chan_details& from_chan_details, const t_chan_details& to_chan_details, Switchblock_Lookup sb_conn, int from_x, int from_y, int to_x, int to_y, t_rr_type from_chan_type, t_rr_type to_chan_type, t_wire_type_sizes* wire_type_sizes, t_switchblock_inf* sb, t_wireconn_inf* wireconn_ptr, t_sb_connection_map* sb_conns, vtr::RandState& rand_state); |
| |
| static int evaluate_num_conns_formula(std::string num_conns_formula, int from_wire_count, int to_wire_count); |
| |
| /* returns the wire indices belonging to the types in 'wire_type_vec' and switchpoints in 'points' at the given channel segment */ |
| static std::vector<t_wire_switchpoint> get_switchpoint_wires(const DeviceGrid& grid, const t_chan_seg_details* chan_details, t_rr_type chan_type, int x, int y, e_side side, const std::vector<t_wire_switchpoints>& wire_switchpoints_vec, t_wire_type_sizes* wire_type_sizes, bool is_dest, SwitchPointOrder order, vtr::RandState& rand_state); |
| |
| static const t_chan_details& index_into_correct_chan(int tile_x, int tile_y, enum e_side side, const t_chan_details& chan_details_x, const t_chan_details& chan_details_y, int* chan_x, int* chan_y, t_rr_type* chan_type); |
| |
| /* checks whether the specified coordinates are out of bounds */ |
| static bool coords_out_of_bounds(const DeviceGrid& grid, int x_coord, int y_coord, e_rr_type chan_type); |
| |
| /* returns the subsegment number of the specified wire at seg_coord*/ |
| static int get_wire_subsegment_num(const DeviceGrid& grid, e_rr_type chan_type, const t_chan_seg_details& wire_details, int seg_coord); |
| |
| int get_wire_segment_length(const DeviceGrid& grid, e_rr_type chan_type, const t_chan_seg_details& wire_details); |
| |
| /* Returns the switchpoint of the wire specified by wire_details at a segment coordinate |
| * of seg_coord, and connection to the sb_side of the switchblock */ |
| static int get_switchpoint_of_wire(const DeviceGrid& grid, e_rr_type chan_type, const t_chan_seg_details& wire_details, int seg_coord, 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(const DeviceGrid& grid, int x, int y, e_sb_location location); |
| |
| /* checks if the specified coordinates represent a corner of the FPGA */ |
| static bool is_corner(const DeviceGrid& grid, int x, int y); |
| |
| /* checks if the specified coordinates correspond to one of the perimeter switchblocks */ |
| static bool is_perimeter(const DeviceGrid& grid, int x, int y); |
| |
| /* checks if the specified coordinates correspond to the core of the FPGA (i.e. not perimeter) */ |
| static bool is_core(const DeviceGrid& grid, int x, int y); |
| |
| /* adjusts a negative destination wire index calculated from a permutation formula */ |
| static int adjust_formula_result(int dest_wire, int src_W, int dest_W, int connection_ind); |
| |
| /************ Function Definitions ************/ |
| /* allocate and build the switchblock permutation map */ |
| t_sb_connection_map* alloc_and_load_switchblock_permutations(const t_chan_details& chan_details_x, |
| const t_chan_details& chan_details_y, |
| const DeviceGrid& grid, |
| std::vector<t_switchblock_inf> switchblocks, |
| t_chan_width* nodes_per_chan, |
| e_directionality directionality, |
| vtr::RandState& rand_state) { |
| /* 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_FATAL_ERROR(VPR_ERROR_ARCH, "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; |
| |
| /* We assume that x & y channels have the same ratios of wire 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_wire_type_sizes wire_type_sizes; |
| count_wire_type_sizes(chan_details_x[0][0].data(), channel_width, &wire_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, &wire_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, |
| grid, channel_width, &wire_type_sizes, directionality, sb_conns); |
| |
| /* compute the switchblock row */ |
| compute_switchblock_row(max_lcm, chan_details_x, chan_details_y, &switchblocks, |
| grid, channel_width, &wire_type_sizes, directionality, &sb_row); |
| |
| /* stamp-out the switchblock row throughout the rest of the FPGA */ |
| stampout_switchblocks_from_row(max_lcm, channel_width, |
| grid, &wire_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_FATAL_ERROR(VPR_ERROR_ARCH, "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. */ |
| for (size_t x_coord = 0; x_coord < grid.width(); x_coord++) { |
| for (size_t y_coord = 0; y_coord <= grid.height(); y_coord++) { |
| if (sb_not_here(grid, x_coord, y_coord, sb.location)) { |
| continue; |
| } |
| /* now we iterate over all the potential side1->side2 connections */ |
| for (e_side from_side : {TOP, RIGHT, BOTTOM, LEFT}) { |
| for (e_side to_side : {TOP, RIGHT, BOTTOM, LEFT}) { |
| /* Fill appropriate entry of the sb_conns map with vector specifying the wires |
| * the current wire will connect to */ |
| compute_wire_connections(x_coord, y_coord, from_side, to_side, |
| chan_details_x, chan_details_y, &sb, grid, |
| &wire_type_sizes, directionality, sb_conns, rand_state); |
| } |
| } |
| } |
| } |
| } |
| #endif |
| |
| return sb_conns; |
| } |
| |
| /* deallocates switch block connections sparse array */ |
| void free_switchblock_permutations(t_sb_connection_map* sb_conns) { |
| sb_conns->clear(); |
| delete sb_conns; |
| sb_conns = nullptr; |
| /* 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. */ |
| vtr::malloc_trim(0); |
| return; |
| } |
| |
| #ifdef FAST_SB_COMPUTATION |
| /* over all connected wire types (i,j), compute the maximum least common multiple of their wire lengths, |
| * ie max(LCM(L_i, L_J)) */ |
| static int get_max_lcm(vector<t_switchblock_inf>* switchblocks, t_wire_type_sizes* wire_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 ((*wire_type_sizes).find(wc->from_type[ifrom]) != (*wire_type_sizes).end() && (*wire_type_sizes).find(wc->to_type[ito]) != (*wire_type_sizes).end()) { |
| // the condition can fail if freq of a seg is 0 (so it is in wc, but not in wire_type_size) |
| int length1 = wire_type_sizes->at(wc->from_type[ifrom]).length; |
| int length2 = wire_type_sizes->at(wc->to_type[ito]).length; |
| int current_lcm = vtr::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 grid.width()-4, whichever is smaller), starting |
| * at coordinate (1,1) */ |
| static void compute_switchblock_row(int sb_row_size, t_chan_details* chan_details_x, t_chan_details* chan_details_y, vector<t_switchblock_inf>* switchblocks, const DeviceGrid& grid, int nodes_per_chan, t_wire_type_sizes* wire_type_sizes, e_directionality directionality, 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(grid, x, y, sb->location)) { |
| continue; |
| } |
| /* now we iterate over all the potential side1->side2 connections */ |
| for (e_side from_side : {TOP, RIGHT, BOTTOM, LEFT}) { |
| for (e_side to_side : {TOP, RIGHT, BOTTOM, LEFT}) { |
| /* Fill appropriate entry of the sb_conns map with vector specifying the wires |
| * the current wire will connect to */ |
| compute_wire_connections(x, y, from_side, to_side, |
| chan_details_x, chan_details_y, sb, grid, |
| wire_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(int sb_row_size, |
| int nodes_per_chan, |
| const DeviceGrid& grid, |
| t_wire_type_sizes* wire_type_sizes, |
| e_directionality directionality, |
| t_sb_connection_map* sb_row, |
| t_sb_connection_map* sb_conns) { |
| /* over all x coordinates that may need stamping out */ |
| for (int x = 1; x < grid.width() - 2; x++) { //-2 for no perim channels |
| /* over all y coordinates that may need stamping out */ |
| for (int y = 1; y < grid.height() - 2; y++) { //-2 for no perim channels |
| /* perimeter has been precomputed */ |
| if (is_perimeter(grid, x, y)) { |
| continue; |
| } |
| /* over each source side */ |
| for (e_side from_side : {TOP, RIGHT, BOTTOM, LEFT}) { |
| /* over each destination side */ |
| for (e_side to_side : {TOP, RIGHT, BOTTOM, LEFT}) { |
| /* can't connect a side to itself */ |
| if (from_side == to_side) { |
| continue; |
| } |
| /* over each source wire */ |
| for (int iwire = 0; iwire < nodes_per_chan; iwire++) { |
| /* 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, from_side, to_side, iwire); |
| Switchblock_Lookup copy_key(copy_x, copy_y, from_side, to_side, iwire); |
| |
| 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(t_chan_details* chan_details_x, t_chan_details* chan_details_y, vector<t_switchblock_inf>* switchblocks, const DeviceGrid& grid, int nodes_per_chan, t_wire_type_sizes* wire_type_sizes, e_directionality directionality, 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+=grid.width()-2 to make more explicit what the ranges of the loop are |
| for (y = 0; y < grid.height(); y++) { |
| if (sb_not_here(grid, x, y, sb->location)) { |
| continue; |
| } |
| /* now we iterate over all the potential side1->side2 connections */ |
| for (e_side from_side : {TOP, RIGHT, BOTTOM, LEFT}) { |
| for (e_side to_side : {TOP, RIGHT, BOTTOM, LEFT}) { |
| /* Fill appropriate entry of the sb_conns map with vector specifying the wires |
| * the current wire will connect to */ |
| compute_wire_connections(x, y, from_side, to_side, |
| chan_details_x, chan_details_y, sb, grid, |
| wire_type_sizes, directionality, sb_conns); |
| } |
| } |
| } |
| x = grid.width() - 2; //-2 for no perim channels |
| } |
| } |
| |
| 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 < grid.width(); x++) { |
| if (sb_not_here(grid, x, y, sb->location)) { |
| continue; |
| } |
| /* now we iterate over all the potential side1->side2 connections */ |
| for (e_side from_side : {TOP, RIGHT, BOTTOM, LEFT}) { |
| for (e_side to_side : {TOP, RIGHT, BOTTOM, LEFT}) { |
| /* Fill appropriate entry of the sb_conns map with vector specifying the wires |
| * the current wire will connect to */ |
| compute_wire_connections(x, y, from_side, to_side, |
| chan_details_x, chan_details_y, sb, grid, |
| wire_type_sizes, directionality, sb_conns); |
| } |
| } |
| } |
| y = grid.height() - 2; //-2 for no perim channels |
| } |
| } |
| } |
| |
| #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(const DeviceGrid& grid, int x, int y, 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(grid, x, y)) { |
| sb_not_here = false; |
| } |
| break; |
| case E_CORNER: |
| if (is_corner(grid, x, y)) { |
| sb_not_here = false; |
| } |
| break; |
| case E_CORE: |
| if (is_core(grid, x, y)) { |
| sb_not_here = false; |
| } |
| break; |
| case E_FRINGE: |
| if (is_perimeter(grid, x, y) && !is_corner(grid, x, y)) { |
| sb_not_here = false; |
| } |
| break; |
| default: |
| VPR_FATAL_ERROR(VPR_ERROR_ARCH, "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(const DeviceGrid& grid, int x, int y) { |
| bool is_corner = false; |
| if ((x == 0 && y == 0) || (x == 0 && y == int(grid.height()) - 2) || //-2 for no perim channels |
| (x == int(grid.width()) - 2 && y == 0) || //-2 for no perim channels |
| (x == int(grid.width()) - 2 && y == int(grid.height()) - 2)) { //-2 for no perim channels |
| is_corner = true; |
| } |
| return is_corner; |
| } |
| |
| /* checks if the specified coordinates correspond to one of the perimeter switchblocks */ |
| static bool is_perimeter(const DeviceGrid& grid, int x, int y) { |
| bool is_perimeter = false; |
| if (x == 0 || x == int(grid.width()) - 2 || y == 0 || y == int(grid.height()) - 2) { |
| 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(const DeviceGrid& grid, int x, int y) { |
| bool is_core = !is_perimeter(grid, x, y); |
| return is_core; |
| } |
| |
| /* Counts the number of wires in each wire type in the specified channel */ |
| static void count_wire_type_sizes(const t_chan_seg_details* channel, int nodes_per_chan, t_wire_type_sizes* wire_type_sizes) { |
| std::string wire_type; |
| std::string new_type; |
| int new_length, length; |
| int new_start, start; |
| int num_wires = 0; |
| Wire_Info wire_info; |
| |
| wire_type = channel[0].type_name(); |
| length = channel[0].length(); |
| start = 0; |
| for (int iwire = 0; iwire < nodes_per_chan; iwire++) { |
| new_type = channel[iwire].type_name(); |
| new_length = channel[iwire].length(); |
| new_start = iwire; |
| if (new_type != wire_type) { |
| wire_info.set(length, num_wires, start); |
| (*wire_type_sizes)[wire_type] = wire_info; |
| wire_type = new_type; |
| length = new_length; |
| start = new_start; |
| num_wires = 0; |
| } |
| num_wires++; |
| } |
| wire_info.set(length, num_wires, start); |
| (*wire_type_sizes)[wire_type] = wire_info; |
| |
| return; |
| } |
| |
| /* returns the wire indices belonging to the types in 'wire_type_vec' and switchpoints in 'points' at the given channel segment */ |
| static std::vector<t_wire_switchpoint> get_switchpoint_wires(const DeviceGrid& grid, const t_chan_seg_details* chan_details, t_rr_type chan_type, int x, int y, e_side side, const std::vector<t_wire_switchpoints>& wire_switchpoints_vec, t_wire_type_sizes* wire_type_sizes, bool is_dest, SwitchPointOrder switchpoint_order, vtr::RandState& rand_state) { |
| std::vector<t_wire_switchpoint> all_collected_wire_switchpoints; |
| |
| int seg_coord = x; |
| if (chan_type == CHANY) { |
| seg_coord = y; |
| } |
| |
| for (const t_wire_switchpoints& wire_switchpoints : wire_switchpoints_vec) { |
| std::vector<t_wire_switchpoint> collected_wire_switchpoints; |
| |
| const auto& wire_type = wire_switchpoints.segment_name; |
| const auto& points = wire_switchpoints.switchpoints; |
| |
| if ((*wire_type_sizes).find(wire_type) == (*wire_type_sizes).end()) { |
| // wire_type_sizes may not contain wire_type if its seg freq is 0 |
| continue; |
| } |
| /* get the number of wires of given type */ |
| int num_type_wires = wire_type_sizes->at(wire_type).num_wires; |
| /* get the last wire belonging to this type */ |
| int first_type_wire = wire_type_sizes->at(wire_type).start; |
| int last_type_wire = first_type_wire + num_type_wires - 1; |
| |
| /* Walk through each wire segment of specified type and check whether it matches one |
| * of the specified switchpoints. |
| * |
| * Note that we walk through the points in order, this ensures that returned switchpoints |
| * match the order specified in the architecture, which we assume is a priority order specified |
| * by the archtitect. |
| */ |
| for (int valid_switchpoint : points) { |
| for (int iwire = first_type_wire; iwire <= last_type_wire; iwire++) { |
| e_direction seg_direction = chan_details[iwire].direction(); |
| |
| /* unidirectional wires going in the decreasing direction can have an outgoing edge |
| * only from the top or right switch block sides, and an incoming edge only if they are |
| * at the left or bottom sides (analogous for wires going in INC direction) */ |
| if (side == TOP || side == RIGHT) { |
| if (seg_direction == DEC_DIRECTION && is_dest) { |
| continue; |
| } |
| if (seg_direction == INC_DIRECTION && !is_dest) { |
| continue; |
| } |
| } else { |
| VTR_ASSERT(side == LEFT || side == BOTTOM); |
| if (seg_direction == DEC_DIRECTION && !is_dest) { |
| continue; |
| } |
| if (seg_direction == INC_DIRECTION && is_dest) { |
| continue; |
| } |
| } |
| |
| int wire_switchpoint = get_switchpoint_of_wire(grid, chan_type, chan_details[iwire], seg_coord, side); |
| |
| /* check if this wire belongs to one of the specified switchpoints; add it to our 'wires' vector if so */ |
| if (wire_switchpoint != valid_switchpoint) continue; |
| |
| collected_wire_switchpoints.push_back({iwire, wire_switchpoint}); |
| } |
| } |
| |
| all_collected_wire_switchpoints.insert(all_collected_wire_switchpoints.end(), |
| collected_wire_switchpoints.begin(), collected_wire_switchpoints.end()); |
| } |
| |
| if (switchpoint_order == SwitchPointOrder::SHUFFLED) { |
| //We new re-order the switchpoints to try to make adjacent switchpoints have different values |
| |
| vtr::shuffle(all_collected_wire_switchpoints.begin(), all_collected_wire_switchpoints.end(), rand_state); |
| } else { |
| VTR_ASSERT(switchpoint_order == SwitchPointOrder::FIXED); |
| //Already ordered so same switchpoints are adjacent by above collection loop |
| } |
| |
| return all_collected_wire_switchpoints; |
| } |
| |
| /* Compute the wire(s) that the wire at (x, y, from_side, to_side) should connect to. |
| * sb_conns is updated with the result */ |
| static void compute_wire_connections(int x_coord, int y_coord, enum e_side from_side, enum e_side to_side, const t_chan_details& chan_details_x, const t_chan_details& chan_details_y, t_switchblock_inf* sb, const DeviceGrid& grid, t_wire_type_sizes* wire_type_sizes, e_directionality directionality, t_sb_connection_map* sb_conns, vtr::RandState& rand_state) { |
| 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; |
| |
| SB_Side_Connection 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); /* 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 */ |
| /* details for source channel */ |
| const t_chan_details& from_chan_details = index_into_correct_chan(x_coord, y_coord, from_side, chan_details_x, chan_details_y, |
| &from_x, &from_y, &from_chan_type); |
| |
| /* details for destination channel */ |
| const t_chan_details& to_chan_details = index_into_correct_chan(x_coord, y_coord, to_side, chan_details_x, chan_details_y, |
| &to_x, &to_y, &to_chan_type); |
| |
| /* make sure from_x/y and to_x/y aren't out of bounds */ |
| if (coords_out_of_bounds(grid, to_x, to_y, to_chan_type) || coords_out_of_bounds(grid, 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 wire types/subsegment_nums */ |
| t_wireconn_inf* wireconn_ptr = &sb->wireconns[iconn]; |
| |
| /* compute the destination wire segments to which the source wire segment should connect based on the |
| * current wireconn */ |
| compute_wireconn_connections(grid, directionality, from_chan_details, to_chan_details, |
| sb_conn, from_x, from_y, to_x, to_y, from_chan_type, to_chan_type, wire_type_sizes, |
| sb, wireconn_ptr, sb_conns, rand_state); |
| } |
| |
| return; |
| } |
| |
| /* computes the destination wire segments that a source wire 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 wire segments (based on wire segment type & switchpoint |
| * as defined at the top of this file), and the indices of wires to connect to are relative to these sets */ |
| static void compute_wireconn_connections(const DeviceGrid& grid, e_directionality directionality, const t_chan_details& from_chan_details, const t_chan_details& to_chan_details, Switchblock_Lookup sb_conn, int from_x, int from_y, int to_x, int to_y, t_rr_type from_chan_type, t_rr_type to_chan_type, t_wire_type_sizes* wire_type_sizes, t_switchblock_inf* sb, t_wireconn_inf* wireconn_ptr, t_sb_connection_map* sb_conns, vtr::RandState& rand_state) { |
| constexpr bool verbose = false; |
| |
| /* vectors that will contain indices of the wires belonging to the source/dest wire types/points */ |
| |
| std::vector<t_wire_switchpoint> potential_src_wires = get_switchpoint_wires(grid, from_chan_details[from_x][from_y].data(), from_chan_type, from_x, from_y, sb_conn.from_side, |
| wireconn_ptr->from_switchpoint_set, wire_type_sizes, false, wireconn_ptr->from_switchpoint_order, rand_state); |
| |
| std::vector<t_wire_switchpoint> potential_dest_wires = get_switchpoint_wires(grid, to_chan_details[to_x][to_y].data(), to_chan_type, to_x, to_y, sb_conn.to_side, |
| wireconn_ptr->to_switchpoint_set, wire_type_sizes, true, wireconn_ptr->to_switchpoint_order, rand_state); |
| |
| VTR_LOGV(verbose, "SB_LOC: %d,%d %s->%s\n", sb_conn.x_coord, sb_conn.y_coord, SIDE_STRING[sb_conn.from_side], SIDE_STRING[sb_conn.to_side]); |
| |
| //Define to print out specific wire-switchpoints used in to/from sets, if verbose is set true |
| #if 0 |
| for (auto from_set : wireconn_ptr->from_switchpoint_set) { |
| VTR_LOGV(verbose, " FROM_SET: %s @", from_set.segment_name.c_str()); |
| for (int switchpoint : from_set.switchpoints) { |
| VTR_LOGV(verbose, "%d ", switchpoint); |
| } |
| } |
| VTR_LOGV(verbose, "\n"); |
| |
| for (auto to_set : wireconn_ptr->to_switchpoint_set) { |
| VTR_LOGV(verbose, " TO_SET: %s @", to_set.segment_name.c_str()); |
| for (int switchpoint : to_set.switchpoints) { |
| VTR_LOGV(verbose, "%d ", switchpoint); |
| } |
| } |
| VTR_LOGV(verbose, "\n"); |
| |
| vector<std::string> src_wire_str; |
| for (t_wire_switchpoint wire_switchpoint : potential_src_wires) { |
| src_wire_str.push_back(std::to_string(wire_switchpoint.wire) + "@" + std::to_string(wire_switchpoint.switchpoint)); |
| } |
| vector<std::string> dst_wire_str; |
| for (t_wire_switchpoint wire_switchpoint : potential_dest_wires) { |
| dst_wire_str.push_back(std::to_string(wire_switchpoint.wire) + "@" + std::to_string(wire_switchpoint.switchpoint)); |
| } |
| auto src_str = vtr::join(src_wire_str, ", "); |
| auto dst_str = vtr::join(dst_wire_str, ", "); |
| VTR_LOGV(verbose, " SRC_WIRES: %s\n", src_str.c_str()); |
| VTR_LOGV(verbose, " DST_WIRES: %s\n", dst_str.c_str()); |
| #endif |
| |
| if (potential_src_wires.size() == 0 || potential_dest_wires.size() == 0) { |
| //Can't make any connections between empty sets |
| return; |
| } |
| |
| /* At this point the vectors 'potential_src_wires' and 'potential_dest_wires' contain the indices of the from_type/from_point |
| * and to_type/to_point wire segments. Now we compute the connections between them, according to permutation functions */ |
| size_t src_W = potential_src_wires.size(); |
| size_t dest_W = potential_dest_wires.size(); |
| |
| //TODO: We could add another user-configurable parameter to control ordering of types in the sets. |
| // Currently we just iterate through them in order, but we could: |
| // * randomly shuffle, or |
| // * interleave (to ensure good diversity) |
| |
| //Determine how many connections to make |
| int num_conns = evaluate_num_conns_formula(wireconn_ptr->num_conns_formula, potential_src_wires.size(), potential_dest_wires.size()); |
| VTR_ASSERT_MSG(num_conns >= 0, "Number of switchblock connections to create must be non-negative"); |
| |
| VTR_LOGV(verbose, " num_conns: %zu\n", num_conns); |
| |
| for (size_t iconn = 0; iconn < size_t(num_conns); ++iconn) { |
| //Select the from wire |
| // We modulo by the src set size to wrap around if there are more connections that src wires |
| int src_wire_ind = iconn % potential_src_wires.size(); //Index in src set |
| int from_wire = potential_src_wires[src_wire_ind].wire; //Index in channel |
| |
| e_direction from_wire_direction = from_chan_details[from_x][from_y][from_wire].direction(); |
| if (from_wire_direction == INC_DIRECTION) { |
| /* if this is a unidirectional wire 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) { |
| continue; |
| } |
| VTR_ASSERT(sb_conn.from_side == BOTTOM || sb_conn.from_side == LEFT); |
| } else if (from_wire_direction == DEC_DIRECTION) { |
| /* a wire 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) { |
| continue; |
| } |
| VTR_ASSERT(sb_conn.from_side == TOP || sb_conn.from_side == RIGHT); |
| } else { |
| VTR_ASSERT(from_wire_direction == BI_DIRECTION); |
| } |
| |
| //Evaluate permutation functions for the from_wire |
| SB_Side_Connection side_conn(sb_conn.from_side, sb_conn.to_side); |
| std::vector<std::string>& permutations_ref = sb->permutation_map[side_conn]; |
| for (int iperm = 0; iperm < (int)permutations_ref.size(); iperm++) { |
| /* Convert the symbolic permutation formula to a number */ |
| t_formula_data formula_data; |
| formula_data.set_var_value("W", dest_W); |
| formula_data.set_var_value("t", src_wire_ind); |
| int raw_dest_wire_ind = get_sb_formula_raw_result(permutations_ref[iperm].c_str(), formula_data); |
| int dest_wire_ind = adjust_formula_result(raw_dest_wire_ind, src_W, dest_W, iconn); |
| |
| if (dest_wire_ind < 0) { |
| VPR_FATAL_ERROR(VPR_ERROR_ARCH, "Got a negative wire from switch block formula %s", permutations_ref[iperm].c_str()); |
| } |
| |
| int to_wire = potential_dest_wires[dest_wire_ind].wire; //Index in channel |
| |
| /* create the struct containing information about the target wire segment which will be added to the |
| * sb connections map */ |
| t_switchblock_edge sb_edge; |
| sb_edge.from_wire = from_wire; |
| sb_edge.to_wire = to_wire; |
| sb_edge.switch_ind = to_chan_details[to_x][to_y][to_wire].arch_wire_switch(); |
| VTR_LOGV(verbose, " make_conn: %d -> %d switch=%d\n", sb_edge.from_wire, sb_edge.to_wire, sb_edge.switch_ind); |
| |
| /* and now, finally, add this switchblock connection to the switchblock connections map */ |
| (*sb_conns)[sb_conn].push_back(sb_edge); |
| |
| /* If bidir architecture, implement the reverse connection as well */ |
| if (BI_DIRECTIONAL == directionality) { |
| t_switchblock_edge sb_reverse_edge = sb_edge; |
| std::swap(sb_reverse_edge.from_wire, sb_reverse_edge.to_wire); |
| //Since we are implementing the reverse connection we have swapped from and to. |
| // |
| //Coverity flags this (false positive), so annotatate so coverity ignores it: |
| // coverity[swapped_arguments : Intentional] |
| Switchblock_Lookup sb_conn_reverse(sb_conn.x_coord, sb_conn.y_coord, sb_conn.to_side, sb_conn.from_side); |
| (*sb_conns)[sb_conn_reverse].push_back(sb_reverse_edge); |
| } |
| } |
| } |
| } |
| |
| static int evaluate_num_conns_formula(std::string num_conns_formula, int from_wire_count, int to_wire_count) { |
| t_formula_data vars; |
| |
| vars.set_var_value("from", from_wire_count); |
| vars.set_var_value("to", to_wire_count); |
| |
| return parse_formula(num_conns_formula, vars); |
| } |
| |
| /* 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 const t_chan_details& index_into_correct_chan(int tile_x, int tile_y, enum e_side side, const t_chan_details& chan_details_x, const t_chan_details& chan_details_y, int* set_x, int* set_y, t_rr_type* chan_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_x = tile_x; |
| *set_y = tile_y + 1; |
| *chan_type = CHANY; |
| return chan_details_y; |
| break; |
| case RIGHT: |
| /* this is x-channel belonging to tile to the right */ |
| *set_x = tile_x + 1; |
| *set_y = tile_y; |
| *chan_type = CHANX; |
| return chan_details_x; |
| break; |
| case BOTTOM: |
| /* this is y-channel on the right of the tile */ |
| *set_x = tile_x; |
| *set_y = tile_y; |
| *chan_type = CHANY; |
| return chan_details_y; |
| break; |
| case LEFT: |
| /* this is x-channel on top of the tile */ |
| *set_x = tile_x; |
| *set_y = tile_y; |
| *chan_type = CHANX; |
| return chan_details_x; |
| break; |
| default: |
| VPR_FATAL_ERROR(VPR_ERROR_ARCH, "index_into_correct_chan: unknown side specified: %d\n", side); |
| break; |
| } |
| VTR_ASSERT(false); |
| return chan_details_x; //Unreachable |
| } |
| |
| /* checks whether the specified coordinates are out of bounds */ |
| static bool coords_out_of_bounds(const DeviceGrid& grid, int x_coord, int y_coord, e_rr_type chan_type) { |
| bool result = true; |
| |
| if (CHANX == chan_type) { |
| if (x_coord <= 0 || x_coord >= int(grid.width()) - 1 || /* there is no x-channel at x=0 */ |
| y_coord < 0 || y_coord >= int(grid.height()) - 1) { |
| result = true; |
| } else { |
| result = false; |
| } |
| } else if (CHANY == chan_type) { |
| if (x_coord < 0 || x_coord >= int(grid.width()) - 1 || y_coord <= 0 || y_coord >= int(grid.height()) - 1) { /* there is no y-channel at y=0 */ |
| result = true; |
| } else { |
| result = false; |
| } |
| |
| } else { |
| VPR_FATAL_ERROR(VPR_ERROR_ARCH, "coords_out_of_bounds(): illegal channel type %d\n", chan_type); |
| } |
| return result; |
| } |
| |
| /* returns the subsegment number of the specified wire at seg_coord */ |
| static int get_wire_subsegment_num(const DeviceGrid& grid, e_rr_type chan_type, const t_chan_seg_details& wire_details, int seg_coord) { |
| /* We get wire subsegment number by comparing the wire's seg_coord to the seg_start of the wire. |
| * The offset between seg_start (or seg_end) and seg_coord is the subsegment 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 subsegment_num; |
| int seg_start = wire_details.seg_start(); |
| int seg_end = wire_details.seg_end(); |
| e_direction direction = wire_details.direction(); |
| int wire_length = get_wire_segment_length(grid, chan_type, wire_details); |
| int min_seg; |
| |
| /* determine the minimum and maximum values that the 'seg' coordinate |
| * of a wire can take */ |
| min_seg = 1; |
| |
| if (seg_start != min_seg) { |
| subsegment_num = seg_coord - seg_start; |
| } else { |
| subsegment_num = (wire_length - 1) - (seg_end - seg_coord); |
| } |
| |
| /* if this wire is going in the decreasing direction, reverse the subsegment num */ |
| VTR_ASSERT(seg_end >= seg_start); |
| if (direction == DEC_DIRECTION) { |
| subsegment_num = wire_length - 1 - subsegment_num; |
| } |
| |
| return subsegment_num; |
| } |
| |
| /* returns wire segment length based on either: |
| * 1) the wire length specified in the segment details variable for this wire (if this wire segment doesn't span entire FPGA) |
| * 2) the seg_start and seg_end coordinates in the segment details for this wire (if this wire segment spans entire FPGA, as might happen for very long wires) |
| * |
| * Computing the wire segment length in this way help to classify short vs long wire segments according to switchpoint. */ |
| int get_wire_segment_length(const DeviceGrid& grid, e_rr_type chan_type, const t_chan_seg_details& wire_details) { |
| int wire_length; |
| |
| int min_seg = 1; |
| int max_seg = grid.width() - 2; //-2 for no perim channels |
| if (chan_type == CHANY) { |
| max_seg = grid.height() - 2; //-2 for no perim channels |
| } |
| |
| int seg_start = wire_details.seg_start(); |
| int seg_end = wire_details.seg_end(); |
| |
| if (seg_start == min_seg && seg_end == max_seg) { |
| wire_length = seg_end - seg_start + 1; |
| } else { |
| wire_length = wire_details.length(); |
| } |
| |
| return wire_length; |
| } |
| |
| /* Returns the switchpoint of the wire specified by wire_details at a segment coordinate |
| * of seg_coord, and connection to the sb_side of the switchblock */ |
| static int get_switchpoint_of_wire(const DeviceGrid& grid, e_rr_type chan_type, const t_chan_seg_details& wire_details, int seg_coord, e_side sb_side) { |
| /* this function calculates the switchpoint of a given wire by first calculating |
| * the subsegmennt number of the specified wire. For instance, for a wire with L=4: |
| * |
| * switchpoint: 0-------1-------2-------3-------0 |
| * subsegment_num: 0 1 2 3 |
| * |
| * So knowing the wire's subsegment_num and which switchblock side it connects to is |
| * enough to calculate the switchpoint |
| * |
| */ |
| |
| int switchpoint; |
| |
| /* get the minimum and maximum segment coordinate which a wire in this channel type can take */ |
| int min_seg = 1; |
| int max_seg = grid.width() - 2; //-2 for no perim channels |
| if (chan_type == CHANY) { |
| max_seg = grid.height() - 2; //-2 for no perim channels |
| } |
| |
| /* check whether the current seg_coord/sb_side coordinate specifies a perimeter switch block side at which all wire segments terminate/start. |
| * in this case only segments with switchpoints = 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) { |
| switchpoint = 0; |
| } else { |
| int wire_length = get_wire_segment_length(grid, chan_type, wire_details); |
| int subsegment_num = get_wire_subsegment_num(grid, chan_type, wire_details, seg_coord); |
| |
| e_direction direction = wire_details.direction(); |
| if (LEFT == sb_side || BOTTOM == sb_side) { |
| switchpoint = (subsegment_num + 1) % wire_length; |
| if (direction == DEC_DIRECTION) { |
| switchpoint = subsegment_num; |
| } |
| } else { |
| VTR_ASSERT(RIGHT == sb_side || TOP == sb_side); |
| switchpoint = subsegment_num; |
| if (direction == DEC_DIRECTION) { |
| switchpoint = (subsegment_num + 1) % wire_length; |
| } |
| } |
| } |
| |
| return switchpoint; |
| } |
| |
| /* adjusts the destination wire calculated from a permutation formula to account for negative indicies, |
| * source wire set offset, and modulo by destination wire set size |
| * */ |
| static int adjust_formula_result(int dest_wire, int src_W, int dest_W, int connection_ind) { |
| int result = dest_wire; |
| |
| if (dest_wire < 0) { |
| //Adjust for negative indicies |
| int mult = (-1 * dest_wire) / dest_W + 1; |
| result = dest_wire + mult * dest_W; |
| } |
| |
| //Offset the destination track by a multiple of src_W to ensure all destination tracks are covered |
| // |
| // The permutation formula produce a 1-to-1 mapping from src track to dest track (i.e. each source |
| // track is mapped to precisely one destination track). This is problematic if we are processing |
| // a wireconn which goes through the source set multiple times (e.g. dest set larger than src set while |
| // processing a WireConnType::TO), since the permutation formula will only generate src_W track indicies |
| // (leaving some of the destination tracks unconnected). To ensure we get different destination tracks on |
| // subsequent passes through the same source set, we offset the raw track by a multiple of src_W. Note the |
| // use of integer division; src_mult will equal 0 on the first pass, 1 on the second etc. |
| int src_mult = connection_ind / src_W; |
| result += src_W * src_mult; |
| |
| //Final result must be modulo dest_W |
| result = (result + dest_W) % dest_W; |
| |
| return result; |
| } |
