January
30th,
2019
目标：
- 硬件结构连接
- 基本通信开销
- 数据如何流动
基本知识
- 术语：node、interface、switch（router）、link
- 直接网络、间接网络：每个节点是否属于网络的端点
- 阻塞网络、非阻塞网络：任意时刻任意两节点是否能通信
互连拓扑结构
bus
- 容易实现缓存一致性
- 所有节点产生竞争；有限带宽
crossbar
- 非阻塞、间接
- 不可扩展
- $O(N^2)$开销
- $O(1)$延迟
ring
- 简单，$O(N)$开销
- $O(N)$高延迟，有限带宽
Mesh
- 直接，阻塞
- $O(N)$开销
- $O(sqrt(N))$延迟
- 节点路径不唯一
Torus
- 和Mesh类似，更加复杂
Tree
- $O(log(N))$延迟
- 适合局部通信较多场景
Multi stage logarithmic
- 间接，阻塞
- $O(Nlog(N))$开销
- $O(log(N))$延迟
缓冲区与控制流
包（packet）格式：
- 头：路由、控制信息
- 数据
- 尾：控制信息，如纠错码等
竞争：
- 来源：两个包同时经过link时
- 解决：
- store-and-forward：每个router处有packet buffer，每个packet需要缓存，增加延迟
- cut-through flow control：和上面类似，packet以流水线方式传输。最坏情况下，如果总线忙，无法流水线，就会退化成上面一种方式。
- wormhole flow control：
- 把packet拆分成更小单元flit进行传输。flit以流水线进行传输，当头flit阻塞时，所有flit同时停止。信息足够长时，延迟与节点距离无关。
- 问题：head-of-line blocking，头结点被其他flit阻塞
- 解决：virtual channel，将buffer分成多个buffer共享一个物理单元
- 把packet拆分成更小单元flit进行传输。flit以流水线进行传输，当头flit阻塞时，所有flit同时停止。信息足够长时，延迟与节点距离无关。
- store-and-forward：每个router处有packet buffer，每个packet需要缓存，增加延迟