面向甚大规模集成电路的时延驱动布局方法  

Timing-Driven Placement Algorithm for Very Large Integrated Circuits

作　　者：吴为民[1] 洪先龙[1] 蔡懿慈[1] 顾钧[2] 

机构地区：[1]清华大学计算机科学与技术系,北京100084 [2]香港科技大学计算机科学系

出　　处：《电子学报》2001年第8期1018-1022,共5页Acta Electronica Sinica

基　　金：国家自然科学基金 (No 697760 2 7) ;973国家关键项目 (No G1 9980 30 4 1 1 )

摘　　要：本文针对甚大规模集成电路的时延驱动布局问题提出了一个新的解决途径 ,其策略是将结群技术应用于二次规划布局过程中 .结群的作用是可大幅度地降低布局部件的数量 .本文设计了一个高效的结群算法CARGO ,其优点是具有全局最优性并且运行速度很快 .采用了一个基于路径的时延驱动二次规划布局算法对结群后的电路完成布局过程 .由于二次规划布局算法能够在很短时间内寻找到全局最优解 ,故本文的算法更有希望彻底解决甚大规模电路的布局问题 .在一组MCMC标准测试电路上对算法进行了测试 。A novel approach for timing-driven placement of very large integrated circuits is presented. Our strategy is to apply clustering technique to a quadratic placement procedure. By clustering, the number of components for placement is reduced considerably. We design al high-efficiency clustering algorithm, named CARGO, which has global optimality and runs very fast. We use a path based timing-driven quadratic placement algorithm to complete the placement of the condensed circuit. Because quadratic placement algorithm can mathematically find global optima in very short time, our new approach might be more promising for solving the problem thoroughly. We test our algorithm on a set of MCNC circuits and obtain satisfactory results.

关 键 词：结群 二次规划 时延驱动 布局 甚大规模集成电路 

分 类 号：TN47[电子电信—微电子学与固体电子学]