NAP: A Nonlinear Analytical Hypergraph Partitioning Method

ABSTRACT

Hypergraph partitioning is commonly used in solving very large scale integration (VLSI) placement problem, data mining, sparse matrix multiplication, and parallel computing. This paper presents a novel heuristic for hypergraph partitioning based on nonlinear programming. In our approach we consider adjacent one-dimensional bins. Since the reduction of cuts is equivalent to reducing the net length across the two bins, the vertices are moved across the bins in such a way that the density of vertices in each bin is balanced as per the partitioning requirement and reduction in the wirelength. For the Walshaw partitioning benchmarks, our tool NAPs’ results are consistently comparable to that obtained by Chaco. Our tool NAP produces better cuts than Chaco on 22 instances out of 29 graph samples.

KEYWORDS:

• Analytical technique
• Graph partitioning
• Nonlinear optimization
• Placement

ACKNOWLEDGEMENTS

The authors would like to thank the Centre for Advanced Computing Laboratory at IIT Guwahati for providing the resources to carry out this research.

DISCLOSURE STATEMENT

No potential conflict of interest was reported by the authors.

Notes

1. We have used analytical technique from our previous work [41].

2. We have used analytical flow from our previous work [41].

Additional information

Notes on contributors

Sameer Pawanekar

Sameer Pawanekar did his Bachelor of Engineering in electronics from Bhilai Institute of Technology, Durg, and Master of Technology from Indian Institute of Technology Bombay, India. He has worked with various companies like IBM, QuickLogic, SoftJin, and LSI Logic as Software Engineer in Bangalore. Currently he is working with Sicon Design Technologies in Bangalore as Lead Engineer in SoC Verification. Along with his job, he is also pursuing PhD from Indian Institute of Technology, Guwahati. His research interests include SoC verification and CAD tool development for physical design.

E-mail: [email protected]

Kalpesh Kapoor

Kalpesh Kapoor is an associate professor in the Department of Mathematics at Indian Institute of Technology Guwahati, India. He completed his Ph.D. in the area of software testing in 2004 from London South Bank University, UK. He received his B.Sc. degree (Mathematics Honours) from Banaras Hindu University, Varanasi, India. He did his Master of Science (applied statistics and informatics) and Master of Technology (computer science) from Indian Institute of Technology Bombay, India. He has also worked as a senior software engineer for one and half years. Kalpesh's research interests are in the area of combinatorics, algorithms, and programming.

E-mail: [email protected]

Gaurav Trivedi

Gaurav Trivedi is an assistant professor in the Department of Electronics and Electrical Engineering at Indian Institute of Technology Guwahati, India. He completed his Ph.D. in the area of VLSI CAD in 2007 from Indian Institute of Technology Bombay, India. He received his Bachelor of Engineering in electronics from Devi Ahilya Vishwavidyalaya (University), Indore, India, in 1998 and his Master of Technology (microelectronics) degree from Indian Institute of Technology Bombay, India in 2000. He has also worked as senior member of technical staff with Cadence Design Systems and Berkeley Design Automation for three years. He joined Indian Institute of Technology Bombay, India, in 2009 as a post-doctoral fellow for two years. Gaurav's research interests are in the area of VLSI CAD, semiconductor devices, digital circuit designing, high-performance computing, computational biology, solar photovoltaics, algorithms and programming.

E-mail: [email protected]