MASES : mobility and slack enhanced scheduler for synchronous dataflow graphs

Nowadays, real-time streaming and digital signal processing applications create an increased demand for embedded systems with better capability to process large-volume data streams with low latency and large throughput. Synchronous dataflow (SDF) graphs allow for static analysis and optimization, and are widely used for modeling real-time streaming applications. To reach a better performance, mapping of SDF descriptions into tightly resource-constrained real-time implementations requires optimization of pipelined scheduling of tasks on different processing elements (PEs). This poses the problem of finding the optimal solution across a multi-dimensional latency-throughput-area objective space. In this report, we address the problem of pipelined scheduling of SDF graphs on heterogeneous multi-processor platforms. Integer linear programming (ILP) models have been applied to solve this problem, providing theoretically optimal results. However, the execution time of solving an ILP model is exponential in the size of the input SDF graph, limiting the usage of ILPs. By contrast, list scheduling heuristics have been proposed to solve the pipelined scheduling problem in polynomial time, but existing approaches do not guarantee the optimality of the result and fail to find a valid schedule when the period constraint of the SDF graph is tight. This report contributes a heuristic called MASES that improves the performance of list scheduling. MASES explores the flexibility in a partial schedule by moving already-placed actors on the timeline such that enough space is created for actors placed next. Different from heuristics based on backtracking, MASES finds a valid actor assignment without the need for un- and re-scheduling of already-placed actors. In contrast to backtracking heuristics, MASES guarantees to find a valid schedule if one exists. In our experiments with randomly generated SDF graphs of varying size, MASES was able to find valid schedules for all test cases whereas backtracking only solved 47.2% of cases on average. Furthermore, for test cases that succeeded for MASES and backtracking, MASES on average reduces execution time by 11% and increases latency by 11% compared to backtracking.