Designing Highly Routable Interconnection Networks via Cyclic Quorums

---

# 🛰️ Designing Highly Routable<br>Interconnection Networks<br>via Cyclic Quorums

### A 30-Minute Technical Briefing

Wai-Shing Luk 👨‍💻 · 2026 📅

---

### 📋 Agenda

**Part 1: The Problem** 🚧
- The crossbar paradox & density wall
- Why naive crossbars don't scale

**Part 2: The Solution** 🧮
- Cyclic quorum systems
- Projective geometry & Singer difference sets

**Part 3: Scaling Strategies** 🧱
- Horizontal tiling & truncation
- Coprime boundary handling

]

**Part 4: Python Demos** 🐍
- Core generation (`perfect_diffset.py`)
- Tiled & truncated designs
- Multi-hop path discovery

**Part 5: Physical Implementation** 🚀
- EDA-friendly design patterns
- Hard-macro reuse & metal stratification

**Part 6: Takeaways** 🎯
- Key design principles
- Q&A

]

---

### 🚧 The Crossbar Paradox

**The challenge:** Connect a massive set of inputs ($N$) to a shared set of outputs ($M$) on a silicon die.

**Naive crossbar approach:**

```
         Outputs (M)
      ┌─────────────
      │░░░░░░░░░░░░░
 I    │░░░░░░░░░░░░░
 n    │░░░░░░░░░░░░░
 p    │░░░░░░░░░░░░░
 u    │░░░░░░░░░░░░░
 t    │░░░░░░░░░░░░░
 s    │░░░░░░░░░░░░░
(N)   │░░░░░░░░░░░░░
```

$N \times M$ junctions = $100 \times 24 = 2{,}400$ vias

]

**The scalability trap:**

| $N$ | $M$ | Junctions |
|-----|-----|-----------|
| 100 | 24 | 2,400 |
| 200 | 48 | 9,600 |
| 500 | 120 | 60,000 |
| 1K | 256 | 262,144 |

❌ **Quadratic scaling** = impossible at 7nm+

]

---

### 🔴 The Four Structural Penalties

**🔴 Routing Congestion**
Heavy local metal crowding blocks routing tracks for other signals. The router struggles to find paths through the via maze.

**🔴 Parasitic Dominance**
Massive wiring capacitance ($C$) and resistance ($R$) cause $RC$ delay violations. The crossbar becomes the critical path.

]

**🔴 Asymmetry Chaos**
Mismatched aspect ratios lead to severe signal skew. Input 0 has a completely different path than Input 99.

**🔴 No Modularity**
Each dense crossbar is a custom layout. No cell reuse, no "stamp and repeat" — every design starts from scratch.

]

---

### 🧮 What is a Cyclic Quorum System?

**Definition:** A collection of overlapping subsets (quorums) mapped onto a cyclic group $\mathbb{Z}_N$.

**The Intersection Property:** For any two input subsets $Q_A$ and $Q_B$:

$$Q_A \cap Q_B \neq \emptyset$$

**Physical translation:** Inputs do not use random paths. They follow a single relative geometric footprint shifted by modular steps → Guaranteed collision at a shared resource with **minimal wiring**.

.mermaid[
<pre>
graph TD
    subgraph Cyclic_Concept[The Virtual Ring Layout]
    I0((In 0)) --> I1((In 1))
    I1 --> I2((In 2))
    I2 -->|...| I99((In 99))
    I99 --> I0
    end
    style Cyclic_Concept fill:#ECEFF4,stroke:#4C566A,stroke-width:2px
    style I0 fill:#5E81AC,stroke:#81A1C1,color:#fff
    style I1 fill:#5E81AC,stroke:#81A1C1,color:#fff
    style I2 fill:#5E81AC,stroke:#81A1C1,color:#fff
    style I99 fill:#5E81AC,stroke:#81A1C1,color:#fff
</pre>
]

---

### 💎 Projective Geometry Core

