An Efficient Hierarchical Tree Partitioning Method for VLSI Design

大規模システムの効率的な階層木分割手法

An Efficient Hierarchical Tree Partitioning Method for VLSI Design

Creators Tokumoto Morihiko

Creators Watanabe Takahiro

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.

[ISSN]1345-5583

[NCID]AA11422756

[isVersionOf] [URI]http://memoirs.lib-e.yamaguchi-u.ac.jp/