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

Article

Free access

Automatic placement a review of current techniques (tutorial session)

Authors:

Bryan T. Preas,

Patrick G. KargerAuthors Info & Claims

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

Pages 622 - 629

Published: 02 July 1986 Publication History

Abstract

This review provides an overview of the placement function within automatic layout systems. The automatic placement problem is defined and the data abstractions are described. The discussion divides placement algorithms into two classes: constructive and iterative. Applications of the algorithms within layout systems are described. A large number of references is provided to allow use as a guide to placement literature.

References

[1]

S.B. Akers, "On the use of the linear assignment algorithm in module placement," in Proceedings of the I gth Design Automation Conference. 1981, pp. 137-144.

Digital Library

[2]

T. Blank, "A survey of hardware accelerators used in computer aided design," in IEEE Desisn and Test of Computers. vol. 1, no. 3, August 1984, pp.21-39.

Digital Library

[3]

J.P. Blanks, "Initial placement of gate arrays using least-squares methods," in Procecdin2s of the 21st Design Automation Conference. t984, pp. 670-671.

Digital Library

[4]

J.P. Blanks, "Near-optimal placement using a quadratic objective function," in Proceedings of the 22nd Desifn Automation Conference. 1985, pp. 609-615.

Digital Library

[5]

J.P. Blanks, "Use of a quadratic objective function for the placement problem in VLSI design," Doctoral Dissertation, University of Texas at Austin, 1985.

Digital Library

[6]

H.N. Brady, "An approach to topological pin assignment," in IEEE Transactions on Comvuter-Aided Design of Integrated Circuits and vol. CAD-3, no. 3, July 1984, pp. 250-255.

[7]

M.A. Breuer, ed., Design Automation of Di~ital Systems. Volume One: Theory and Techniques. Englewood Cliffs, New Jersey: Prentice-Hall, Inc, 1972.

[8]

M.A. Breuer, "A class of rain-cut placement algorithms," in Proceedings of the 14th Design Automation Conference. 1977, pp. 284-290.

Digital Library

[9]

M.S. Chandrasekhar and M.A. Breuer, '*Optimum placement of two rectangular blocks," in Proceedings of the l_gth Design Automation Conference. 1982, pp. 879-886.

Digital Library

[10]

S. Chang, "The generation of minimal trees with a Steiner topology," in Journal of the Association for Comoufine Machinery. vol. 19, no. 4, October 1972, pp. 699-711.

Digital Library

[11]

C.K. Cherts and E.S. Kuh, "Module placement based on resistive network optimization," in IEEE Transactions on Comvuter-Aided Desian of lnte~ated Circuits and Systems. vol. CAD-3, no. 3, July 1984, pp. 218-225.

[12]

C.S. Chow, "Phoenix: An interactive hierarchical topological floorplanning placer," Masters Thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, 1985.

[13]

D. Chyan and M.A. Breuer, "A placement algorithm for array processors," in proceedin~s of the 20th Desi_~n Automation Conference, 1983, pp. 182-188.

Digital Library

[14]

P. L. Ciampi, "A system for solution of the placement problem," in Pro~;eedings of thel2th Design Automation Conference. 1975, pp. 317-323.

Digital Library

[15]

L.I. Corrigan, "A placement capability based on partitioning," in Profeedin2s of the 16th Design Automation Conference. 1979, pp. 406-413.

Digital Library

[16]

L.C. Cote and A.M. Patel, "The interchange algorithms for circuit placement problems," in Proceedings of the 17th Design Automation Confer_e_nce. 1980, pp. 528-534.

Digital Library

[17]

G.W. Cox and B,D. Carroll, "The standard transistor array (star), part II: automatic cell placement techniques," in Eroceedin~ of the 17th Desi_~n Automation Conference. 1980, pp. 451-457.

Digital Library

[18]

N. Duo, Graph Theory with Applications to Engineering and Computer Science. Englewood Cliffs, New Jersey: Prentice Hall, Inc., 1974.

