정련법을 이용한 하이퍼그래프 분할
Hypergraph Partitioning By Using Reodered Simulated-anealing
1
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
In this paper we present a reodered simulated-anealing algorithm which is capable of applying odering based k-way partitioned clusters. This method is used for improvement of the objectives of partitioning which are k-way partitioned by using odering algorithm. It changes the positions of the clusters and the vertices in each clusters. Reodered vertices are splitted by using DP-RP method and this process has an opportunity to improve the objective functions. This algorithm has advantages to improve the quality of the solutions for various purposes. Experimental results on several graphs demonstrate that proposed algorithm provides substantial enhancement.
Abstract
In this paper we present a reodered simulated-anealing algorithm which is capable of applying odering based k-way partitioned clusters. This method is used for improvement of the objectives of partitioning which are k-way partitioned by using odering algorithm. It changes the positions of the clusters and the vertices in each clusters. Reodered vertices are splitted by using DP-RP method and this process has an opportunity to improve the objective functions. This algorithm has advantages to improve the quality of the solutions for various purposes. Experimental results on several graphs demonstrate that proposed algorithm provides substantial enhancement.
참고문헌 (16)
- S. Dutt, "Probability-Based Approaches to VLSI Curcuit Partitioning", IEEE Trans. CAD, 19(5), pp.534~549 (2000)
- H. Nagamochi, "Computing Edge-Connectivity in Multigraphs and Capacitated Graphs", Siam Journal of Discrete Mathematics, 5(1), pp.54~66 (1992)
- C. J. Alpert, "A General Framework for Vertex Orderings, With Application to Circuit Clustering", IEEE Transactions on VLSI Systems, 4(2), pp.240~246 (1996)
- C. J. Alpert, "Multi-Way Partitioning Via Space-filling Curves and Dynamic Programming", Proc. of the ACM, 1994, 652~657
- C. J. Alpert., "Multi-way Graph and Hypergraph Partitioning", 박사, Dep’t of Computer Science, pp.1996
- Y. C. Wei, "Towards Efficient Hierarchical Designs by Ratio Cut Partitioning", Proc. of the IEEE, 1989, 298~301
- P. K. Chan, "Spectral K-way Ratio-Cut Partitioning and Clustering", IEEE Transactions on Computer- Aided Design, 13(8), pp.1088~1096 (1994)
- C. W. Yeh, "A Probabilistic Multi-Commodity Flow Solution to Circuit Clustering Problems", Proc. of the IEEE, 1992, 428~431
- W. Son, "Efficient and Effective Placements for Very Large Circuits", Proc. of the IEEE, 1993, 170~177
- J. Cong, "Net Partitions Yield Better Module Partitions", Proc. of the ACM, 1992, 47~52
- D. J. H. Huang, "When Clusters Meet Partitions: New Density-Based Methods for Circuit Decomposition", Proc. European Design and Test Conf., pp.60~64 (1995)
- R. Rajaraman, "Optimal clustering for delay minimization", Proc. of the ACM, 1993, 309~314
- N. Selvakkumaran, "Multi-Objective Hypergraph Partitioning Algorithms for Cut and Maximum Subdomain Degree Minimization", IEEE Transactions on CAD, 25(3), pp.504~517 (2006)
- 김재진, "제한조건을 고려한 효율적 회로 설계 알고리즘", (사)디지털산업정보학회 논문지, 8(1), pp.41~46 (2012), (사)디지털산업정보학회
- S. J. Kim, "Reordering Algorighm for Hypergraph Partitioning", 박사, pp.2000
- 최현준, "FPGA를 이용한 디지털 계측 시스템의 설계 및 구현", (사)디지털산업정보학회 논문지, 9(2), pp.55~61 (2013), (사)디지털산업정보학회