Minimising Buffer Requirements of Synchronous Dataflow Graphs with Model Checking
Signal processing and multimedia applications are often implemented on resource constrained embedded systems. It is therefore important to find implementations that use as little resources as possible. These applications are frequently specified as synchronous dataflow graphs. Communication between actors of these graphs requires storage capacity. In this paper, we present an exact method to determine the minimum storage capacity required to execute the graph using model-checking techniques. This can be done for different measures of storage capacity. The problem is known to be NP-complete and because of this, existing buffer minimisation techniques are heuristics and hence not exact. Modern model-checking tools are quite efficient and they have been successfully applied to different scheduling-related problems. We study the feasibility of this approach with a number of examples.
Minimizing Buffer Requirements of Synchronous Dataflow Graphs with Model Checking
M. Geilen, T. Basten and S. Stuijk.
Technical Report ESR-2005-01, Eindhoven University of Technology, Department of Electrical Engineering, Eindhoven, The Netherlands, January 2005. (abstract, pdf)