InterSim2/allocators/ — Switch & VC Allocation Algorithms

Contents

Architecture

classDiagram
    class Module {
        +Name()
        +FullName()
    }
    class Allocator {
        #int _inputs
        #int _outputs
        #vector~int~ _inmatch
        #vector~int~ _outmatch
        +AddRequest(in, out, label, in_pri, out_pri)
        +Allocate()*
        +OutputAssigned(in) int
        +InputAssigned(out) int
        +NewAllocator()$ Allocator*
    }
    class DenseAllocator {
        #vector~vector~sRequest~~ _request
        +ReadRequest()
    }
    class SparseAllocator {
        #vector~map~ _in_req
        #vector~map~ _out_req
        +ReadRequest()
    }
    Module <|-- Allocator
    Allocator <|-- DenseAllocator
    Allocator <|-- SparseAllocator
    DenseAllocator <|-- Wavefront
    DenseAllocator <|-- PIM
    DenseAllocator <|-- LOA
    DenseAllocator <|-- MaxSizeMatch
    SparseAllocator <|-- iSLIP_Sparse
    SparseAllocator <|-- SeparableAllocator
    SparseAllocator <|-- SelAlloc
    SeparableAllocator <|-- SeparableInputFirstAllocator
    SeparableAllocator <|-- SeparableOutputFirstAllocator

Allocation Flow

flowchart LR
    A["IQRouter: SA/VA stage"] -->|"AddRequest(in,out,pri)"| B["Allocator"]
    B --> C{"Allocate()"}
    C -->|iSLIP| D["Grant/Accept\nround-robin pointers"]
    C -->|Wavefront| E["Diagonal sweep\non dense matrix"]
    C -->|Separable| F["Input Arb → Output Arb\n(or vice-versa)"]
    C -->|PIM| G["Random parallel\nmatching iterations"]
    D --> H["OutputAssigned(in)\nInputAssigned(out)"]
    E --> H
    F --> H
    G --> H
    H --> I["Router crossbar\ntraversal"]

Key Classes

Data Structures

Interactions

Configuration

Directory Map

allocators/
├── allocator.hpp / .cpp           ← Base class, DenseAllocator, SparseAllocator, factory
├── islip.hpp / .cpp               ← iSLIP iterative round-robin matching
├── wavefront.hpp / .cpp           ← Diagonal-sweep dense matching
├── separable.hpp / .cpp           ← SeparableAllocator base (holds Arbiter vectors)
├── separable_input_first.hpp/.cpp ← Input-first separable allocation
├── separable_output_first.hpp/.cpp← Output-first separable allocation
├── pim.hpp / .cpp                 ← Parallel Iterative Matching
├── loa.hpp / .cpp                 ← Lonely Output Allocator
├── selalloc.hpp / .cpp            ← Selection-based allocator with output masking
└── maxsize.hpp / .cpp             ← Maximum-size matching via augmenting paths

Deep-Dive Highlights

Core allocation algorithms extracted for in-depth exploration. Each topic covers one algorithm family with diagrams, code walks, and configuration details.

Deep-Dive Pages

Code Examples

Example: Allocator Factory & Usage in IQRouter

// Router constructs allocators at init time via factory
_vc_allocator = Allocator::NewAllocator(
    this, "vc_allocator", config.GetStr("vc_allocator"),
    _vcs * _inputs, _vcs * _outputs, &config);

_sw_allocator = Allocator::NewAllocator(
    this, "sw_allocator", config.GetStr("sw_allocator"),
    _inputs * _input_speedup, _outputs * _output_speedup, &config);

Example: iSLIP Grant-Accept Loop

// Simplified iSLIP Allocate() — one iteration
void iSLIP_Sparse::Allocate() {
  for (int iter = 0; iter < _iSLIP_iter; ++iter) {
    // Phase 1: Grant — each output scans from _gptrs[out] round-robin
    for (int out = 0; out < _outputs; ++out) {
      auto &req = _out_req[out];
      int best = -1;
      for (auto &r : req) {
        if (_inmatch[r.first] == -1) {  // input not yet matched
          if (best == -1 || /* round-robin priority */ ...)
            best = r.first;
        }
      }
      if (best != -1) { _outmatch[out] = best; }
    }
    // Phase 2: Accept — each input picks best granted output
    for (int in = 0; in < _inputs; ++in) {
      // accept from _aptrs[in], update pointers on match
    }
  }
}