企业官网建设流程全解析

Chapter 3: Baseline Switching Modules and Routers

（本文版权归作者所有，任何形式的转载都请注明出处）

1. 对于 N-to-1 访问，无论采用 VCT 或 WH 哪种流控，一般下游节点需要具有并行的多个 Queue 的微架构才支持不同 Packet 交织（Interleave）；否则仲裁器只有在前一数据包的 Tail 通过后，才能切换到下一个来自不同源的 Head 并锁定仲裁，直到 Tail 通过再次切换。实际上，一般交织需要通过虚通道（Virtual Channel）实现。

2. 多输入仲裁可以分层，形成树形的仲裁结构。每一级仲裁间插入寄存器，表示上一级的仲裁输出作为下一级的仲裁输入。当某一路发生阻塞时，不影响其他子树的仲裁。

3. 一个 N-to-N 的 Switch 结构，包含 N bit 输入in[i]和输出out[i]：

   • 独热码数组outPort[i][j]表示in[i]请求访问out[j]，由 Head 携带 dstID 信息置 1，Tail 通过时清 0。
   • outLock[i]由granted[i]置 1，用于锁住outPort值从而保持独占，Tail 通过时清 0。
   • outAvailable[j]表示输出 j 空闲，输出 j 被 Head 独占后清 0，Tail 通过时置 1，从而开启新一轮仲裁。

   综上，该结构可以达到多个输出口并行，占用同一输出口的请求需要串行化。

4. 若输入为单 FIFO 队列，头阻塞（Head-of-Line Blocking, HOLB）一般无法避免——就像直行 + 右转的单车道，若队首正等待直行，欲右转的后车只能等待。

   计算每个输出口的吞吐期望：已知每 clk 都有新的 flit 输入，且送往每个输出口的概率相等，即输入 i 选择输出 j 的概率Pij = 1/N，则输入 i 不选择输出 j 的概率P'ij = 1 - 1/N。那么，所有 N 个输入都不选择输出 j 的概率为Π(P'ij) = (1 - 1/N)^N。所以，最终输出 j 被占用的概率：

   Pj=1−(1−1N)NPj = 1 - (1 - \frac{1}{N})^NPj=1−(1−N1​)N

   随着 N → ∞，Pj → 0.63。论文《Karol M, Hluchyj M, Morgan S (1987) Input versus output queueing on a space-division packet switch. IEEE Trans on Communications COM-35(12):1374–1356》中证明，考虑到前后两包 flit 调度并非完全独立事件，所以最终随着 N → ∞，每个输出口的吞吐只能接近约58%。

5. 通过路由计算得到请求占用哪个方向的输出口。路由信息可以由两种方式得到：
   • 源路由（Source Routing）：源节点处发出完整路由信息，到达每一个 hop 直接可以得到输出口信息，并寄存到outPort中，用完后移位更新路由信息给到下一 hop 使用；
   • 分布式路由（Distributed Routing）：路由信息由每一 hop 根据 dstID 分布式计算得到，一般会采用路由算法（如查找表、X-Y 路由等），有时也会参考输出口 busy 状态。

6. RC（Routing Computation）单元会增加 Router 内部的逻辑路径，解决时序压力可以将 RC 前移（Lookahead RC）：
   • 如Fig 3.17.b所示，将 RC 前移到输入之前，与 Link 并行；
   • 如Fig 3.17.c所示，RC 可继续前移到上个 Router 处——当前 flit 输入后即可提前计算下个 Router 的输出信息，并且需要计算所有可能的输出，在得到当前 Router 输出信息后，选择正确的计算结果传递给下一 Router。

7. 对于每个输出口的 N bit 仲裁，同样可以优化成树形结构。一方面仲裁（遍历）的复杂度从 O(N) 优化为 O(log N)，即优化组合逻辑级数；另一方面，可以“定制化”路由，如需禁止某些转向，就可以 tie-off 这些连线。