Digital synthesis using simulated annealing
Michael Quayle · 1992
We have developed a simulated annealing based behavior compiler, DPE, which has been successfully applied to the high level synthesis problem. DPE automatically translates an algorithm specified in a high level language to a digital system consisting of a datapath and controller. It differs from a traditional compiler, however, in that the hardware resources for which it compiles are not fixed. Resources are automatically allocated or deleted by evaluating the relationship between speed, parallelism, and hardware required in order to produce an acceptable result. DPE begins by translating a behavior description into an internal representation which iteratively tracks data dependencies and resource assignments. Synthesis is performed by repeatedly apply a number of basic transformations to the internal representation. A user specified cost function guides the exploration of the design space as variables are grouped into registers, registers are grouped into register banks, and operators are grouped into multifunction ALUs. DPE efficiently exploits mutual exclusivity between disjoint operations when synthesizing conditional control flow constructs. Synthesis transformations are restricted only by data dependencies, not by the basic block structure, allowing global code motions to be performed. Software pipelining has been adapted for loop synthesis, including synthesis of nested loops, loops with unknown bounds, and pipelined systems. DPE is able to synthesize high throughput systems through automatic optimal allocation and placement of pipeline stage registers. Standard lifetime analysis techniques have been extended to allow maximum schedule flexibility. DPE also supports structural pipelining of individual functional units. These techniques have been applied to the VLIW compilation problem by imposing a fixed target architecture. In this case, register allocation and code scheduling are performed by DPE within the target architecture interconnection restrictions. Finally, analysis indicates that resource sharing is not always optimal in terms of layout area and speed. Increased controller complexity and data routing costs often offset the gain from sharing resources. By including these factors during synthesis, the area and speed of the designs have been greatly improved. Combining these innovations permits effective synthesis of complex digital systems. DPE has been integrated into the Bell Laboratories standard cell synthesis environment and consistently produces results which are both smaller and faster than the clique partitioning approach.