一种新的基于晶体管级的电路划分算法

薛冀颖; 孙楠; 张炜; 张文俊; 余志平

doi:10.3724/SP.J.1146.2009.00132

一种新的基于晶体管级的电路划分算法

doi: 10.3724/SP.J.1146.2009.00132

基金项目:

国家重点基础研究发展规划项目(2006CB302700)资助课题

计量
- 文章访问数: 3026
- HTML全文浏览量: 82
- PDF下载量: 729
- 被引次数: 0
出版历程
- 收稿日期: 2009-02-02
- 修回日期: 2009-07-13
- 刊出日期: 2009-12-19

A Novel Algorithm for Circuit Partitioning at Transistor Level

摘要

摘要: 随着VLSI电路规模的不断增加，为实现电路并行仿真所做的电路划分算法的质量显得日益重要。鉴于现有算法未能同时保证均衡的分块间规模和最少的互联信号数目，该文提出了一种新的基于晶体管级的电路划分算法。该算法首先通过一个聚合过程对电路网表进行分割，得到一个比较好的初始分割；然后通过平衡分块间规模差异和进一步优化分块间互连线的数目，最终得到理想的电路划分结果。应用该电路划分算法对工业界的实际电路网表进行测试，结果表明：相比于目前普遍使用的COPART算法，该算法在分块间规模的均衡性方面平均改善了25%，在分块间的互联信号数目方面平均减少了18%。
- 电路划分; 分块规模差异; 互联信号线
Abstract: As the size of VLSI circuits keeps growing, the quality of circuit partitioning for parallel simulation is becoming increasingly crucial. In view of the fact that the present algorithms cannot guarantee the size balance and minimize the cut-signals among partitions simultaneously, a novel algorithm for circuit partitioning at transistor level is presented. The proposed algorithm first conducts clustering procedure to obtain a good initial partition result, and then makes an adjustment procedure to achieve well-balanced partitions with fewer cut-signals. The excellent performance of the new algorithm is demonstrated on several industrial circuits. Compared with the COPART algorithm which is widely used, the size discrepancy among different partitions and the number of cut-signals obtained using the new algorithm decrease by 25% and 18% on average, respectively.

HTML全文

参考文献(1)

Kernighan B W and Lin S. An efficient heuristic procedurefor partitioning graphs. The Bell System Technical Journal,1970, 49(1): 291-307.[2]Schweikert D G and Kernighan B W. A proper model for thepartitioning of electrical circuits. Proc. of 9th ACM/IEEEDesign Automation Conf., New York, 1972: 57-62.[3]Fiduccia C M and Mattheyses R M. A linear-time heuristicfor improving network partitions. Proc. of 19th ACM/IEEEDesign Automation Conf., Piscataway, NJ, 1982: 175-181.[4]Krishnamurthy B. An improved min-cut algorithm forpartitioning VLSI networks[J].IEEE Transactions onComputers.1984, 33(5):438-446[5]Sanchis L A. Multiple-way network partitioning[J].IEEETransactions on Computers.1989, 38(1):62-81[6]Dasdan A and Aykanat C. Two novel multiway circuitpartitioning algorithms using relaxed locking[J].IEEETransactions on Computer-aided Design of IntegratedCircuits and Systems.1997, 16(2):169-178[7]Frohlich N, Glockel V, and Fleischmann J. A newpartitioning method for parallel simulation of VLSI circuitson transistor level. Proc. of Design, Automation and Test inEurope Conference and Exhibition, Paris, 2000: 679-684.[8]Li J and Behjat L. Net cluster: A net-reduction-basedclustering preprocessing algorithm for partitioning andplacement[J].IEEE Transactions on Computer-Aided Design ofIntegrated Circuits and Systems.2007, 26(4):669-679[9]Bazylevych R, Podolskyy I, and Bazylevych L. Partitioningoptimization by recursive moves of hierarchically builtclusters. Proc. of Design and Diagnostics of ElectronicCircuits and Systems, Krakow, 2007: 1-4.Behjat L, Li J, and Huang J. Two clustering preprocessingtechniques for large-scale circuits. Proc. of Circuits andSystems, New Orleans, 2007: 1057-1060.[10]Leinweber L and Bhunia S. Fine-grained supply gatingthrough hypergraph partitioning and shannon decompositionfor active power reduction. Proc. of Design, Automation andTest in Europe, Munich, 2008: 373-378.Shan Y and Lin B. Application-specific Network-on-Chiparchitecture synthesis based on set partitions and SteinerTrees. Proc. of Design Automation Conference, SamFrancisco, 2008: 277-282.

施引文献

资源附件(0)

访问统计