Earliest-deadline first scheduling of multiple independent dataflow graphs

Static dataflow graphs are widely used in design of concurrent real-time streaming applications on multiprocessor systems-on-chip. The increasing complexity of these systems advocates using real-time operating systems and dynamic scheduling to manage applications and resources. Providing timing guarantees (e.g. minimum throughput, deadlines) and minimizing the required amount of resources (e.g. number of processors, buffer capacities) are crucial aspects of these systems. This paper addresses uniprocessor and partitioned multiprocessor earliest-deadline first scheduling of multiple concurrent applications, each designed as an independent dataflow graph. Our scheduling approach maps each actor to a periodic realtime task and computes the appropriate buffer sizes and timing and scheduling parameters (i.e. periods, processor allocation, etc.). The proposed parametric schedulability analysis aims at maximizing the overall processor utilization, and hence allows for reducing the required number of processors.