More Web Proxy on the site http://driver.im/

Article

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

Authors:

D. F. WongAuthors Info & Claims

ASP-DAC '01: Proceedings of the 2001 Asia and South Pacific Design Automation Conference

Pages 521 - 526

https://doi.org/10.1145/370155.370523

Published: 30 January 2001 Publication History

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.

References

[1]

Semiconductor Industry Association. National Technology Roadmap for Semiconductors, 1997.

[2]

N. Sherwani. Algorithms for VLSI Physical Design Automation, Kluwer Academic Publishers, Boston, 1995.

Digital Library

[3]

M. Sarrafzadeh and C.K. Wong. An Introduction to VLSI Physical Design, McGraw Hill, 1996.

Digital Library

[4]

J. Parkhurst, N. Sherwani, S. Maturi, D. Ahrams, and E. Chiprout. "SRC physical design top ten problems", ISPD- 99, pp. 55-58, 1999.

Digital Library

[5]

H. Murata, K. Fujiyoshi, S. Nakatake, and Y. Kajitani. "VLSI module placement based on rectangle-packing by the sequence pair", IEEE Transaction on Computer Aided Design of Integrated Circuits and Systems, vol. 15:12, pp. 1518- 1524, 1996.

Digital Library

[6]

H. Murata, K. Fujiyoshi, and M. Kaneko. "VLSI/PCB placement with obstacles based on sequence pair", ISPD-97, pp. 26-31, 1997.

Digital Library

[7]

H. Murata, and E.S. Kuh. "Sequence-pair based placement method for hard/soft/pre-placed modules", ISPD-98, pp. 167-172, 1998.

Digital Library

[8]

J. Xu, P.N. Guo, and C.K. Cheng. "Rectilinear block placement using sequence pair", ISPD-98, pp. 173-178, 1998.

Digital Library

[9]

M. Kang, and W.W.M. Dai. "Topology constrained rectilinear block packing for layout reuse", ISPD-98, pp. 179-186, 1998.

Digital Library

[10]

K. Fujiyoshi, and H. Murata. "Arbitrary convex and concave rectilinear block packing using sequence pair", ISPD-99, pp. 103-110, 1999.

Digital Library

[11]

F. Balasa, and K. Lampaert, "Module placement for analog layout using the sequence pair representation", DAC-99, pp. 274-279, 1999.

Digital Library

[12]

P.N. Guo, C.K. Cheng, and T. Yoshimura, "An O-tree representation of non-slicing oorplans and its applications", DAC-99, pp. 268-273, 1999.

Digital Library

[13]

Y. Pang, C.K. Cheng, and T. Yoshimura, "An enhanced perturbing algorithm for oorplan design using the O-tree representation", ISPD-2000, pp. 168-173, 2000.

Digital Library

[14]

Y.C. Chang, Y.W. Chang, G.M. Wu, and S.W. Wu. " B*- trees: a new representation for non-slicing oorplans", DAC- 2000, pp. 458-463, 2000.

Digital Library

[15]

T. Takahashi. "An algorithm for finding a maximum-weight decreasing sequence in a permutation, motivated by rectangle packing problem ", Technical Report of IEICE, VLD96, vol. VLD96, No. 201, pp. 31-35, 1996.

[16]

X. Tang, R. Tian, and D.F. Wong. "Fast evaluation of sequence pair in block placement by longest common subsequence computation", DATE-2000, pp. 106-111, 2000.

Digital Library

[17]

P. Van Emde Boas, R. Kaas, and Z. Zijlstra. "Design and implementation of an efficient priority queue", Mathematical Systems Theory 10, pp. 99-127, 1977.

[18]

D.B. Johnson. "A priority queue in which initialization and queue operations take O(log log D) time", Mathematical Systems Theory 15, pp. 295-309, 1982.

[19]

Y.W. Chang. Personal communication.

Cited By

Yu SDu SYang C(2024)A Deep Reinforcement Learning Floorplanning Algorithm Based on Sequence PairsApplied Sciences10.3390/app1407290514:7(2905)Online publication date: 29-Mar-2024
https://doi.org/10.3390/app14072905
Kahng AVaradarajan RWang Z(2024) Hier-RTLMP : A Hierarchical Automatic Macro Placer for Large-Scale Complex IP Blocks IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2023.334628443:5(1552-1565)Online publication date: May-2024
https://doi.org/10.1109/TCAD.2023.3346284
Tolman EBeatty CKohli MAbbott JBybee SFrandsen PStephen Gosnell JGuralnick RKalkman VNewton LSuvorov AWare J(2024)A molecular phylogeny of the Petaluridae (Odonata: Anisoptera): A 160-Million-Year-Old story of drift and extinctionMolecular Phylogenetics and Evolution10.1016/j.ympev.2024.108185200(108185)Online publication date: Nov-2024
https://doi.org/10.1016/j.ympev.2024.108185
Show More Cited By

Index Terms

FAST-SP: a fast algorithm for block placement based on sequence pair
1. Applied computing
  1. Physical sciences and engineering
    1. Electronics
2. Hardware
  1. Emerging technologies
  2. Very large scale integration design

Recommendations

Fast floorplanning by look-ahead enabled recursive bipartitioning

