Dynamic response time optimization for SDF graphs

Synchronous Data Flow (SDF) is a well-known model of computation that is widely used in the control engineering and digital signal processing domains. Existing scheduling methods are mainly static approaches that assume full knowledge of the environment, e.g., data arrival times. In a growing number of practical cases like internet multimedia applications there exists only partial knowledge of the environment, e.g. average data rates. Here, only dynamic scheduling can yield optimal results. In this paper we propose a new dynamic scheduling method that minimizes the maximal response time of the system. It is a generalization of a deadline revision method to allow treatment of data-dependent tasks using EDF scheduling. The applicability and benefit of the new approach is shown using a real-world example.