[19]

W.E. Donath, "Complexity theory and design automation,'* in Proceedings_of the 17th Desi~n Automation Conference. 1980, pp. 412-419.

Digital Library

[20]

CJ. Fisk, D.L Caskey and L.E~ West, "ACCEL: automated circuit card etching layout," in Proceedin~s~oLthe IEEE. vol. 55, no. 11, November 1967, pp. 1971-1982.

[21]

K. Fukunaga, S. Yamada, H.S. Stone and T. Kuai, "Placement of circuit modules using a graph space approach," in Pr0ceedings.of the 20th Design Automation Conference. 1983, pp. 465-471.

Digital Library

[22]

R.G. Garside and T.AJ. Nicholson, "Permutation p~ure for the backboard-wiring problem," in ProceeAin~_ of the IEEE. vol. 115, no. 1, January 1968, pp. 27-30.

[23]

P.C. Gilmore, "Optimal and suboptimal algorithms for the quadratic assignment problem," in Journal of the Society for Industrial and Applied Mathematics. vol. I0, no. 2, June 1962, pp. 305-313.

[24]

S. Goto, I. Cederbaum, and B. S. Tins, "Suboptimum solution of the back-board ordering with channel capacity constraint," in IEEE Transactions on Circuits and Systems. vol. CAS-24, no. I1, November 1977, pp. 645-652.

[25]

J.W. Greene and KJ. Supowit, "Simulated annealing without rejected moves," in proceedings=of the intemationaLConference on Computer Des_ian. 1984, pp. 658-663.

[26]

M. Hanan, "On Steiner's problem with rectilinear distance," in SIAM Journal on Awlied Mathematics. vol. 14, no. 2, March 1966, pp. 255-265.

[27]

M. Hanan and J.M. Kurtzberg, "Placement techniques," in M.A. Breuer, ed., Design Automation of Digital Svstems.~totume One: Theory and Technio_ues. Englewood Cliffs, New Jersey: Prentice-Hall, lnc, 1972, ch. 5, pp. 213-282.

[28]

M. Hanan and J.M. Kurtzberg, "A review of the placement and quadratic usignment problems," in SIAM Review, vol. 14, no. 2, April 1972, pp. 324-342.

Digital Library

[29]

M. Hanan, P.K. Wolff St. and BJ. Agule, "Some experimental results on placement techniques," in Pmceedin2s of the 13th Design Automation Conference. 1976, pp. 214-224.

Digital Library

[30]

M. Hanan, P.K. Wolf St. and B.J. Agule, "A study of placement techniques," in Journal of Design Automation and Fault-Tolerant vol. 1, no.I, October 1976, pp. 28-61.

[31]

M. Hanan, P.K. Wolff Sr. and BJ. Agule, "Some experimental results on placement techniques," in Journal of Design Automation and Fault-Tolerant Computing. vol. 2, May 1978, pp. 145-168.

[32]

W.R. Huller, G. $orkin and K. Maling, "The planar package planner for system designers," in p~roceedin~s of the 19th Desiun Automation Conference. 1982, pp. 253-260.

Digital Library

[33]

F.S. Hillier and G.J. Lieberman, Introduction to Operations ~if, tt;h. San Francisco: Holden-Day, Inc., 1980.

Digital Library

[34]

M. S. Hung and W. O. Rom, "Solving the assignment problem by relaxation," in Operations Research. vol. 28, no. 4, July-August 1980, pp. 969-982.

Digital Library

[35]

F.K. Hwang, "On Steiner minimal trees with rectilinear distance," in SIAM Journal on Annlied Mathematics. vol. 30, no. 1, January 1976, pp. 104-114.

[36]

A. losupovici, C. King and M.A. Breuer, "A model interchange placement machine," in Proceedings of the 20th Design Auto, nation 1983, pp. 171-174.

Digital Library

[37]

