Section 7 of 7

3.7 Summary

This chapter has discussed the representation of VLSI design. The first half of the chapter covered basic representational needs for any design task. The remainder of the chapter concentrated on the specific representations for circuitry: hierarchy, views, connectivity, and geometry. Implementation of a complete VLSI design database is complex but provides the necessary basis for the algorithms described in the rest of this book.

Questions

1. When is the array a useful structure?
2. Besides relieving the problem of fragmented memory, what is another advantage of clustering memory allocation into separate arenas?
3. How could a pointer-based representation remain identical on disk and in memory?
4. What is the disadvantage of having the database manage change control?
5. To implement wires the ends of which do not extend beyond their connection point, some systems pull the connection points toward the center and then compute a normal wire that extends its ends by one-half of its width. What problems might this approach cause?
6. Would sparse matrix representations work for VLSI geometry? Why or why not?
7. How would you extend corner stitching to handle arbitrary angles?

References

• Arnold, John E., "The Knowledge-Based Test Assistant's Wave/Signal Editor: An Interface for the Management of Timing Constraints," Proceedings 2nd Conference on Artificial Intelligence Applications, 130-136, December 1985.
• Atwood, Thomas M., "An Object-Oriented DBMS for Engineering Design Support Applications," Proceedings Compint Conference, Montreal, 299-307, September 1985.
• Barton, E. E. and Buchanan, I., "The Polygon Package," Computer Aided Design, 12:1, 3-11, January 1980.
• Batali, J. and Hartheimer, A., "The Design Procedure Language Manual," AI Memo 598, Massachusetts Institute of Technology, 1980.
• Baumgart, Bruce Guenther, Geometric Modeling for Computer Vision, PhD dissertation, Stanford University, August 1974.
• Borning, Alan, "ThingLab-A Constraint-Oriented Simulation Laboratory," PhD dissertation, Stanford University, July 1979.
• Borriello, Gaetano, "WAVES: A Digital Waveform Editor for the Design, Documentation, and Specification of Interfaces," unpublished document.
• Brown, Harold; Tong, Christofer; and Foyster, Gordon, "Palladio: An Exploratory Environment for Circuit Design," IEEE Computer, 16:12, 41-56, December 1983.
• Bryant, Randal, "Preface", Proceedings 3rd Caltech Conference on VLSI (Bryant ed), Computer Science Press, v-viii, March 1983.
• Clark, G. C. and Zippel, R. E., "Schema: An Architecture for Knowledge Based CAD," ICCAD '85, 50-52, November 1985.
• Deutsch, L. P. and Bobrow, D. G., "An Efficient Incremental Automatic Garbage Collector," CACM, 19:9, 522-526, September 1976.
• Gosling, James, Algebraic Constraints, PhD dissertation, Carnegie-Mellon University, CMU-CS-83-132, May 1983.
• Guttman, Antonin, "R-Trees: A Dynamic Index Structure for Spatial Searching," ACM SIGMOD, 14:2, 47-57, June 1984.
• Karplus, Kevin, "Exclusion Constraints, a new application of Graph Algorithms to VLSI Design," Proceedings 4th MIT Conference on Advanced Research in VLSI (Leiserson, ed), 123-139, April 1986.
• Kedem, Gershon, "The Quad-CIF Tree: A Data Structure for Hierarchical On-Line Algorithms," Proceedings 19th Design Automation Conference, 352-357, June 1982.
• Knuth, Donald E., The Art of Computer Programming, Volume 1/Fundamental Algorithms, Addison-Wesley, Reading, Massachusetts, 1969.
• Lanfri, Ann R., "PHLED45: An Enhanced Version of Caesar Supporting 45 degree Geometries," Proceedings 21st Design Automation Conference, 558-564, June 1984.
• Leinwand, Sany M., "Integrated Design Environment," unpublished manuscript, April 1984.
• McCreight, E.M., "Efficient Algorithms for Enumerating Intersecting Intervals and Rectangles," Xerox Palo Alto Research Center, CSL-80-9, 1980.
• Mead, C. and Conway, L., Introduction to VLSI Systems, Addison-Wesley, Reading, Massachusetts, 1980.
• Nelson, Greg, "Juno, a constraint-based graphics system," Computer Graphics, 19:3, 235-243, July 1985.
• Newell, Martin E. and Sequin, Carlo H., "The Inside Story on Self-Intersecting Polygons," Lambda, 1:2, 20-24, 2nd Quarter 1980.
• Newman, William M. and Sproull, Robert F., Principles of Interactive Computer Graphics, 2nd Edition, McGraw-Hill, New York, 1979.
• Ousterhout, J. K., "Caesar: An Interactive Editor for VLSI Layouts," VLSI Design, II:4, 34-38, 1981.
• Ousterhout, John K., "Corner Stitching: A Data-Structuring Technique for VLSI Layout Tools," IEEE Transactions on CAD, 3:1, 87-100, January 1984.
• Reddy, D. R. and Rubin, Steven M., "Representation of Three-Dimensional Objects," Carnegie-Mellon University Department of Computer Science, Report CMU-CS-78-113, April 1978.
• Schediwy, Richard R., A CMOS Cell Architecture and Library, Masters thesis, University of Calgary Department of Computer Science, 1987.
• Sproull, Robert F. and Sutherland, Ivan E., Asynchronous Systems II: Logical Effort and Asynchronous Modules, to be published.
• Stamos, James W., "A Large Object-Oriented Virtual Memory: Grouping Strategies, Measurements, and Performance," Xerox PARC SCG-82-2, May 1982.
• Steele, G. L. Jr., The Definition and Implementation of a Computer Programming Language Based on Constraints, PhD dissertation, Massachusetts Institute of Technology, August 1980.
• Sussman, Gerald Jay and Steele, Guy Lewis, "CONSTRAINTS-A Language for Expressing Almost-Hierarchical Descriptions," Artificial Intelligence, 14:1, 1-39, August 1980.
• Sutherland, Ivan E., Sketchpad: A Man-Machine Graphical Communication System, PhD dissertation, Massachusetts Institute of Technology, January 1963.
• Weinreb, Daniel and Moon, David, "Flavors: Message Passing in the Lisp Machine," MIT Artificial Intelligence Lab Memo #602, November 1980.
• Whitney, Telle, Hierarchical Composition of VLSI Circuits, PhD dissertation, California Institute of Technology Computer Science, report 5189:TR:85, 1985.
• Zippel, Richard, "An Expert System for VLSI Design," Proceedings IEEE International Symposium on Circuits and Systems, 191-193, May 1983.

Previous

Table of Contents

Next

Steven M. Rubin

Static Free Software