Efficient DAG synthesis [VLSI logic design]

A method is presented for synthesis in the presence of arbitrary conditional branches. The synthesis system, DPE, is based on the simulated annealing algorithm. DPE translates the initial specification into an internal, graph-oriented representation. Simulated annealing is used to apply compaction transformations to the graph. A user-specified cost function, which includes registers, arithmetic and logic units (ALUs), control steps, and interconnect requirements, is used to evaluate the effect of the transformations and the quality of the resulting data path. This approach produces very-high-quality results in a reasonable time. DPE was enhanced to accept arbitrary program DAGs as input. This required four modifications to the standard basic block synthesis technique: resource sharing, statement coloring, multiple definitions, and addition of control information and dependencies