T. Kambe, T. Chiba, S. Kimura, T. Inufushi, N. Okuda and I. Nishioka, "A placement algorithm for polycell LSI and its evaluation," in Proc~~dines of the 19th Desien Automation Conference. 1982, pp. 655-662.

Digital Library

[38]

S. Kang, "Linear ordering and application to placement," in Proceedinc, s of the 20th Desi~,n Automation Conference. 1983, pp. 457-464.

Digital Library

[39]

K. Kani, H. Kawanishi and A. Kishimota, "ROBIN: a building block LSI routing problem," in Proceedines of the International Symposium on Circuits and Systems. 1976, pp. 658-661.

[40]

P.G. Karger and M. Malek, "Formulation of component placement as a constrained optimization problem," in ProceedinRs of the International Conference on Computer Design. 1984, pp. 814-819.

[41]

B.W. Kernighan and S. Lin, "An efficient heuristic proced~,re for partitioning graphs," in Bell System Technical Journal. vol. 49, no. 2, February 1970, pp. 291-307.

[42]

K.H. Khokhani anti A.M. Patel, "The chip layout problem: a placement procedure for LSI," in Proceedings of the 14th Design Automation Conference. 1977, pp. 291-297.

Digital Library

[43]

K.H. Khokhani, A.M. Patel, W. Ferguson: J. Sessa and D. ltatton, "Placement of variable size circuits on LSI masterslice:s," in Proceedings of the 18th Design Automation Conference. 19~;1, pp. 426-434.

Digital Library

[44]

S. Kirkpatrick, C.D. Gelatt and M.P. Vecchi, "Optimization by simulated annealing," in Science. vol. 220, no. 4598, May 1983, pp. 671-680.

[45]

N.L. Koren, "Pin assignment in automated printed circuit board design," in Proceedings of the 9th Design Automation Workshop. 1972, pp. 72-79.

Digital Library

[46]

T. Kozawa, H. Terai, T. ishii, M. Hayase, C. Miura, Y. Ogawa, K. Kishida, N. Yamada and Y. Ohno, "Automatic placement algorithms for high packing density VLSI," in Proceedings of the 20th Design Automation Conference. 1983, pp. 175-181.

Digital Library

[47]

J.M. Kurtzberg, "Algorithms for backplane formation," in Microelectronics in Large Systems, Washington, D.C.: Spartan Books, 1965, pp. 51-76.

[48]

U. Lauther, "A rain-cut placement algorithm for general cell assemblies based on a graph representation," in Proceedings 16th Design Automation Conference. 1979, pp. 1-10.

Digital Library

[49]

E.L Lawler and D.E. Wood, "Branch-and-bound methods: a survey," in Operations Research, vol. 14, no. 4, July-August 1966, pp. 699-719.

Digital Library

[50]

S. Lin, "Computer solutions of the traveling salesman problem'" in Bell System Technical Journal, vol. 44, no. 10, December 1965, pp. 2245-2269.

[51]

K.J. Loosemore, "Automated layout of integrated circu:its," in Proceedings of the IEEE International Svmvosium on Circuits and 1979, pp. 665-668.

[52]

W.G. Magnuson, "A comparison of constructive placement algorithms," in IEEE Region 6 Conference Record. 1977, pp. :!8-32.

[53]

N. Metropolis, A.W. Rosenbluth, M.N. Rosenbluth, and A.H. Teller and E. Teller, "Equation of state calculations by fast computing machines," in Journal of Chemical Physics. vol. 21, no. 6, June 1953, pp. 1087-1092.

[54]

L. Mory-Rauch, "Pin assignment on a printed circuit boca'd," in Proceedings of the 15th Design Automation Conference. 1978, pp. 70-73.

Digital Library

[55]

S. Mural, M. Kakinuma, M. Imai and H. Tsuji, "The effects of the initial placement t~:chniques on the final placement results," in Proceedings of the IEEE Conference on Circuits and Comtmters. 1980, pp. 80-82.

