A Fast Heuristic to Pipeline SDF Graphs

International audienceA common optimization of signal and image processing applications is the pipelining on multiple Processing Elements (PE) available on multicore or manycore architectures. Pipelining an application often increases the throughput at the price of a higher memory footprint. Evaluating different pipeline configurations to select the best one is time consuming: for some applications, there are billions of different possible pipelines. This paper proposes a fast heuristic to pipeline signal and image processing applications modelled with the Synchronous DataFlow (SDF) Model of Computation (MoC). The heuristic automatically adds pipeline stages in the SDF graph in the form of delays, given the Execution Time (ET) of the actors and the number of PEs. The heuristic decreases the time spent by the developer to pipeline its application from hours to seconds. The efficiency of the approach is illustrated with the optimisation of a set of signal and image processing applications executed on multiple PEs. On average, when adding one pipeline stage, our heuristic selects a stage resulting in a better throughput than 90% of all possible stage emplacements