Avoid massive single-layer grids by using an **Order-3 Projective Plane $(13, 4, 1)$**.

**The Math:**
- $13 \times 13$ matrix
- Singer Difference Set:
  $\mathcal{D} = \{0, 1, 3, 9\} \pmod{13}$
- **4 connections per column**

**Efficiency:**
- Total vias: $13 \times 4 = \mathbf{52}$
- vs. $13 \times 13 = 169$ dense
- **69% reduction** 🎯
- Intersection: $\lambda = 1$

]

**Why 4 connections is optimal:**

.mermaid[
<pre>
graph LR
    subgraph Core[13 x 13 Core]
    C1((Col 0)) -->|d=0| R0[Row 0]
    C1 -->|d=1| R1[Row 1]
    C1 -->|d=3| R3[Row 3]
    C1 -->|d=9| R9[Row 9]
    end
    style Core fill:#ECEFF4,stroke:#4C566A
    style C1 fill:#5E81AC,stroke:#81A1C1,color:#fff
    style R0 fill:#A3BE8C,stroke:#81A1C1
    style R1 fill:#A3BE8C,stroke:#81A1C1
    style R3 fill:#A3BE8C,stroke:#81A1C1
    style R9 fill:#A3BE8C,stroke:#81A1C1
</pre>
]

Each column connects to **exactly 4 rows** — no more, no less.

]

---

### 🎯 The Singer Difference Set

**Definition:** A set $\mathcal{D} = \{d_1, d_2, \dots, d_k\}$ modulo $v$ such that every nonzero residue modulo $v$ appears exactly $\lambda$ times as a difference $d_i - d_j$. **Our set:** $\mathcal{D} = \{0, 1, 3, 9\}$ modulo $13$

**All nonzero differences appear exactly once:**

| $a-b$ | Value |
|-------|-------|
| $1 - 0$ | 1 |
| $3 - 0$ | 3 |
| $9 - 0$ | 9 |
| $3 - 1$ | 2 |
| $9 - 1$ | 8 |
| $9 - 3$ | 6 |

]

| $a-b$ | Value |
|-------|-------|
| $0 - 1$ | 12 |
| $0 - 3$ | 10 |
| $0 - 9$ | 4 |
| $1 - 3$ | 11 |
| $1 - 9$ | 5 |
| $3 - 9$ | 7 |

✅ Every value $1, 2, \dots, 12$ appears **exactly once**!

This property guarantees **uniform connectivity** — every row sees the same load.

]
]

---

### 📊 13×13 Core Matrix — Cyclic Shift Pattern

The Singer Difference Set creates a regular diagonal wave pattern when visualized.

.pull-left[
.mermaid[
<pre>
graph TD
    subgraph Legend["Legend"]
    D0["● d=0"] --- D1["● d=1"]
    D1 --- D3["● d=3"]
    D3 --- D9["● d=9"]
    end
    style D0 fill:#BF616A,stroke:#BF616A
    style D1 fill:#EBCB8B,stroke:#EBCB8B
    style D3 fill:#A3BE8C,stroke:#A3BE8C
    style D9 fill:#5E81AC,stroke:#5E81AC
    style Legend fill:#ECEFF4,stroke:#4C566A
</pre>
]

**The cyclic shift rule:**
$$\text{Row}(i, d) = (i + d) \pmod{13} \\\\
\text{for } d \in \{0, 1, 3, 9\}$$

]
.pull-right[

| Input $i$ | Row connections (shifted by $\mathcal{D}$) |
|-----------|------------------------------------------|
| 0 | Row 0, 1, 3, 9 |
| 1 | Row 1, 2, 4, 10 |
| 2 | Row 2, 3, 5, 11 |
| 3 | Row 3, 4, 6, 12 |
| $\vdots$ | $\vdots$ |
| 12 | Row 12, 0, 2, 8 |
]

---

# 🐍 Python Demos

---

