The week's pick
Reseach Article
An Interconnectivity based Efficient Partitioning Algorithm of Combinational CMOS Circuits
| 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.
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
- C. J. Alpert and A. B. Kahng, "Recent directions in netlist partitioning: A survey," VLSI J. Integr. , vol. 19, pp. 1–81, 1995.
- 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.
- C. M. Fiduccia and R. M. Mattheyses, "A linear time heuristic for improving network partitions," in Proc. ACM/IEEE DAC, 1982, pp. 175–181.
- 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.
- C. J. Alpert, "The ISPD98 circuit benchmark suite," in Proc. ACM/IEEE ISPD, 1998, pp. 80–85.
- 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.
- G. Karypis and V. Kumar, "Multilevel k-way hypergraph partitioning," in Proc. ACM/IEEE DAC, 1999, pp. 343–348.
- 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.
- 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.
- 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.
- Y. Saab, "An effective multilevel algorithm for bisecting graphs and hypergraphs," IEEE Trans. Comput. , vol. 53, no. 6, pp. 641–652, Jun. 2004.
- B. Hu and M. Marek-Sadowska, "Fine granularity clustering for large scale placement problems", in Proc. ACM/IEEE ISPD, 2003, pp. 67–74.
- B. W. Kernighan, and S. Lin, "An Efficient Heuristic Procedure for Partitioning Graphs", The Bell Systems Technical Journal, 49/2 (1970), pp. 291-307.
- M. R. Garey and D. S. Johnson, Computers and Intractability, Freeman, San Fransisco, CA. 1979.
- L. A. Sanchis, "A Multiple- Way Network Partitioning", IEEE Transactions on Computer, vol. 38, No. 1, (1989), pp. 62-81.
- C. Reeves, "Modern Heuristic Techniques for Combinatorial Problems", John Wiley & Sons, Inc. , New York, 1983.
- 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
Keywords