标题: | 使用规则导向且考虑障碍物之多层直角史坦纳树的建造 Rule Based Multi-Layer Obstacle-Avoiding Recitlinear Steiner Tree Construction |
作者: | 洪祯徽 Chen-Hui Hung 陈宏明 Hung-Ming Chen 电子研究所 |
关键字: | 绕线;史坦纳树;考虑障碍物;Routing;Recitlinear Steiner Tree;Obstacle-Avoiding |
公开日期: | 2007 |
摘要: | 随着超大型积体电路设计的大小增加,绕线的问题也越来越重要。绕线树建立在绕线器的运作中对于最后的绕线结果影响尤其重大。在我们的论文当中,我们提出了一个单/多层考虑障碍物之直角史坦纳树的建造有效且可以快速的建立多层绕线的方法。 我们介绍了一个最小化总绕线长度的方法,可以称之为共用边。在同样的拓墣结构中,这个方法比只有考虑U型修正来最小化总绕线长度好[20]。 在多层绕线部分,我们提出一个多层级近似的方法来处理这个问题,比起一次考虑整个问题的方法,可以大量的缩短运算时间。实验数据显示,当测试档的大小增大时,我们的方法依然有很好的效能。 In very/ultra large scale design (VLSI/ULSI), routing is a very challenging work. Especially, the routing tree construction, as an extremely important step for routers, plays a crucial role for the routing results. In this thesis, we have proposed an algorithm to construct a single/multi-layer obstacle-avoiding rectilinear Steiner tree, which can get good solution at single layer and fast yet effective at multi layers. We use a concept called co-edge to minimize the total wirelength. It is better than just considering the U-Shaped refinement [20] under the same topology. In multi-layer, we proposed a hierarchical and heuristic approach to solve this problem. Experimental results have shown that our algorithm is still efficient in larger multi-layer cases, with slightly more wirelength. |
URI: | http://140.113.39.130/cdrfb3/record/nctu/#GT009411666 http://hdl.handle.net/11536/80579 |
显示于类别: | Thesis |
文件中的档案:
If it is a zip file, please download the file and unzip it, then open index.html in a browser to view the full text content.