Automatic Programming Applied to VLSI CAD Software

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.