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 contribution

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 (US)
Title of host publicationProceedings of the ASP-DAC 2001
Subtitle of host publicationAsia and South Pacific Design Automation Conference 2001
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages521-526
Number of pages6
ISBN (Electronic)0780366336
DOIs
StatePublished - Jan 1 2001
Externally publishedYes
EventAsia and South Pacific Design Automation Conference 2001, ASP-DAC 2001 - Yokohama, Japan
Duration: Jan 30 2001Feb 2 2001

Publication series

NameProceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC
Volume2001-January

Other

OtherAsia and South Pacific Design Automation Conference 2001, ASP-DAC 2001
CountryJapan
CityYokohama
Period1/30/012/2/01

Fingerprint

Cost functions

Keywords

  • Circuit optimization
  • Conductors
  • Cost function
  • Design automation
  • Integrated circuit interconnections
  • Integrated circuit technology
  • Runtime
  • Simulated annealing
  • Transistors
  • Very large scale integration

ASJC Scopus subject areas

  • Computer Science Applications
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering

Cite this

Tang, X., & Wong, D. F. (2001). FAST-SP: A fast algorithm for block placement based on sequence pair. In Proceedings of the ASP-DAC 2001: Asia and South Pacific Design Automation Conference 2001 (pp. 521-526). [913361] (Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC; Vol. 2001-January). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ASPDAC.2001.913361

FAST-SP : A fast algorithm for block placement based on sequence pair. / Tang, Xiaoping; Wong, D. F.

Proceedings of the ASP-DAC 2001: Asia and South Pacific Design Automation Conference 2001. Institute of Electrical and Electronics Engineers Inc., 2001. p. 521-526 913361 (Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC; Vol. 2001-January).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Tang, X & Wong, DF 2001, FAST-SP: A fast algorithm for block placement based on sequence pair. in Proceedings of the ASP-DAC 2001: Asia and South Pacific Design Automation Conference 2001., 913361, Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC, vol. 2001-January, Institute of Electrical and Electronics Engineers Inc., pp. 521-526, Asia and South Pacific Design Automation Conference 2001, ASP-DAC 2001, Yokohama, Japan, 1/30/01. https://doi.org/10.1109/ASPDAC.2001.913361
Tang X, Wong DF. FAST-SP: A fast algorithm for block placement based on sequence pair. In Proceedings of the ASP-DAC 2001: Asia and South Pacific Design Automation Conference 2001. Institute of Electrical and Electronics Engineers Inc. 2001. p. 521-526. 913361. (Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC). https://doi.org/10.1109/ASPDAC.2001.913361
Tang, Xiaoping ; Wong, D. F. / FAST-SP : A fast algorithm for block placement based on sequence pair. Proceedings of the ASP-DAC 2001: Asia and South Pacific Design Automation Conference 2001. Institute of Electrical and Electronics Engineers Inc., 2001. pp. 521-526 (Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC).
@inproceedings{353d87b9a5ae467295297d177994a640,
title = "FAST-SP: A fast algorithm for block placement based on sequence pair",
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.",
keywords = "Circuit optimization, Conductors, Cost function, Design automation, Integrated circuit interconnections, Integrated circuit technology, Runtime, Simulated annealing, Transistors, Very large scale integration",
author = "Xiaoping Tang and Wong, {D. F.}",
year = "2001",
month = "1",
day = "1",
doi = "10.1109/ASPDAC.2001.913361",
language = "English (US)",
series = "Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "521--526",
booktitle = "Proceedings of the ASP-DAC 2001",
address = "United States",

}

TY - GEN

T1 - FAST-SP

T2 - A fast algorithm for block placement based on sequence pair

AU - Tang, Xiaoping

AU - Wong, D. F.

PY - 2001/1/1

Y1 - 2001/1/1

N2 - 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.

AB - 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.

KW - Circuit optimization

KW - Conductors

KW - Cost function

KW - Design automation

KW - Integrated circuit interconnections

KW - Integrated circuit technology

KW - Runtime

KW - Simulated annealing

KW - Transistors

KW - Very large scale integration

UR - http://www.scopus.com/inward/record.url?scp=84949784966&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84949784966&partnerID=8YFLogxK

U2 - 10.1109/ASPDAC.2001.913361

DO - 10.1109/ASPDAC.2001.913361

M3 - Conference contribution

AN - SCOPUS:84949784966

T3 - Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC

SP - 521

EP - 526

BT - Proceedings of the ASP-DAC 2001

PB - Institute of Electrical and Electronics Engineers Inc.

ER -