A new paradigm is introduced for floorplanning any combination of fixed-shape and variable-shape blocks under tight fixed-outline area constraints and a wirelength objective. Dramatic improvement over traditional floorplanning methods is achieved by the ...
Modern floorplanning based on fast simulated annealing
ISPD '05: Proceedings of the 2005 international symposium on Physical design

Unlike classical floorplanning that usually handles only block packing to minimize silicon area, modern VLSI floorplanning typically needs to pack blocks within a fixed die (outline) and additionally considers the packing with block positions and ...
Modern floorplanning based on B^*-tree and fast simulated annealing

Unlike classical floorplanning that usually handles only block packing to minimize silicon area, modern very large scale integration (VLSI) floorplanning typically needs to pack blocks within a fixed die (outline), and additionally considers the packing ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ASP-DAC '01: Proceedings of the 2001 Asia and South Pacific Design Automation Conference

January 2001

662 pages

ISBN:0780366344

DOI:10.1145/370155

Chairman:
Satoshi Goto
NEC Corp., Kawasaki, Japan

Copyright © 2001 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

IEICE: Inst of Electronics, Info & Communication Engineers
IPSJ: Information Processing Society of Japan
SIGDA: ACM Special Interest Group on Design Automation
IEEE HK CAS: IEEE HK CAS and Comm. Joint Chapter

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 30 January 2001

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

ASP-DAC01

Sponsor:

IEICE
IPSJ
SIGDA
IEEE HK CAS

ASP-DAC01: Asia and South Pacific Design Automation Conference 2001

Yokohama, Japan

Acceptance Rates

Overall Acceptance Rate 466 of 1,454 submissions, 32%

Upcoming Conference

ASPDAC '25

Sponsor:
sigda

30th Asia and South Pacific Design Automation Conference

January 20 - 23, 2025

Tokyo , Japan

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

105
Total Citations
View Citations
727
Total Downloads

Downloads (Last 12 months)43
Downloads (Last 6 weeks)5

Reflects downloads up to 18 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Yu SDu SYang C(2024)A Deep Reinforcement Learning Floorplanning Algorithm Based on Sequence PairsApplied Sciences10.3390/app1407290514:7(2905)Online publication date: 29-Mar-2024
https://doi.org/10.3390/app14072905
Kahng AVaradarajan RWang Z(2024) Hier-RTLMP : A Hierarchical Automatic Macro Placer for Large-Scale Complex IP Blocks IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2023.334628443:5(1552-1565)Online publication date: May-2024
https://doi.org/10.1109/TCAD.2023.3346284
Tolman EBeatty CKohli MAbbott JBybee SFrandsen PStephen Gosnell JGuralnick RKalkman VNewton LSuvorov AWare J(2024)A molecular phylogeny of the Petaluridae (Odonata: Anisoptera): A 160-Million-Year-Old story of drift and extinctionMolecular Phylogenetics and Evolution10.1016/j.ympev.2024.108185200(108185)Online publication date: Nov-2024
https://doi.org/10.1016/j.ympev.2024.108185
Yu SDu S(2024)VLSI Floorplanning Algorithm Based on Reinforcement Learning with ObstaclesBiologically Inspired Cognitive Architectures 202310.1007/978-3-031-50381-8_110(1034-1043)Online publication date: 14-Feb-2024
https://doi.org/10.1007/978-3-031-50381-8_110
Lin JTsai TTsai T(2023)Multilevel Fixed-Outline Component Placement and Graph-Based Ball Assignment for System in PackageIEEE Transactions on Very Large Scale Integration (VLSI) Systems10.1109/TVLSI.2023.329138131:9(1308-1319)Online publication date: Sep-2023
https://doi.org/10.1109/TVLSI.2023.3291381
Lin JTsai TShen R(2023)Routability-Driven Orientation-Aware Analytical Placement for System in Package2023 IEEE/ACM International Conference on Computer Aided Design (ICCAD)10.1109/ICCAD57390.2023.10323927(1-8)Online publication date: 28-Oct-2023
https://doi.org/10.1109/ICCAD57390.2023.10323927
Kahng AVaradarajan RWang ZBehjat LYang S(2022)RTL-MPProceedings of the 2022 International Symposium on Physical Design10.1145/3505170.3506731(3-11)Online publication date: 13-Apr-2022
https://dl.acm.org/doi/10.1145/3505170.3506731
He ZMa YZhang LLiao PWong NYu BWong M(2020)Learn to Floorplan through Acquisition of Effective Local Search Heuristics2020 IEEE 38th International Conference on Computer Design (ICCD)10.1109/ICCD50377.2020.00061(324-331)Online publication date: Oct-2020
https://doi.org/10.1109/ICCD50377.2020.00061
Lakhani JKhunteta AChowdhary AHarwani D(2020)Multiple Sequence Alignment Algorithm Using Adaptive Evolutionary ClusteringAdvances in Information Communication Technology and Computing10.1007/978-981-15-5421-6_36(349-364)Online publication date: 19-Aug-2020
https://doi.org/10.1007/978-981-15-5421-6_36
Singh AJain L(2018)VLSI Floorplanning Using Entropy Based Intelligent Genetic AlgorithmComputing, Analytics and Networks10.1007/978-981-13-0755-3_5(53-71)Online publication date: 7-Jul-2018
https://doi.org/10.1007/978-981-13-0755-3_5
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents