A New 2-way Multi-level Partitioning Algorithm. Issue 3 (2000)

• Record Type: Journal Article
• Authors: Saab, Youssef
• Is Part Of: VLSI design. Volume 11:Issue 3(2000)
• Page Start: 301
• Page End: 310
• Publication Date: 2000
• Subjects: Hypergraph partitioning -- Multi-level -- Clustering -- Contraction; Integrated circuits -- Very large scale integration -- Periodicals; 621.395
• DOI: 10.1155/2000/65821
• Languages: English
• ISSNs: 1065-514X

Abstract

Abstract : Partitioning is a fundamental problem in the design of VLSI circuits. In recent years, the multi-level partitioning approach has been used with success by a number of researchers. This paper describes a new multi-level partitioning algorithm (PART) that combines a blend of iterative improvement and clustering, biasing of node gains, and local uphill climbs. PART is competitive with recent state-of-the-art partitioning algorithms. PART was able to find new lower cuts for many benchmark circuits. Under suitably mild assumptions, PART also runs in linear time.