InterSim2/arbiters/ — Contention Resolution Mechanisms
Arbiters — Contention Resolution Mechanisms
Low-level building blocks that select exactly one winner from a set of competing requests on a single shared resource. Used by separable allocators and event-driven routers.
📚 What is this & why does it exist?
When several inputs compete for a single output port, someone has to decide who goes first. An arbiter is a tiny decision-making unit that picks one winner per resource per cycle. Allocators use arrays of arbiters (one per input port, one per output port) to decompose the global NxM matching problem into simpler 1-of-N selections.
💡 Real-world analogy
Think of a busy deli counter with one ticket dispenser. Customers pull numbered tickets (requests) and wait. The counter clerk (arbiter) calls the next number in order (round-robin), or serves the VIP customer first (priority), or consults a fairness chart that tracks who has been served least recently (matrix arbiter). The tree arbiter is like having multiple regional deli counters whose winners then compete at a master counter — a hierarchical tournament.
Contents
Architecture
classDiagram
class Module {
+Name()
+FullName()
}
class Arbiter {
#vector~entry_t~ _request
#int _size
#int _selected
#int _highest_pri
#int _best_input
+int _num_reqs
+AddRequest(input, id, pri)
+Arbitrate(id*, pri*) int
+UpdateState()*
+Clear()
+PrintState()*
+NewArbiter()$ Arbiter*
}
class RoundRobinArbiter {
-int _pointer
+Arbitrate() int
+UpdateState()
+Supersedes()$ bool
}
class MatrixArbiter {
-vector~vector~int~~ _matrix
-int _last_req
+Arbitrate() int
+UpdateState()
}
class TreeArbiter {
-int _group_size
-vector~Arbiter*~ _group_arbiters
-Arbiter* _global_arbiter
+Arbitrate() int
+UpdateState()
}
class PriorityArbiter {
-int _rr_ptr
#list~sRequest~ _requests
#int _match
+AddRequest(in, label, pri)
+Arbitrate()
+Match() int
}
Module <|-- Arbiter
Module <|-- PriorityArbiter
Arbiter <|-- RoundRobinArbiter
Arbiter <|-- MatrixArbiter
Arbiter <|-- TreeArbiter
TreeArbiter o-- Arbiter : _group_arbiters
TreeArbiter o-- Arbiter : _global_arbiter
Arbitration Flow
sequenceDiagram
participant Alloc as SeparableAllocator
participant InArb as Input Arbiter
participant OutArb as Output Arbiter
Alloc->>InArb: AddRequest(input, id, pri)
Alloc->>OutArb: AddRequest(input, id, pri)
Alloc->>InArb: Arbitrate() → winner
Alloc->>OutArb: Arbitrate() → winner
Alloc->>InArb: UpdateState()
Alloc->>OutArb: UpdateState()
Note over InArb,OutArb: Priority pointers rotate after each grant
Alloc->>InArb: Clear()
Alloc->>OutArb: Clear()
Key Classes
| Class | File | Purpose |
|---|---|---|
Arbiter | arbiter.hpp | Abstract base: AddRequest(input, id, pri), Arbitrate(), UpdateState(), Clear(); factory NewArbiter() |
entry_t | arbiter.hpp | Request entry struct: valid, id, pri — stored in _request vector |
RoundRobinArbiter | roundrobin_arb.hpp | Classic rotating-priority arbiter with _pointer; static Supersedes() helper for priority comparison |
MatrixArbiter | matrix_arb.hpp | NxN _matrix priority table — winner demotes all losers; guarantees fairness with O(1) convergence |
PriorityArbiter | prio_arb.hpp | Strict-priority with round-robin tie-breaking (_rr_ptr); uses list<sRequest> — used by EventRouter |
TreeArbiter | tree_arb.hpp | Hierarchical: _group_arbiters select group winners, _global_arbiter selects overall winner; scalable to large port counts |
RoundRobinArbiter::Supersedes | roundrobin_arb.hpp | Static inline — determines if request at input1 supersedes input2 given current offset and size |
Arbiter::_selected | arbiter.hpp | Index of the last winning input — accessible via LastWinner() |
Arbiter::_num_reqs | arbiter.hpp | Public counter of active requests this cycle — used for statistics |
MatrixArbiter::_last_req | matrix_arb.hpp | Index of the last request processed — used to update the priority matrix |
Data Structures
| Type | Name | Description |
|---|---|---|
| struct | entry_t | Arbiter request: {valid, id, pri} — one per potential input |
| struct | PriorityArbiter::sRequest | Priority arbiter request: {in, label, pri} — stored in linked list |
| vector<entry_t> | _request | Fixed-size array of request slots, indexed by input port |
| vector<vector<int>> | _matrix | MatrixArbiter NxN priority matrix: _matrix[i][j]=1 means i has priority over j |
| int | _pointer | RoundRobin current priority pointer — points to highest-priority input |
| vector<Arbiter*> | _group_arbiters | TreeArbiter array of sub-group arbiters (one per group of inputs) |
| vector<int> | _group_reqs | TreeArbiter per-group request counts for hierarchical selection |
Interactions
| Direction | Partner | Interface | Description |
|---|---|---|---|
| ← | SeparableAllocator | NewArbiter() | Creates per-input and per-output arbiters at allocator construction |
| ← | SeparableAllocator | AddRequest() | Registers competing inputs for a single output (or vice versa) |
| → | SeparableAllocator | Arbitrate() | Returns winning input index; optionally populates id and pri pointers |
| ← | SeparableAllocator | UpdateState() | Rotates priority (RR), updates matrix (Matrix), or propagates to children (Tree) |
| ← | EventRouter | PriorityArbiter::Arbitrate() | Event router uses PriorityArbiter for arrival and transport arbitration |
| ← | Configuration | arb_type string | Arbiter type selection: round_robin, matrix, tree |
Configuration
| Knob / Parameter | Default | Description |
|---|---|---|
arb_type | round_robin | Arbiter type for separable allocators: round_robin, matrix, tree |
input_arbiter_type | (inherits arb_type) | Override arbiter type for per-input arbitration phase only |
output_arbiter_type | (inherits arb_type) | Override arbiter type for per-output arbitration phase only |
tree_arbiter_groups | 4 | Number of groups in TreeArbiter hierarchy (group size = size/groups) |
num_vcs | 4 | Determines arbiter size for VC allocation (inputs = vcs × ports) |
sw_allocator | islip | When set to separable, allocator instantiates arbiter arrays |
vc_allocator | islip | When set to separable, allocator instantiates arbiter arrays for VA |
sw_alloc_iters | 1 | Iterations of arbitration per cycle in the SA stage |
vc_alloc_iters | 1 | Iterations of arbitration per cycle in the VA stage |
routing_delay | 0 | Cycles of delay before arbitration begins (pipeline depth) |
vc_alloc_delay | 0 | Additional delay in VC allocation stage |
sw_alloc_delay | 0 | Additional delay in switch allocation stage |
Directory Map
Source tree for arbiters/
arbiters/
├── arbiter.hpp / .cpp ← Abstract base class, factory NewArbiter()
├── roundrobin_arb.hpp / .cpp ← Classic round-robin with rotating pointer
├── matrix_arb.hpp / .cpp ← NxN priority matrix arbiter (fair, O(1) converge)
├── prio_arb.hpp / .cpp ← Strict-priority arbiter (used by EventRouter)
└── tree_arb.hpp / .cpp ← Hierarchical tree arbiter (group → global)
Deep-Dive Highlights
Core arbitration mechanisms extracted for detailed analysis. Each page covers one policy with state machine diagrams, fairness proofs, and performance characteristics.
Deep-Dive Pages
Round-Robin Arbitration Focus
Rotating priority pointer ensures long-term fairness. Constant-time selection with Supersedes() static helper for modular distance comparison.
Matrix & Priority Arbiter Focus
Matrix arbiter maintains an NxN priority table updated on each grant — provably fair with O(1) convergence to maximum matching. Priority arbiter serves highest-priority request with RR tie-breaking.
Hierarchical Tree Arbitration Focus
Scalable design: inputs divided into groups, each with its own sub-arbiter. Group winners compete at a global arbiter. Reduces wiring complexity from O(N) to O(√N).
Code Examples
Example: RoundRobinArbiter Arbitrate Logic
int RoundRobinArbiter::Arbitrate(int* id, int* pri) {
// Scan from _pointer position, wrapping around
for (int offset = 0; offset < _size; ++offset) {
int input = (_pointer + offset) % _size;
if (_request[input].valid) {
_selected = input;
if (id) *id = _request[input].id;
if (pri) *pri = _request[input].pri;
return input;
}
}
return -1; // no valid request
}
void RoundRobinArbiter::UpdateState() {
if (_selected >= 0)
_pointer = (_selected + 1) % _size; // rotate past winner
}
Example: MatrixArbiter Priority Update
void MatrixArbiter::UpdateState() {
if (_selected < 0) return;
// Winner loses priority against all losers
for (int i = 0; i < _size; ++i) {
_matrix[_selected][i] = 0; // winner demoted vs everyone
_matrix[i][_selected] = 1; // everyone promoted vs winner
}
}