Estimating the storage requirements of the rectangular and L-shaped corner stitching data structures

ABSTRACT

This paper proposes a technique for estimating the storage requirements of the Rectangular Corner Stitching (RCS) data structure [Ousterhout 1984] and the L-shaped Corner Stitching (LCS) data structure [Mehta and Blust 1997] on a given circuit by studying its (the circuit's) geometric properties. This provides a method for estimating the storage requirements of a circuit without having to implement the corner stitching data structure, which is a tedious and time-consuming task. This technique can also be used to estimate the amount of space saved by employing the LCS data structure over the RCS data structure on a given circuit.

REFERENCES

• 1: Ku, L. 1993. Algorithms for incremental bin-packing. Tech. Rep. Project 16, DISCS. National University of Singapore, Singapore.
• 2: MARPLE, D., SMULDERS, M., AND HEGEN, g. 1990. Tailor: A layout system based on trapezoidal corner stitching. IEEE Trans. CAD 9, 1 (Jan), 66-90.
• 3: MEHTA, D. P. 1993. Estimating the storage requirements of the rectangular and L-shaped corner stitching data structures. CS93-01. University of Tennessee Space Institute, Tullahoma, TN.
• 4: MEHTA, D. P. 1998. CLOTH MEASURE: A software tool for estimating the memory requirements of corner stitching data structures. Int. J. Comput. Aided VLSI Des. 7, 4 (Dec.), 425-436.
• 5: MEHTA, D. P. AND BLUST, G. 1997. Corner stitching for simple rectilinear shapes. IEEE Trans. CAD 16 (Feb.), 186-198.
• 6: OUSTERHOUT, J. K. 1984. Corner stitching: A data structuring technique for VLSI layout tools. IEEE Trans. CAD 3, 1 (Jan.), 87-100.
• 7: John K. Ousterhout , Gordon T. Hamachi , Robert N. Mayo , Walter S. Scott , George S. Taylor, Magic: A VLSI layout system, Proceedings of the 21st conference on Design automation, p.152-159, June 25-27, 1984, Albuquerque, New Mexico, United States
• 8: SEQUIN, C. H. AND FA~ANHA, H. D. S. 1993.Corner stitched tiles with curved boundaries. IEEE Trans. CAD 12, 1 (Jan.), 47-58.

INDEX TERMS

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

Additional Classification:
  E. Data
  E.2 DATA STORAGE REPRESENTATIONS
      Subjects: Linked representations

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

General Terms:
Algorithms

Keywords:
L-shapes, corner stitching, data structures, memory requirements analysis, rectangle, retilinear polygons