Knowledge-based synthesis of custom VLSI router software
Dorothy E. Setliff · 1989
This thesis describes a synthesis architecture for automatic generation of technology-sensitive VLSI physical design tools from high-level specifications. Physical design refers to the process of reducing a structural description of a piece of hardware down to the geometric layout of an integrated circuit. Successful physical design tools must cope with shifting technology and application environments. We argue that the appropriate place for technology-dependent information is not in the run-time environment of such tools, but in a generator for these tools. We describe a synthesis architecture and its prototype implementation--called ELF--that integrates knowledge of the application domain with knowledge of generic programming mechanics. ELF strives to meet the demands of the target technology by automatically generating an implementation of the tool to match the application requirements. The ELF synthesis architecture has three key features. First, a very high level language, lacking data structure implementation specifications, is used to describe algorithm design styles. Second, application domain knowledge and generic program synthesis knowledge are used to guide search among candidate design styles for all necessary component algorithms, and to deduce compatible data structure implementations for these components. Third, code generation is used to transform the resulting abstract descriptions of selected algorithms and data structures into final, executable code. Code generation is an incremental, stepwise refinement process, and also relies on application domain knowledge, as well as generic program synthesis knowledge. ELF operates in the domain of VLSI wire-routing tasks. A wide variety of fully-functional routers has been synthesized by ELF, and verified on both synthetic and industrial routing benchmarks. ELF demonstrates a synthesis architecture that efficiently generates router software using router domain-specific and generic program synthesis knowledge as a synthesis guide.