Published Articles >> Table of Contents >> Abstract

Third IEEE International Conference on Engineering of Complex Computer Systems (ICECCS '97)   p. 130
Feasibility concerns in PGM graphs with bounded buffers
S. Baruah, Dept. of Comput. Sci., Vermont Univ., Burlington, VT, USA
S. Goddard, Dept. of Comput. Sci., Vermont Univ., Burlington, VT, USA
K. Jeffay, Dept. of Comput. Sci., Vermont Univ., Burlington, VT, USA

Full Article Text:

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ICECCS.1997.622304
Send link to a friend

Abstract
The Processing Graph Method (PGM)-a dataflow model widely used in the design and analysis of embedded signal-processing applications-is studied from a real-time scheduling perspective. It is shown that the problem of deciding if instances of the general model are feasible on a single processor is intractable (co-NP-complete in the strong sense); however, a useful special case is sometimes more tractable. An efficient feasibility test and an optimal preemptive scheduling algorithm are derived for this special case, and a procedure is presented which permits system architects to make efficient use of computational resources and memory requirements for buffers while constructing real-time dataflow applications that offer hard service guarantees.
Back to Top Additional Information
Index Terms- data flow graphs; feasibility concerns; bounded buffers; processing graph method; dataflow model; embedded signal processing; real-time scheduling; co-NP-complete; feasibility test; optimal preemptive scheduling algorithm; system architects; computational resources; memory requirements Citation:  S. Baruah, S. Goddard, K. Jeffay, "Feasibility concerns in PGM graphs with bounded buffers," iceccs, p. 130,  Third IEEE International Conference on Engineering of Complex Computer Systems (ICECCS '97),  1997