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

作者：刘锐董社勤洪先龙龙迪顾钧

来源：软件学报, 2004, (05): 641-649.

• 模拟集成电路
• 二维Stack
• 模块合并
• 对称欧拉路径 analog VLSI
• 2-dimensional stack
• block merging
• symmetric Eulerian graph

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

• 单位
  中国科学院软件研究所; 香港科技大学