NAP: A Nonlinear Analytical Hypergraph Partitioning Method
| Autor: | Gaurav Trivedi, Kalpesh Kapoor, Sameer Pawanekar |
|---|---|
| Rok vydání: | 2016 |
| Předmět: |
Very-large-scale integration
Hypergraph Mathematical optimization Heuristic (computer science) Graph partition 020206 networking & telecommunications 02 engineering and technology Bin 020202 computer hardware & architecture Computer Science Applications Theoretical Computer Science Nonlinear programming Reduction (complexity) 0202 electrical engineering electronic engineering information engineering Graph (abstract data type) Electrical and Electronic Engineering Algorithm Mathematics |
| Zdroj: | IETE Journal of Research. 63:60-70 |
| ISSN: | 0974-780X 0377-2063 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|