CFP last date
20 June 2024
Reseach Article

An Interconnectivity based Efficient Partitioning Algorithm of Combinational CMOS Circuits

Published on March 2013 by Milon Mahapatra, M. Malathi, B. Srinath
National Conference on VLSI and Embedded Systems
Foundation of Computer Science USA
NCVES - Number 1
March 2013
Authors: Milon Mahapatra, M. Malathi, B. Srinath
b03bcda8-65b6-4aba-8c93-a0b8298e4e33

Milon Mahapatra, M. Malathi, B. Srinath . An Interconnectivity based Efficient Partitioning Algorithm of Combinational CMOS Circuits. National Conference on VLSI and Embedded Systems. NCVES, 1 (March 2013), 18-21.

@article{
author = { Milon Mahapatra, M. Malathi, B. Srinath },
title = { An Interconnectivity based Efficient Partitioning Algorithm of Combinational CMOS Circuits },
journal = { National Conference on VLSI and Embedded Systems },
issue_date = { March 2013 },
volume = { NCVES },
number = { 1 },
month = { March },
year = { 2013 },
issn = 0975-8887,
pages = { 18-21 },
numpages = 4,
url = { /proceedings/ncves/number1/11308-1305/ },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Proceeding Article
%1 National Conference on VLSI and Embedded Systems
%A Milon Mahapatra
%A M. Malathi
%A B. Srinath
%T An Interconnectivity based Efficient Partitioning Algorithm of Combinational CMOS Circuits
%J National Conference on VLSI and Embedded Systems
%@ 0975-8887
%V NCVES
%N 1
%P 18-21
%D 2013
%I International Journal of Computer Applications
Abstract

In this new technology era, circuit partitioning is a fundamental problem in very large-scale integration (VLSI) physical design automation. In this brief, we present a new interconnection oriented clustering algorithm for combinational VLSI circuit partitioning. The proposed clustering method focuses on capturing clusters in a circuit, i. e. , the groups of cells that are highly interconnected in a VLSI circuit. Therefore, the proposed clustering method can reduce the size of large-scale partitioning problems without losing partitioning solution qualities. The performance of the proposed clustering algorithm is evaluated on a standard set of partitioning benchmarks—ISCAS85 benchmark suite. The experimental results show that the proposed algorithm yields results comparable to that of the rajaraman-wong optimum delay clustering approach with a faster execution time.

References
  1. C. J. Alpert and A. B. Kahng, "Recent directions in netlist partitioning: A survey," VLSI J. Integr. , vol. 19, pp. 1–81, 1995.
  2. S. Dutt and W. Deng, "Probability-based approaches to vlsi circuit partitioning," IEEE Trans. Comput. -Aided Des. Integr. Circuits, vol. 19, pp. 534–549, 2000.
  3. C. M. Fiduccia and R. M. Mattheyses, "A linear time heuristic for improving network partitions," in Proc. ACM/IEEE DAC, 1982, pp. 175–181.
  4. L. W. Hagen, D. J. Huang, and A. B. Kahng, "On implementation choices for iterative improvement partitioning methods," in Proc. Eur. DAC, 1995, pp. 144–149.
  5. C. J. Alpert, "The ISPD98 circuit benchmark suite," in Proc. ACM/IEEE ISPD, 1998, pp. 80–85.
  6. G. Karypis, R. Aggarwal, V. Kumar, and S. Shekhar, "Multilevel hypergraph partitioning: Application in VLSI domain," IEEE Trans. Very Large Scale Integr. (VLSI) Syst. , vol. 7, no. 1, pp. 69–79, Jan. 1999.
  7. G. Karypis and V. Kumar, "Multilevel k-way hypergraph partitioning," in Proc. ACM/IEEE DAC, 1999, pp. 343–348.
  8. C. J. Alpert, D. Huang, and A. B. Kahng, "Multilevel circuit partitioning," IEEE Trans. Comput. -Aided Des. Integr. Circuits, vol. 17, no. 8, pp. 655–667, Aug. 1998.
  9. A. E. Caldwell, A. B. Kahng, and I. L. Markov, "Improved algorithms for hypergraph bi-partitioning," in Proc. Asia South Pacific DAC, 2000, pp. 661–666.
  10. J. Cong and S. Lim, "Edge separability-based circuit clustering with application to multilevel circuit partitioning," IEEE Trans. Comput. -Aided Des. Integr. Circuits, vol. 23, no. 3, pp. 346–357, 2004.
  11. Y. Saab, "An effective multilevel algorithm for bisecting graphs and hypergraphs," IEEE Trans. Comput. , vol. 53, no. 6, pp. 641–652, Jun. 2004.
  12. B. Hu and M. Marek-Sadowska, "Fine granularity clustering for large scale placement problems", in Proc. ACM/IEEE ISPD, 2003, pp. 67–74.
  13. B. W. Kernighan, and S. Lin, "An Efficient Heuristic Procedure for Partitioning Graphs", The Bell Systems Technical Journal, 49/2 (1970), pp. 291-307.
  14. M. R. Garey and D. S. Johnson, Computers and Intractability, Freeman, San Fransisco, CA. 1979.
  15. L. A. Sanchis, "A Multiple- Way Network Partitioning", IEEE Transactions on Computer, vol. 38, No. 1, (1989), pp. 62-81.
  16. C. Reeves, "Modern Heuristic Techniques for Combinatorial Problems", John Wiley & Sons, Inc. , New York, 1983.
  17. Rajmohan Rajaraman and D. F. Wong, "Optimum clustering for delay minimization," IEEE Trans. on Comput. -Aided Des. Integr. Circuits, vol. 14 no. 12, December 1995.
Index Terms

Computer Science
Information Sciences

Keywords

Clustering Benchmark Algorithms Partitioning