Article

Free access

Path-delay constrained floorplanning: a mathematical programming approach for initial placement

Authors:

S. Prasitjutrakul,

W. J. KubitzAuthors Info & Claims

DAC '89: Proceedings of the 26th ACM/IEEE Design Automation Conference

Pages 364 - 369

https://doi.org/10.1145/74382.74443

Published: 01 June 1989 Publication History

PDF eReader

Abstract

A procedure for path-delay constrained initial placement during chip floorplanning is presented which directly incorporates timing and geometrical constraints into the process. The problem is modeled and mathematically formulated as a constrained non-linear programming problem which is systematically divided and solved in three steps: timing minimization with module overlap, module separation and timing minimization without module overlap. To save computation time, two techniques for eliminating non-logical and noncritical paths are used to reduce the number of paths considered during the optimization. Experimental results show that the placement results satisfy all given timing and geometrical constraints, and have good total normalized wire delays.

References

[1]

Alon, A. and Ascher, U., "Model and Solution Strategy for Placement of Rectangular Blocks in the Euclidean Plane," IEEE Trans. on Computer-Aided Design, Vol.7 No.3 (1988), pp. 378-380.

Digital Library

Google Scholar

[2]

Berkcan, E~ and Kinnen, E., "Dim-REL: Performance Biased Placement Program for Custom IC Layout," Proc. Custom Integrated Circuit Conf. (lgs ), pp 2 3-2 8.

Google Scholar

[3]

Burstein, M. and Youssef, M., "Timing Influenced Layout Design," Proc. 22nd Design Automation Conf., IEEE, (1985), pp. 124-130.

Digital Library

Google Scholar

[4]

Dunlop, A.E., Ag~awal, V.D. and et.ul., "Chip Layout Optimization Using Critical Path Weighting," Pr0e. 21st Desig Automation conf., ZEEE, (1 ~s~), pp. 142-148.

Digital Library

Google Scholar

[5]

Dai, W., Chen, H., Dutta, R., Jackson, M. and et.al., "Bear: A New Building-Block Layout System," Proc. International Conf. on Computer- Aided Design (1987), pp. 34-37.

Google Scholar

[6]

Fiacco, A. and McCormick, G., Nonlinear Programming." Sequential Unconstrained Minimization Techniques, New York: Wiley, 1968.

Google Scholar

[7]