### 🐍 Core Generation: perfect_diffset.py

**Generating the 13×13 sparse matrix:**

```python
import numpy as np

# Singer Difference Set
diff_set = [0, 1, 3, 9]
N_core = 13

# Core sparse matrix
core_grid = np.zeros(
    (N_core, N_core), dtype=int
)
for i in range(N_core):
    for j in range(N_core):
        if (i - j) % N_core in diff_set:
            core_grid[i][j] = 1
```

]

**The visualization logic:**

```python
# Grid lines (wires)
for j in range(N_core):
    ax.axhline(y=j, color='#e0e0e0')
for i in range(N_core):
    ax.axvline(x=i, color='#e0e0e0')

# Physical vias = black dots
via_y,via_x = np.where(core_grid.T == 1)
ax.scatter(via_x, via_y,
    color='#000000', s=60,
    label='Physical Via')
```

**Result:** Clean white grid with **52 black dots** arranged in a perfect diagonal pattern ✨

]

---

### 🖼️ Visualizing the Grid

**North-South Columns (Inputs) vs. West-East Rows (Outputs)**

.mermaid[
<pre>
flowchart TD
    subgraph DesignFlow["Design Flow"]
        A["Singer Difference Set\n𝒟 = {0, 1, 3, 9}"] --> B["Cyclic Shift Rule\nRow = (col + d) mod 13"]
        B --> C["Sparse 13×13 Matrix\n52 vias (69% sparse)"]
        C --> D["Visualize Grid\n⬜ Grid + ⚫ Vias"]
        C --> E["BFS Path Discovery\nDesign-time routing"]
        E --> F["Hardcoded LUT\nZero-latency silicon"]
    end
    style DesignFlow fill:#ECEFF4,stroke:#4C566A,stroke-width:2px
    style A fill:#5E81AC,stroke:#81A1C1,color:#fff
    style B fill:#81A1C1,stroke:#88C0D0,color:#fff
    style C fill:#A3BE8C,stroke:#81A1C1
    style D fill:#EBCB8B,stroke:#81A1C1
    style E fill:#D08770,stroke:#81A1C1
    style F fill:#BF616A,stroke:#81A1C1,color:#fff
</pre>
]

---

# 🧱 Scaling the Network

---

### 🔬 Horizontal Tiling (39 × 13)

**Problem:** What if 13 inputs aren't enough? We need 39 inputs but only 13 outputs.

**Solution:** Copy-paste the $13 \times 13$ macro-cell **three times** side-by-side.

**Tiling concept:**
```
┌──────────┬──────────┬──────────┐
│  13×13   │  13×13   │  13×13   │
│  Core    │  Core    │  Core    │
│  Tile 0  │  Tile 1  │  Tile 2  │
└──────────┴──────────┴──────────┘
  In 0-12    In 13-25   In 26-38
```

**Math:** $3 \times 13 = 39$ inputs, 13 outputs

**Vias:** $3 \times 52 = 156$ (vs. $39 \times 13 = 507$ dense)

]

**Python (perfect_diffset_39_13.py):**

```python
import numpy as np

# 1. Build 13×13 core
base_core = np.zeros((13,13), dtype=int)
for i in range(13):
    for j in range(13):
        if (i - j) % 13 in [0, 1, 3, 9]:
            base_core[i][j] = 1

# 2. Tile horizontally ×3
tiled_grid = np.tile(base_core, (3, 1))
# Shape: (39, 13)
```

**✅ Core macro cell is reused identically**

]

---

### ✂️ Truncation (38 × 13)

**Problem:** The design spec says exactly **38** inputs — but our tiled design gives 39.

**Solution:** Slice off the final column (Column 38).

**Truncation is safe because:**
- ✅ Underlying macro-cell design remains identical
- ✅ Columns 0–37 maintain the same electrical & crosstalk profiles
- ✅ Via density stays the same (`4` per column)
- ❌ Only 156 vias needed (vs. 494 in dense 38×13)

**Visual:** Each tile boundary is marked with a dashed pink line 🔴

]

**Python (perfect_diffset_38_13.py):**

```python
# 1. Generate tiled 39×13 grid
full_grid = np.tile(base_core, (3, 1))

# 2. Truncate to exact target
target = 38
design_grid = full_grid[:target, :]

# 3. Visualize tile boundaries
for t in [1, 2]:
    ax.axvline(x=t * 13 - 0.5,
        color='#ff3366', linestyle='--')
```

**Bonus:** Tiling + truncation works for **any** input count $N$ — just tile ceil($N/13$) times and slice.

]

---

### 🔄 Coprime Boundaries (41 × 12)

**Problem:** What if $M$ isn't 13? Design spec: **41 inputs, 12 outputs**. Tiling doesn't help because $12 \neq 13$.

**Solution:** Direct cyclic distribution modulo $M$.

**The rule:**
$$\text{Row} = (i + d) \pmod{12} \quad \text{for } d \in \{0, 1, 4, 6\}$$

Since $\gcd(41, 12) = 1$, the connections form a **perfectly uniform diagonal wave** across the die.

- Density: **33.3%** (164 vias vs. 492 dense)
- Every column: **4 connections**
- Perfect row-load balance ✅

]

**Load verification:**
```
Total vias: 164
Vias/column: 4 (uniform!)
Vias/row: Min=13, Max=14
                    (≈ balanced)
```

**The secret:** The offset set $\{0, 1, 4, 6\}$ was found via exhaustive search to **minimize row-load variance** — this is what `interconnection.py` does!

]

---

### 🐍 Python: 41×12 Design

**Direct cyclic design (perfect_diffset_41_12.py):**

def design_41x12(N=41, M=12):
    # Optimized for min row-load variance
    diff_set = [0, 1, 4, 6]

grid = np.zeros((N, M), dtype=int)

for i in range(N):
        for d in diff_set:
            row_idx = (i + d) % M
            grid[i][row_idx] = 1

# Verify uniform density
    vias_per_col = np.sum(grid, axis=1)
    vias_per_row = np.sum(grid, axis=0)

print(f"Total vias: {np.sum(grid)}")
    print(f"Vias/col: {vias_per_col[0]}")
    print(f"Vias/row: min={min(vias_per_row)}, "
          f"max={max(vias_per_row)}")

return grid, diff_set
```
]

]

**Output:**
```
Total vias: 164
Vias/col: 4 (Perfect uniformity)
Vias/row: Min=13, Max=14
```

.mermaid[
<pre>
graph TD
    subgraph Design_41x12["41×12 Design Flow"]
        DS["Diff Set\n{0,1,4,6}"] --> CS["Cyclic Shift\nRow=(i+d) mod 12"]
        CS --> GM["41×12 Grid\n164 vias"]
        GM --> VF["Verify\nUniform Load"]
    end
    style Design_41x12 fill:#ECEFF4,stroke:#4C566A
    style DS fill:#5E81AC,stroke:#81A1C1,color:#fff
    style CS fill:#81A1C1,stroke:#88C0D0,color:#fff
    style GM fill:#A3BE8C,stroke:#81A1C1
    style VF fill:#EBCB8B,stroke:#81A1C1
</pre>
]

**🔬 Key insight:** When $\gcd(N, M) = 1$, the cyclic shift guarantees **perfect uniformity** across rows.

]

---

# 🧭 Multi-Hop Routing

---

### 🔗 Beyond Single-Hop Connections

**Sparse crossbars = not all input-output pairs have a direct via.** That's actually **OK** — we route through intermediate hops!

**The 100×23 design (multi_hop.py):**

```python
# Map 23 outputs evenly to 100 inputs
P = [round(j * 100 / 23) % 100
     for j in range(23)]

# Optimized 6-wire per column diff set
diff_set = [0, 4, 12, 25, 50, 75]

