Hierarchical VLSI design systems based on attribute grammars

ABSTRACT

The attribute grammar technique used for design of structure editors is suggested as a foundation for building <i>hierarchical incremental design editors</i> for VLSI circuits. The usual definition of attribute grammars is extended: the cycles that occur in VLSI design make us come to terms with circular attributes (under conditions that guarantee their least fixpoint solution, namely that the functions be monotone and yield values over a lattice of bounded height). Many interesting VLSI design problems can be cast in attributes meeting this condition, for example, timing verification, logic simulation, power dissipation, and adherence to clocking disciplines, to name a few. As an illustration of the formalism, attributes are presented which solve the All Bidirectional Edges problem that labels the direction of information flow in a circuit. The incremental evaluation algorithm of [Rep82] is extended to handle fixpoint computations of circular attributes by noting that when the dependency graph is broken into its strongly connected components, a directed acyclic graph results. The worst-case running time of the resulting incremental evaluation algorithm is bounded by <i>O</i> (<i>hk</i> |AFFECTEDSCC|), where <i>h</i> is the height of the largest attribute lattice, <i>k</i> the largest number of attributes in any one strongly connected component, and |AFFECTEDSCC| the number of strongly connected components affected by a single modification to the design tree.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: Gregor V. Bochmann, Semantic evaluation from left to right, Communications of the ACM, v.19 n.2, p.55-62, Feb. 1976 [doi>10.1145/359997.359999]
• 3: {Bro84} S. D. Brookes, Reasoning About Synchronous Systems, <i>Research Report CMU-CS-84-145,</i>, Mar. 1984.
• 4: R. E. Bryant, A SWITCH-LEVEL SIMULATION MODEL FOR INTEGRATED LOGIC CIRCUITS, Massachusetts Institute of Technology, Cambridge, MA, 1981
• 5: {Bry85} R. E. Bryant, Symbolic Verification of MOS Circuits, <i>1985 Chapel Hill Conference on Very Large Scale Integration,,</i> May 1985, pp. 419--438.
• 6: {ChM83} M. C. Chen and C. A. Mead, A Hierarchical Simulator Based on Formal Semantics, <i>Third Caltech Conference on Very Large Scale Integration,</i>, 1983, pp. 207--223.
• 7: Alan Demers , Thomas Reps , Tim Teitelbaum, Incremental evaluation for attribute grammars with application to syntax-directed editors, Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.105-116, January 26-28, 1981, Williamsburg, Virginia [doi>10.1145/567532.567544]
• 8: {Fit82} D. T. Fitzpatrick, <i>MEXTRA: A Manhatten Circuit Extractor,</i> University of California at Berkely, Memorandum No. UCB/ERL M82/42, Jan. 1982.
• 9: Mehdi Jazayeri , William F. Ogden , William C. Rounds, The intrinsically exponential complexity of the circularity problem for attribute grammars, Communications of the ACM, v.18 n.12, p.697-706, Dec. 1975 [doi>10.1145/361227.361231]
• 10: Gregory F. Johnson , Charles N. Fischer, Non-syntactic attribute flow in language based editors, Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.185-195, January 25-27, 1982, Albuquerque, Mexico [doi>10.1145/582153.582174]
• 11: Gregory F. Johnson , C. N. Fischer, A meta-language and system for nonlocal incremental attribute evaluation in language-based editors, Proceedings of the 12th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.141-151, January 14-16, 1985, New Orleans, Louisiana, United States [doi>10.1145/318593.318627]
• 12: Kevin Karplus, Formal Model of MOS Clocking Disciples, Cornell University, Ithaca, NY, 1984
• 13: {Kas80} Kastens, Ordered Attribute Grammars, <i>Acta Informatica 13,</i> 3 (1980), pp. 229--256.
• 14: {Knu68a} D. E. Knuth, Semantics of Context-free Languages, <i>Math. Syst. Theory 2,</i> 2 (June 1968), pp. 127--145.
• 15: Donald Ervin Knuth, The Art of Computer Programming, 2nd Ed. (Addison-Wesley Series in Computer Science and Information, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1978
• 16: {MaO81} Y. Malachi and S. S. Owicki, Temporal Specifications of Self-Timed Systems, <i>VLSI Systems and Computations,</i>, Oct. 1981, pp. 203--212.
• 17: Thomas M. McWilliams , Lawrence C. Widdoes, Jr., SCALD: Structured Computer-Aided Logic Design, Proceedings of the 15th conference on Design automation, p.271-277, June 19-21, 1978, Las Vegas, Nevada, United States
• 18: {Mis84} B. Mishra, An Efficient Algorithm to Find All 'Bidirectional' Edges of an Undirected Graph., <i>25th Annual Symp. on Foundations of Computer Science,</i> Oct. 1984, pp. 207--216.
• 19: {Nag75} L. W. Nagel, <i>SPICE2: A Computer Program to Simulate Semiconductor Circuits,</i> University of California at Berkeley, Memorandum No. ERL-M520, May 1975.
• 20: {New78} A. R. Newton, <i>The Simulation of Large-Scale Integrated Circuits,</i> University of California at Berkeley, Memorandum No. UCB/ERL M78/52, July 1978.
• 21: {Ous81} J. K. Ousterhout, Caesar: An Interactive Editor for VLSI Layouts, <i>VLSI Design 2,</i> 4 (Fourth Quarter 1981), pp. 34--41.
• 22: John K. Ousterhout, Switch-level delay models for digital MOS VLSI, Proceedings of the 21st conference on Design automation, p.542-548, June 25-27, 1984, Albuquerque, New Mexico, United States
• 23: 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
• 24: George S. Taylor , John K. Ousterhout, Magic's incremental design-rule checker, Proceedings of the 21st conference on Design automation, p.160-165, June 25-27, 1984, Albuquerque, New Mexico, United States
• 25: Thomas Reps, Optimal-time incremental semantic analysis for syntax-directed editors, Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.169-176, January 25-27, 1982, Albuquerque, Mexico [doi>10.1145/582153.582172]
• 26: Thomas W. Reps, Generating language-based environments, Massachusetts Institute of Technology, Cambridge, MA, 1984
• 27: Thomas W. Reps , Carla Marceau , Tim Teitelbaum, Remote attribute updating for language-based editors, Proceedings of the 13th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.1-13, January 01, 1986, St. Petersburg Beach, Florida [doi>10.1145/512644.512645]
• 28: {Sei80} C. Seitz, System Timing, <i>Introduction to VLSI systems,</i>, C. Mead and L. Conway, Addison Wesley, Reading, MA, Second Printing, Oct. 1980.
• 29: Tim Teitelbaum , Thomas Reps, The Cornell program synthesizer: a syntax-directed programming environment, Communications of the ACM, v.24 n.9, p.563-573, Sept. 1981 [doi>10.1145/358746.358755]
• 30: C. J. Terman, SIMULATION TOOLS FOR DIGITAL LSI DESIGN, Massachusetts Institute of Technology, Cambridge, MA, 1983