Delay-optimal simultaneous technology mapping and placement with applications to timing optimization

ABSTRACT

Technology mapping and placement have significant impact on the delays in standard cell based very large scale integrated (VLSI) circuits. Traditionally, these steps are applied separately to optimize delays, possibly since efficient algorithms that allow the simultaneous exploration of the mapping and placement solution spaces are unknown. In this paper, we present an exact polynomial time algorithm for delay-optimal placement of a tree and extend the same to simultaneous technology mapping and placement for optimal delay in the tree. We extend the algorithm by employing Lagrangian relaxation technique, which assesses the timing criticality of paths beyond a tree, to optimize the delays in directed acyclic graphs (DAGs). Experimental results on benchmark circuits in a 70 nm technology show that our algorithms improve timing significantly with remarkably less run-times compared to a competitive approach of iterative conventional timing driven mapping and multi-level placement.

REFERENCES

• 1: K. Keutzer, DAGON: technology binding and local optimization by DAG matching, Proceedings of the 24th ACM/IEEE conference on Design automation, p.341-347, June 28-July 01, 1987, Miami Beach, Florida, United States [doi>10.1145/37888.37940]
• 2: K. Chaudhary , M. Pedram, A near optimal algorithm for technology mapping minimizing area under delay constraints, Proceedings of the 29th ACM/IEEE conference on Design automation, p.492-498, June 08-12, 1992, Anaheim, California, United States
• 3: Massoud Pedram , Narasimha Bhat, Layout driven technology mapping, Proceedings of the 28th conference on ACM/IEEE design automation, p.99-105, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.127635]
• 4: Jinan Lou , Amir H. Salek , Massoud Pedram, An exact solution to simultaneous technology mapping and linear placement problem, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.671-675, November 09-13, 1997, San Jose, California, United States
• 5: Joey Y. Lin , Ashok Jagannathan , Jason Cong, Placement-driven technology mapping for LUT-based FPGAs, Proceedings of the 2003 ACM/SIGDA eleventh international symposium on Field programmable gate arrays, February 23-25, 2003, Monterey, California, USA [doi>10.1145/611817.611836]
• 6: Wilsin Gosti , Sunil P. Khatri , Alberto L. Sangiovanni-Vincentelli, Addressing the timing closure problem by integrating logic optimization and placement, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
• 7: D. Pandini, L. T. Pileggi, and A. J. Strojwas, "Global and local congestion optimization in technology mapping," IEEE Trans. CAD, vol. 22, no. 4, pp. 498--505, Apr. 2003.
• 8: X. Wang and S. Burns, "Technology mapping using a fixed delay and variable area-power model," in Proc. IWLS, June 2007.
• 9: Jason Cong , Joseph R. Shinnerl , Min Xie , Tim Kong , Xin Yuan, Large-scale circuit placement, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.10 n.2, p.389-430, April 2005 [doi>10.1145/1059876.1059886]
• 10: Michael J. Fischer , Michael S. Paterson, Optimal tree layout (Preliminary Version), Proceedings of the twelfth annual ACM symposium on Theory of computing, p.177-189, April 28-30, 1980, Los Angeles, California, United States [doi>10.1145/800141.804665]
• 11: S. Chatterjee, Z. Wei, A. Mischenko, and R. Brayton, "A linear time algorithm for optimum tree placement," in Proc. IWLS, June 2007.
• 12: Mihalis Yannakakis, A polynomial algorithm for the min-cut linear arrangement of trees, Journal of the ACM (JACM), v.32 n.4, p.950-988, Oct. 1985 [doi>10.1145/4221.4228]
• 13: E. M. Sentovich, "SIS: A system for sequential circuit synthesis," Memorandum No. UCB/ERL M92/41, May 1992.
• 14: Tony Chan , Jason Cong , Kenton Sze, Multilevel generalized force-directed method for circuit placement, Proceedings of the 2005 international symposium on Physical design, April 03-06, 2005, San Francisco, California, USA [doi>10.1145/1055137.1055177]
• 15: M. Bazaraa, H. Sherali, and C. Shetty, Nonlinear Programming: Theory and Algorithms, 2nd ed. Wiley, New York, NY, 2003.
• 16: "Berkeley predictive technology model," http://www-device.eecs.berkeley.edu/~ptm/download.html.
• 17: Alexander Marquardt , Vaughn Betz , Jonathan Rose, Timing-driven placement for FPGAs, Proceedings of the 2000 ACM/SIGDA eighth international symposium on Field programmable gate arrays, p.203-213, February 10-11, 2000, Monterey, California, United States [doi>10.1145/329166.329208]