[56]

S. Nahar, S. Sahni and E. Shragowitz, "Experiments with simulated annealing," in Proceedings of the 22nd Des'ran Automation Conference, 1985, pp. 748-752.

Digital Library

[57]

R. Nair, A. Brass and J. Reif, "Linear time algorithms for optimal CMOS layout," in _VLSI: Algorithms and Architecture. P. Bertolazzi and F. Luccio, eds. North-Holland: Elsevier Science Publishers B.V., 1985, pp. 327-338.

[58]

I. Nishioka, T. Kurimoto, S. Yamamoto, I. Shirakawa and H. Ozaki, "An approach to gate assignment and module placement for printed wiring hoards," in Proceedinea of the 15th DesiRn Automation 1978, pp. 60- 69.

Digital Library

[59]

G. Odawara, K. lijima and K. Wakabayashi, "Knowledge-based placement technique for printed wiring boards," in Proceedings of the 22nd Desiim Automation Conference. 1985, pp. 616-622.

Digital Library

[60]

R.H.J.M. Otten, "Automatic floorplan design," in Proceedings of the 19th Desien Automation~.onference. 1982, pp. 261-267.

Digital Library

[61]

M. Palczewski, "Performance of algorithms for initial placement," in Proceedings of the 21st Design Automation Conference. 1984, pp. 399-404.

Digital Library

[62]

T.S. Payne and W.M. vanC!eemput, "Automated partitioning of hierarchically specified digital lystcms," in Proceedines of the 19th Desien Automation Conference,. 1982, pp. 182-192.

Digital Library

[63]

G. Persky, "PRO - an automatic string placement program for polycell layout," in. Proceedings of the 13th Desien Automation Conference. 1976, }pp. 417-424.

Digital Library

[64]

B.T. Preas and C.W. Gwyn, "Methods for hierarchical automatic layout of custom I,SI circuit masks," in Proceeding~ of the _15th Design Automation Conference. 1978, pp. 206-212.

Digital Library

[65]

B.T. Preas and W.M. vanCleemput, "Placement algorithms for arbitrarily shaped blocks," in Pro~~e.dint~s of the 16th Design Automation Conference, 1979, pp. 474 - 480.

Digital Library

[66]

B.T. Preas, "Placement and routing algorithms for hierarchical integrated circuit layout," Doctoral Dissertation, Department of Electrical Engineering, Stanford University, 1979.

Digital Library

[67]

B.T. Preas and ('.S. Chow, "Placement and routing algorithms for topological integrated circuit layout," in Pr__ocee_dings of the_ International Symposium on Circuits and Systems. 1985, pp.17-20.

[68]

B.T. Preas and P.G. Karger, "Automatic placement", in P_ L0. .c, g. .e, ttiag~ of the Automation :86 Hiszh Technolo~,v Comt)uter Conference. 1986, pp. 229-248.

[69]

R.C. Prim, "Shortest connection networks and some generalizations," in Bell System Technical Joernal. vol. 36, no. 6, November 1957, pp. 1389-140l.

[70]

N.R. Quinn, "The placement problem as viewed from the physics of classical mechanics," in Proceedines of the 12th Desien Automation .Q.9.BLf.Ltn.f~ 1975, pp. 173-178.

Digital Library

[71]

S. Reiter and G. Sherman, "Discrete optimizing," in Journal of the Society for Industrial and Applied Mathematics. vol. 13, no. 3, September 1965, pp. 864-889.

[72]

B.D. Richard, "A standard cell initial placement strategy," in Proceedings of the 21st Desiell Automation Conference. 1984, pp. 392-398.

Digital Library

[73]

F. Romeo, A. Sangiovanni-Vincentelli, and C. Sechen, "Research on simulated annealing at Berkeley," in Proceedines of the International Conference on Computer Design, 1984, pp. 652-657.

[74]

