Feasibility concerns in PGM graphs with bounded buffers

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. Keywords: Data-flow, real-time, scheduling theory, embedded systems, software architecture. University of Vermont/ Department of Computer Science, Votey 351/ Burlington, VT 05405. Email: sanjoy@cs.uvm.edu y Department of Computer Sci..