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, XYRouting

Public Functions

inline virtual ~NocRouting()
virtual void route_flow(NocRouterId src_router_id, NocRouterId sink_router_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.

  • 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.

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 Functions

inline NocRoutingAlgorithmCreator()
inline ~NocRoutingAlgorithmCreator()

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:

NocRouting* A reference to the created NoC routing algorithm

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:

---------                   ---------                    ---------
/       /                   /       /                    /       /
/   $   / ----------------- /       / ------------------ /       /
/       /                   /       /                    /       /
---------                   ---------                    --------- 
    /^                          /                            /
    /+                          /                            /
    /+                          /                            /
    /+                          /                            /
---------                   ---------                    ---------
/       /                   /       /                    /       /
/       / ----------------- /       / ------------------ /       /
/       /                   /       /                    /       /
---------                   ---------                    ---------     
    /^                          /                            /
    /+                          /                            /
    /+                          /                            /
    /+                          /                            /
---------                   ---------                    ---------
/       /<++++++++++++++++++/       /<+++++++++++++++++++/       /
/       / ----------------- /       / ------------------ /   *   /
/       /                   /       /                    /       /
---------                   ---------                    ---------
In the example above, the router marked with the ‘*’ character is the start and the router marked with the ‘$’ character is the destination. The path determined by the XY-Routing algorithm is shown as “<++++”.

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.

Enums

enum class RouteDirection

This enum describes the all the possible directions the XY routing algorithm can choose to travel.

Values:

enumerator LEFT

Moving towards the negative X-axis

enumerator RIGHT

Moving towards the positive X-axis

enumerator UP

Moving towards the positive Y-axis

enumerator DOWN

Moving towards the negative Y-axis

class XYRouting : public NocRouting
#include <xy_routing.h>

Public Functions

~XYRouting() override
virtual void route_flow(NocRouterId src_router_id, NocRouterId sink_router_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 XY-routing 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.

  • 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.

Private Functions

RouteDirection get_direction_to_travel(int sink_router_x_position, int sink_router_y_position, int curr_router_x_position, int curr_router_y_position)

Based on the position of the current router the algorithm is visiting, this function determines the next direction to travel.

Parameters:
  • sink_router_x_position – The horizontal grid position of the destination router on the FPGA

  • sink_router_y_position – The vertical grid position of the destination router on the FPGA

  • curr_router_x_position – The horizontal grid position of the router that is currently being visited on the FPGA

  • curr_router_y_position – The vertical grid position of the router that is currently being visited on the FPGA

Returns:

RouteDirection The direction to travel next

bool move_to_next_router(NocRouterId &curr_router_id, int curr_router_x_position, int curr_router_y_position, RouteDirection next_step_direction, std::vector<NocLinkId> &flow_route, std::unordered_set<NocRouterId> &visited_routers, const NocStorage &noc_model)

Given the direction to travel next, this function determines the outgoing link that should be used to travel in the intended direction. Each router may have any number of outgoing links and each link is not guaranteed to point in the intended direction, So this function makes sure that the link chosen points in the intended direction.

Parameters:
  • curr_router_id – The physical router on the FPGA that the routing algorithm is currently visiting.

  • curr_router_x_position – The horizontal grid position of the router that is currently being visited on the FPGA

  • curr_router_y_position – he vertical grid position of the router that is currently being visited on the FPGA

  • next_step_direction – The direction to travel next

  • 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 NoC link found to travel next will be added to this path.

  • visited_routers – Keeps track of which routers have been reached already while traversing the NoC.

  • noc_model – A model of the NoC. This is used to traverse the NoC and find a route between the two routers.

Returns:

true A suitable link was found that we can traverse next

Returns:

false No suitable link was found that could be traversed

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.

class BFSRouting : public NocRouting
#include <bfs_routing.h>

Public Functions

~BFSRouting() override
virtual void route_flow(NocRouterId src_router_id, NocRouterId sink_router_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.

  • 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).