Simulated evolutionary code generation for heterogeneous memory-register DSP-architectures

Efficient algorithms exist that generate optimum straight-line code for expression trees. However, when applied to graphs, the drawback of tree-based straight-line code generation is the fact that there is no joint optimization of the tree code and the data transfers between the trees. The purpose of this paper is to introduce an evolutionary hybrid that combines evolutionary optimization strategies with tree techniques. The goal is to minimize the execution time of the program by jointly optimizing the schedule, selected instructions, and allocated registers. The core of our technique is a linear-time algorithm that translates expression trees into optimal straight-line code segments satisfying a set of boundary conditions for the tree interface variables. Experiments indicate that this technique allows to generate code of such high quality that is extremely difficult to achieve manually.