Congestion-Constrained Layer Assignment for Via Minimization in Global Routing
Congestion-Constrained Layer Assignment for Via Minimization in Global Routing
复制标题
DOI：
10.1109/tcad.2008.927733
复制
发表时间：
2008-09
影响因子：
2.9
通讯作者：
Tsung-Hsien Lee;Ting-Chi Wang
中科院分区：
文献类型：
--
作者：
Tsung-Hsien Lee;Ting-Chi Wang
在本文中，我们研究了多层全局布线期间出现的过孔最小化的层分配问题。在解决这个问题时，我们将总溢出和最大溢出作为给定单层全局路由解决方案的拥塞约束，并旨在为每个网络找到一个层分配结果，使得在满足给定拥塞约束的同时使过孔成本最小化。为了解决这个问题，我们提出了一种多项式时间算法，该算法首先生成网络顺序，然后使用动态规划根据该顺序一次执行一个网络的层分配。我们的算法保证生成满足给定拥塞约束的层分配解决方案。我们使用ISPD'07全球路由竞赛发布的六层基准测试来测试我们的算法。实验结果表明，我们的算法能够提高前三名获胜者 MaizeRouter、BoxRouter 和 FGR 在每个基准测试中的比赛成绩。与 BoxRouter 2.0 和 FGR 1.1（BoxRouter 和 FGR 的较新版本）相比，我们的算法分别在所有基准测试和一半基准测试中产生较小的过孔成本。我们的算法还可以适用于以逐网方式细化给定的多层全局布线解决方案，实验结果表明，这种细化方法改善了 FGR 1.1 所有基准的过孔成本。
In this paper, we study the problem of layer assignment for via minimization, which arises during multilayer global routing. In addressing this problem, we take the total overflow and the maximum overflow as the congestion constraints from a given one-layer global routing solution and aim to find a layer assignment result for each net such that the via cost is minimized while the given congestion constraints are satisfied. To solve the problem, we propose a polynomial-time algorithm which first generates a net order and then performs layer assignment one net at a time according to the order using dynamic programming. Our algorithm is guaranteed to generate a layer assignment solution satisfying the given congestion constraints. We used the six-layer benchmarks released from the ISPD'07 global routing contest to test our algorithm. The experimental results show that our algorithm was able to improve the contest results of the top three winners MaizeRouter, BoxRouter, and FGR on each benchmark. As compared to BoxRouter 2.0 and FGR 1.1, which are newer versions of BoxRouter and FGR, our algorithm respectively produced smaller via costs on all benchmarks and half the benchmarks. Our algorithm can also be adapted to refine a given multilayer global routing solution in a net-by-net manner, and the experimental results show that this refinement approach improved the via costs on all benchmarks for FGR 1.1.