Multi-stack optimization for data-path chip (microprocessor) layout

ABSTRACT

As data-path chips such as microprocessors and RISC chips become more complex, multiple stacks of data-path macros are required to implement the entire data-path. The physical decomposition of a chip into a single data-path stack, and control logic of random logic as in the past is not always feasible. This paper describes a special multi-stack structure, optimization techniques and algorithms to partition, place and wire the data-path macros in the form of the multi-stack structure, taking into account the connectivity of the entire chip logic (data-path, control logic, chip drivers, on-chip memory). The overall objective is: (1) to fit the circuits within the chip, (2) to ensure data-path wireability, including stack to random logic wireability, and (3) to minimize wire lengths for wireability and timing. A tool for automatic multi-stack optimization has been implemented and applied successfully to layout some high density data-path chips.

REFERENCES

• Cra86: J. Crawford, Architecture of the intel 80386, Proc. IEEE ICCD, pp. 154-160, October 1986.
• KerLin70: B. W. Kernighan and S. Lin, An Efficient Heuristics for Partitioning Graphs, Bell System Technical Journal, 49, (2), pp. 291-307, 1970.
• KirGel83: S. Kirkpatrick, C. Gelatt Jr., and M. Veeehi, Optimization by simulated annealing, Science, Vol. 220, pp, 671-680, May 1983.
• Kri84: B. Krishnamurthy, An improved min-cut algorithm for partitioning VLSI networks, IEEE Trans. on Computers, Vol. C-33, pp.438-446, May 1984.
• LukDea89b: W.K. Luk, A. Dean and J. Mathews, Partitioning and floor-planning for data-path chip (microprocessor) layout, IBM Research Report, 1989. (to appear)
• LukSip87: W.K. Luk, P. Sipala, M. Tamminen, D. Tang, L. Woo and C.K. Wong, A hierarchical global wiring algorithm for custom chip design, IEEE Trans. on CAD, Vol. CAD-6, pp.518-533, July 1987.
• MeaCon80: Carver Mead , Lynn Conway, Introduction to VLSI Systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1979
• OngCha86: S. Ong, H.H. Chao, et. al., Micro-370, A 32-bit single chip microprocessor, ISSCC Digest of Technical Papers, pp. 28-29, 1986.
• SecSan85: C. Sechen and A. Sangiovanni-Vincentelli, The TimberWolf placement and routing package, IEEE Journal of Solid- State Circuits, Vol. 20, No. 2, p. 510, April 1985.

INDEX TERMS

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

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Optimization
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: VLSI (very large scale integration)

General Terms:
Algorithms, Design, Performance