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

刘锐; 董社勤; 洪先龙; 龙迪; 顾钧

引用本文:	刘锐,董社勤,洪先龙,龙迪,顾钧.模拟集成电路二维Stack生成及模块合并算法.软件学报,2004,15(5):641-649

【打印本页】【下载PDF全文】【查看/发表评论】【EndNote】【RefMan】【BibTex】

←前一篇|后一篇→

过刊浏览高级检索

本文已被：浏览 5336次下载 5892次	码上扫一扫！
分享到：微信更多字体:加大+\|默认\|缩小-
模拟集成电路二维Stack生成及模块合并算法
刘锐^1,2, 董社勤², 洪先龙², 龙迪², 顾钧³
1.中国科学院,软件研究所,北京,100080;2.清华大学,计算机科学与技术系,北京,100084;3.香港科技大学,计算机系,香港

摘要:

在模拟集成电路设计中,关于X轴和y轴同时对称的Stack,以及模块之间的合并,对于增加器件之间的匹配和控制寄生是至关重要的.描述了模拟集成电路二轴对称Stack生成算法和模块合并算法.通过对于对称欧拉图和对称欧拉路径的研究,得出了多项理论结果.在此基础上,提出了时间复杂度为O(n)的伪器件插入算法、对称欧拉路径构造算法和二轴对称Stack生成算法.生成的Stack,不但关于X轴和y轴对称,而且具有公共质心(commoncentroid)的结构.还描述了模块合并算法,给出了计算最大合并距离的公式.该算法本质上是独立于任何拓扑表示的.实验结果验证了算法的有效性.

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

DOI：

分类号:

基金项目:Supported by the National Nature Science Foundation of China under Grant Nos.90307005 and 60121120706(国家自然科学基金); the National Nature Science Foundation of China and Research Grants Council of Hong Kong joint Project under Grant No.60218004(国家自然基金与香港研究资助局联合资助)；the National Natural Science Foundation of USA (NSF) under Grant No. CCR-0096383 (美国国家自然科学基金)；the National High-Tech Research and Development Plan of China under Grant No.2002AA1Z1460 (国家高技术研究发展计划(863))

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

LIU Rui,DONG She-Qin,HONG Xian-Long,LONG Di,GU Jun

Abstract:

In analog VLSI design, 2-dimensional symmetry stack and block merging are critical for mismatch minimization and parasitic control. In this paper, 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 Eepresentation. Formula for calculating the maximum block merging distance is given. Experimental results show the effectiveness of the algorithms.

Key words: analog VLSI 2-dimensional stack block merging symmetric Eulerian graph