Floorplanning of pipelined array modules using sequence pairs

ABSTRACT

Floorplanning individual pipelined array modules of a larger overall die can yield beneficial results. Critical paths in every pipeline stage of a pipelined design are roughly equivalent after synthesis. The inability of synthesis tools to predict without full placement both wire congestion and the distance traveled by a wire or wires between consecutive registers are the greatest causes of additional delay and area during place and route. This paper will detail a floorplanning methodology for pipelined arrays that is used to regulate wire congestion and the shortest/longest distances travelled by wire(s) between consecutive registers. A new wire length metric for pipelined arrays will be discussed that attempts to measure the distance travelled by wire(s) between registers. A new move set for floorplanning pipelined arrays using sequence pairs will also be introduced that significantly reduces the annealing design space from previous work. These two contributions when used together have produced up to 10% faster clock periods, 12% smaller designs, and 85% less area used to fix hold time violations in a placed and routed 0.18 μm design.

REFERENCES

• 1: Jim Crenshaw , Majid Sarrafzadeh , Prithviraj Banerjee , Pradeep Prabhakaran, An Incremental Floorplanner, Proceedings of the Ninth Great Lakes Symposium on VLSI, p.248, March 04-06, 1999
• 2: Yung-Ming Fang , D. F. Wong, Simultaneous functional-unit binding and floorplanning, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.317-321, November 06-10, 1994, San Jose, California, United States
• 3: H. Murata, K. Fujiyoshi, S. Nakatake, Y. Kajitani, "VLSI Module Placement Based on Rectangle Packing by the Sequence Pair," IEEE Trans. on Computer Aided Design of Integrated Circuits and Systems, vol. 15, no. 12, pp. 1518--1524, December 1996.
• 4: 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]
• 5: S. Wimer, I. Koren, I. Cederbai,. "Optimal Aspect Ratios of Building Blocks in VLSI," IEEE Trans. on Computer Aided Design, vol. 8, no. 2, pp. 139--145, December 1996.
• 6: Hiroshi Murata , Ernest S. Kuh, Sequence-pair based placement method for hard/soft/pre-placed modules, Proceedings of the 1998 international symposium on Physical design, p.167-172, April 06-08, 1998, Monterey, California, United States [doi>10.1145/274535.274560]
• 7: Pravin M. Vaidya, A new algorithm for minimizing convex functions over convex sets, Mathematical Programming: Series A and B, v.73 n.3, p.291-341, June 30, 1996 [doi>10.1007/BF02592216]
• 8: F. Y. Young, C. C. N. Chu, W.S. Luk, and Y. C. Wong, "Handling Soft Modules in General Nonslicing Floorplan Using Lagrangian Relaxation," in IEEE Trans. on Computer Aided Design of Integrated Circuits and Systems, vol. 20, no. 5, pp. 687--692, May 2001.
• 9: http://www.cse.ucsc.edu/research/surf/GSRC/progress.html#V
• 10: Bruce Schneier, Applied Cryptography, Second Edition, John Wiley & Sons, Inc., 1996, pp. 319--325.
• 11: R. G. Gallager "Low Density Parity Check Nodes," IRE Trans. Inform. Theory, Jan. 1962, pp. 21--28.
• 12: "Design Compiler Reference Manual", Synopsys Inc., 1999.
• 13: "Dolphin 2.0 Online Help", Monterey Design Systems, December 2000.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Layout

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Placement and routing

General Terms:
Algorithms, Design

Keywords:
floorplan, pipelined array, sequence pair