F. Romeo and A. Sangiovanni-Vincentelli, "Probabilistic hill climbing algorithms" properties and application s," in Proceedings of the: 1985 Chapel.Hill Conference on VLSI. 1985, pp.393-417.

[75]

S. Sahni and A. Bhatt, "The complexity of design automation problems," in ~.roceedings o f the 17th De_sign Automation Conference, 1980, pp. 402-411.

Digital Library

[76]

D.M. Schuler and E.G. ULrich, "Clustering and linear placement," in Proceedings of the 9th Design Automation Workshoo. 1972, pp. 50-56.

Digital Library

[77]

D.G. Schweikert and B.W. Kernighan, "A proper model for the partitioning of electrical, circuits," in Proceedings of the,Qth Design Auwmation Workshop. 1972, pp. 57-62.

Digital Library

[78]

D.G. Schweikert, "A 2-dimensional placement algorithm for the layout of electrical circuits," in Proceedin2s of the 13th D~sj~n Automation Conference. 19"/6, pp. 408-416.

Digital Library

[79]

L. Sha and R.W. Dutton, "An analytical algorithm for placement of arbitrarily sized rectangular blocks," in Proceedings of the 22nd Design Automation Conference_ 1985, pp. 602-608.

Digital Library

[80]

E.A. Slutz, "Shape determination and placement algorithms for hierarchical integrated circuit layout," Doctoral Dissertation, Department of Electrical Engineering and Computer Science, Stanford University, 1980.

Digital Library

[81]

J. Soak,p, "Circuit layout," in Pr~e~dinas of th~IEEE, vol. 69, no. I0, pp. 1281- 1304, October 1981.

[82]

P.M. Spira and C. Hage, "Hardware acceleration of gate array layout," in Proceedings of the 22rid Design Automation I985, pp. 359-366.

Digital Library

[83]

L. Steinberg, "The backboard wiring problem: a placement algorithm," in SIAM Review, vol. 3, no. l, January 1961, pp. 37-50.

[84]

A.A. Sz~pienicc and R.HJ.M. Often, "The genealogical approach to the layout problem," in Proceedin_~s of the 17th Desi2n Automation Conferenc~. 1980, pp. 535-542.

Digital Library

[85]

T. Uehara and W.M. vanCleemput, "Optimal layout of CMOS functional arrays," in IEEE Transactions on Comnuting. vol. C-30, May 1981, pp. 305-312.

[86]

M.M. Wada, "SLOOP: Sandia standard cell layout optimization program: a user's manual," Sandia National Laboratories, SAND82-0331, March 1982.

[87]

G.R. Walsh, Methods of ODtimization, John Wiley and Sons, Ltd., 1975.

[88]

S.R. White, "Concepts of scale in simulated annealing," in proceedinc, s of the International Conference on Comvuter Design. 1984, pp. 646-651.

[89]

G.J. Wipfler, M. Wiesel and D.A. Mlynski, "A combined force and cut algorithm for hierarchical VLSI layout," in Proceedinas of the 19th Design Automation Conference. 1982, pp. 671-677.

Digital Library

Cited By

Subbaraj PSivakumar P(2011)Multithreaded memetic algorithm for VLSI placement problemProceedings of the Second international conference on Swarm, Evolutionary, and Memetic Computing - Volume Part I10.1007/978-3-642-27172-4_67(569-576)Online publication date: 19-Dec-2011
https://dl.acm.org/doi/10.1007/978-3-642-27172-4_67
LaPaugh A(2010)VLSI layout algorithmsAlgorithms and theory of computation handbook10.5555/1882723.1882731(8-8)Online publication date: 1-Jan-2010
https://dl.acm.org/doi/10.5555/1882723.1882731
Hao XBrewer F(2005)Wirelength optimization by optimal block orientationProceedings of the 2005 IEEE/ACM International conference on Computer-aided design10.5555/1129601.1129613(64-70)Online publication date: 31-May-2005
https://dl.acm.org/doi/10.5555/1129601.1129613
Show More Cited By

