HubRouter: Learning Global Routing via Hub Generation and Pin-hub Connection
Introduction
全局布线(Global Routing - GR)是 VLSI 设计中最复杂且最耗时的组合问题之一。GR 目标是总线长最小，同时避免拥塞(Congestion)，是个 NP 问题。
传统采用启发式算法，多样性和规模问题对传统算法有了挑战，机器学习(ML)已经用于全局布线，在芯片设计中从逻辑合成到布局。
新式算法：
-
深度强化学习(Deep Reinforcement Learning - DRL )和生成式模型(Generative model)已经被用来解决全局布线。问题在于，DRL很受状态空间(State Space)影响，随着网格空间增大，需要花费大量时间生成。相反，生成式模型有一次性生成能力，在计算上更容易处理。
-
生成式方法在训练时候考虑连通性限制，确保布线满足电路连通性要求。但是问题在于，如果初始生成路径不满足连通性要求时候，后处理阶段会变成一种穷举搜索过程。
图一这里上图表示原始布线，下图表示算法生成的布线，生成布线没有正确连接所有应该连接的点(pin)，对于这样的情况，平均连通率很低，低于20%，意味着超过80%的生成布线需要经过耗时的后处理才能达到要求。显著的缺点。
Hub
为了解决上述问题，定义了一个新的概念，叫hub。将pin - pin问题 --> hub - pin问题 。
提出了一种新的两阶段全局布线方法 --> HubRouter
1.Hub-generation phase（hub生成阶段）
可以在多个框架下生成，比如 GAN (Generative Adversarial Nets) , VAE (Variational Auto-Encoder) , DPM (Diffusion Probabilistic Models) 。虽然hub是生成阶段的主要输出，但为了提升生成质量和准确性，发现生成附加信息是非常有用的。比如感知和掩码(local perception and stripe masks)，能够去除噪声点。
2.pin-hub-connection phase（hub和pin连接阶段）
将连接视为最小斯坦纳树(RSMT)问题，使用 actor-critic 模型网络策略。
图二是与不同全局布线方法特点对比。
文中总结重点是：
-
提出 hub，意味布线的关键点，在保证连接性情况下有效连接。
-
设计 HubRouter 算法，连通性保证消除了耗时的后处理(Post-Processing)。
-
生成阶段，引入多任务学习，布线和掩码一起生成，提高 hub 生成质量；连接阶段，采用 actor-critic 模型网络有效模拟 RSMT 构建。
-
在多个真实数据集上实验，目前的SOTA模型。
Background and Preliminaries
Global Routing（全局布线）
图 a ：芯片画布和网表
图 b： 网格图
全局布线主要目标连接所有需要的连接，在基础上，减少布线线长(WL)和溢出(OF)。
Generative Global Routing（生成全局布线）
生成模型 views：
一般看来：全局布线 --> 布线图
生成模型：布局 --> 图像 ； 布线 --> 独立条件的图像生成
具体来说，像素(pixels)代表全局布线中小方格(tiles)，从给定条件图像生成布局输出图像。
条件图像包含三个 channel：第一个 channel 代表引脚位置，另外两个 channel 代表水平和垂直网格边缘容量。
图 c：条件图像 --> 亮点代表引脚位置
图 d：布线图像 --> 布线路径
Hub
图 d 还表示了 hub 的四种不同形态，我的理解就是 1，2，3，4 个引脚输出：+ ⊤ ⌞ ·
Difference between Hubs and Steiner Points（Hub 点和斯坦纳点不同）
斯坦纳点(Rectilinear Steiner Point --> RSP)是搜索全局最小总距离，但是 hub 是来确定路径。
RSP是Hub的特例，Hub可以随意生成不同形状的路径(不仅是最短的)
From Pin-Pin to Hub-Pin Connection: A Two-phase Routing Scheme
Approach Overview
概括了一个两阶段模型：
1.第一阶段：中心点生成阶段（Hub-Generation Phase）
在这个阶段，模型旨在逼近条件分布 pθ(x|z, c) 使其接近先验分布 p(x|c)。给定条件 c 和从先验分布 pz(z) 中采样得到的潜在变量 z（通常假设为高斯分布），模型会生成一些“中心点（hubs）”。
这里的 c 和 x 分别代表条件图像和输入图像。条件图像可能包括引脚位置、已经提取的中心点以及条带掩模（stripe mask）。条带掩模是用来指示布线区域的一种方式，它可以帮助模型更好地理解哪些区域可以用于布线。
2.第二阶段：引脚-中心点连接阶段（Pin-Hub-Connection Phase）
在这个阶段，模型连接第一阶段生成的中心点，以获得最终的布线路由。这个过程可以被视为构建矩形稳定最小生成树（Rectilinear Steiner Minimum Tree，RSMT）的一部分。为了完成布线，模型遵循了一个基于强化学习（Reinforcement Learning，RL）的算法 REST。
在两阶段的过程中，作者还提出了一个多任务学习框架来提高生成中心点的质量。特别是，提出了一种新颖的条带掩模学习方法，旨在减轻噪声点案例可能造成的负面影响。算法的具体细节在附录 B 中给出。
Hub-generation Phase: Multi-task Learning of Hub, Mask, and Unused Pre-Routing（Hub 生成阶段）
Hub 生成可以表示为图像到图像的任务，附录 B 介绍了将 GAN，VAE，EAN 纳入到生成框架。
对比 PRNet 生成模型，PRNet 在 CGAN 中使用双向映射将连接约束注入训练目标，将准确率提高了 10%，但在复杂情况下几乎无效。
Hub 生成与其他图片生成任务有所不同，在布线时候，很微小的噪声都会对结果产生很大的影响。特别是最外侧的噪声，会显著增加线路长度，eg 图(b) 和图© 。图(b) 的两个噪声点导致了图© 的线长显著增加（所有生成的 Hub 都需要在同一线路连接）。
为了保持高精度生成结果，提出多任务处理框架，输入 input 为：Hub ，Route ，Mask。Hub 为第一阶段主要目的，Route 和 Mask 为辅助。特别是，预先生成的 Routes 是预路由结果，在第二阶段并不使用，但是用于在基于 CNN 的网络中获得更好的连续局部感知。
提出了 stripe mask 新掩码模块，以关注 hub 生成的不良情况。具体来说，stripe mask 定义为一个矩阵，其中的值只有 0 和 1，值为 1 表示在对应行或列有一个 hub。在推理时，通过一个二值化的 stripe mask 来掩盖生成的 hubs，从而剔除噪声点，这样可以缩短生成的路线，去除多余的路径。
两个优点：
-
实际测试，适当的stripe mask可以消除大部分噪声点。
-
布线结果不需要唯一，而stripe mask模块能够提供不同的路由选择。例如在图4(d)中，两个黑色的hubs可以任意选择一个黄色点作为转折点来相互连接，同时路径长度保持相同。
Pin-hub-connection Phase: RSMT Construction
Pin - Hub 连接 归纳为 RSMT 过程。
Hub 优势：
-
没有Hub，RSMT构造只能找到最短布线，不能在合适情况下生成合适布线。
-
一个好的Hub生成可以将RSMT布线阶段时间复杂度表示为O(n log n)。
图 3 中 Actor 网络用于创建有坐标信息的 RES 结果，Crieic 网络设置 Baseline 预测 Actor 网络构建的 RSMT 预期布线长度，通过更新策略最小化 RSMT 长度。
Experiment and Analysis
实验设备：i9-10920X CPU, NVIDIA RTX 3090 GPU and 128 GB RAM
实验过程：不同种子下重复三次，平均值和标准差值与 PRNet 一致。
Datasets and Setups
ISPD-07 和 ISPD-98
“Route-small-4”和“Route-small”分别表示具有不超过和超过 4 个引脚并且引脚的半周长线长（HPWL）小于 16 的情况。
'Route-large-4’和’Route-large’相似，其 HPWL 大于 16。
Unconnected Cases in Previous Generative Global Routing Approaches（连通情况对比）
HubRouter 为最优结果
Benchmarking Global Routing and Ablation Study（全局布线 消融实验）
Benchmarking Global Routing（全局布线）
简单来说：需要高质量 --> GAN ; 需要速度快 --> VAE ; 有丰富的计算资源 --> DPM
Ablation Study（消融实验）
1.Hubs --> HubRouter-h
2.Hubs + Routers --> HubRouter-hr
3.Hubs + Routers + Stripe Masks --> HubRouter-hrm
结果表明：
生成过程中，HubRouter-hrm 效果最好
连接过程中，HubRouter (T=8)效果最好
Further Studies and Discussion（进一步研究）
HubRouter 不仅可以做全局布线，分别执行 RSMT 构造和交互式路径重规划，以体现 HubRouter 的通用性。使用 GAN 网络。
RSMT Construction（RSMT 构造）
当度小于 25 时，REST 的性能最好，而当度大于 30 时，HubRouter 的性能优于其他方法。
os：这里的度(degree)我觉得是前面提到的。好吧其实我不太理解。
Interactive Path Replanning（交互式路径规划）
通过不同的 Hub 决定新的路径规划。
Analysis of Scalability and Time Overhead（可扩展性和时间）
HubRouter 的 RSMT 构建时间比 GeoSteiner 慢。
Non End-to-End framework（非端到端框架）
HubRouter 是两阶段框架，PRNet 是端到端框架。各有千秋。
