NoC Routing¶
NocRouting¶
This file defines the NocRouting class, which handles the packet routing between routers within the NoC. It describes the routing algorithm for the NoC.
Overview¶
The NocRouting class is an abstract class. It is intended to be used as a base class and should not be used on its own. The NocRouting class is used as a base (interface) class.
Usage¶
When a new routing algorithm for the NoC is needed, a new class should be made that inherits this class. Then the following needs to be done:
The routing algorithm should be implemented inside the route_flow function and should match the prototype declared below
-
class NocRouting¶
- #include <noc_routing.h>
Subclassed by BFSRouting, TurnModelRouting
Public Functions
-
virtual ~NocRouting() = default¶
-
virtual void route_flow(NocRouterId src_router_id, NocRouterId sink_router_id, NocTrafficFlowId traffic_flow_id, std::vector<NocLinkId> &flow_route, const NocStorage &noc_model) = 0¶
Finds a route that goes from the starting router in a traffic flow to the destination router. A route consists of a series of links that should be traversed when travelling between two routers within the NoC. Derived classes will primarily differ by the routing algorithm they use. The expectation is that this function should be overridden in the derived classes to implement the routing algorithm.
- Parameters:
src_router_id – The source router of a traffic flow. Identifies the starting point of the route within the NoC. This represents a physical router on the FPGA.
sink_router_id – The destination router of a traffic flow. Identifies the ending point of the route within the NoC.This represents a physical router on the FPGA.
traffic_flow_id – The unique ID for the traffic flow being routed.
flow_route – Stores the path returned by this function as a series of NoC links found by a NoC routing algorithm between two routers in a traffic flow. The function will clear any previously stored path and re-insert the new found path between the two routers.
noc_model – A model of the NoC. This is used to traverse the NoC and find a route between the two routers.
-
virtual ~NocRouting() = default¶
NocRoutingAlgorithmCreator¶
This file defines the NocRoutingAlgorithmCreator class, which creates the routing algorithm that will be used to route packets within the NoC.
Overview¶
There are a number of different available NoC routing algorithms. This class is a factory object for the NocRouting abstract class. This class constructs the appropriate routing algorithm based on the user specification in the command line. The user identifies a specific routing algorithm in the command line by providing a string (which is the name of routing algorithm). Then the corresponding routing algorithm is created here based on the provided string.
-
class NocRoutingAlgorithmCreator¶
- #include <noc_routing_algorithm_creator.h>
Public Static Functions
-
static std::unique_ptr<NocRouting> create_routing_algorithm(const std::string &routing_algorithm_name)¶
Given a string that identifies a NoC routing algorithm, this function creates the corresponding routing algorithm and returns a reference to it. If the provided string does not match any available routing algorithms then an error is thrown.
- Parameters:
routing_algorithm_name – A user provided string that identifies a NoC routing algorithm
- Returns:
std::unique_ptr<NocRouting> A reference to the created NoC routing algorithm
-
static std::unique_ptr<NocRouting> create_routing_algorithm(const std::string &routing_algorithm_name)¶
XYRouting¶
This file defines the XYRouting class, which represents a direction oriented routing algorithm.
Overview¶
The XYRouting class performs packet routing between routers in the NoC. This class is based on the XY routing algorithm.
XY Routing Algorithm¶
The algorithm works by first travelling in the X-direction and then in the Y-direction.
First the algorithm compares the source router and the destination router, checking the coordinates in the X-axis. If the coordinates are not the same (so not horizontally aligned), then the algorithm moves in the direction towards the destination router in the X-axis. For each router in the path, the algorithm checks again to see whether it is horizontally aligned with the destination router; otherwise it moves in the direction of the destination router (once again the movement is done in the X-axis).
Once horizontally aligned (current router in the path has the same X-coordinate as the destination) the algorithm checks to see whether the y-axis coordinates match between the destination router and the current router in the path (checking for vertical alignment). Similar to the x-axis movement, the algorithm moves in the Y-axis towards the destination router. Once again, at each router in the path the algorithm checks for vertical alignment; if not aligned it then moves in the y-axis towards the destination router until it is aligned vertically.
The main aspect of this algorithm is that it is deterministic. It will always move in the horizontal direction and then the vertical direction to reach the destination router. The path is never affected by things like congestion, latency, distance and etc..).
Below we have an example of the path determined by this algorithm for a 3x3 mesh NoC:
--------- --------- ---------
/ / / / / /
/ $ / ----------------- / / ------------------ / /
/ / / / / /
--------- --------- ---------
/^ / /
/+ / /
/+ / /
/+ / /
--------- --------- ---------
/ / / / / /
/ / ----------------- / / ------------------ / /
/ / / / / /
--------- --------- ---------
/^ / /
/+ / /
/+ / /
/+ / /
--------- --------- ---------
/ /<++++++++++++++++++/ /<+++++++++++++++++++/ /
/ / ----------------- / / ------------------ / * /
/ / / / / /
--------- --------- ---------
Note that this routing algorithm in inherently deadlock free.
Usage¶
It is recommended to use this algorithm when the NoC topology is of type Mesh. This algorithm will work for other types of topologies but the directional nature of the algorithm makes it ideal for mesh topologies. If the algorithm fails to find a router then an error is thrown; this should only happen for non-mesh topologies. If this algorithms is used for non-mesh topologies, it might be able to generate routes for all traffic flows, but the generated routes are not guaranteed to be deadlock free in a non-mesh topology. Im mesh and torus topologies, xy-routing algorithm is guaranteed to generate deadlock free routes.
-
class XYRouting : public TurnModelRouting¶
- #include <xy_routing.h>
Public Functions
-
~XYRouting() override¶
Private Functions
-
virtual const std::vector<TurnModelRouting::Direction> &get_legal_directions(NocRouterId src_router_id, NocRouterId curr_router_id, NocRouterId dst_router_id, const NocStorage &noc_model) override¶
Returns legal directions that the traffic flow can follow. The legal directions might be a subset of all directions to guarantee deadlock freedom.
- Parameters:
src_router_id – A unique ID identifying the source NoC router.
curr_router_id – A unique ID identifying the current NoC router.
dst_router_id – A unique ID identifying the destination NoC router.
noc_model – A model of the NoC. This might be used by the derived class to determine the position of NoC routers.
- Returns:
std::vector<TurnModelRouting::Direction> All legal directions that the a traffic flow can follow.
-
virtual TurnModelRouting::Direction select_next_direction(const std::vector<TurnModelRouting::Direction> &legal_directions, NocRouterId src_router_id, NocRouterId dst_router_id, NocRouterId curr_router_id, NocTrafficFlowId traffic_flow_id, const NocStorage &noc_model) override¶
Selects a direction from legal directions. The traffic flow travels travels in that direction.
- Parameters:
legal_directions – Legal directions that the traffic flow can follow. Legal directions are usually a subset of all possible directions to ensure deadlock freedom.
src_router_id – A unique ID identifying the source NoC router.
dst_router_id – A unique ID identifying the destination NoC router.
curr_router_id – A unique ID identifying the current NoC router.
noc_model – A model of the NoC. This might be used by the derived class to determine the position of NoC routers.
- Returns:
Direction The direction to travel next
-
~XYRouting() override¶
BFSRouting¶
This file defines the BFSRouting class.
Overview¶
The BFSRouting class performs packet routing between physical routers in the FPGA. This class is based on the BFS algorithm.
The BFS algorithm is used to explore the NoC from the starting router in the traffic flow. Once the destination router is found a path from the source to the destination router is generated. The main advantage of this algorithm is that the found path from the source to the destination router uses the minimum number of links required within the NoC. This algorithm does not guarantee deadlock freedom. In other words, the algorithm might generate routes that form cycles in channel dependency graph.
-
class BFSRouting : public NocRouting¶
- #include <bfs_routing.h>
Public Functions
-
~BFSRouting() override¶
-
virtual void route_flow(NocRouterId src_router_id, NocRouterId sink_router_id, NocTrafficFlowId traffic_flow_id, std::vector<NocLinkId> &flow_route, const NocStorage &noc_model) override¶
Finds a route that goes from the starting router in a traffic flow to the destination router. Uses the BFS algorithm to determine the route. A route consists of a series of links that should be traversed when travelling between two routers within the NoC.
- Parameters:
src_router_id – The source router of a traffic flow. Identifies the starting point of the route within the NoC. This represents a physical router on the FPGA.
sink_router_id – The destination router of a traffic flow. Identifies the ending point of the route within the NoC.This represents a physical router on the FPGA.
traffic_flow_id – The unique ID for the traffic flow being routed.
flow_route – Stores the path returned by this fuction as a series of NoC links found by a NoC routing algorithm between two routers in a traffic flow. The function will clear any previously stored path and re-insert the new found path between the two routers.
noc_model – A model of the NoC. This is used to traverse the NoC and find a route between the two routers.
Private Functions
-
void generate_route(NocRouterId sink_router_id, std::vector<NocLinkId> &flow_route, const NocStorage &noc_model, const std::unordered_map<NocRouterId, NocLinkId> &router_parent_link)¶
Traces the path taken by the BFS routing algorithm from the destination router to the starting router. Starting with the destination router, the parent link (link taken to get to this router) is found and is added to the path. Then the algorithm moves to the source router of the parent link. Then it repeats the previous process of finding the parent link, adding it to the path and moving to the source router. This is repeated until the starting router is reached.
- Parameters:
start_router_id – The router to use as a starting point when tracing back the route from the destination router. to the the starting router. Generally this would be the sink router of the flow.
flow_route – Stores the path as a series of NoC links found by a NoC routing algorithm between two routers in a traffic flow. The function will clear any previously stored path and re-insert the new found path between the two routers.
noc_model – A model of the NoC. This is used to traverse the NoC and find a route between the two routers.
router_parent_link – Contains the parent link associated to each router in the NoC (parent link is the link used to visit the router during the BFS routing algorithm).
-
~BFSRouting() override¶