VLSI cell placement techniques

ABSTRACT

VLSI cell placement problem is known to be NP complete. A wide repertoire of heuristic algorithms exists in the literature for efficiently arranging the logic cells on a VLSI chip. The objective of this paper is to present a comprehensive survey of the various cell placement techniques, with emphasis on standard cell and macro placement. Five major algorithms for placement are discussed: simulated annealing, force-directed placement, min-cut placement, placement by numerical optimization, and evolution-based placement. The first two classes of algorithms owe their origin to physical laws, the third and fourth are analytical techniques, and the fifth class of algorithms is derived from biological phenomena. In each category, the basic algorithm is explained with appropriate examples. Also discussed are the different implementations done by researchers.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	AARTS, E. H. L, DEBONT, F. M. J., AND HABERS, E. H. A. 1985. Statistical cooling: A general approach to combinatorial optimization problems. Philips J. Res. 40, 4, 193-226.
	2	E H L Aarts , F M J de Bont , E H A Habers , P J M van Laarhoven, Parallel implementations of the statistical cooling algorithm, Integration, the VLSI Journal, v.4 n.3, p.209-238, Sept. 1986 [doi>10.1016/0167-9260(86)90002-7]
	3	Sheldon B. Akers, On the use of the linear assignment algorithm in module placement, Proceedings of the 18th conference on Design automation, p.137-144, June 29-July 01, 1981, Nashville, Tennessee, United States
	4	ANTREICH, K. J., JOHANNES, F. M., AND KmSCH, F H. 1982. A new approach for solving the placement problem using force models. In Proceed~ngs of the IEEE International Symposium on Circuits and Systems. pp. 481-486.
	5	BAr~NERJEE, P., AND JONES, M. 1986. A parallel simulated annealing algorithm for standard cell placement on a hypercube computer. In Proceedings of the IEEE International Confer~ ence on Computer Design. p. 34.
	6	BENDERS, J. F. 1962. Partitioning procedures for solving mixed variable problems. Numer. Math. 4,238-252.
	7	John P. Blanks, Initial placement of gate arrays using least-squares methods, Proceedings of the 21st conference on Design automation, p.670-671, June 25-27, 1984, Albuquerque, New Mexico, United States
	8	John P. Blanks, Near-optimal placement using a quadratic objective function, Proceedings of the 22nd ACM/IEEE conference on Design automation, p.609-615, June 1985, Las Vegas, Nevada, United States [doi>10.1145/317825.317953]
	9	John Peyton Blanks, Use of a quadratic objective function for the placement problem in vlsi design (eigenvector, cad(computer-aided design, optimization, automation), 1985
	10	BREU~R, M. A. 1977a. Min-cut placement. J. De~ sign Automation and Fault-Tolerant Computing 1, 4 (Oct.) 343-382.
	11	Melvin A. Breuer, A class of min-cut placement algorithms, Proceedings of the 14th conference on Design automation, p.284-290, January 1977
	12	CASSOTO, A., ROMEO, F., AND SANGIOVANNI- VINCENTELLI, A. 1987. A parallel simulated annealing algorithm for the placement of standard cells. IEEE Trans. Comput.-Aided Design CAD-6, 5 (May), 838.
	13	CHAN, H. M., AND MAZUMDER, P. 1989. A genetic algorithm for macro cell placement. Tech. Rep. Computing Research Laboratory, Dept. of Electrical Engineering and Computer Science, University of Michigan, Ann Arbor, Mich.
	14	Shi-Kuo Chang, The Generation of Minimal Trees with a Steiner Topology, Journal of the ACM (JACM), v.19 n.4, p.699-711, Oct. 1972 [doi>10.1145/321724.321733]
	15	CHEN, N. P. 1983. New algorithms for steiner tree on graphs. In Proceedings of the International Symposium on Circuits and Systems. pp. 1217-1219.
	16	CHENG, C. 1984. Placement algorithms and applications to VLSI design. Ph.D. dissertation Dept. of Electrical Engineering, Univ. of California, Berkeley.
	17	CHENG, C., AND KUH, E. 1984. Module placement based on resistive network optimization. {BEE Trans. Comput.-Aided Design CAD-3, 7 (July), 218-225.
	18	CHUNG, M. J., AND RAO, K. K. 1986. Parallel simulated annealing for partitioning and routing. In Proceedings of the IEEE International Conference on Computer Design. pp. 238-242.
	19	Dah-Juh Chyan , Melvin A. Breuer, A placement algorithm for array processors, Proceedings of the 20th conference on Design automation, p.182-188, June 27-29, 1983, Miami Beach, Florida, United States
	20	James Cohoon , Sartaj Sahni, Heuristics for the Circuit Realization Problem, Proceedings of the 20th conference on Design automation, p.560-566, June 27-29, 1983, Miami Beach, Florida, United States
	21	COHOON, J. P., AND PASIS, W. D. 1986. Genetic placement. In Proceedings of the IEEE International Conference on Computer-Aided Design. pp. 422-425.
	22	Lorretta I. Corrigan, A placement capability based on partitioning, Proceedings of the 16th Conference on Design automation, p.406-413, June 25-27, 1979, San Diego, CA, United States
	23	DAVIS, L. 1985. Applying adaptive algorithms to epistatic domains. In Proceedings of the International Joint Conference on Artificial Intelligence.
	24	W. E. Donath, Complexity theory and design automation, Proceedings of the 17th conference on Design automation, p.412-419, June 23-25, 1980, Minneapolis, Minnesota, United States [doi>10.1145/800139.804563]
	25	DUNLOP, A. E., AND KERNIGHAN, B. W. 1985. A procedure for placement of standard cell VLSI circuits. IEEE Trans. Comput.-Aided Design CAD-4, i (Jan.), 92-98.
	26	C. M. Fiduccia , R. M. Mattheyses, A linear-time heuristic for improving network partitions, Proceedings of the 19th conference on Design automation, p.175-181, January 1982
	27	FtSK, C. J., CASKEY, D. L., AND WEST, L. E. 1967. Acceh Automated circuit card etching layout. Proc. IEEE 55, 11 (Nov.) 1971-1982.
	28	Kunio Fukunaga , Shoichiro Yamada , Harold S. Stone , Tamotsu Kasai, Placement of circuit modules using a graph space approach, Proceedings of the 20th conference on Design automation, p.465-471, June 27-29, 1983, Miami Beach, Florida, United States
	29	GIDAS, B. 1985. Non-stationary Markov chains and convergence of the annealing algorithm. J. Stat. Phys. 39, 73-131.
	30	GmMORE, P. C. 1962. Optimum and suboptimum algorithms for the quadratic assignment problem. J. SIAM 10, 2 (June), 305-313.
	31	David E. Goldberg , Robert Lingle, Jr., AllelesLociand the Traveling Salesman Problem, Proceedings of the 1st International Conference on Genetic Algorithms, p.154-159, July 01, 1985
	32	GOTO, S. 1981. An efficient algorithm for the two-dimensional placement problem in electrical circuit layout. IEEE Trans. Circuits Syst., CAS-28 (Jan.), 12-18.
	33	GOTO, S., AND KUH, E. S. 1976. An approach to the two-dimensional placement problem in circuit layout. IEEE Trans. Circuits Syst. CAS- 25, 4, 208-214.
	34	GoTo, S., CEDERBAUM, I., AND TING, B.S. 1977. Suboptimal solution of the backboard ordering with channel capacity constraint. IEEE Trans. Circuits Syst. (Nov. 1977), 645-652.
	35	GOTO, S., AND MATSUDA, T. 1986. Partitioning, assignment and placement. In Layout Design And Verification, T. Ohtsuki, Ed. Elsevier North-Holland, New York, Chap. 2, pp. 55-97.
	36	GREENE, J. W., AND SU{~OWIT, K. J. 1984. Simulated annealing without rejected moves. In Proceedings of the J'EEE International Conference on Computer Design. pp. 658-663.
	37	Proceedings of the 1st International Conference on Genetic Algorithms, July 1985
	38	Proceedings of the Second International Conference on Genetic Algorithms on Genetic algorithms and their application, October 1987
	39	L. K. Grover, Standard cell placement using simulated sintering, Proceedings of the 24th ACM/IEEE conference on Design automation, p.56-59, June 28-July 01, 1987, Miami Beach, Florida, United States [doi>10.1145/37888.37896]
	40	Bruce Hajek, Cooling schedules for optimal annealing, Mathematics of Operations Research, v.13 n.2, p.311-329, May 1988 [doi>10.1287/moor.13.2.311]
	41	HALL, K. M. 1970. An r-dimensional quadratic placement algorithm. Manage. Sci. 17, 3 (Nov.), 219-229.
	42	HANAN, M, AND KURTZBERG, J. M. 1972a. Placement techniques. In Design Automation of Digital Systems, 1, M. A. Breuer, Ed. Prentice Hall, Englewood Cliffs, N.J., Chap. 5, pp. 213-282.
	43	HANAN, M., AND KURTZBERG, J. M. 1972b. A review of placement and quadratic assignment problems. SIAM Rev. 14, 2 (Apr.), 324-342.
	44	Maurice Hanan , Peter K. Wolff, Sr. , Barbara J. Agule, Some experimental results on placement techniques, Proceedings of the 13th conference on Design automation, p.214-224, June 28-30, 1976, San Francisco, California, United States [doi>10.1145/800146.804817]
	45	HANAN, M., AND WOLFF, P. K., AND AGULE, B. J. 1976b. A study of placement techniques. J. Design Automation and Fault-Tolerant Computing 1, i (Oct.), 28-61.
	46	HANAN, M., WOLFF, P. K., AND AGULE, B. J. 1978. Some experimental results on placement techniques. J. Design Automation and Fault- Tolerant Computing 2 (May), 145-168.
	47	A. Herrigel , W. Fichtner, An analytic optimization technique for placement of macro-cells, Proceedings of the 26th ACM/IEEE conference on Design automation, p.376-381, June 25-28, 1989, Las Vegas, Nevada, United States [doi>10.1145/74382.74445]
	48	HmDEB~ANDT, T. 1985. An annotated placement bibliography. ACM SIGDA Newsletter 15, 4 (Dec.), 12-21.
	49	HILLNER, H., Wins, B. X., AND MLYNSKI, D. A. 1986. The discrete placement problem: A dynamic programming approach. In Proceedings of the International Symposium on C~rcuits and Systems. pp. 315-318.
	50	John H. Holland, Adaptation in natural and artificial systems, MIT Press, Cambridge, MA, 1992
	51	Hu, T. C., AND KUH, E. S. 1985. VLSI C~rcuit Layout. IEEE Press, New York.
	52	HUANG, M. D., ROMEO, F., AND SANGIOVANNI- VINC~NTELLI, A. 1986. An efficient general cooling schedule for simulated annealing. In Proceedings of the IEEE International Conference on Computer-Aided Design. pp. 381-384.
	53	HWANG, F. K. 1976. "On Steiner Minimal Trees with Rectilinear Distance," SIAM J. Appl. Math. Vol. 30, pp.104-114, 1976.
	54	HWANG, F. K. 1979. An O(nlog n) algorithm for suboptimal rectilinear steiner trees. IEEE Trans. Circuits Syst. CAS-26, 1, 75-77.
	55	JARMON, D. 1987. An automatic placer for arbitrary sized rectangular blocks based on a cellular model. In Proceedings of the IEEE International Conference on Computers and Applications, pp. 842-845.
	56	JOHANNES, F. M., JUST, K. M., AND ANTREICH, K. J. 1983. On the force placement of logic arrays. In Proceedings of the 6th European Conference on Circuit Theory and Destgn. pp. 203-206.
	57	JOHNSON, D. B., AND MIZOGUCHI, T. 1978. Selecting the kth element in X+ Y and X1 +X2 + '" +Xm. SIAM J. Comput. 7, 2 (May), 141-143.
	58	T. Kambe , T. Chiba , S. Kimura , T. Inufushi , N. Okuda , I. Nishioka, A placement algorithm for polycell LSI and ITS evaluation, Proceedings of the 19th conference on Design automation, p.655-662, January 1982
	59	Sungho Kang, Linear ordering and application to placement, Proceedings of the 20th conference on Design automation, p.457-464, June 27-29, 1983, Miami Beach, Florida, United States
	60	H. J. Kappen , F. M. J. de Bont, An efficient placement method for large standard-cell and sea-of-gates designs, Proceedings of the conference on European design automation, March 12-15, 1990, Glasgow, Scotland
	61	K~SmER, P. G., AND MALEK, M. 1984. Formulation of component placement as a constrained optimization problem. In Proceedings of the International Conference on Computer Design. pp. 814-819.
	62	KERNIGHAN, B. W., AND LIN, S. 1970. An efficient heuristic procedure for partitioning graphs. Bell Syst. Tech. J. 49, 2, 291-308.
	63	KIRKPATRICK, S., GELATT, C. D., AND VECCHI, M. P. 1983. Optimization by simulated annealing. Science 220. 4598 (May), 671-680.
	64	KLING, R. M. 1987. Placement by simulated evolution. Master's thesis, Coordinated Science Lab, College of Engr., Univ. of Illinois at Urbana-Champaign.
	65	R.-M. Kling , P. Banerjee, ESP: a new standard cell placement package using simulated evolution, Proceedings of the 24th ACM/IEEE conference on Design automation, p.60-66, June 28-July 01, 1987, Miami Beach, Florida, United States [doi>10.1145/37888.37897]
	66	Tokinori Kozawa , Chihei Miura , Hidekazu Terai, Combine and top down block placement algorithm for hierarchical logic VLSI layout, Proceedings of the 21st conference on Design automation, p.667-669, June 25-27, 1984, Albuquerque, New Mexico, United States
	67	T. Kozawa , H. Terai , T. Ishii , M. Hayase , C. Miura , Y. Ogawa , K. Kishida , N. Yamada , Y. Ohno, Automatic placement algorithms for high packing density V L S I, Proceedings of the 20th conference on Design automation, p.175-181, June 27-29, 1983, Miami Beach, Florida, United States
	68	K~USKAL, J. 1956. On the shortest spanning subtree of a graph and the traveling salesman problem. In Proceedings of the American Mathematical Society, Vol. 7, No. 1, pp. 48-50.
	69	P. J. M. Laarhoven , E. H. L. Aarts, Simulated annealing: theory and applications, Kluwer Academic Publishers, Norwell, MA, 1987
	70	LAM, J., AND DELOSME, J. 1986. Logic minimization using simulated annealing. In Proceedings of the IEEE International Conference on Computer-Aided Design. p. 378.
	71	Jimmy Lam , Jean-Marc Delosme, Performance of a new annealing schedule, Proceedings of the 25th ACM/IEEE conference on Design automation, p.306-311, June 12-15, 1988, Atlantic City, New Jersey, United States
	72	Ulrich Lauther, A min-cut placement algorithm for general cell assemblies based on a graph representation, Proceedings of the 16th Conference on Design automation, p.1-10, June 25-27, 1979, San Diego, CA, United States
	73	LEmHTON, F. T. 1983. Complexity Issues ~n VLSI. MIT Press, Cambridge, Mass.
	74	LUNDY, M., AND MEES, A. 1984. Convergence of the annealing algorithm. In Proceedings of the Simulated Annealing Workshop.
	75	MAGNUSON, W. G. 1977. A comparison of constructive placement algorithms. IEEE Region 6 Conf. Rec. 28-32.
	76	Sivanarayana Mallela , Lov K. Grover, Clustering based simulated annealing for standard cell placement, Proceedings of the 25th ACM/IEEE conference on Design automation, p.312-317, June 12-15, 1988, Atlantic City, New Jersey, United States
	77	Lev A. Markov , Jeffrey R. Fox , John H. Blank, Optimization techniques for two-dimensional placement, Proceedings of the 21st conference on Design automation, p.652-654, June 25-27, 1984, Albuquerque, New Mexico, United States
	78	MITEA, D., ROMEO, F., AND SANGIOVANNI-VINCEN- TELLI, A. 1985. Convergence and finite-time behavior of simulated annealing. In Proceedings of the 24th Conference on Deciswn and Control. pp. 761-767.
	79	MOGAKI, M., MIURA, C., AND TEEAI, H. 1987. Algorithm for block placement with size optimization technique by the linear programming approach. In Proceedings IEEE International Conference on Computer-Aided Design. pp. 80-83.
	80	MUROGA, S. 1982. VLSI System Design. John Wiley, New York, Chap. 9, pp. 365-395.
	81	Surendra Nahar , Sartaj Sahni , Eugene Shragowitz, Experiments with simulated annealing, Proceedings of the 22nd ACM/IEEE conference on Design automation, p.748-752, June 1985, Las Vegas, Nevada, United States [doi>10.1145/317825.317977]
	82	I. M. Oliver , D. J. Smith , J. R. C. Holland, A study of permutation crossover operators on the traveling salesman problem, Proceedings of the Second International Conference on Genetic Algorithms on Genetic algorithms and their application, p.224-230, October 1987, Cambridge, Massachusetts, United States
	83	OTTEN, R., AND VAN GINNEKIN, L. 1984. Floorplan design using simulated annealing. In Proceedrags of the IEEE International Conference on Computer-Aided Design. pp. 96-98.
	84	Michael Palczewski, Performance of algorithms for initial placement, Proceedings of the 21st conference on Design automation, p.399-404, June 25-27, 1984, Albuquerque, New Mexico, United States
	85	G. Persky , D. N. Deutsch , D. G. Schweikert, LTX - a system for the directed automatic design of LSI circuits, Proceedings of the 13th conference on Design automation, p.399-407, June 28-30, 1976, San Francisco, California, United States [doi>10.1145/800146.804840]
	86	Bryan Thomas Preas, Placement and routing algorithms for hierarchical integrated circuit layout, 1979
	87	Bryan T. Preas , Patrick G. Karger, Automatic placement a review of current techniques (tutorial session), Proceedings of the 23rd ACM/IEEE conference on Design automation, p.622-629, July 1986, Las Vegas, Nevada, United States
	88	PREAS, B., AND LORENZETTI, M. 1988. Placement, assignment and fioorplanning. In 20Physical Design Automation of VLSI Systems. The Benjamin Cummings Publishing Co., Menlo Park, Calif., Chap. 4, pp. 87-156.
	89	Neil R. Quinn, Jr., The placement problem as viewed from the physics of classical mechanics, Proceedings of the 12th conference on Design automation, p.173-178, January 1975
	90	QUINN, N. R., AND BREUER, M. A. 1979. A force directed component placement procedure for printed circuit boards. IEEE Trans. Circuits Syst. CAS-26 (June), 377-388.
	91	RANDELMAN, R. E., AND GREST, G. S. 1986. N-city traveling salesman problem: Optimization by simulated annealings. J. Stat. Phys. 45, 885-890.
	92	ROBSON, G. 1984. Automatic placement and routing of gate arrays. VLSI Design 5, 4, 35-43.
	93	ROMEO, F., AND SANGIOVANNI-VINCENTELLI, A. 1985. Convergence and finite time behavior of simulated annealing. In Proceedings of the 24th Conference on Decision and Control. pp. 761-767.
	94	ROMEO, F., SANGIOVANNI-VINCENTELLI, h., AND SECHEN, C. 1984. Research on simulated annealing at Berkeley. In Proceedings of the IEEE International Conference on Computer Design. pp. 652-657.
	95	Sartaj Sahni , Atul Bhatt, The complexity of design automation problems, Proceedings of the 17th conference on Design automation, p.402-411, June 23-25, 1980, Minneapolis, Minnesota, United States [doi>10.1145/800139.804562]
	96	SANGIOVANM-VINCENTELLI, A. 1987. Automatic layout of integrated circuits. In Design Systems for VLSI Circuzts, G. De Micheli, A. Sangiovanni-Vincentelli, and P. Antognetti, Eds. Kluwer Academic Publishers, Hingham, Mass., pp. 113-195.
	97	Daniel G. Schweikert, A 2-dimensional placement algorithm for the layout of electrical circuits., Proceedings of the 13th conference on Design automation, p.408-416, June 28-30, 1976, San Francisco, California, United States [doi>10.1145/800146.804841]
	98	D. G. Schweikert , B. W. Kernighan, A proper model for the partitioning of electrical circuits, Proceedings of the 9th workshop on Design automation, p.57-62, June 26-28, 1972 [doi>10.1145/800153.804930]
	99	SECHEN, C. 1986. The TimberWolf3.2 Standard Cell Placement and Global Routing Program. User's Guide for Version 3.2, Release 2.
	100	Carl Sechen, Chip-planning, placement, and global routing of macro/custom cell integrated circuits using simulated annealing, Proceedings of the 25th ACM/IEEE conference on Design automation, p.73-80, June 12-15, 1988, Atlantic City, New Jersey, United States
	101	SECHEN, C. 1988b. VLSI Placement and Global Routing Using S*mulated Annealing. Kluwer, B. V., Deventer, The Netherlands.
	102	SECHEN, C. AND LEE, K.-W. 1987. An improved simulated annealing algorithm for row-based placement. In Proceedings of the IEEE International Conference on Computer-Aided Design. pp. 478-481.
	103	Carl Sechen , Alberto Sangiovanni-Vincentelli, TimberWolf3.2: a new standard cell placement and global routing package, Proceedings of the 23rd ACM/IEEE conference on Design automation, p.432-439, July 1986, Las Vegas, Nevada, United States
	104	SHA, L. AND BLANK, T. 1987. ATLAS: A technique for layout using analytic shapes. In Proceedings of the IEEE International Conference on Computer-Aided Design. pp. 84-87.
	105	Lu Sha , Robert W. Dutton, An analytical algorithm for placement of arbitrarily sized rectangular blocks, Proceedings of the 22nd ACM/IEEE conference on Design automation, p.602-608, June 1985, Las Vegas, Nevada, United States [doi>10.1145/317825.317952]
	106	SHAHOOKAR, K., AND MAZUMDER, P. 1990. A genetic approach to standard cell placement using meta-genetic parameter optimization. IEEE Trans. Comput.-Aided Design 9, 5 (May), 500-511.
	107	Hiroshi Shiraishi , Fumiyasu Hirose, Efficient placement and routing techniques for master slice LSI, Proceedings of the 17th conference on Design automation, p.458-464, June 23-25, 1980, Minneapolis, Minnesota, United States [doi>10.1145/800139.804570]
	108	SOUKUP, J. 1981. Circuit layout. Proc. IEEE 69, 10 (Oct.), 1281 1304.
	109	ST~INBERG~ L. 1961. The backboard wiring problem: A placement algorithm. SIAM Rev. 3, 1 (Jan.), 37-50.
	110	James Edward Stevens, Jr., Fast heuristic techniques for placing and wiring printed circuit boards, 1972
	111	SuAms, P, AND KEDEM, G. 1987. Quadrisection: A new approach to standard cell layout. In Proceedings of the IEEE International Conference on Computer-Aided Design. pp. 474-477
	112	H Szu, Fast simulated annealing, AIP Conference Proceedings 151 on Neural Networks for Computing, p.420-425, March 1987, Snowbird, Utah, United States
	113	TSAY, R., KUH, E. AND Hsu, C. 1988. Module placement for large chips based on sparse linear equations. Int. J. Circuit Theory Appl. 16, 411-423.
	114	UEDA, K., KASAI, R., ANn SUDO, T. 1986. Layout strategy, standardization, and CAD tools. In Layout Design And Verification, T. Ohtsukl, Ed. Elsevier Science Pub. Co., New York, Chap. 1.
	115	VECCm, M. P., AND KIRKPATRICK, S. 1983. Global wiring by simulated annealing. IEEE Trans. Comput.-A~ded Design CAD-2, 215-222.
	116	VLSI SYSTEMS DESmN STAFF. 1987. Survey of automatic layout software. VLSI Syst. Design 8, 4, 78-89.
	117	VLSI SYSTEMS DESIGN STAFF. 1988. Survey of automatic IC layout software. VLSI Syst. Design 9, 4, 40-49
	118	WALSH, G. R. 1975. Methods of Optimization. John Wiley and Sons, New York.
	119	WroTE, S. R. 1984. Concepts of scale in simulated annealing. In Proceedings of the IEEE International Conference on Computer Design. pp. 646-651
	120	G. J. Wipfler , M. Wiesel , D. A. Mlynski, A combined force and cut algorithm for hierarchical VLSI layout, Proceedings of the 19th conference on Design automation, p.671-677, January 1982
	121	WONt, D. F., LEONG, H. W., AND LIu, C. L. 1986. Multiple PLA folding by the method of simulated annealing In Proceedtngs of the Custom IC Conference. pp. 351-355.
	122	WON% D. F., LEONG, H. W., AND LIu, C. L. 1988. Placement. In S~mulated Anneal~n~ for VLSI Design, Kluwer B.V., Deventer, The Netherlands, Chap. 2.