VLSI电路划分算法综述  

A survey of VLSI circuit partitioning algorithms

作　　者：朱文兴[1] 陈家瑞[1] 

机构地区：[1]福州大学离散数学研究中心,福建福州350108

出　　处：《福州大学学报（自然科学版）》2011年第5期622-630,共9页Journal of Fuzhou University(Natural Science Edition)

基　　金：国家自然科学基金资助项目(61070020);教育部高校博士点专项科研基金资助项目(20093514110004)

摘　　要：电路划分作为VLSI物理设计中的一个关键阶段,其划分的结果直接影响后续的布图规划、布局、布线等过程.电路划分把由逻辑门或标准单元组成的电路分成多个子集,以降低VLSI设计的复杂性,其通常要求每个子集所包含的元件数目平衡,目标一般是这些子集之间的线网连接数达到最小.电路划分本质上属于图/超图划分,是NP-hard问题.根据近年来划分算法的研究进展,对划分算法进行了研究与综述,主要包括:基于移动的迭代改进方法、计算智能、基于聚类的多级方法、近似算法、多目标优化方法等.最后对全文进行总结,并展望了进一步的研究方向.Circuit partitioning is a very important stage during very large-scale integrated circuits（VLSI） physical design.The quality of circuit partitioning directly affects the sequent floorplanning,placement,routing,etc.The essence of circuit partitioning is to divide the circuit consisting of logic gates or standard cells into subsets.It aims to reduce the VLSI design complexity.The objective of circuit partitioning is to minimize the number of inter-connection of subsets,such that the number of cells in each subsets are roughly equal.It can be modeled as a graph/hypergraph partitioning problem,which is known to be NP-hard.The problem has been great concern in recent years,and a number of algorithms have been proposed.This paper reviews the partitioning algorithms,mainly including： move-based iterative improvement methods,computational intelligence,multilevel methods based on clustering,approximation algorithms,multi-objective optimization methods.Finally,the points are summarized,moreover,some issues for further research are addressed.

关 键 词：VLSI 电路 划分 图 超图 多级方法 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]