Article

Free access

A quadratic metric with a simple solution scheme for initial placement

Authors:

Lawrence T. Pillage,

Ronald A. RohrerAuthors Info & Claims

DAC '88: Proceedings of the 25th ACM/IEEE Design Automation Conference

Pages 324 - 329

Published: 01 June 1988 Publication History

PDF eReader

Abstract

For the initial placement problem a nets-as-points model provides a quadratic cost metric which when minimized localizes the gates. Fixed constraints are added to the cost function so that a minimum is guaranteed to exist, and can be obtained by means of a simple iterative solution. The initial placement is obtained in near linear time. An annular snap-to-grid heuristic completes the initial placement. The nets-as-points metric is shown to produce desirable results.

References

[1]

K.M. Hall. "An r-Dimensional Quadratic Placement Algorithm" Management Science 17, 3 (1970), 219-229.

Digital Library

Google Scholar

[2]

C. Cheng and E.S. Kuh. "Module Placement Based on Resistive Network Optimization". {EEE Trans. Computer-Aided Design of Integrated Circuit8 and System8 CAD-3 (1984), 218-225.

Google Scholar

[3]

J.P. Blanks. Near-optimal Placement Using z Quadratic Objective Function. Proceedings of the 22nd Design Automation Conference, June, 1985.

Digital Library

Google Scholar

[4]

K.M. Just, J.M. Kleinhans, and P.M. Johannes. On the Relative Placement and the Transportation Problem for Standard-Cell Layout. Proceedings of the 23nd Design Automation Conference, June, 1986.

Digital Library

Google Scholar

[5]

J. Frankle and R.M. Karp. Circuit Placements and Cost Bounds by Eigenvector Decomposition. Proceedings of the IEEE International Conference on Computer-Aided Design, November, 1986.

Google Scholar

[6]

M.A. Breuer. A Class of Min-Cut Placement Algorithms. Proceedings of the 14th Design Automation Conference, 1977, pp. 343-362.

Digital Library

Google Scholar

[7]

D.G. Schweikert and B.W. Kernighan. A Proper Model for the Partitioning of Electrical Circuits. Proceedings of the 9th Design Automation Workshop, 1972, pp. 57-62.

Digital Library

Google Scholar

[8]

G. Str~n~. Introduction to Applied Atathematics. Wellesley-C~mbridge Press, Wellesley, MA., 1986.

Google Scholar

[9]

A. Ralston and P. Rabinowitz. Firet Course in Numerical Analysis. McGraw-Hill Book Company, New York, N.Y., 1978.

Google Scholar

[10]

S. Kirkpatrick, C.D. Gelatt, Jr., and M.P. Vecchi. "Optimization by Simulated Annealing". Science 220 (1983), 45-54.

Google Scholar

[11]

C.M. Fiduccia and R.M. Mattheyses. A Linear-Time Heuristic for Improving Network Partitions. Proceedings of the 19th Design Automation Conference, 1982, pp. 175-181.

Digital Library

Google Scholar

[12]

A.E. Dunlop and B.W. Kernighan. "A Placement Procedure for Layout of VLSI Circuits". IEEE Trans. CAD of IC8 and System8 4, 1 (1985), 92-98.

Google Scholar

Cited By

View all

Alupoaei SKatkoori S(2002)Net Clustering Based Macrocell PlacementProceedings of the 2002 Asia and South Pacific Design Automation Conference10.5555/832284.835380Online publication date: 7-Jan-2002
https://dl.acm.org/doi/10.5555/832284.835380
Cong JHagen LKahng ASchweikert D(1992)Net partitions yield better module partitionsProceedings of the 29th ACM/IEEE Design Automation Conference10.5555/113938.110434(47-52)Online publication date: 1-Jul-1992
https://dl.acm.org/doi/10.5555/113938.110434
Yeh CCheng CLin TNewton A(1991)A general purpose multiple way partitioning algorithmProceedings of the 28th ACM/IEEE Design Automation Conference10.1145/127601.127706(421-426)Online publication date: 1-Jun-1991
https://dl.acm.org/doi/10.1145/127601.127706
Show More Cited By

Index Terms

A quadratic metric with a simple solution scheme for initial placement

Recommendations

OptiPlace: optimized placement solution for mixed-size designs
Abstract
In this paper, an optimized placement approach has been presented for mixed-size designs. A novel initial placement approach is introduced to achieve routability-aware global placement using new routability-aware cell clustering, cluster ...
Sub-quadratic objectives in quadratic placement
DATE '13: Proceedings of the Conference on Design, Automation and Test in Europe

This paper presents a new flexible quadratic and partitioning-based global placement approach which is able to optimize a wide class of objective functions, including linear, sub-quadratic, and quadratic net lengths as well as positive linear ...
Quadratic placement revisited
DAC '97: Proceedings of the 34th annual Design Automation Conference

The "quadratic placement" methodology is rooted in [Module Placement Based on Resistive Network Optimization, Proud: A Sea-Of-Gate Placement Algorithm, A Combined Force and Cut Algorithm for Hierarchical VLSI Layout]and is reputedly used in many ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

DAC '88: Proceedings of the 25th ACM/IEEE Design Automation Conference

June 1988

730 pages

ISBN:0818688645

Chairmen:
Dennis W. Shaklee
AT&T/ISL, Denver, CO
,
A. Richard Newton
Univ. of California, Berkeley

Publisher

IEEE Computer Society Press

Washington, DC, United States

Publication History

Published: 01 June 1988

Check for updates

Qualifiers

Article

Conference

DAC88

Sponsor:

SIGDA
IEEE

DAC88: Design Automation Conference

June 12 - 15, 1988

New Jersey, Atlantic City, USA

Acceptance Rates

DAC '88 Paper Acceptance Rate 125 of 400 submissions, 31%;

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
243
Total Downloads

Downloads (Last 12 months)42
Downloads (Last 6 weeks)8

Reflects downloads up to 18 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Alupoaei SKatkoori S(2002)Net Clustering Based Macrocell PlacementProceedings of the 2002 Asia and South Pacific Design Automation Conference10.5555/832284.835380Online publication date: 7-Jan-2002
https://dl.acm.org/doi/10.5555/832284.835380
Cong JHagen LKahng ASchweikert D(1992)Net partitions yield better module partitionsProceedings of the 29th ACM/IEEE Design Automation Conference10.5555/113938.110434(47-52)Online publication date: 1-Jul-1992
https://dl.acm.org/doi/10.5555/113938.110434
Yeh CCheng CLin TNewton A(1991)A general purpose multiple way partitioning algorithmProceedings of the 28th ACM/IEEE Design Automation Conference10.1145/127601.127706(421-426)Online publication date: 1-Jun-1991
https://dl.acm.org/doi/10.1145/127601.127706
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

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

OptiPlace: optimized placement solution for mixed-size designs

Sub-quadratic objectives in quadratic placement

Quadratic placement revisited