基于Cell对称矩阵结构的电路划分方法

摘要：

电路划分是超大规模集成电路自动化设计中的一个关键的阶段,同时也是NP-hard组合优化问题.文中基于结点移动的Fiduccia-Mattheyses(FM)算法提出新的cell对称矩阵数据结构,实现一种电路划分方法.首先使用对称矩阵数据结构存储结点和线网信息,然后利用简单的加减运算代替划分过程中结点增益的计算,最后简化原始算法中复杂的判断与计算完成对电路的划分.实验结果表明,与原始FM算法相比,在保证得到等价划分结果的情况下,该方法显著简化了实现过程,并且保持了线性复杂度;对电路实例进行划分,平均切边优化效果达到95.89%.

关键词：电路划分、物理设计、FM算法、增益计算、cell对称矩阵、超大规模集成电路

所属期刊栏目：28

分类号：TP391.72(计算技术、计算机技术)

资助基金：国家自然科学基金重点项目61133007,61402505

在线出版日期：2016-06-21（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：836-840