Cyclo-Static DataFlow Phases Scheduling Optimization for the Throughput Constrained Buffer Sizes Minimization Problem
Cyclo-Static DataFlow (CSDF) is a powerful model for the specification of DSP applications. However, as in any asynchronous model, the synchronization of the different communicating tasks (processes) is made through buffers that have to be sized such that timing constraints are met. In this paper, we want to determine buffer sizes such that the throughput constraint is satisfied. This problem has been proved to be of exponential complexity. Exact techniques to solve this problem are too time and/or space consuming because of the self-timed schedule needed to evaluate the maximum throughput. Therefore, a periodic schedule is used. Each CSDF actor is associated with a period that satisfies the throughput constraint and sufficient buffer sizes are derived in polynomial time. However, within a period, an actor phases can be scheduled in different manners which impacts the evaluation of sufficient buffer sizes. This paper presents a Min-Max Linear Program that derives an optimized periodic phases scheduling per CSDF actor in order to minimize buffer sizes. It is shown through an MP3 Playback and an H.263 Encoder that this Min-Max Linear Program allows to obtain close to optimal values while running in polynomial time. The impact of phases scheduling on periodic schedulability of applications with critical cycles is also highlighted on a Channel Equalizer.