一个快速高效进行布线拥挤优化的总体布线器

设计实现了一个高效的线长模式下基于多处理机的并行总体布线器.通过对非时延驱动模式下串、并行算法的总运行时间和求解时间的比较,表明该并行算法能够在保证求解质量无明显变化的前提下大大加快总体布线算法的求解速度.同时,也提出了基于分布式体系结构的并行总体布线算法.     

SSTT: Efficient local search for GSI global routing

In this paper, a novel global routing algorithm is presented for congestion opti-mization based on efficient local search, named SSTT (search space traversing technology). This method manages to traverse the whole search space. A hybrid optimization strategy is adopted,consisting of three optimization sub-strategies: stochastic optimization, deterministic optimiza-tion and local enumeration optimization, to dynamically reconstruct the problem structure. Thus,“transition” can be made from a local minimum point to reach other parts of the search space,traverse the whole search space, and obtain the global (approximate) optimal routing solution.Since any arbitrary initial routing solution can be used as the start point of the search, the initial-ization in SSTT algorithm is greatly simplified. SSTT algorithm has been tested on both MCNC benchmark circuits and industrial circuits, and the experimental results were compared with those of typical existing algorithms. The experimental results show that SSTT algorithm can obtain the global (approximate) optimal routing solution easily and quickly. Moreover, it can meet the needs of practical applications. The SSTT global routing algorithm gives a general-purpose routing solution.     

性能驱动总体布线的关键技术及研究进展

在计算机软件领域,超大规模集成电路技术的迅猛发展迫切需要高性能CAD工具——电子设计自动化(EDA)软件工具的支持.与物理设计相关的CAD技术称为布图设计,总体布线是布图设计中一个极为重要的环节.目前,在深亚微米、超深亚微米工艺下的超大规模、甚大规模集成电路设计中,性能驱动总体布线算法已成为布图设计中的一个国际研究热点.针对这一热点,分析了性能驱动总体布线算法研究中亟待解决的关键技术,并详细阐述了国内外的重要相关研究工作进展情况.     

基于Sakurai模型的时延驱动Steiner树算法

时延驱动的Ｓｔｅｉｎｅｒ树构造算法是时延驱动总体布线的基础．本文首先简介了求解最佳Ｓｔｅｉｎｅｒ树的Ｄｒｅｙｆｕｓ－Ｗａｇｎｅｒ算法．随后通过引入Ｓａｋｕｒａｉ时延模型,提出了直接基于Ｓａｋｕｒａｉ模型的提高线网时延性能的时延驱动ＤＷ算法．当集成电路工艺的特征宽度较小时,该算法求得的Ｓｔｅｉｎｅｒ树中关键点的时延值,明显小于ＩＤＷ和ＣＦＤ算法的结果．     

CNB: A critical-network-based timing optimization method for standard cell global routing

A novel method, named critical-network-based (CNB),for timing optimization in global routing is presented in this paper.The essence of this method is different from that of the typical existing ones,named nets-based (NB) and critical-path-based (CPB).The main contribution of this paper is that the CNB delay reduction method is more efficient than the typical existing ones.This new method makes it possible to reduce the delay in an overall survey.Based on CNB,a timing optimization algorithm for global routing is implemented and tested on Microelectronics Center of North Carolina (MCNC) benchmarks in this paper.The experimental results axe compared between this algorithm and the existing ones.The experimental results show that this algorithm is able to control the delay efficiently.     

一种新的与线网顺序无关的随机优化总体布线算法

针对目前总体布线中仍然存在的3个关键问题;布线结果受布线顺序的影响、总体布线图中拥挤区域的不可预见性、线网连接式样受到算法的限制等,该文提出了一种新的不受线网顺序影响的总体布线算法,并实现了相应的总体布线器RINO－Router。该算法采用随机优化方法来保 证先后被拆线重布的线网有相同的通过拥挤区域的机会,并能得到GRG边的拥挤度估计值;采用高效的Steiner树改造算法构造避开拥挤区域的布线树,采用典型电路实例进行了测试,并将布线结果与基于多商品流算法的总体布线器Matula-Router进行了对比。结果表明,RINO－Router能够在短得多的运行时间内求得质量与Matula-Router相近的总体布线解。     

一个快速高效进行布线拥挤优化的总体布线器

设计实现了一个高效的线长模式下基于多处理机的并行总体布线器.通过对非时延驱动模式下串、并行算法的总运行时间和求解时间的比较,表明该并行算法能够在保证求解质量无明显变化的前提下大大加快总体布线算法的求解速度.同时,也提出了基于分布式体系结构的并行总体布线算法.