首页 | 本学科首页   官方微博 | 高级检索  
     

SSTT: Efficient Local Search for GSI Global Routing
作者姓名:经彤  洪先龙  鲍海云  许静宇  顾钧
作者单位:[1]DepartmentofComputerScienceandTechnology,TsinghuaUniversity,Beijing100084,P.R.China [2]DepartmentofComputerScience,HongKongUniversityofScienceandTechnology,HongKong,P.R.China
基金项目:This work was supported partly by the National Hi-Tech Research and Development 863 Program of China under Grant No.2002AA1Z1460, Key Faculty Support Program of Tsinghua University under Grant No.[2002] 4, NSFC under Grant No.60121120706, and NSF of USA
摘    要: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.

关 键 词:SSTT  GSI  全局布线  局部查找  检索空间  超大规模集成电路

SSTT: Efficient local search for GSI global routing
Jing?Tong?Email author,Hong?XianLong,Bao?HaiYun,Xu?JingYu,Gu?Jun.SSTT: Efficient Local Search for GSI Global Routing[J].Journal of Computer Science and Technology,2003,18(5):0-0.
Authors:Email author" target="_blank">Jing?Tong?Email author  Hong?XianLong  Bao?HaiYun  Xu?JingYu  Gu?Jun
Affiliation:(1) Department of Computer Science and Technology, Tsinghua University, 100084 Beijing, P.R. China;(2) Department of Computer Science, Hong Kong University of Science and Technology, Hong Kong, P.R. China
Abstract:In this paper, a novel global routing algorithm is presented for congestion optimization 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 optimization 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 initialization 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.
Keywords:GSI (giga-scale integrated circuits)  layout  global routing  local search  SSTT (search space traversing technology)
本文献已被 CNKI 维普 万方数据 SpringerLink 等数据库收录!
点击此处可从《计算机科学技术学报》浏览原始摘要信息
点击此处可从《计算机科学技术学报》下载全文
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号