Automatic Programming Applied to VLSI CAD Software: A Case Study

This book, and the research it describes, resulted from a simple observation we made sometime in 1986. Put simply, we noticed that many VLSI design tools looked "alike". That is, at least at the overall software architecture level, the algorithms and data structures required to solve problem X looked much like those required to solve problem X'. Unfortunately, this resemblance is often of little help in actually writing the software for problem X' given the software for problem X. In the VLSI CAD world, technology changes rapidly enough that design software must continually strive to keep up. And of course, VLSI design software, and engineering design software in general, is often exquisitely sensitive to some aspects of the domain (technology) in which it operates. Modest changes in functionality have an unfortunate tendency to require substantial (and time-consuming) internal software modifications. Now, observing that large engineering software systems are technology dependent is not particularly clever. However, we believe that our approach to xiv Preface dealing with this problem took an interesting new direction. We chose to investigate the extent to which automatic programming ideas cold be used to synthesize such software systems from high-level specifications. This book is one of the results of that effort.

Contenu

1. Introduction.- 1.1. The Application Domain.- 1.2. Knowledge Sources.- 1.3. Book Organization.- References.- 2. Application Domain: Routing Algorithms.- 2.1. Routing Algorithms.- 2.2. Application Domain: Maze Routers.- 2.3. Maze Router Varieties.- 2.4. Why Choose Maze Routers?.- 2.5. Chapter Summary.- References.- 3. Software Reusability.- 3.1. Composition-Based Systems.- 3.2. Generation-Based Systems.- 3.3. Chapter Summary.- References.- 4. ELF: A Program Synthesis Architecture.- 4.1. Combining Router Knowledge with Program Synthesis Knowledge.- 4.2. Algorithm Schema Representation.- 4.3. Data Structure Style Representation.- 4.4. Intermediate Representation for Synthesized Code.- 4.5. Domain Knowledge Representation Using a Rule-Based System.- 4.6. Architecture Overview.- 4.7. Architecture Overview.- 4.8. Chapter Summary.- References.- 5. The Input Stage.- 5.1. Input Stage Operation.- 5.2. Input Stage Rule Types.- 5.3. Chapter Summary.- References.- 6. The Selection Stage.- 6.1. Selection Control Module.- 6.2. The Dependency Analysis Module.- 6.3. The Data Structure Designer Module.- 6.4. The Algorithm Designer Module.- 6.5. Chapter Summary.- References.- 7. The Code Generator Stage.- 7.1. I/O Operation Synthesis.- 7.2. The Use of Router Domain Knowledge in the Transformation Process.- 7.3. Stepwise Refinement in the Transformation Process.- 7.4. Chapter Summary.- References.- 8. Implementation.- 8.1. Implementation Characteristics.- 8.2. Design History.- 8.3. Modifying ELF: Is It Really Better?.- 8.4. Issues in Debugging ELF-synthesized Code.- 8.5. Chapter Summary.- References.- 9. ELF Validation.- 9.1. Experimental Methodology.- 9.2. Gate Array Style Routers.- 9.3. Printed Circuit Board Style Router.- 9.4. Macro-Cell IC Style Router.- 9.5. Chapter Summary.- References.- 10. Conclusion.- 10.1. Summary.- 10.2. ELF: Hindsight and Evolution.- References.- Appendix I. Router Specification Manual.- I.1. Syntax Description.- I.2. Constraint Level Structure.- I.2.1. Top-Level Constraint Specifications.- I.2.2. Aigorithm Constraints.- I.2.2.1. Net_sorting.- I.2.2.2. Node_sorting.- I.2.2.3. Cost_function.- I.2.2.4. Netlist.- I.2.2.5. Output.- I.2.2.6. Expansion.- I.2.2.7. Net_composition.- I.2.2.8. Routing_composition.- I.2.3. Application Constraints.- I.2.3.1. Type.- I.2.3.2. Sub type.- I.2.3.3. Alg_type.- I.2.3.4. Number_of_nets.- I.2.3.5. Number_of_cells_per_net.- I.2.4. Fabrication Constraints.- I.2.4.1. Units.- I.2.4.2. Pads.- I.2.4.3. Connections.- I.2.4.4. Xsize, Ysize,Zsize.- I.2.4.5. Technology.- I.2.4.6. PCB.- I.2.4.7. Number_of_layers.- I.2.4.8. Available_via_positioning.- I.2.4.9. Layer.- I.2.4.10. IC.- I.3. Input constraint Schemes.