A dynamic and efficient representation of building-block layout

ABSTRACT

Dynamic layout representation is a key problem in developing a building block layout system. We have unified topological and geometrical representations, and developed efficient methods to update topological information after geometrical operations. The experimental results are very promising. This representation is the key for information flow in BEAR — a new building block layout system being developed at U. C. Berkeley.

REFERENCES

• 1: Sheldon B. Akers , James M. Geyer , Donald L. Roberts, IC mask layout with a single conductor layer, Proceedings of the 7th workshop on Design automation, p.7-16, June 22-25, 1970, San Francisco, California, United States [doi>10.1145/800160.805107]
• 2: K.D. Brinkmann and D. A. Mlynski, "Computer aided chip minimization for IC-layout," in Proc. of Int. Syrup. on Circuits and Systems, pp. 650-653, 1976.
• 3: R.L. Brooks, C. A. B. Smith, A. H. Stone, and W. T. Tutte, "The dissection of rectangles into squares," Duke Math. J., Vol. 7, pp. 312-340, 1940.
• 4: N.P. Chen, C. P. Hsu, and E. S. Kuh, "The Berkeley building-block (BBL) layout system for VLSI design," in Dig. Tech. Papers, IEEE Int. Conf. on Computer-Aided Des~'gn, pp. 40-41, 1983.
• 5: B.W. Colbry and J. Soukup, "Layout aspects of the VLSI microprocessor design," in Proc. of I98g IEEE Int. Syrup. on Circuits and Systems, pp. 1214-1228, 1982.
• 6: W.M. Dai, T. Asano, E. S. Kuh, "Routing region definition and ordering scheme for building-block layout," IEEE Trans. on Computer- Aided Design of ICs and Syat., Vol. CAD-4, No. 3, 1985.
• 7: W.M. Dad and E. S. Kuh, "Global spacing of building-block layout," to appear in Proc. of VLSI 1987, 1987.
• 8: K. Kani, H. Kawanishi, and A. Kishirnoto, "ROBIN: A building block LSI routing program," in Pros. of Int. Syrup. on Circuits and Systems, pp. 658-660, 1976.
• 9: E.S. Kuh, Ed., "The special issue on routing and microelectronics," IEEE Trans. on Computer-Aided Design of ICa and Syst., Vol. CAD-2, No. 4, Oct. 1983.
• 10: Ulrich Lauther, A min-cut placement algorithm for general cell assemblies based on a graph representation, Proceedings of the 16th Conference on Design automation, p.1-10, June 25-27, 1979, San Diego, CA, United States
• 11: U.P. Lauther, "Channel routing in a general cell environment," in Proc. of VLS{1985, 1985.
• 12: T. Ohtsuki, N. Sugiyama, and H. Kawanishi, "An optimization technique for integrated circuit layout design," in Proc. ICCST-Kyoto, pp. 67-68, Sept. t970.
• 13: T. Ohtsuki, Layout design and verification, Elsevier Science Publishers B. V., Amsterdam, The Netherlands, 1986
• 14: R.H.J.M. Otten, "Complexity and diversity in IC layout design," in Pros. of Int. Conf. on Circuits and Computers, pp. 764-767, 1980.
• 15: R. H. $. M. Otten, Layout Structures, IBM Research Report RC9657~ Thomas $. Watson Research Center, Yorktown Heights, N. Y., 1982.
• 16: J.K. Ousterhout, "Corner Stitching: A Data, Structuring Technique for VLSI Layout Tools," IEEE Trans. on Computer-Aided Design of IC~ and S~at., Vol. CAD-3, No. 1, 1984.
• 17: G. Persky , C. Enger , D. M. Selove, The Hughes Automated Layout System - automated LSI/VLSI layout based on channel routing, Proceedings of the 18th conference on Design automation, p.22-28, June 29-July 01, 1981, Nashville, Tennessee, United States
• 18: B. T. Preas , C. W. Gwyn, Methods for hierarchical automatic layout of custom LSI circuit masks, Proceedings of the 15th conference on Design automation, p.206-212, June 19-21, 1978, Las Vegas, Nevada, United States
• 19: B. T. Preas and C. S. Chow, "Placement and routing algorithms for topological integrated circuit layout," in Proe. of Int. Syrup. on Circuita and Syatems, pp. 17-20, 1985.
• 20: Bryan T. Preas , Patrick G. Karger, Automatic placement a review of current techniques (tutorial session), Proceedings of the 23rd ACM/IEEE conference on Design automation, p.622-629, July 1986, Las Vegas, Nevada, United States
• 21: J. Soukup , J. Royle, Cell map representation for hierarchical layout, Proceedings of the 17th conference on Design automation, p.591-594, June 23-25, 1980, Minneapolis, Minnesota, United States [doi>10.1145/800139.804591]
• 22: M. Wiesel and D. A. Mlynski, "An efficient channel model for building block LSI," in Proc. of Int. Syrup. on Circuits and Systems, pp. 118-121, 1981.
• 23: K. Zibert and R. Sa~i, "On computer aided hybrid circuit layout," in Proc. Int. Syrup. on Circuits and Systems, pp. 314-318, 1974.

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Design, Theory