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

This paper addresses the problem of trading-off between the minimization of program and data memory requirements of single-processor implementations of dataflow programs. Based on the formal model of synchronous data flow (SDF) graphs [ LM87 ] , so called single appearance schedules are known to be program-memory optimal. Among these schedules, buffer memory schedules are investigated and explored based on a two-step approach: (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). This iterative approach is compared to existing heuristics for buffer memory optimization. Chapter 1 Introduction Dataflow specifications are widespread in areas of digital signal and image processing. In dataflow, a specification consists of a directed graph in which the nodes represent computations and the arcs ..