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 |