EDA 论文选读
Abstract. 因为最近在一个 EDA 组里轮转,所以需要学一些经典 EDA 算法。现在主要包括如下线索:
- Trees in Routing
Trees in Routing
在 Routing 时,我们需要找一种方法来连通所有的引脚。为了方便芯片的加工,通常要求一切连边都是水平 / 垂直方向的。在连接时,应当优化如下两个目标:
- 线路延迟. 对应路径长度。
- 资源消耗. 对应线缆总长度。
前者对应曼哈顿距离度量下的最短路树问题,可以用 Dijkstra 等经典算法在 $O((n + m)\log n)$ 时间内完美解决;而单独考虑资源消耗的问题就已经非常困难,因为它对应经典的 steiner tree 问题,这个问题是 $\mathbf{NP}\text{-complete}$ 的。
因此常常需要考虑两个问题:最小 steiner tree 问题(SMT),和最短路 steiner tree 问题(SPT / RSA),或者将其合起来然后探究一些 trade-off(对应所谓的 shallow light tree(SLT)问题)。
Title | Keywords |
---|---|
FLUTE Algorithm | RSMT Lookup Table, Divide & Conquer |
GPU-Accelerated Rectilinear Steiner Tree Generation | RSMT GPU Acceleration |
启发式 RSMA 算法 | RSMA ? |
SALT Algorithm | Steiner SLT Spanner, Divide & Conquer |