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.

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.1.1. Router Classifications.- 2.1.2. Types of Routing Constraints.- 2.2. Application Domain: Maze Routers.- 2.3. Maze Router Varieties.- 2.3.1. Fabrication Constraints.- 2.3.2. Application Constraints.- 2.3.3. Algorithm Constraints.- 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.5.1. Design Generation Knowledge.- 4.5.1.1. Router Structure Knowledge.- 4.5.1.2. Routing Phase Requirement Knowledge.- 4.5.1.3. Router Dependency Knowledge.- 4.5.2. Program Synthesis Knowledge.- 4.5.2.1. Application Language Syntactic Knowledge.- 4.5.2.2. Data Structure Implementation Knowledge.- 4.5.3. Domain Interaction Knowledge.- 4.5.4. ELF-control Knowledge.- 4.6. Architecture Overview.- 4.6.1. Input Stage.- 4.6.2. Selection Stage.- 4.6.3. Selection.- 4.6.4. Separation of Algorithm and Data Structure Selection.- 4.6.5. Output Code Generator Stage.- 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.3.1. Representation of Data Structure Interdependency Information.- 6.3.2. Data Structure Representation During Selection.- 6.3.3. Data Structure Selection Operation.- 6.3.3.1. Router Domain Knowledge.- 6.3.3.2. Program Synthesis Knowledge.- 6.3.3.3. Design Interaction Knowledge.- 6.3.3.4. ELF-control Knowledge.- 6.3.3.5. Operations on the Interdependency Graph.- 6.4. The Algorithm Designer Module.- 6.4.1. Algorithm Representation.- 6.4.2. Algorithm Selection Operation.- 6.5. Chapter Summary.- References.- 7. The Code Generator Stage.- 7.1. I/O Operation Synthesis.- 7.1.1. Input and Output Specification and Operation.- 7.1.2. Input Netlist Code Generation: An Example.- 7.2. The Use of Router Domain Knowledge in the Transformation Process.- 7.2.1. Effects of Applying Domain Knowledge.- 7.2.2. Domain Knowledge Driven Transformation: An Example.- 7.3. Stepwise Refinement in the Transformation Process.- 7.3.1. The Transformation Process.- 7.3.2. Transformation Comparison.- 7.4. Chapter Summary.- References.- 8. Implementation.- 8.1. Implementation Characteristics.- 8.1.1. Input Stage.- 8.1.2. Selection Stage.- 8.1.3. Code Generator Stage.- 8.2. Design History.- 8.3. Modifying ELF: Is It Really Better?.- 8.3.1. How To Add a New Technology?.- 8.3.2. How To Add a New Algorithm Representation?.- 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.2.1. Comparison of ELF-synthesized Gate Array Routers.- 9.2.2. A Gate Array Routing Task.- 9.2.3. Comparison with Hand-crafted Code.- 9.3. Printed Circuit Board Style Router.- 9.3.1. ELF-Synthesized PCB Router.- 9.3.2. A PCB Routing Task.- 9.3.3. Comparison With a Production-Quality Router.- 9.4. Macro-Cell IC Style Router.- 9.4.1. ELF-Synthesized Macro-Cell IC Global Router.- 9.4.2. A Macro-Cell IC Routing Task.- 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.