Index Terms

Automatic placement a review of current techniques (tutorial session)
1. Applied computing
  1. Physical sciences and engineering
    1. Engineering
2. Hardware
  1. Electronic design automation
    1. Physical design (EDA)

Recommendations

Combinatorial techniques for mixed-size placement

While recent literature on circuit layout addresses large-scale standard-cell placement, the authors typically assume that all macros are fixed. Floorplanning techniques are very good at handling macros, but do not scale to hundreds of thousands of ...
Simultaneous analog placement and routing with current flow and current density considerations
DAC '13: Proceedings of the 50th Annual Design Automation Conference

Current-flow and current-density are two major considerations for placement and routing of analog layout synthesis. The current-flow constraints are specified to the critical nets with monotonic current/signal paths to reduce parasitic impacts. The ...
New techniques 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%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
528
Total Downloads

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

Reflects downloads up to 18 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Subbaraj PSivakumar P(2011)Multithreaded memetic algorithm for VLSI placement problemProceedings of the Second international conference on Swarm, Evolutionary, and Memetic Computing - Volume Part I10.1007/978-3-642-27172-4_67(569-576)Online publication date: 19-Dec-2011
https://dl.acm.org/doi/10.1007/978-3-642-27172-4_67
LaPaugh A(2010)VLSI layout algorithmsAlgorithms and theory of computation handbook10.5555/1882723.1882731(8-8)Online publication date: 1-Jan-2010
https://dl.acm.org/doi/10.5555/1882723.1882731
Hao XBrewer F(2005)Wirelength optimization by optimal block orientationProceedings of the 2005 IEEE/ACM International conference on Computer-aided design10.5555/1129601.1129613(64-70)Online publication date: 31-May-2005
https://dl.acm.org/doi/10.5555/1129601.1129613
Areibi SYang Z(2004)Effective memetic algorithms for VLSI design automation = genetic algorithms + local search + multi-level clusteringEvolutionary Computation10.1162/106365604177494712:3(327-353)Online publication date: 1-Sep-2004
https://dl.acm.org/doi/10.1162/1063656041774947
Foo HSong JZhuang WEsbensen HKuh E(1997)Implementation of a parallel genetic algorithm for floorplan optimization on IBM SP2Proceedings of the High-Performance Computing on the Information Superhighway, HPC-Asia '9710.5555/523549.822945Online publication date: 28-Apr-1997
https://dl.acm.org/doi/10.5555/523549.822945
Yan J(1996)A simple yet effective genetic approach for the orientation assignment on cell-based layoutProceedings of the 9th International Conference on VLSI Design: VLSI in Mobile Communication10.5555/525699.834729Online publication date: 3-Jan-1996
https://dl.acm.org/doi/10.5555/525699.834729
Nourani MPapachristou CDunlop A(1993)A layout estimation algorithm for RTL datapathsProceedings of the 30th international Design Automation Conference10.1145/157485.164895(285-291)Online publication date: 1-Jul-1993
https://dl.acm.org/doi/10.1145/157485.164895
Cheng CYao SHu T(1991)The Orientation of Modules Based on Graph DecompositionIEEE Transactions on Computers10.1109/12.9025540:6(774-780)Online publication date: 1-Jun-1991
https://dl.acm.org/doi/10.1109/12.90255
Banerjee PJones MSargent J(1990)Parallel Simulated Annealing Algorithms for Cell Placement on Hypercube MultiprocessorsIEEE Transactions on Parallel and Distributed Systems10.1109/71.801281:1(91-106)Online publication date: 1-Jan-1990
https://dl.acm.org/doi/10.1109/71.80128
Dai W(1987)Some issues raised in physical design workshop 1987ACM SIGDA Newsletter10.1145/378916.37895517:3(58)Online publication date: 1-Sep-1987
https://dl.acm.org/doi/10.1145/378916.378955
Show More Cited By

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