Chapter 3: Baseline Switching Modules and Routers本文版权归作者所有任何形式的转载都请注明出处对于 N-to-1 访问无论采用 VCT 或 WH 哪种流控一般下游节点需要具有并行的多个 Queue 的微架构才支持不同 Packet 交织Interleave否则仲裁器只有在前一数据包的 Tail 通过后才能切换到下一个来自不同源的 Head 并锁定仲裁直到 Tail 通过再次切换。实际上一般交织需要通过虚通道Virtual Channel实现。多输入仲裁可以分层形成树形的仲裁结构。每一级仲裁间插入寄存器表示上一级的仲裁输出作为下一级的仲裁输入。当某一路发生阻塞时不影响其他子树的仲裁。一个 N-to-N 的 Switch 结构包含 N bit 输入in[i]和输出out[i]独热码数组outPort[i][j]表示in[i]请求访问out[j]由 Head 携带 dstID 信息置 1Tail 通过时清 0。outLock[i]由granted[i]置 1用于锁住outPort值从而保持独占Tail 通过时清 0。outAvailable[j]表示输出 j 空闲输出 j 被 Head 独占后清 0Tail 通过时置 1从而开启新一轮仲裁。综上该结构可以达到多个输出口并行占用同一输出口的请求需要串行化。若输入为单 FIFO 队列头阻塞Head-of-Line Blocking, HOLB一般无法避免——就像直行 右转的单车道若队首正等待直行欲右转的后车只能等待。计算每个输出口的吞吐期望已知每 clk 都有新的 flit 输入且送往每个输出口的概率相等即输入 i 选择输出 j 的概率Pij 1/N则输入 i 不选择输出 j 的概率Pij 1 - 1/N。那么所有 N 个输入都不选择输出 j 的概率为Π(Pij) (1 - 1/N)^N。所以最终输出 j 被占用的概率Pj1−(1−1N)NPj 1 - (1 - \frac{1}{N})^NPj1−(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%。通过路由计算得到请求占用哪个方向的输出口。路由信息可以由两种方式得到源路由Source Routing源节点处发出完整路由信息到达每一个 hop 直接可以得到输出口信息并寄存到outPort中用完后移位更新路由信息给到下一 hop 使用分布式路由Distributed Routing路由信息由每一 hop 根据 dstID 分布式计算得到一般会采用路由算法如查找表、X-Y 路由等有时也会参考输出口 busy 状态。RCRouting Computation单元会增加 Router 内部的逻辑路径解决时序压力可以将 RC 前移Lookahead RC如Fig 3.17.b所示将 RC 前移到输入之前与 Link 并行如Fig 3.17.c所示RC 可继续前移到上个 Router 处——当前 flit 输入后即可提前计算下个 Router 的输出信息并且需要计算所有可能的输出在得到当前 Router 输出信息后选择正确的计算结果传递给下一 Router。对于每个输出口的 N bit 仲裁同样可以优化成树形结构。一方面仲裁遍历的复杂度从 O(N) 优化为 O(log N)即优化组合逻辑级数另一方面可以“定制化”路由如需禁止某些转向就可以 tie-off 这些连线。