PolarFly
基于射影平面极性图的直径 2 拓扑，通过扩大可选规模点演进 SlimFly
核心要点：
- Lakhotia et al. SC 2022 提出，与 SlimFly 同目标 （直径 2 + 接近 Moore 界）
- 基于 Erdős-Rényi 极性图 （射影平面 + 正交关系）
- 参数 $q$ 接受任意素数幂 (vs SlimFly 仅 $q \equiv 1 \pmod 4$ 素数)
- 可选规模点约 SlimFly 3-4 倍
- 节点 $N = q^2 + q + 1$，度 $q + 1$
- $q$ 为 2 的幂时图完全正则 （无自极点）
- Moore 界效率随 $q$ 提升：76% ($q=3$) → 97% ($q=32$)
- 与 SlimFly 同样无生产部署 （相同工程化障碍）
核心论文：[Lakhotia et al., PolarFly: A Cost-Effective and Flexible Low-Diameter Topology, SC 2022][1]
与 SlimFly 是什么关系？
同目标 （直径 2 + 接近 Moore 界 + 低成本），不同数学构造：
| SlimFly | PolarFly | |
|---|---|---|
| 数学基础 | MMS 图 （有限域上二次剩余） | Erdős-Rényi 极性图 （射影平面上正交） |
| 参数约束 | $q$ 素数且 $q \equiv 1 \pmod 4$ | $q$ 任意素数幂 |
| 节点数 | $2q^2$ | $q^2 + q + 1$ |
| 度数 | $\frac{3q-1}{2}$ | $q + 1$ |
@tbl-topo-pf-vs-sf PolarFly vs SlimFly
核心改进：大幅放宽参数约束。SlimFly 只能用 $q = 5, 13, 17, 29, ...$；PolarFly 接受 $q = 2, 3, 4, 5, 7, 8, 9, 11, 13, ...$ — 可选规模点约 SlimFly 3 倍。
Moore 界背景见 2.9 SlimFly。
射影平面 $\text{PG}(2,q)$ 是什么？
普通平面 + 无穷远点，使得任意两条不同直线恰好交于一点。
问题：普通平面上平行线永远不交，"两条不同直线可能不交"这个特例造成不对称。
解决：添加无穷远点，平行线交于无穷远点，消除特例获得完美对称结构。
$\text{PG}(2,q)$ 构造 ($q$ 为素数幂):
- 点：$\text{GF}(q)$ 上的三维非零向量 $(x, y, z)$，成比例的向量视为同一点：$(x, y, z) \sim (\lambda x, \lambda y, \lambda z)$
- 点数：$\frac{q^3 - 1}{q - 1} = q^2 + q + 1$
直觉：$\text{PG}(2,q)$ 有 $q^2 + q + 1$ 个点和 $q^2 + q + 1$ 条线 （数量相同），每条线过 $q+1$ 个点，每点在 $q+1$ 条线上。任意两点确定唯一线，任意两线交于唯一点。
PolarFly 的连接规则是什么？
两点正交时相连 （内积为零）[2]:
节点 = $\text{PG}(2,q)$ 的点
节点 $[x_1, y_1, z_1]$ 与 $[x_2, y_2, z_2]$ 相连 $\iff x_1 x_2 + y_1 y_2 + z_1 z_2 \equiv 0 \pmod q$
就是标准的正交条件，只是在有限域上而非实数域。
具体示例：$q = 3$ 怎么构造？
$q = 3$ 是 PolarFly 可用但 SlimFly 不可用的最小参数。
枚举所有点
$\text{PG}(2,3)$ 有 13 个点。选每等价类的标准代表 （第一非零坐标归一为 1）：
| 编号 | 坐标 |
|---|---|
| $P_0$ | $(1,0,0)$ |
| $P_1$ | $(1,1,0)$ |
| $P_2$ | $(1,2,0)$ |
| $P_3$ | $(1,0,1)$ |
| $P_4$ | $(1,1,1)$ |
| $P_5$ | $(1,2,1)$ |
| $P_6$ | $(1,0,2)$ |
| $P_7$ | $(1,1,2)$ |
| $P_8$ | $(1,2,2)$ |
| $P_9$ | $(0,1,0)$ |
| $P_{10}$ | $(0,1,1)$ |
| $P_{11}$ | $(0,1,2)$ |
| $P_{12}$ | $(0,0,1)$ |
@tbl-topo-pf-q3-points $\text{PG}(2,3)$ 的 13 个点
计算 $P_0$ 邻居
$P_0 = (1,0,0)$，内积 $= x \equiv 0$，即第一坐标为 0 的点：$\{P_9, P_{10}, P_{11}, P_{12}\}$。4 个邻居，度 $= q + 1 = 4$。
计算 $P_4$ 邻居
$P_4 = (1,1,1)$，内积 $= x + y + z \equiv 0 \pmod 3$:
| 点 | 内积 $\pmod 3$ | 相连？ |
|---|---|---|
| $P_2(1,2,0)$ | 0 | 是 |
| $P_6(1,0,2)$ | 0 | 是 |
| $P_{11}(0,1,2)$ | 0 | 是 |
| 其他 | ≠ 0 (含 $P_4$ 自身) | 否 |
@tbl-topo-pf-q3-p4 $P_4$ 邻居
$P_4$ 邻居只有 3 个，因为 $P_4 \cdot P_4 = 3 \equiv 0$ 但自身不能算邻居 — 引出自极点概念。
自极点是什么？
满足 $x^2 + y^2 + z^2 \equiv 0 \pmod q$ 的点 — 与自身"正交"。
$q = 3$ 的自极点:
| 点 | $x^2 + y^2 + z^2 \pmod 3$ | 自极？ |
|---|---|---|
| $P_4(1,1,1)$ | $1+1+1 \equiv 0$ | 是 |
| $P_5(1,2,1)$ | $1+4+1 \equiv 0$ | 是 |
| $P_7(1,1,2)$ | $1+1+4 \equiv 0$ | 是 |
| $P_8(1,2,2)$ | $1+4+4 \equiv 0$ | 是 |
| 其他 9 个 | ≠ 0 | 否 |
@tbl-topo-pf-q3-selfpolar $q = 3$ 自极点
$q = 3$ 时有 $q + 1 = 4$ 个自极点，度为 $q = 3$ （少 1）。其他 9 个点度为 $q + 1 = 4$。
对拓扑的影响：
- 自极点少一连接，图不完全正则 （"近正则"）
- 自极点只在 $q$ 为奇数时存在
- $q$ 为偶数 （2 的幂：2, 4, 8, 16, ...） 时不存在自极点，图完全正则
这是 PolarFly 相比 SlimFly 的额外优势：选 $q$ 为 2 的幂可获得完全正则图。
Moore 界效率随 $q$ 怎么变化？
$q$ 越大，效率越接近 100% — 不同于 SlimFly 恒定 89%。
$$\begin{equation} \frac{N}{N_{\text{Moore}}} = \frac{q^2 + q + 1}{q^2 + 2q + 2} \approx 1 - \frac{q+1}{q^2+2q+2} \label{eq:topo-polarfly-density-ratio} \end{equation}$$| $q$ | $N$ | $d$ | Moore 界 | 效率 |
|---|---|---|---|---|
| 3 | 13 | 4 | 17 | 76% |
| 5 | 31 | 6 | 37 | 84% |
| 8 | 73 | 9 | 82 | 89% |
| 16 | 273 | 17 | 290 | 94% |
| 32 | 1,057 | 33 | 1,090 | 97% |
@tbl-topo-pf-efficiency PolarFly Moore 界效率
PolarFly 在大规模下效率更高，SlimFly 是恒定 89%。
关键参数和可选规模
核心问题：PolarFly 的交换机数、度数、直径、割集等关键参数是多少？$q \leq 32$ 范围内可选规模点有多少？
| 属性 | 值 |
|---|---|
| 交换机总数 | $N = q^2 + q + 1$ |
| 度数 （非自极点） | $q + 1$ |
| 度数 (自极点，奇 $q$) | $q$ |
| 交换机 radix | $R = T + (q + 1)$ |
| 直径 | 2 （恒定） |
| 割集带宽 | $\sim \frac{N}{2} b$ |
| Vertex-Transitive | Yes |
@tbl-topo-pf-params PolarFly 关键参数
可选规模 ($q \leq 32$) (@tbl-topo-pf-scale):
| $q$ | 类型 | 交换机数 $N$ | 度 $d$ | 完全正则？ |
|---|---|---|---|---|
| 2 | $2^1$ | 7 | 3 | 是 |
| 3 | 素数 | 13 | 4 | 否 （4 自极点） |
| 4 | $2^2$ | 21 | 5 | 是 |
| 5 | 素数 | 31 | 6 | 否 |
| 7 | 素数 | 57 | 8 | 否 |
| 8 | $2^3$ | 73 | 9 | 是 |
| 9 | $3^2$ | 91 | 10 | 否 |
| 11 | 素数 | 133 | 12 | 否 |
| 13 | 素数 | 183 | 14 | 否 |
| 16 | $2^4$ | 273 | 17 | 是 |
| 17 | 素数 | 307 | 18 | 否 |
| 19 | 素数 | 381 | 20 | 否 |
| 23 | 素数 | 553 | 24 | 否 |
| 25 | $5^2$ | 651 | 26 | 否 |
| 27 | $3^3$ | 757 | 28 | 否 |
| 29 | 素数 | 871 | 30 | 否 |
| 31 | 素数 | 993 | 32 | 否 |
| 32 | $2^5$ | 1,057 | 33 | 是 |
@tbl-topo-pf-scale PolarFly 可选规模
$q \leq 32$ 范围内 PolarFly 有 17 个有效规模点，SlimFly 仅 4 个 ($q = 5, 13, 17, 29$)。
与 SlimFly 相近规模对比 (@tbl-topo-pf-vs-sf-detail):
| 属性 | PolarFly ($q=17$) | SlimFly ($q=13$) |
|---|---|---|
| 交换机数 | 307 | 338 |
| 度数 | 18 | 19 |
| 直径 | 2 | 2 |
| Moore 界效率 | 94% | 89% |
| 完全正则 | 否 （18 自极点） | 是 |
| 连接规则 | 内积 = 0 | MMS 代数构造 |
@tbl-topo-pf-vs-sf-detail PolarFly vs SlimFly 相近规模
两者性能非常接近，PolarFly 主要优势是规模灵活性而非性能差异。
拓扑特性
核心问题：PolarFly 的直径 2、非层级、偶数 q 完全正则这三个特性各自带来什么工程影响？
恒定直径 2：射影平面的组合性质保证任意两个不直接相连的节点至少有一个公共邻居。
非层级：与 SlimFly 相同，连接由代数决定，无层级划分。路由需预计算转发表 ($O(N)$ 规模)，无法用前缀匹配。
偶数 $q$ 完全正则: $q = 2, 4, 8, 16, 32, ...$ 时图完全正则，所有节点度相同，布线完全对称 — 物理部署有实际优势 （每交换机端口分配一致，线缆规划简单）。
适用场景与局限
核心问题：PolarFly 适合和不适合哪些并行策略和部署场景？
适用 （继承 SlimFly 所有场景）：
- 集群规模无法匹配 SlimFly 离散约束
- 需要完全正则拓扑简化布线 (选偶数 $q$)
- 延迟敏感、成本约束严格的中等规模
- 流量模式接近均匀
局限：
- 布线非结构化，运维困难
- 路由表 $O(N)$ 预计算，不如前缀匹配可扩展
- 割集非严格全带宽，对抗性流量弱于 Fat-tree
- 增量扩展不可行 ($q$ 变化需重构)
- 奇数 $q$ 有 $q+1$ 个自极点近正则性
实际部署：同样无生产部署
核心问题：PolarFly 为什么和 SlimFly 一样没有生产部署？工程化障碍有哪些？
无生产部署，PolarFly 面临与 SlimFly 完全相同的工程化障碍：
- 交换机 ASIC 不支持非层级拓扑预计算路由
- 非结构化布线无法管理
- 商业生态缺失 （SDN / 监控 / 故障诊断工具不支持）
相比 SlimFly 的真正改进：更宽可选规模 + 偶数 $q$ 完全正则。但不足以克服工程化障碍 — 两者面临相同产业化鸿沟。
Takeaway
| 知识点 | 核心结论 |
|---|---|
| 与 SlimFly 关系 | 同目标 （直径 2 + Moore 界），不同数学构造 |
| 数学基础 | Erdős-Rényi 极性图，射影平面 + 正交 |
| 参数约束 | 任意素数幂 (vs SlimFly $q \equiv 1 \pmod 4$ 素数) |
| 规模灵活性 | 可选点约 SlimFly 3-4 倍 |
| Moore 效率 | 76% ($q=3$) → 97% ($q=32$)，规模越大越接近 |
| 完全正则 | 偶数 $q$ （2 的幂） 时获得 |
| 自极点 | 奇数 $q$ 时 $q+1$ 个自极点度数少 1 |
| 部署 | 同 SlimFly，无生产部署 |
参考资料
- Lakhotia K. et al., PolarFly: A Cost-Effective and Flexible Low-Diameter Topology, SC 2022. https://doi.org/10.1109/SC41404.2022.00017
- Erdős P. and Rényi A., On a Problem in the Theory of Graphs, 1962. https://doi.org/10.1007/BF02018441