InterSim2/routers/ — Packet Switching & Forwarding

Routers — Packet Switching & Forwarding

Implements the router pipeline models — the heart of the NoC. Each router reads input flits, computes routes, allocates VCs and switch bandwidth, traverses the crossbar, and sends flits on output channels.

4
Classes
8
Files
~4.5 k
Lines
5
Pipeline Stages

📚 What is this & why does it exist?

Every node in the network (SM or memory partition) connects to a router. The router receives flits from input channels, decides which output port to send them on, arbitrates for the crossbar switch, and forwards flits to the next hop. The routers sub-module provides three different microarchitectures: an input-queued (IQ) router for production use, a chaos router for deflection routing, and an event-driven router for latency-optimized workloads.

💡 Real-world analogy

A router is like a postal sorting facility. Packages (flits) arrive at loading docks (input ports). Workers first read the destination address (route computation), then reserve a sorting lane (VC allocation), compete for time on the conveyor belt (switch allocation), ride the belt to the correct outbound dock (crossbar traversal), and are loaded onto the next truck (output channel). The IQ router is a highly organized facility with assigned lanes; the chaos router is a looser facility where packages get deflected to any available dock if their preferred one is busy.

Contents

IQRouter Pipeline Architecture

flowchart LR
    subgraph Pipeline["IQRouter 5-Stage Pipeline"]
        direction LR
        RC["RC\nRoute\nCompute"] --> VA["VA\nVC\nAlloc"]
        VA --> SA["SA\nSwitch\nAlloc"]
        SA --> ST["ST\nSwitch\nTraversal"]
        ST --> LT["LT\nLink\nTraversal"]
    end
    IN["Input\nChannels"] --> BUF["Input\nBuffers\n(per-VC)"]
    BUF --> RC
    LT --> OUT["Output\nChannels"]
    CR["Credit\nReturn"] -.-> BUF

Class Hierarchy

classDiagram
    class TimedModule {
        +ReadInputs()*
        +Evaluate()
        +WriteOutputs()*
    }
    class Router {
        #int _id
        #int _inputs, _outputs, _classes
        #int _crossbar_delay, _credit_delay
        #vector~FlitChannel*~ _input_channels
        #vector~FlitChannel*~ _output_channels
        #vector~CreditChannel*~ _input_credits
        #vector~CreditChannel*~ _output_credits
        +NewRouter()$ Router*
        +AddInputChannel()
        +AddOutputChannel()
        +GetUsedCredit()* int
        +GetBufferOccupancy()* int
    }
    class IQRouter {
        -int _vcs
        -bool _speculative, _noq
        -bool _hold_switch_for_packet
        -Allocator* _vc_allocator
        -Allocator* _sw_allocator
        -Allocator* _spec_sw_allocator
        -vector~Buffer*~ _buf
        -vector~BufferState*~ _next_buf
        -SwitchMonitor* _switchMonitor
        -BufferMonitor* _bufferMonitor
        -_RouteEvaluate()
        -_VCAllocEvaluate()
        -_SWAllocEvaluate()
        -_SwitchEvaluate()
    }
    class ChaosRouter {
        -vector~queue~Flit*~~ _input_frame
        -vector~queue~Flit*~~ _multi_queue
        -vector~eQState~ _input_state
        -PipelineFIFO~Flit~* _crossbar_pipe
        -_NextInterestingChannel()
        -_OutputAdvance()
    }
    class EventRouter {
        -vector~Buffer*~ _buf
        -vector~EventNextVCState*~ _output_state
        -PipelineFIFO~Flit~* _crossbar_pipe
        -PipelineFIFO~Credit~* _credit_pipe
        -vector~PriorityArbiter*~ _arrival_arbiter
        -vector~PriorityArbiter*~ _transport_arbiter
    }
    TimedModule <|-- Router
    Router <|-- IQRouter
    Router <|-- ChaosRouter
    Router <|-- EventRouter

Key Classes

ClassFilePurpose
Routerrouter.hppAbstract base — ReadInputs(), Evaluate(), WriteOutputs(); factory NewRouter(); stall tracking constants
IQRouteriq_router.hppPrimary router — input-queued with VCs. 5-stage pipeline: RC→VA→SA→ST→LT. Supports speculative SA, NOQ, switch-hold-for-packet
ChaosRouterchaos_router.hppChaos/deflection routing — multi-queue buffers with 6 states: empty, filling, full, leaving, cut_through, shared
EventRouterevent_router.hppEvent-driven router — uses EventNextVCState for VC tracking, PriorityArbiter for arrival/transport arbitration
EventNextVCStateevent_router.hppPer-output VC state machine: idle/busy/tail_pending; manages waiting lists and credit/presence counters
tArrivalEventevent_router.hppEventRouter struct: input, output, src_vc, dst_vc, head/tail flags for flit arrival events
tTransportEventevent_router.hppEventRouter struct: input, src_vc, dst_vc for crossbar transport events
eQStatechaos_router.hppChaosRouter buffer state enum: empty, filling, full, leaving, cut_through, shared
Router::STALL_*router.hppStatic stall-reason constants: BUFFER_BUSY, BUFFER_CONFLICT, BUFFER_FULL, BUFFER_RESERVED, CROSSBAR_CONFLICT
tRoutingFunctionroutefunc.hppFunction pointer type used by all routers: (Router*, Flit*, int, OutputSet*, bool)

Data Structures

