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

Article

Free access

On the relative placement and the transportation problem for standard-cell layout

Authors:

Jürgen M. Kleinhans,

Frank M. JohannesAuthors Info & Claims

DAC '86: Proceedings of the 23rd ACM/IEEE Design Automation Conference

Pages 308 - 313

Published: 02 July 1986 Publication History

Abstract

A new two-phased method for the simultaneous placement of modules for standard-cell layout is presented. In phase one, a relative placement is calculated by application of an iterative solution method taking advantage of net-list scarcity. A fast algorithm is derived from a new formulation of the problem. In addition, signal weights and pin coordinates are considered. In phase two, different-sized modules are assigned to physical locations by solving a transportation problem.

References

[1]

Blanks, J.P.,Near-Optimal Placement Using a Quadratic Objective Function, 22nd Design Automation Conference, pp. 609-615, 1985.

Digital Library

[2]

Breuer, M.A.,A Class of Min-Cut Placement Algorithms, 1.4th Design Automation Conference, pp. 284-290, 1977.

Digital Library

[3]

Cheng, C.-K. and E.S. Kuh,Module Placement Based on Resistive Network Optimization, IEEE Trans. on Computer-Aided Design, Vol. CAD-3, No. 3, pp. 218-225,'July 1984.

[4]

Dunlop, A.E. and B.W. Kernighan,A Procedure for Placement of Standard-Cell VLSI Circuits, IEEE Trans. on CAD, Vol. CAD-4, No. 1, pp. 92-98, January 1985.

[5]

Hageman, L.A. and D.M. Young, Applied Iterative Methods, Academic Press, New York, 1981.

[6]

Hanan, M., P.K. Wolff, and B.J. Agule,Some Experimental Results on Placement Techniques, Proc. 13th Design Automation Conference, pp. 214- 224, June 1976.

Digital Library

[7]

Johannes, F.M., K.M. Just, and K.J. Antreich,~,On the Force Placement of Logic Arrays, Proc. 6th European Conference on Circuit Theory and Design, pp. 203-206, 1983.

[8]

Just, K.M. and J.M. Kleinhans,On the Simultaneous Placemenl.of Modules of Integrated Circuits, (in German) AEU Archiv for Elektronik und Uber tragungstechnik, Vol. 39, No. 4, pp. 217-224, July/August 1985.

[9]

Kirsch, F.,RechnergestxStzte Lrsungsverfahren zur Relativplazierung bei der Lay_~utsynthese, Dr.-Ing. Dissertation, Munich,Germany, xechn. Univ. of Munich, 1984.

[10]

Lauther, U.,A Min-Clut Placement Algorithm for General Cell Assemblies based on a Graph Representation, Proc. 16th Design Automation Conference, pp. 1-10, 1979.

Digital Library

[11]

Otten, R.H .M,Eigensolutions in Top-Down Layout Design, IEEE" Proc. International Symposium on Circuits and Systems, pp. 1017-1020, 1982.

[12]

Patel, A. M. and L. C. Cote,Partitioning for VLSI Placement Problems, 18th Design Automation Conference, pp. 411-418, 1981.

Digital Library

[13]

uinn, N.R. and Breuer M.A.,A Force Directed Component Placement Procedure for Printed Circuit Boards, IEEE Trans. on Circuits and Systems, Vol. CAS-26, pp. 377-388, 1979.

[14]

Steinberg, L.,The Backboard Wiring Problem" A Placement Algorithm, SIAM Review, Vol. 3, No. 1, pp. 37-50, January 1961.

[15]

Wipfler, G.J., M. Wiesel, and D.A. Mlynski,A Combined Force and Cut Algorithm for Hierarchical VLSI Layout, 19th Design Automation Conference, pp. 671-676, 1982.

Digital Library

[16]

Spaeth,H., Ausgewahlte Operations Research-Algorithmen in FORTRAN, R.Oldenbourg Verlag, Mfinchen Wien, 1975.

Cited By

Shin HKim CKim WOh MRhee KChoi SChung HLightner MJess J(1993)A combined hierarchical placement algorithmProceedings of the 1993 IEEE/ACM international conference on Computer-aided design10.5555/259794.259822(164-169)Online publication date: 7-Nov-1993
https://dl.acm.org/doi/10.5555/259794.259822
Kyung CWidder JMlynski DAdshead GJess J(1990)Adaptive Cluster Growth (ACG)Proceedings of the conference on European design automation10.5555/949970.950013(191-195)Online publication date: 12-Mar-1990
https://dl.acm.org/doi/10.5555/949970.950013
Zhang XPillage TRohrer RThomas D(1989)Efficient final placement based on nets-as-pointsProceedings of the 26th ACM/IEEE Design Automation Conference10.1145/74382.74479(578-581)Online publication date: 1-Jun-1989
https://dl.acm.org/doi/10.1145/74382.74479
Show More Cited By

Index Terms

On the relative placement and the transportation problem for standard-cell layout
1. Applied computing
  1. Physical sciences and engineering
    1. Engineering
2. Hardware
  1. Electronic design automation
    1. Physical design (EDA)
  2. Very large scale integration design

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. ...
Routability driven white space allocation for fixed-die standard-cell placement
ISPD '02: Proceedings of the 2002 international symposium on Physical design

The use of white space in fixed-die standard-cell placement is an effective way to improve routability. In this paper, we present a white space allocation approach that dynamically assigns white space according to the congestion distribution of the ...
Congestion and timing optimization for standard-cell placement

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

DAC '86: Proceedings of the 23rd ACM/IEEE Design Automation Conference

July 1986

835 pages

ISBN:0818607025

Chairman:
Don Thomas
IBM, Thomas J. Watson Research Center, Yorktown Heights, NY

Sponsors

SIGDA: ACM Special Interest Group on Design Automation

Publisher

IEEE Press

Publication History

Published: 02 July 1986

Check for updates

Qualifiers

Article

Acceptance Rates

DAC '86 Paper Acceptance Rate 124 of 300 submissions, 41%;

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

4
Total Citations
View Citations
222
Total Downloads

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

Reflects downloads up to 18 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Shin HKim CKim WOh MRhee KChoi SChung HLightner MJess J(1993)A combined hierarchical placement algorithmProceedings of the 1993 IEEE/ACM international conference on Computer-aided design10.5555/259794.259822(164-169)Online publication date: 7-Nov-1993
https://dl.acm.org/doi/10.5555/259794.259822
Kyung CWidder JMlynski DAdshead GJess J(1990)Adaptive Cluster Growth (ACG)Proceedings of the conference on European design automation10.5555/949970.950013(191-195)Online publication date: 12-Mar-1990
https://dl.acm.org/doi/10.5555/949970.950013
Zhang XPillage TRohrer RThomas D(1989)Efficient final placement based on nets-as-pointsProceedings of the 26th ACM/IEEE Design Automation Conference10.1145/74382.74479(578-581)Online publication date: 1-Jun-1989
https://dl.acm.org/doi/10.1145/74382.74479
Pillage LRohrer RShaklee DNewton A(1988)A quadratic metric with a simple solution scheme for initial placementProceedings of the 25th ACM/IEEE Design Automation Conference10.5555/285730.285783(324-329)Online publication date: 1-Jun-1988
https://dl.acm.org/doi/10.5555/285730.285783

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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

Media

Figures

Other

Tables

View Table of Contents