TY - GEN
T1 - Feasibility concerns in PGM graphs with bounded buffers
AU - Baruah, S.
AU - Goddard, S.
AU - Jeffay, K.
N1 - Publisher Copyright:
© 1997 IEEE.
PY - 1997
Y1 - 1997
N2 - 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.
AB - 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.
UR - https://www.scopus.com/pages/publications/0004129528
U2 - 10.1109/ICECCS.1997.622304
DO - 10.1109/ICECCS.1997.622304
M3 - Conference contribution
AN - SCOPUS:0004129528
T3 - Proceedings of the IEEE International Conference on Engineering of Complex Computer Systems, ICECCS
SP - 130
EP - 139
BT - Proceedings - 3rd IEEE International Conference on Engineering of Complex Computer Systems, ICECCS 1997
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 3rd IEEE International Conference on Engineering of Complex Computer Systems, ICECCS 1997
Y2 - 8 September 1997 through 12 September 1997
ER -