Hauge, P., N~ir, R. and Yoffa, E., "Circuit Placement for Predictable Performance," Proc. International Conj. on Computer-Aided Design (i sV, pp. ss-oi.

Google Scholar

[8]

Hsh, Y-C. and Kubitz, W., "A Procedure for Chip Floorplanning," Proc. International Syrup. on Circuits and Systems (1987}, pp. 568-571.

Google Scholar

[9]

JackSon, M., Kuh, E.S. and Marek-Sadowska, M., "Timing Driven Routing for Building Block Layout, pq Proc. International Syrup. on Circuits and Systems (i987), pp. 518-519.

Google Scholar

[10]

Ogawa, Y., Ishii, T. and et.al., "Efficient Placement Algorithms Optimization Delay for High Speed ECL Masterslice LSI's," Proc. 23rd Design Automation Conf., IEEE, (i986~, pp. 404-410.

Digital Library

Google Scholar

[11]

Peressini, A., Sullivan, F. and Uhl, J., The Mathematics of Nonlinear Programming, Springer-Srerlag New York Inc.

Digital Library

Google Scholar

[12]

Rose, M., Wiesel, M., Kirkpatrick, D. and Nettleton, N., "Dense, Performance Directed, Auto Place and Route." Proc. Custom Integrated Circuit Conf. (I988), pp 11.1.1 - 11.1.4.

Google Scholar

[13]

Shragowitz, E., Youssef, H. and Benning, L., "Predictive Tools in VLSI System Design : Timing Aspects," COMPEURO (1988), pp. 48-55.

Google Scholar

[14]

Weste, N. and Eshraghian, K., Principles of CMOS VLSI Design, A Systems Perspective, Addison-Wesley, 1985

Digital Library

Google Scholar

Cited By

View all

Chochaev RFrolova P(2022)Initial Placement Algorithms for Island-Style FPGAs2022 Conference of Russian Young Researchers in Electrical and Electronic Engineering (ElConRus)10.1109/ElConRus54750.2022.9755518(586-589)Online publication date: 25-Jan-2022
https://doi.org/10.1109/ElConRus54750.2022.9755518
Chatterjee DManikas T(2010)On-chip thermal optimisation by whitespace reallocation using a constrained particle-swarm optimisation algorithmIET Circuits, Devices & Systems10.1049/iet-cds.2009.00494:3(251)Online publication date: 2010
https://doi.org/10.1049/iet-cds.2009.0049
Luo CAnjos MVannelli A(2008)A nonlinear optimization methodology for VLSI fixed-outline floorplanningJournal of Combinatorial Optimization10.1007/s10878-008-9148-y16:4(378-401)Online publication date: 4-Apr-2008
https://doi.org/10.1007/s10878-008-9148-y
Show More Cited By

Index Terms

Path-delay constrained floorplanning: a mathematical programming approach for initial placement

Recommendations

Consistent placement of macro-blocks using floorplanning and standard-cell placement
ISPD '02: Proceedings of the 2002 international symposium on Physical design

While a number of recent works address large-scale standard-cell placement, they typically assume that all macros are fixed. Floorplanning techniques are very good at handling macros, but do not scale to hundreds of thousands of placeable objects. ...
Unification of vlsi placement and floorplanning
A timing-driven soft-macro placement and resynthesis method in interaction with chip floorplanning

In this paper, we present a complete chip design method which incorporates a soft-macro placement and resynthesis method in interaction with chip floorplanning for area and timing improvements. We present a performance-driven soft-macro clustering and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

DAC '89: Proceedings of the 26th ACM/IEEE Design Automation Conference

June 1989

839 pages

ISBN:0897913108

DOI:10.1145/74382

Chairman:
Donald E. Thomas
Carnegie Mellon Univ., Pittsburgh, PA

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 1989

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

DAC89

Sponsor:

IEEE-CS\TCDA
SIGDA

DAC89: The 26th ACM/IEEE-CS Design Automation Conference

June 25 - 28, 1989

Nevada, Las Vegas, USA

Acceptance Rates

DAC '89 Paper Acceptance Rate 156 of 465 submissions, 34%;

Overall Acceptance Rate 1,770 of 5,499 submissions, 32%

Upcoming Conference

DAC '25

Sponsor:
sigda

62nd ACM/IEEE Design Automation Conference

June 22 - 26, 2025

San Francisco , CA , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
237
Total Downloads

Downloads (Last 12 months)38
Downloads (Last 6 weeks)9

Reflects downloads up to 27 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Chochaev RFrolova P(2022)Initial Placement Algorithms for Island-Style FPGAs2022 Conference of Russian Young Researchers in Electrical and Electronic Engineering (ElConRus)10.1109/ElConRus54750.2022.9755518(586-589)Online publication date: 25-Jan-2022
https://doi.org/10.1109/ElConRus54750.2022.9755518
Chatterjee DManikas T(2010)On-chip thermal optimisation by whitespace reallocation using a constrained particle-swarm optimisation algorithmIET Circuits, Devices & Systems10.1049/iet-cds.2009.00494:3(251)Online publication date: 2010
https://doi.org/10.1049/iet-cds.2009.0049
Luo CAnjos MVannelli A(2008)A nonlinear optimization methodology for VLSI fixed-outline floorplanningJournal of Combinatorial Optimization10.1007/s10878-008-9148-y16:4(378-401)Online publication date: 4-Apr-2008
https://doi.org/10.1007/s10878-008-9148-y
Koide TWakabayashi S(1999)A timing-driven floorplanning algorithm with the Elmore delay model for building block layoutIntegration, the VLSI Journal10.1016/S0167-9260(98)00016-927:1(57-76)Online publication date: 1-Jan-1999
https://dl.acm.org/doi/10.1016/S0167-9260%2898%2900016-9
Shi JRandhar ABhatia D(1997)Macro Block Based FPGA FloorplanningProceedings of the Tenth International Conference on VLSI Design: VLSI in Multimedia Applications10.5555/523974.834913Online publication date: 4-Jan-1997
https://dl.acm.org/doi/10.5555/523974.834913
Shi JBhatia DEbeling C(1997)Performance driven floorplanning for FPGA based designsProceedings of the 1997 ACM fifth international symposium on Field-programmable gate arrays10.1145/258305.258321(112-118)Online publication date: 9-Feb-1997
https://dl.acm.org/doi/10.1145/258305.258321
Shi JRandhar ABhatia D(1997)Macro block based FPGA floorplanningProceedings Tenth International Conference on VLSI Design10.1109/ICVD.1997.567955(21-26)Online publication date: 1997
https://doi.org/10.1109/ICVD.1997.567955
Sait SYoussef HTanvir SBenten M(1995)Timing influenced general-cell genetic floorplannerProceedings of ASP-DAC'95/CHDL'95/VLSI'95 with EDA Technofair10.1109/ASPDAC.1995.486214(135-140)Online publication date: 1995
https://doi.org/10.1109/ASPDAC.1995.486214
Sutanthavibul SShragowitz ENewton A(1991)Dynamic prediction of critical paths and nets for constructive timing-driven placementProceedings of the 28th ACM/IEEE Design Automation Conference10.1145/127601.127165(632-635)Online publication date: 1-Jun-1991
https://dl.acm.org/doi/10.1145/127601.127165
Lin IDu DSmith R(1991)Performance-driven constructive placementProceedings of the 27th ACM/IEEE Design Automation Conference10.1145/123186.123235(103-106)Online publication date: 3-Jan-1991
https://dl.acm.org/doi/10.1145/123186.123235
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

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

Cited By

Index Terms

Recommendations

Consistent placement of macro-blocks using floorplanning and standard-cell placement

Unification of vlsi placement and floorplanning

A timing-driven soft-macro placement and resynthesis method in interaction with chip floorplanning