Real-Time Scheduling in Video Systems

Abstract

We consider the problem of mapping video algorithms onto systems of high-performance
video signal processors with hard real-time constraints. The mapping problem under
consideration is computationally hard due to the many constraints that need to be
satisfied. We present a compact mathematical formulation which identifies the
decision variables and the constraints that are involved. We demonstrate that the
mapping problem is NP-hard in the strong sense. The insight resulting from the
mathematical formulation leads to a solution approach in which the problem is
decomposed into subproblems called delay management, partitioning, and scheduling.
These subproblems are handled with well-known techniques from the literature such as
network flow, local search, and constraint satisfaction.