Real-Time Scheduling in Video Systems

Main Article Content

E. A. de Kock
Emile H. L. Aarts
G. Essink

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.

Article Details

Section
Special Issue Papers