An Efficient Hierarchical Tree Partitioning Method for VLSI Design

Recently,a circuit complexity of VLSIs,especially SOCs(Systm-on-a-chip),has been increased more and more due to the requirements of high performance and various functions,and their layout design has become a great di cult task. So that,circuit partitioning is indispensable to an e cient and superior system design,where the whole circuit is partitioned into sub-circuits of a reasonable size. Circuit partitioning is reduced to a graph partitioning problem. But the problem is known as an NP-complete problem,even if two-way partitioning of a graph with unity node-size and edge-weight.So,we propose a hier- archical tree partitioning method,where two greedy algorithms are executed in some probability. Experimental results show that the proposed method can e ciently make a good circuit partition,and it is very useful for a VLSI design.

Cricuit Partitioning

Graph partitioning

Greedy Algorithm

Hierarchical Tree Partitioning