A DSM design flow: putting floorplanning, technology-mapping, and gate-placement together

ABSTRACT

This paper presents an integrated design flowwhich combines floorplanning, technology mapping, andplacement using a dynamic programming algorithm. Theproposed design flow consists of five steps: maximum treesub-structure formation, levelized cluster tree construction,minimum area implementation using 2-D shape functions,critical path identification, and repeated application ofsimultaneous floorplanning, technology mapping and gateplacement along the timing critical paths. Experimentalresults obtained from an extensive set of benchmarksdemonstrate the effectiveness of the proposed flow.

REFERENCES

• CP92: 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
• CLB94: Jason Cong , Zheng Li , Rajive Bagrodia, Acyclic multi-way partitioning of Boolean networks, Proceedings of the 31st annual conference on Design automation, p.670-675, June 06-10, 1994, San Diego, California, United States [doi>10.1145/196244.196609]
• GJ79: M. R. Garey and D. S. Johnson, Computers and Intractability, Bell Telephone Lab Inc., 1979.
• HS96: Gary D. Hachtel , Fabio Somenzi, Logic Synthesis and Verification Algorithms, Kluwer Academic Publishers, Norwell, MA, 2000
• IPFC93: S. Iman, M. Pedram, C. Fabian, and J. Cong, "Finding ,unidirectional cuts based on physical partitioning and logic restructing," 4th ACM/SIGDA Physical Design Workshop, pages 187-198, April 1993.
• Ke87: 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]
• Le82: T. Lengauer, "Upper and lower bounds on the complexity of the mm-cut linear arrangement problem on trees," In SIAM J. Alg. Disc. Meth., vol. 3, no. 1, pages 99-113, March 1982.
• LSP97: 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
• LSP98: J. Lou, A. H. Salek, and M. Pedram,"An integrated flow for technology remapping and placement of sub-half-micron circuits," In Proceedings of Axa and South Pacific Design Automation Conference, pages 295-300, February 1998.
• MFNK96: H. Murata, K. Fujiyoshi, S. Nakatake, and Y. Kajitani,"VLSI module placement based on rectangle packing by the sequence-pair," IEEE. Transactions on Computer-Aided Design of Integrated Circuits and Systems, 15(12), pages 1518-1524, December 1996.
• NFMK96: Shigetoshi Nakatake , Kunihiro Fujiyoshi , Hiroshi Murata , Yoji Kajitani, Module placement on BSG-structure and IC layout applications, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.484-491, November 10-14, 1996, San Jose, California, United States
• PK92: M. Pedram and E. Kuh "Bear-FP: A Robust Framework For Floorplanning," In International Journal of High Speed Electronics, Vol. 3, No. 1, pages 137-170, 1992.
• RU89: Richard L. Rudell , Alberto Sangiovanni-Vincentelli, Logic synthesis for vlsi design, 1989
• Sh93: Naveed A. Sherwani, Algorithms for VLSI Physical Design Automation, Kluwer Academic Publishers, Norwell, MA, 1993
• SLP98: A. H. Salek, J. Lou, and M. Pedram "Simultaneous floorplanning, technology mapping, and gate-placement for deep submicron designs," University of Southern California Technical Report, 1997.
• SSLM92: E. M. Sentovich, K. J. Singh, L. Lavagno, C. Moon, R. Murgai, A.Saldanha, H. Savoj, P. R. Stephan, R. K. Brayton, and A. Sangiovanni- Vincentelli" SIS: A system for sequential circuit synthesis", Memorandum No UCB/ERL M92/41 ,Electronics Research Laboratory, College of Engineering, University of California, Berkeley, CA 94720, May 1992.
• St83: Larry Stockmeyer, Optimal orientations of cells in slicing floorplan designs, Information and Control, v.57 n.2-3, p.91-101, May/June 1983 [doi>10.1016/S0019-9958(83)80038-2]
• TMBW90: Hervé J. Touati , Cho W. Moon , Robert K. Brayton , Albert Wang, Performance-oriented technology mapping, Proceedings of the sixth MIT conference on Advanced research in VLSI, p.79-97, March 1990, Boston, Massachusetts, United States
• Ya85: 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]

INDEX TERMS

Primary Classification:
  J. Computer Applications

Additional Classification:
  C. Computer Systems Organization

  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Dynamic programming

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance, Theory