模拟集成电路二维Stack生成及模块合并算法(英文)  

Two-Dimensional Stack Generation and Block Merging Algorithms for Analog VLSI

作　　者：刘锐[1,2] 董社勤[3] 洪先龙[3] 龙迪[3] 顾钧[4] 

机构地区：[1]中国科学院软件研究所 [2]清华大学计算机科学与技术系,北京100084 [3]清华大学计算机科学与技术系 [4]香港科技大学计算机系

出　　处：《软件学报》2004年第5期641-649,共9页Journal of Software

基　　金：国家自然科学基金90307005 ;60121120706;国家自然基金与香港研究资助局联合资助60218004 ;美国国家自然科学基金CCR-0096383 ;国家高技术研究发展计划(863)2002AA1Z1460~~

摘　　要：在模拟集成电路设计中,关于X轴和Y轴同时对称的Stack,以及模块之间的合并,对于增加器件之间的匹配和控制寄生是至关重要的.描述了模拟集成电路二轴对称Stack生成算法和模块合并算法.通过对于对称欧拉图和对称欧拉路径的研究,得出了多项理论结果.在此基础上,提出了时间复杂度为O(n)的伪器件插入算法、对称欧拉路径构造算法和二轴对称Stack生成算法.生成的Stack,不但关于X轴和Y轴对称,而且具有公共质心(common- centroid)的结构.还描述了模块合并算法,给出了计算最大合并距离的公式.该算法本质上是独立于任何拓扑表示的.实验结果验证了算法的有效性.In analog VLSI design, 2-dimensional symmetry stack and block merging are critical for mismatch minimization and parasitic control. Algorithms for analog VLSI 2-dimensional symmetry stack and block merging are described. Several theoretical results are obtained by studying symmetric Eulerian graph and symmetric Eulerian trail. Based on them, an O(n) algorithm for dummy transistor insertion, symmetric Eulerian trail construction and 2-dimensional symmetry stack construction is developed. The generated stacks are 2-dimensional symmetric and common-centroid. A block merging algorithm is described, which is essentially independent of the topological representation. Formula for calculating the maximum block merging distance is given. Experimental results show the effectiveness of the algorithms.

关 键 词：模拟集成电路 二维Stack 模块合并 对称欧拉路径 

分 类 号：TP302[自动化与计算机技术—计算机系统结构]