A New 2-way Multi-level Partitioning Algorithm

VLSI Design. 2000;11(3):301-310 DOI 10.1155/2000/65821

 

Journal Homepage

Journal Title: VLSI Design

ISSN: 1065-514X (Print); 1563-5171 (Online)

Publisher: Hindawi Publishing Corporation

LCC Subject Category: Science: Mathematics: Instruments and machines: Electronic computers. Computer science

Country of publisher: Egypt

Language of fulltext: English

Full-text formats available: PDF, HTML, ePUB

 

AUTHORS

Youssef Saab (Computer Engineering and Computer Science Department, University of Missouri-Columbia, Engineering Building West, Columbia 65211, MO, USA)

EDITORIAL INFORMATION

Blind peer review

Editorial Board

Instructions for authors

Time From Submission to Publication: 19 weeks

 

Abstract | Full Text

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.