Computer Aids for VLSI Design
Steven M. Rubin
Copyright © 1994
Chapter 3: Representation
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.
- When is the array a useful structure?
- Besides relieving the problem of fragmented memory, what is another advantage
of clustering memory allocation into separate arenas?
- How could a pointer-based representation remain identical on disk and in memory?
- What is the disadvantage of having the database manage change control?
- 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?
- Would sparse matrix representations work for VLSI geometry?
Why or why not?
- How would you extend corner stitching to handle arbitrary angles?
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
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,
Leinwand, Sany M., "Integrated Design Environment," unpublished manuscript,
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,
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
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
Zippel, Richard, "An Expert System for VLSI Design," Proceedings IEEE
International Symposium on Circuits and Systems, 191-193, May 1983.