Partitioning and mapping dynamic dataflow programs

Partitioning and mapping are important design decisions in exploiting the parallelism of programs that are to be run on systems with multiple processing elements. In this paper we introduce a fast, incremental approach for mapping dynamic dataflow programs to multiprocessor systems. We use causation traces and architecture descriptions as input for the mapping process that devises several heuristics for reaching a short makespan for the given trace. We evaluate our approach by comparing our results to two different lower bounds and another algorithm used often in solving mapping problems: simulated annealing.