An Efficient Hierarchical Tree Partitioning Method for VLSI Design
Memoirs of the Faculty of Engineering, Yamaguchi University Volume 52 Issue 1
Page 5-12
published_at 2001-10
Title
大規模システムの効率的な階層木分割手法
An Efficient Hierarchical Tree Partitioning Method for VLSI Design
Creators
Tokumoto Morihiko
Creators
Watanabe Takahiro
Source Identifiers
Creator Keywords
Cricuit Partitioning
Graph partitioning
Greedy Algorithm
Hierarchical Tree Partitioning
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.
Languages
jpn
Resource Type
departmental bulletin paper
Publishers
山口大学工学部
Date Issued
2001-10
File Version
Version of Record
Access Rights
open access
Relations
[ISSN]1345-5583
[NCID]AA11422756
[isVersionOf]
[URI]http://memoirs.lib-e.yamaguchi-u.ac.jp/
Schools
工学部