Pranav Tendulkar, Peter Poplavko, Oded Maler
Symmetry Breaking for Multi-Criteria Mapping and Scheduling on Multicores (2013)
Symmetry Breaking for Multi-Criteria Mapping and Scheduling on Multicores (2013)
TR-2013-3.pdf
Keywords: synchronous data-flow, multiprocessor, multicore, mapping, scheduling, SMT, SAT solver
Abstract: Multiprocessor mapping and scheduling is a long-old difficult problem. In this work we propose a new methodology to perform mapping and scheduling along with buffer memory optimization using an SMT solver. We target split-join graphs, a formalism inspired by synchronous data-flow (SDF) which provides a compact symbolic representation of data-parallelism. Unlike the traditional design flow for SDF which involves splitting of a big problem into smaller heuristic sub-problems, we deal with this problem as a whole and try to compute exact Pareto-optimal solutions for it. We introduce symmetry breaking constraints in order to reduce the run-times of the solver. We have tested our work on a number of SDF graphs and demonstrated the practicality of our method. We validate our models by running an image decoding application on the Tilera multicore platform.
