ORCA a sea-of-gates place and route system

ABSTRACT

Sea-of-gates is becoming an important design style for Application Specific Integrated Circuits (ASICs). The sea-of-gates technology offers more flexible placement and routing options not available in gate arrays. Very few systems are available today that can automatically layout sea-of-gates and none of these systems effectively use the features available in sea-of-gates architecture. ORCA is a place and route system for sea-of-gates, whose objective is to produce the highest density layout by fully exploiting the inherent features of this new design style. The ORCA system starts with a module generator which preprocesses memory arrays and other logic with a regular structure to form high density macros. The remaining logic is clustered together to form flexible macros, which we call porous. The porous macro-cells allow global routing to pass through the macro instead of detouring around its perimeter. The porous macros are dynamically shaped and resized by interaction with global wiring analysis. Finally, a general channelless area router has been developed to address the multiple layers of interconnect and routing areas which will be dominantly over-the-cell. Due to the large size of the problem (e.g. 100,000 gates), the placement and routing algorithms are hierarchical.

REFERENCES

• 1: A. Hui et al. A 4.1k gates double metal hcmos sea of gates array. Proc. IEEE CICC, : 15-17, May 1985.
• 2: B.W. Kernighan and S. Lin. An efficient heuristic procedure for partitioning graphs. Bell Systems Technical Journal, 49:291-307, Feb 1970.
• 3: C. M. Fiduccia , R. M. Mattheyses, A linear-time heuristic for improving network partitions, Proceedings of the 19th conference on Design automation, p.175-181, January 1982
• 4: A.E. Dunlop and B. W. Kernighan, A procedure for Placement of Standard VLSI Circuits. IEEE Trans. on Computer-Aided Design, CAD-4:92-98, 1985.
• 5: 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]
• 6: C. Lee. An algorithm for path connection and its applications. IRE Trans. Electronic Computers, EC-10:346-365, 1961.
• 7: K. A. Chen , M. Feuer , K. H. Khokhani , N. Nan , S. Schmidt, The chip layout problem: An automatic wiring procedure, Proceedings of the 14th conference on Design automation, p.298-302, January 1977
• 8: Ravi Nair. A simple yet effective technique for global wiring. IEEE Trans. on Computer-Aided Design, CAD-6:165-172, 1987.
• 9: M. Burstein and R. Pelavin. Hierarchical wire routing. IEEE Trans. on Computer-Aided Design, CAD-2:223-234, 1983.
• 10: Jr. J. B. Kruskal. On the shortest spanning subtree of a graph and the traveling salesman problem. Proc. Amer. Math. Soc., 7:48-50, 1956.
• 11: D. Harrison et al. Data management and graphics editing in the Berkeley design environment. Proc. ICCAD, Nov 1986.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Gate arrays

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

General Terms:
Algorithms, Design, Performance