# Build adjacency matrix
grid = np.zeros((100, 23), dtype=int)
for i in range(100):
    for j in range(23):
        if (i - P[j]) % 100 in diff_set:
            grid[i][j] = 1
```

]

**Why this works:**
- Each input connects to **6 of 23 outputs**
- The quorum intersection property guarantees that **any two inputs share at least one output**
- This gives us a **connected bipartite graph**
- **Diameter = 2 hops** max 🎯

**Design-time BFS discovers paths → hardcode in LUT**

]

---

### 🗺️ BFS Path Discovery Algorithm

When Input 40 needs to reach Output 16 but has no direct via:

.mermaid[
<pre>
flowchart LR
    S["Input 40\nNeeds Output 16"] --> Q{"Direct via?\ngrid[40][16] == 1?"}
    Q -->|"Yes ✅"| D["Direct connection\nSingle hop"]
    Q -->|"No ❌"| M["Find intermediate\noutput reachable from In 40"]
    M --> L["grid[40][intermediate] == 1\nAND\ngrid[loopback][16] == 1"]
    L --> N(( ))
    style S fill:#5E81AC,stroke:#81A1C1,color:#fff
    style Q fill:#EBCB8B,stroke:#81A1C1
    style D fill:#A3BE8C,stroke:#81A1C1
    style M fill:#D08770,stroke:#81A1C1
</pre>
]

.mermaid[
<pre>
flowchart LR
    N(( )) --> H1["Hop 1: Input 40 → Output k"]
    H1 --> LB["Loopback: Output k\n→ Intermediate Input"]
    LB --> H2["Hop 2: Intermediate\nInput → Output 16"]
    H2 --> R["Route found! ✅\n2-hop path"]
    style R fill:#BF616A,stroke:#81A1C1,color:#fff
</pre>
]

**Result:** Since the quorum graph is connected with $\lambda = 1$, **every** input-output pair is reachable in ≤ 2 hops.

---

### 🐍 Python: Multi-Hop Routing Demo

**Route finder (multi_hop.py):**

.font-sm[
```python
def find_route(grid, P, diff_set,
               start=40, target=16):
    N, M = 100, 23

# Check direct connection
    if grid[start][target] == 1:
        return [("Direct", start, target)]

# Search for 2-hop path
    for mid_out in range(M):
        if grid[start][mid_out] == 1:
            # Loopback to input
            mid_in = round(
                mid_out * N / M) % N
            if grid[mid_in][target] == 1:
                return [
                    ("Hop 1", start, mid_out),
                    ("Hop 2", mid_in, target)
                ]
    return None  # No path (shouldn't happen)
```
]
]

**Execution:**
```
Path from Input 40 to Output 16:
  → Hop 1: Connect Input 40 to Output 5
  → Hop 2: Connect Input 21 to Output 16
```

**Visualization highlights the path:**
- 🔴 Step 1 highlighted in red
- 🟢 Step 2 highlighted in green
- Dashed tracking lines show signal flow

**🧠 Design-time only:** The BFS runs once during design. The discovered path is **hardcoded** into a lookup table for zero-latency silicon execution.

]

---

### 🔬 Optimal Diff Set Search

The `interconnection.py` script goes further — it **searches** for the best difference set.

**Exhaustive optimization:**

# Candidate wire spans
candidates = [0, 1, 2, 4, 5, 8, 10,
              12, 15, 20, 25, 33, 40, 50]

best_var = float('inf')
best_diff = None

for diff_set in combinations(
    candidates, 6):  # 6 wires/input

# Check row-load variance
    output_counts = np.zeros(M)
    for i in range(N):
        for j in range(M):
            if (i - P[j]) % N in diff_set:
                output_counts[j] += 1

variance = np.var(output_counts)
    if variance < best_var:
        best_var = variance
        best_diff = diff_set
```
]
]

**Why variance matters:**

