基于概率增益的电路划分算法

胡云; 王伶俐; 唐璞山; 童家榕

doi:10.3724/SP.J.1146.2006.00377

基于概率增益的电路划分算法

doi: 10.3724/SP.J.1146.2006.00377

基金项目:

国家自然科学基金(60676020)，上海应用材料科技合作共同计划项目(AM0406)和复旦大学青年科学基金(JKH1203001)资助课题

计量
- 文章访问数: 2778
- HTML全文浏览量: 75
- PDF下载量: 1008
- 被引次数: 0
出版历程
- 收稿日期: 2006-03-28
- 修回日期: 2006-08-25
- 刊出日期: 2007-11-19

A Circuit Partition Algorithm Basing on Probability Gain

摘要

摘要: 该文提出了一种新的划分算法，算法中引入可变线网权重。由于超图(hypergraph)中的线网连接节点数一般多于两个，为了充分将线网增加的权重作用到与该线网相连的所有节点上去，线网增益采用了概率增益模型。该算法与原有算法相比较，可以有效地让电路的划分跳出局部最小，结果有较大的改进，特别是当电路规模比较大的时候，改进更明显。由于采用概率增益模型，出现浮点数，节点增益的存储采用了平衡二叉树(balanced binary tree)，因此算法的速度相对于FM算法有所下降，但是时间复杂度仍然接近为线性复杂度，时间复杂度为O(P log2(n))(P为电路所有逻辑单元的引脚数之和，n为电路的逻辑单元数)。
- 电路划分;最小割;概率增益;NP-完全问题
Abstract: This paper proposes a new partition algorithm. The variable weight of the nets is introduced into the algorithm. Generally, the nodes connected to the nets are more than two in the hypergraph, so the probability gain model is used to enforce the effect of the increased weight of the nets. This algorithm can jump out of local minimal effectively when compared with original algorithm. The improvement is especially obvious for the large-scale circuits. For the gain value of the cell is floating-point, balanced binary tree is used to store the gain value of the cells, so the speed of this algorithm is several times slower than FM algorithm. The time complexity of this algorithm is O(P log2(n))(where P is the sum of the pins of all logic cells of the circuit, and n is the number of the circuit logic cells).

HTML全文

参考文献(1)

Kernighan B W and Lin S. An efficient heuristic procedure for partitioning graphs [J]. Bell System Tech. Journal, 1970, 49: 291-307.[2]Cong J, Labio W, and Shivakumar N. Multi-way VLSI circuit partitioning based on dual net representation [J].IEEE Trans on Computer-Aided Design of Integrated Circuits and Systems.1996, 15:396-409[3]Karypis G and Kumar V. Parallel multilevel k-way partitioning scheme for irregular graphs [A]. Proceedings of the 1996 ACM/IEEE Conference on Supercomputing, Pennsylvania, CA, 1996: 35-42.[4]Saab Youssef G. An effective multilevel algorithm for bisecting graphs and hypergraphs [J]. IEEE Transactions on Computers, 2004, 53: 641-652.[5]Wei Y C and Cheng C K. Towards efficient hierarchical designs by ratio cut partitioning [A]. IEEE/ACM International Conference on Computer Aided Design, Santa Clara, CA, 1989: 298-301.[6]Chan P, Schlag M, and Zien J. Spectral k-way ratio-cut partitioning and clustering [J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems.1994, 13:1088-1096[7]Fiduccia C M and Mattheyses R M. A linear time heuristic for improving network partitions [A]. Proceedings of the 19th Conference on Design Automation, Piscataway, CA, 1982: 175-181.[8]Alpert C J and Kahng A B. A general framework for vertex ordering with application to netlist clustering [J].IEEE Transactions on Very Large Scale Integration Systems.1996, 4:240-246[9]Dutt D and Deng W. VLSI circuit partitioning by cluster-removal using iterative improvement techniques [A]. IEEE/ACM International Conference on Computer-Aided Design, San Jose, CA, 1996: 194-200.[10]Eem C K and Chong J W. An efficient iterative improvement technique for VLSI circuit partitioning using hybrid bucket structures [A]. Proceedings of the ASP-DAC '99 on Design Automation Conference, Wanchai, HK, 1999, 1: 73-76.[11]Hagen L W, Huang D J H, and Kahng A B. On implementation choices for iterative improvement partitioning algorithms[A]. Proceedings of the Conference on European Design Automation, Brighton, UK, 1995: 144-149.[12]Alpert Arles J and Kahng Andrew B. Recent directions in netlist partitioning [J].Integration the VLSI Journal.1995, 19:1-81[13]Krishnamurthy B. An improved min-cut algorithm for partitioning VLSI networks [J].IEEE Trans. on Computer.1984, C-33:438-446[14]Schweikert D G and Kernighan B W. A proper model for the partitioning of electrical circuits[A]. Proceedings of the 9th Workshop on Design Automation, New York, CA, 1972: 57-62.

施引文献

资源附件(0)

访问统计