Optimized Software Synthesis for Digital Signal Processing Algorithms: An Evolutionary Approach

Based on the model of synchronous data flow (SDF) [13], so called single appearance schedules are known to provide memory-optimal schedules. Among these, the problem of buffer memory optimization is treated: (1) An Evolutionary Algorithm (EA) is applied to efficiently explore the (in general) exponential search space of actor firing orders. (2) For each order, the buffer costs are evaluated by applying a dynamic programming post-optimization step (GDPPO). Introduction Dataflow specifications are widespread in areas of digital signal and image processing. Synchronous dataflow (SDF) graphs [13] present a class of dataflow in which the nodes, called actors have a simple firing rule: The number of data values (tokens, samples) produced and consumed by each actor is fixed and known at compile-time. The SDF model is used in many industrial DSP design tools, e.g., SPW by Cadence, COSSAP by Synopsys, as well as in research-oriented environments, e.g., [4, 12, 15]. In general, a code generatio..