Routing Configuration

In Constellation, the desired routing relation is specified by the user as an abstract Scala function, instead of an RTL implementation of a routing table. Constellation will use this function to “compile” a hardware implementation of the desired routing algorithm.

abstract class RoutingRelation(topo: PhysicalTopology) {
  // Child classes must implement these
  def rel       (srcC: ChannelRoutingInfo,
                 nxtC: ChannelRoutingInfo,
                 flow: FlowRoutingInfo): Boolean

  def isEscape  (c: ChannelRoutingInfo,
                 vNetId: Int): Boolean = true

  def getNPrios (src: ChannelRoutingInfo): Int = 1

  def getPrio   (srcC: ChannelRoutingInfo,
                 nxtC: ChannelRoutingInfo,
                 flow: FlowRoutingInfo): Int = 0

Channel Identifier

The ChannelRoutingInfo case class uniquely identifies a virtual channel, ingress channel, or egress channel in the system.

case class ChannelRoutingInfo(
  src: Int,
  dst: Int,
  vc: Int,
  n_vc: Int
) {

The fields of this case class are:

  • src is the source physical node of the channel. If this is an ingress channel, this value is -1.

  • dst is the destination physical node of the channel. If this is an egress channel, this value is -1.

  • vc is the virtual channel index within the channel.

  • n_vc is the number of available virtual channels in this physical channel.

Consider a toy network depicted below with bidirectional physical channels, and two virtual channels on each physical channel. The list of all possible ChannelRoutingInfo in this network is shown

// Ingresses
ChannelRoutingInfo(src=-1, dst=0, vc=0, n_vc=1)
ChannelRoutingInfo(src=-1, dst=1, vc=0, n_vc=1)

// Egresses
ChannelRoutingInfo(src=0, dst=0, vc=0, n_vc=1)
ChannelRoutingInfo(src=0, dst=3, vc=0, n_vc=1)

// Routing channels
ChannelRoutingInfo(src=0, dst=1, vc=0, n_vc=2)
ChannelRoutingInfo(src=0, dst=1, vc=1, n_vc=2)
ChannelRoutingInfo(src=1, dst=0, vc=0, n_vc=2)
ChannelRoutingInfo(src=1, dst=0, vc=1, n_vc=2)
...

terminals

Note

In the current implementations, packets arriving at the egress physical node are always directed to the egress. Thus, ChannelRoutingInfo for the egress channels are not used. Additionally, this limitation prevents the implementation of deflection routing algorithms

Flow Identifier

The FlowRoutingInfo case class uniquely identifies a potential flow, or packet that might traverse the NoC.

case class FlowRoutingInfo(
  ingressId: Int,
  egressId: Int,
  vNetId: Int,
  ingressNode: Int,
  ingressNodeId: Int,
  egressNode: Int,
  egressNodeId: Int,
  fifo: Boolean
) {

The fields of this case class are:

  • ingressId is the ingress index of the flow.

  • ingressNode is the physical node of the ingress of this flow.

  • ingressNodeId is the index of the ingress within all ingresses at the physical node.

  • egressId is the egress index of the flow

  • egressNode is the physical node of the egress of this flow

  • egressNodeId is the physical node of the egress within all egresses at the physical node

  • vNetId is the virtual subnetwork identifier of this flow

As an example, consider the same topology with two virtual subnetworks, for odd and even ingress and egresses.

                         egressId
          ingressNodeId  |  egressNode
         ingressNode  |  |  |  egressNodeId
        ingressId  |  |  |  |  |  vNetId
                |  |  |  |  |  |  |
FlowRoutingInfo(0, 0, 0, 0, 0, 0, 0)
FlowRoutingInfo(0, 0, 0, 2, 3, 1, 0)
FlowRoutingInfo(0, 0, 0, 2, 3, 1, 0)
FlowRoutingInfo(2, 1, 1, 0, 0, 0, 0)
FlowRoutingInfo(2, 1, 1, 2, 3, 1, 0)
FlowRoutingInfo(2, 1, 1, 2, 3, 1, 0)

FlowRoutingInfo(1, 1, 1, 1, 3, 1, 1)
FlowRoutingInfo(1, 1, 1, 1, 3, 1, 1)
FlowRoutingInfo(1, 1, 1, 1, 3, 1, 1)

terminals

Base Routing Relations

Numerous builtin routing relations are provided. These provide deadlock-free routing for the included topology generators.

RoutingRelation

Description

AllLegalRouting

Allows any packet to transition to any VC. Only useful for trivial networks

UnidirectionalLineRouting

Routing for a UnidirectionalLine topology.

BidirectionalLineRouting

Routing for a BidirectionalLine topology.

UnidirectionalTorus1DDatelineRouting

Routing for a UnidirectionalTorus1D topology. Uses a dateline to avoid deadlock. Requires at least 2 VCs per physical channel

BidirectionalTorus1DRandomRouting

Routing for a BidirectionalTorus1D topology. Uses a dateline to avoid deadlock. Packets randomly choose a direction at ingress. Requires at least 2 VCs per physical channel

BidirectionalTorus1DShortestRouting

Routing for a BidirectionalTorus1D topology. Uses a dateline to avoid deadlock. Packets choose direction at ingress which minimizes hops. Requires at least 2 VCs per physical channel.

ButterflyRouting

Routing for a Butterfly topology with arbitrary kAry and nFly.

BidirectionalTreeRouting

Routing for a BidirectionalTree topology.

Mesh2DDimensionOrderedRouting

Routing for a Mesh2D topology. Routes in one dimension first, than the other to prevent deadlock

Mesh2DWestFirstRouting

Routing for a Mesh2D topology. Routes in the westward dimension first to prevent deadlock

MEsh2DNorthLastRouting

Routing for a Mesh2D topology. Routes in the northward dimension last to prevent deadlock.

Mesh2DEscapeRouting

Escape-channel based adaptive minimal routing for Mesh2D topology. Escape channel routes using dimension ordered routing, while other channels route any minimal path.

DimensionOrderedUnidirectionalTorus2DRouting

Routing for the UnidirectionalTorus2D topology. Routes in the X dimension first.

DimensionOrderedBidirectionalTorus2DRouting

Routing for the BidirectioanlTorus2D topology. Routes in the X dimension first.

Compositional Routing Relations

Several compositional routing relation classes are provided.

Escape Channel Routing

Escape-channel based routing can be used to build deadlock-free adaptive routing policies. When the routing policy on the escape virtual channels is deadlock-free, and packets in the escape channels cannot route on the non-escape virtual channels, the resulting policy is deadlock-free, even if circular dependencies exist among the non-escape virtual channels.

The EscapeChannelRouting class has three parameters:

  • escapeRouter: the base deadlock-free routing algorithm that will be used on the escape VCs.

  • normalRouter: the routing algorithm for all non-escape VCs.

  • nEscapeChannels: the number of VCs to dedicate for escape channels on each physical channel

For example, a Mesh2DEscapeRouting algorithm with two escape channels using dimension-orderd routing can be described as:

EscapeChannelRouting(
  escapeRouter    = Mesh2DDimensionOrderedRouting(),
  normalRouter    = Mesh2DMinimalRouting(),
  nEscapeChannels = 2
)

Terminal Router Routing

TerminalRouter topologies require the TerminalRouterRouting routing relation. The baseRouting field is the base routing relation used to route among the non-terminal routers in the topology.

topolog = TerminalRouter(BidirectionalLine(4))
routing = TerminalRouterRouting(BidirectionalLineRouting())

topo_term

Hierarchical Topology Routing

Hierarchical toplogies require the HierarchicalRouting routing relation. The baseRouting field is the routing relation for the base topology, while the childRouting field is alist of routing relations for the sub-topologies.

Hierarchical routing can be composed with terminal router routing.

topology = HierarchicalTopology(
  base = UnidirectionalTorus1D(4),
  children = Seq(
    HierarchicalSubTopology(0,2,BidirectionalLine(5)),
    HierarchicalSubTopology(2,1,BidirectionalLine(3))
  )
)
routing = HierarchicalRouting(
  baseRouting = UnidirectionalTorus1DDatelineRouting(),
  childRouting = Seq(
    BidirectionalLineRouting(),
    BidirectionalLineRouting()
  )
)

topo_hier

 
topology = TerminalRouter(HierarchicalTopology(
  base = UnidirectionalTorus1D(4),
  children = Seq(
    HierarchicalSubTopology(0,2,BidirectionalLine(5)),
    HierarchicalSubTopology(2,1,BidirectionalLine(3))
  )
))
routing = TerminalRouter(HierarchicalRouting(
  baseRouting = UnidirectionalTorus1DDatelineRouting(),
  childRouting = Seq(
    BidirectionalLineRouting(),
    BidirectionalLineRouting()
  )
)

topo_hierterm

Virtual Subnetwork Routing Relations

A special class of compositional routing relations can enforce forwards progress on networks with multiple virtual subnetworks.

  • The NonblockingVirtualSubnetworksRouting policy guarantees all virtual subnetworks on the network can always make forwards progress by dedicating some number of virtual channels to each subnetwork.

  • The BlockingVirtualSubnetworksRouting policy guarantees that lower-indexed virtual subnetworks can always make forwards progress while higher-indexed virtual subnetworks are blocked.