Low variance = every output has the same electrical load = **matched $RC$ delays** = predictable timing ✨

.font-sm[
| Variance | Load Balance | Timing |
|----------|-------------|--------|
| 0.0 | Perfect | ✅ Deterministic |
| 0.5 | Good | ⚡ Predictable |
| 2.0+ | Poor | ❌ Skew issues |
]
**The search finds $\mathcal{D}$ that minimizes variance — a key EDA concern.**

]

---

# 🚀 Physical Implementation

---

### ⚡ Why EDA Routers Love Cyclic Quorums

**🛠️ Hard-Macro Copy-Paste**
Design a single vertical column template and "stamp" it across the floorplan. Each column is **electrically identical**.

```
┌────┐┌────┐┌────┐┌────┐   ┌────┐
│M2  ││M2  ││M2  ││M2  │   │M2  │
│M3  ││M3  ││M3  ││M3  │   │M3  │
│Via ││Via ││Via ││Via │...│Via │
│M6  ││M6  ││M6  ││M6  │   │M6  │
└────┘└────┘└────┘└────┘   └────┘
Col 0  Col 1  Col 2  Col 3  Col N
```

]

**⚡ Metal Layer Stratification**

| Span | Layer | Use |
|------|-------|-----|
| Local | $M2/M3$ | Thin, dense wires |
| Global | $M6/M7$ | Thick, low-$R$ "hyper-chords" |

**📉 Predictable Timing**
No congestion hotspots = matched $RC$ delays across all channels.

**🧠 Deterministic Paths**
Design-time BFS → hardcoded LUT → **zero-latency** silicon execution.

]

---

### 📉 Dense Crossbar vs. Cyclic Quorum Comparison

.font-sm[
| Metric | Dense Crossbar | Cyclic Quorum | Savings |
|--------|---------------|---------------|---------|
| **13×13 core** | 169 vias | **52 vias** | 69% 🔥 |
| **39×13 tiled** | 507 vias | **156 vias** | 69% 🔥 |
| **38×13 trunc.** | 494 vias | **152 vias** | 69% 🔥 |
| **41×12 custom** | 492 vias | **164 vias** | 67% 🔥 |
| **100×23 sparse** | 2,300 vias | **600 vias** | 74% 🔥 |
| Row-load variance | High | Near-zero | ✅ |
| Cell reusability | None | Identical columns | ✅ |
| Timing closure | Unpredictable | Deterministic | ✅ |
]

**Bottom line:** ~**70% via reduction** + **predictable EDA flow** = tapeout with confidence 🎯

---

### 🎯 Key Takeaways

#### 1️⃣ **Sparsity Over Density**
Replace dense crossbars with cyclic block matrices to reduce via overhead by **up to 80%**.

**The magic:** $k$ wires per column instead of $M$ — and $k$ can be as low as 4.

#### 2️⃣ **Deterministic Paths**
Use graph-search (BFS) at **design-time** to discover paths, then hardcode them for zero-latency execution.

**Runtime = O(1)** — just a table lookup.

]

#### 3️⃣ **Scalable Workflows**
Use **Tiling** and **Truncation** to hit exact specification targets without redesigning the core macro blocks.

$N$ inputs, $M$ outputs — just pick the right difference set.

#### 4️⃣ **EDA-Friendly Design**
- ✅ Identical column templates
- ✅ Matched $RC$ delays
- ✅ No congestion hotspots
- ✅ Predictable timing closure

**🔥 Ready for Silicon Implementation.**

]

---

# ❓ Q&A 🎤

### 🛰️ Designing Highly Routable Interconnection Networks via Cyclic Quorums

**Questions? Comments? Ideas?**

**References:**
- 🔗 [github.com/luk036](https://github.com/luk036)
- 🐍 `perfect_diffset.py`, `multi_hop.py`, `interconnection.py`

]

**Thank you!** 🙏

Wai-Shing Luk 👨‍💻

@luk036

]