TypeNameDescription
vector<Buffer*>_bufPer-input-port buffer objects, each containing multiple VCs
vector<BufferState*>_next_bufDownstream buffer state trackers (credit counters for next-hop router)
map<int,Flit*>_in_queue_flitsIQRouter staging map for flits received this cycle
deque<pair>_route_vcsIQRouter pipeline deque for VCs awaiting route computation
deque<pair>_crossbar_flitsIQRouter deque for flits traversing the crossbar with delay
vector<queue>_output_bufferIQRouter output-side flit queues (post-crossbar)
vector<int>_switch_hold_in/out/vcIQRouter switch-hold state for multi-flit packet optimization
enumeQStateChaosRouter 6-state buffer FSM: empty→filling→full→leaving→empty

Interactions

DirectionPartnerInterfaceDescription
←NetworkNewRouter()Network topology creates routers via factory at build time
↔FlitChannelReadInputs() / WriteOutputs()Receives flits from input channels, sends flits on output channels each cycle
↔CreditChannel_SendCredits() / _ReceiveCredits()Returns credits to upstream routers when buffer space is freed
→AllocatorAddRequest() / Allocate()IQRouter delegates VA and SA to allocator sub-modules
→Buffer / VCAddFlit() / RemoveFlit()Input buffers store flits organized by virtual channel
→BufferStateSendingFlit() / ProcessCredit()Tracks downstream buffer availability via credit flow
→SwitchMonitortraversal(in, out, flit)IQRouter reports crossbar activity for power estimation
→BufferMonitorread() / write()IQRouter reports buffer R/W activity for power estimation
←routefunctRoutingFunction _rfTopology-specific routing function assigned at init

Configuration

Knob / ParameterDefaultDescription
routeriqRouter type: iq (input-queued), chaos, event
num_vcs4Number of virtual channels per input port
vc_buf_size8Buffer depth per VC (in flits)
routing_delay0Extra cycles for route computation stage (RC)
vc_alloc_delay0Extra cycles for VC allocation stage (VA)
sw_alloc_delay0Extra cycles for switch allocation stage (SA)
st_prepare_delay0Extra cycles for switch traversal preparation
credit_delay1Cycles for credit to travel back to upstream router
crossbar_delay0Additional crossbar traversal latency
speculative0Enable speculative switch allocation (SA before VA completes)
hold_switch_for_packet0Hold crossbar grant for entire multi-flit packet
noq0Next-hop Output Queuing — pre-compute next-hop output for head flits
output_buffer_size0Output buffer depth (0 = unlimited)
input_speedup1Input-side speedup factor for the crossbar
output_speedup1Output-side speedup factor for the crossbar

Directory Map

Source tree for routers/ 
routers/
├── router.hpp / .cpp            ← Abstract base, stall constants, factory NewRouter()
├── iq_router.hpp / .cpp         ← Input-Queued router (primary), 5-stage pipeline
├── chaos_router.hpp / .cpp      ← Chaos/deflection router with multi-queue buffers
└── event_router.hpp / .cpp      ← Event-driven router with PriorityArbiter

Deep-Dive Highlights

Router microarchitectures extracted for in-depth exploration. Each page covers pipeline stages, state machines, and performance trade-offs.

Deep-Dive Pages

IQRouter Pipeline (RC→VA→SA→ST) Focus

Detailed walk-through of the 5-stage input-queued pipeline: route compute, VC alloc, switch alloc, switch traversal, and link traversal. Covers speculative SA, NOQ optimization, and switch-hold-for-packet.

Extracted topic page

Chaos Deflection Routing Focus

Buffer state machine (empty→filling→full→leaving), multi-queue overflow handling, and deflection-based forwarding when preferred outputs are unavailable.

Extracted topic page

Event-Driven Router Focus

Event-based forwarding with arrival/transport queues, EventNextVCState waiting-list management, and PriorityArbiter for per-output contention resolution.

Extracted topic page

Code Examples

Example: IQRouter Pipeline Evaluate Cycle

void IQRouter::_InternalStep() {
  // Pipeline stages execute in reverse order to avoid combinational loops
  _InputQueuing();          // Stage flits from channels into buffers

  _RouteEvaluate();         // RC: compute output port for head flits
  _VCAllocEvaluate();       // VA: allocate output VC from Allocator
  _SWHoldEvaluate();        // SA-hold: maintain switch for multi-flit packets
  _SWAllocEvaluate();       // SA: compete for crossbar bandwidth
  _SwitchEvaluate();        // ST: traverse crossbar, enqueue to output buffer

  _RouteUpdate();           // Commit RC results
  _VCAllocUpdate();         // Commit VA results
  _SWHoldUpdate();          // Commit hold decisions
  _SWAllocUpdate();         // Commit SA results
  _SwitchUpdate();          // Commit ST results

  _OutputQueuing();         // Move flits from output buffer to channels
}

Example: Router Factory

Router *Router::NewRouter(const Configuration& config,
    Module *parent, const string & name, int id,
    int inputs, int outputs) {
  const string type = config.GetStr("router");
  if (type == "iq")    return new IQRouter(config, parent, name, id, inputs, outputs);
  if (type == "chaos") return new ChaosRouter(config, parent, name, id, inputs, outputs);
  if (type == "event") return new EventRouter(config, parent, name, id, inputs, outputs);
  cerr << "Unknown router type: " << type << endl;
  exit(-1);
}
← Back to InterSim2 Overview