Maximum-throughput mapping of SDFGs on multi-core SoC platforms

• We face Max-Throughput Mapping and Scheduling of streaming applications (SDF) on MPSoC platforms.
• We develop a Constraint-based solver relying on an incremental algorithm to narrow the search space.
• The method is complete, but we devise heuristics to quickly guide search to high quality solutions.
• We perform an extensive evaluation to assess the method effectiveness and scalability.
• Adding incrementality speeds-up tree-search pruning by orders of magnitude.

Data-Flow models are attracting renewed attention because they lend themselves to efficient mapping on multi-core architectures. The key problem of finding a maximum-throughput allocation and scheduling of Synchronous Data-Flow graphs (SDFGs) onto a multi-core architecture is NP-hard and has been traditionally solved by means of heuristic (incomplete) algorithms with no guarantee of global optimality. In this paper we propose an exact (complete) algorithm for the computation of a maximum-throughput mapping of applications specified as SDFG onto multi-core architectures. This is, to the best of our knowledge, the first complete algorithm for generic SDF graphs, including those with loops and a finite iteration bound. Our approach is based on Constraint Programming, it guarantees optimality and can handle realistic instances in terms of size and complexity. Extensive experiments on a large number of SDFGs demonstrate that our approach is effective and robust.