EDA 论文选读

Abstract. 因为最近在一个 EDA 组里轮转,所以需要学一些经典 EDA 算法。现在主要包括如下线索:

  • Trees in Routing

Trees in Routing

在 Routing 时,我们需要找一种方法来连通所有的引脚。为了方便芯片的加工,通常要求一切连边都是水平 / 垂直方向的。在连接时,应当优化如下两个目标:

  1. 线路延迟. 对应路径长度。
  2. 资源消耗. 对应线缆总长度。

前者对应曼哈顿距离度量下的最短路树问题,可以用 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