New Challenges in Scheduling Theory

September, 12-17 2010, Centre CNRS "La Villa Clythia", Frejus

Speculative data prefetching for branching structures in dataflow programs

SpeakerJacques Carlier

Co-authorsSergiu Carpov, Renaud Sirdey, Dritan Nace

This paper deals , to some extent, with the problem of speculative data prefetching for dataflow programming models. We focus on finding optimum prefetch strategiesfor a simple n-way dataflow branching structure with respect to several objective functions and exhibit polynomial algorithms for doing so.
Keywords: Knapsack, Shortest path, Parallel Computing, OR in Compilation.