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

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)

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.
`ShortestPathGeneralizedDatelineRouting`	Routing for any `CustomTopology` topology. Routes using the shortest possible path to destination. It avoids deadlock but detecting datelines and incrementing VC index each time it crosses one. Requires multiple VCs depending on the number of the cycles present.
`CustomLayeredRouting`	Routing for any `CustomTopology` topology. Routes by assigning each flow to a unique layer (VC). At least one VC will contain the shortest possible path between source and destination. Requires as many VCs as layers to prevent deadlock.

Note

To guarantee deadlock-freedom, both ShortestPathGeneralizedDatelineRouting and CustomLayeredRouting require sufficient virtual channels to be available.

For ShortestPathGeneralizedDatelineRouting, the number of VCs needed equals the maximum number of dateline crossings on any path plus one.
For CustomLayeredRouting, the number of VCs must match the number of packed layers computed during path decomposition.

These are automatically computed before elaboration. If an insufficient number of VCs is specified, the Chisel elaboration step may fail to complete successfully. The required number of VCs will be printed during hardware generation in the chisel.log file.

Different algorithms may produce different VC requirements depending on the structure of the topology. These trade-offs should be considered when selecting a routing relation for your system.

In practice:

ShortestPathGeneralizedDatelineRouting often requires fewer VCs but enforces VC transitions only at datelines.

CustomLayeredRouting may use more VCs but guarantees a purely acyclic per-flow assignment.

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
)

Note

ShortestPathRouting can also be used as the normalRouter in EscapeChannelRouting, particularly when targeting CustomTopology configurations.

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())

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()
  )
)

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()
  )
)

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.

Routing Configuration¶

Channel Identifier¶

Flow Identifier¶

Base Routing Relations¶

Compositional Routing Relations¶

Escape Channel Routing¶

Terminal Router Routing¶

Hierarchical Topology Routing¶

Virtual Subnetwork Routing Relations¶

Constellation

Navigation

Related Topics