A comprehensive modeling approach for the task mapping problem in heterogeneous systems with dataflow processing units

We introduce a new model for the task mapping problem to aid in the systematic design of algorithms for heterogeneous systems including, but not limited to, CPUs, GPUs, and FPGAs. A special focus is set on the communication between the devices, its influence on parallel execution, as well as on device-specific differences regarding parallelizability and streamability. We give a comprehensive description on how a given task mapping can be abstractly evaluated including mappings to dataflow-based hardware accelerators. We show how this model can be utilized in different system design phases and present two novel mixed-integer linear programs to demonstrate the usage of the model, showing significant improvements compared to pure CPU mapping for randomly generated task graphs. To the best of our knowledge, we present the first ILP for task mapping that considers pipelining effects when streaming tasks on an FPGA.