Placement is a critical component in the physical synthesis design flow of large-scale integrated circuits and is a major contributor to timing closure results. It is often run multiple times during various stages of the physical synthesis flow. In addition, circuit sizes that need to be handled by placement algorithms are steadily increasing to over tens of millions of modules. Hence, it is necessary to have efficient and scalable placement algorithms that can produce high-quality solutions satisfying a variety of design objectives.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
R. Barrett et al. Templates for the Solution of Linear Systems: Building Blocks for Itera- tive Methods. SIAM, 2nd edition, 1994
T. Chan, J. Cong, T. Kong, and J. Shinnerl. Multilevel optimization for large-scale circuit placement. In Proc. IEEE/ACM Int. Conf. Comput.-Aided Design, pages 171-176, 2000
T. Chan, J. Cong, and K. Sze. Multilevel generalized force-directed method for circuit placement. In Proc. Int. Symp. Phys. Design, pages 185-192, 2005
T. F. Chan, J. Cong, J. R. Shinnerl, K. Sze, and M. Xie. mPL6: Enhanced multilevel mixed-size placement. In Proc. Int. Symp. Phys. Design, pages 212-214, 2006
C. C. Chang, J. Cong, and X. Yuan. Multi-level placement for large-scale mixed-size IC designs. In Proc. Asia and South Pacific Design Automat. Conf., pages 325-330, 2003
J. Cong and M. Xie. A robust detailed placement for mixed-size ic designs. In Proc. Asia and South Pacific Design Automat. Conf., pages 188-194, 2006
S. Goto. An efficient algorithm for the two-dimensional placement problem in electrical circuit layout. IEEE Trans. Circuits and Systems, CAS-28(1):12-18, 1981
K. M. Hall. An r-dimensional quadratic placement algorithm. Manage. Sci., 17:219-229, 1970
B. Hu and M. Marek-Sadowska. Fine granularity clustering for large scale placement problems. In Proc. Int. Symp. Phys. Design, pages 67-74, 2003
B. Hu and M. Marek-Sadowska. Multilevel fixed-point-addition-based VLSI placement. IEEE Trans. Comput.-Aided Design, 24(8):1188-1203, August 2005
A. B. Kahng, S. Reda, and Q. Wang. APlace: A general analytic placement framework. In Proc. Int. Symp. Phys. Design, pages 233-235, 2005
A. B. Kahng, S. Reda, and Q. Wang. Architecture and details of a high quality, largescale analytical placer. In Proc. IEEE/ACM Int. Conf. on Comput.-Aided Design, pages 890-897, 2005
A. B. Kahng, P. Tucker, and A. Zelikovsky. Optimization of linear placements for wire- length minimization with free sites. In Proc. Asia and South Pacific Design Automat. Conf., pages 241-244, 1999
A. B. Kahng and Q. Wang. Implementation and extensibility of an analytic placer. IEEE Trans. Comput.-Aided Design, 24(5):734-747, May 2005
D. S. Kershaw. The Incomplete Cholesky-Conjugate Gradient method for the iterative solution of systems of linear equations. J. Comp. Phys., 26:43-65, 1978.
F. Mo, A. Tabbara, and R. Brayton. A force-directed macro-cell placer. In Proc. IEEE/ACM Intl. Conf. on Computer-Aided Design, pages 177-180, 2000
H. Murata, K. Fujiyoshi, S. Nakatake, and Y. Kajitani. VLSI module placement based on rectangle-packing by the sequence pair. IEEE Trans. Comput.-Aided Design, 15 (12):1518-1524, December 1996
G.-J. Nam, S. Reda, C. J. Alpert, P. G. Villarrubia, and A. B. Kahng. A fast hierarchical quadratic placement algorithm. IEEE Trans. Comput.-Aided Design, 25(4):678-691, April 2006
M. Pan, N. Viswanathan, and C. Chu. An efficient and effective detailed placement algorithm. In Proc. IEEE/ACM Intl. Conf. on Comput.-Aided Design, pages 48-55, 2005
J. A. Roy, S. N. Adya, D. A. Papa, and I. L. Markov. Min-cut floorplacement. IEEE Trans. Comput.-Aided Design, 25(7):1313-1326, July 2006
T. Taghavi, X. Yang, B.-K. Choi, M. Wang, and M. Sarrafzadeh. Dragon2005: Largescale mixed-size placement tool. In Proc. Intl. Symp. Phys. Design, pages 245-247, 2005
N. Viswanathan and C. C.-N. Chu. FastPlace: Efficient analytical placement using cell shifting, iterative local refinement and a hybrid net model. IEEE Trans. Comput.-Aided Design, 24(5):722-733, May 2005
N. Viswanathan, M. Pan, and C. Chu. Fastplace 2.0: An efficient analytical placer for mixed-mode designs. In Proc. Asia and South Pacific Design Automat. Conf., pages 195-200, 2006
N. Viswanathan, M. Pan, and C. Chu. Fastplace 3.0: A fast multilevel quadratic placement algorithm with placement congestion control. In Proc. Asia and South Pacific Design Automat. Conf., pages 135-140, 2007
N. Viswanathan, M. Pan, and C. Chu. FastPlace: An Analytical Placer for Large-scale VLSI Circuits. url=http://www.public.iastate.edu/̃nataraj/FastPlace.html.
J. Vygen. Algorithms for large-scale flat placement. In Proc. ACM/IEEE Design Automat. Conf., pages 746-751, 1997
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2007 Springer Science+Business Media, LLC
About this chapter
Cite this chapter
Viswanathan, N., Pan, M., Chu, C. (2007). FastPlace: An Efficient Multilevel Force-Directed Placement Algorithm. In: Nam, GJ., Cong, J. (eds) Modern Circuit Placement. Series on Integrated Circuits and Systems. Springer, Boston, MA. https://doi.org/10.1007/978-0-387-68739-1_8
Download citation
DOI: https://doi.org/10.1007/978-0-387-68739-1_8
Publisher Name: Springer, Boston, MA
Print ISBN: 978-0-387-36837-5
Online ISBN: 978-0-387-68739-1
eBook Packages: EngineeringEngineering (R0)