Conference proceeding
Feasibility concerns in PGM graphs with bounded buffers
Proceedings. Third IEEE International Conference on Engineering of Complex Computer Systems (Cat. No.97TB100168), pp.130-139
1997
DOI: 10.1109/ICECCS.1997.622304
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.
Details
- Title: Subtitle
- Feasibility concerns in PGM graphs with bounded buffers
- Creators
- Sanjoy Baruah - Dept. of Comput. Sci., Vermont Univ., Burlington, VT, USASteve Goddard - Dept. of Comput. Sci., Vermont Univ., Burlington, VT, USAKevin Jeffay
- Resource Type
- Conference proceeding
- Publication Details
- Proceedings. Third IEEE International Conference on Engineering of Complex Computer Systems (Cat. No.97TB100168), pp.130-139
- DOI
- 10.1109/ICECCS.1997.622304
- Publisher
- IEEE
- Language
- English
- Date published
- 1997
- Academic Unit
- Computer Science
- Record Identifier
- 9984259468602771
Metrics
19 Record Views