FAST-SP: a fast algorithm for block placement based on sequence pair

Xiaoping Tang, D. F. Wong

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-review

147 Citations (Scopus)

Abstract

In this paper we present FAST-SP which is a fast block placement algorithm based on the sequence-pair placement representation. FAST-SP has two significant improvements over previous sequence-pair based placement algorithms: 1) FAST-SP translates each sequence pair to its corresponding block placement in O(n log log n) time based on a fast longest common subsequence computation. This is much faster than the traditional O(n2) method by first constructing horizontal and vertical constraint graphs and then performing longest path computations. As a result, FAST-SP can examine more sequence pairs and obtain a better placement solution in less runtime. 2) FAST-SP can handle placement constraints such as pre-placed constraint, range constraint, and boundary constraint. No previous sequence-pair based algorithms can handle range constraint and boundary constraint. Fast evaluation in O(n log log n) time is still valid in the presence of placement constraints and a novel cost function which unifies the evaluation of feasible and infeasible sequence pairs is used. We have implemented FAST-SP and obtained excellent experimental results. For all MCNC benchmark block placement problems, we have obtained the best results ever reported in the literature (including those reported by algorithms based on O-tree and B*-tree) with significantly less runtime. For example, the best known result for ami49 (36.8 mm2) was obtained by a B*-tree based algorithm using 4752 seconds, and FAST-SP obtained a better result (36.5 mm2) in 31 seconds.

Original languageEnglish
Title of host publicationProceedings of the 6th Asia and South Pacific Design Automation Conference, ASP-DAC 2001
Place of PublicationUnited States
PublisherAssociation for Computing Machinery (ACM)
Pages521-526
Number of pages6
ISBN (Electronic)0780366344
ISBN (Print)9780780366343, 0780366336
DOIs
Publication statusPublished - Jan 2001
Event6th Asia and South Pacific Design Automation Conference, ASP-DAC 2001 - Conference Center, Pacifico Yokohama, Yokohama, Japan
Duration: 30 Jan 20012 Feb 2001
https://www.aspdac.com/2001/ (Conference website )
https://www.aspdac.com/2001/eng/ap/techprg2001.pdf (Conference program)
https://dl.acm.org/doi/proceedings/10.1145/370155 (Conference proceedings)

Publication series

NameProceedings of The Asia and South Pacific Design Automation Conference, ASP-DAC
ISSN (Print)2153-6961
ISSN (Electronic)2153-697X

Conference

Conference6th Asia and South Pacific Design Automation Conference, ASP-DAC 2001
Country/TerritoryJapan
CityYokohama
Period30/01/012/02/01
Internet address

Fingerprint

Dive into the research topics of 'FAST-SP: a fast algorithm for block placement based on sequence pair'. Together they form a unique fingerprint.

Cite this