Symbolic Buffer Sizing for Throughput-Optimal Scheduling of Dataflow Graphs

International audienceThe synchronous dataflow model is widely usedto design real-time streaming applications which must assure aminimum quality-of-service. A benefit of that model is to allowstatic analyses to predict and guarantee timing (e.g., throughput) and buffering requirements of an application. Performanceanalyses can either be performed at compile time (for designspace exploration) or at run-time (for resource management andreconfigurable systems). However, these algorithms, which oftenhave an exponential time complexity, may cause a huge runtime overhead or make design space exploration unacceptablyslow. In this paper, we argue that symbolic analyses are moreappropriate since they express the system performance as afunction of parameters (i.e., input and output rates, executiontimes). Such functions can be quickly evaluated for each differentconfiguration or checked w.r.t. many different non-functionalrequirements. We first provide a symbolic expression of themaximal throughput of acyclic synchronous dataflow graphs. Wethen perform an analytic and exact study of the minimum buffersizes needed to achieve this maximal throughput for a singleparametric edge graph. Based on these investigations, we definesymbolic analyses that approximate the minimum buffer sizesneeded to achieve maximal throughput for acyclic graphs. Weassess the proposed analyses experimentally on both syntheticand real benchmarks