Other Type Of Dependencies
OTHER TYPES OF DEPENDENCIES
Like nonreal-time applications, real-time applications sometimes contain redundant modules, carry out heuristic searches, use multiple versions, execute some job conditionally, and so forth. We add other extensions to the classical precedence graphs in order to model such jobs and dependencies. These extensions include temporal distance, OR jobs, conditional branches, and pipe (or pipeline).
Temporal Dependency: Some jobs may be constrained to complete within a certain amount of time relative to one another. We call the difference in the completion times of two jobs the temporal distance [HaLH] between them. Jobs are said to have a temporal distance constraint if their temporal distance must be no more than some finite value. Jobs with temporal distance constraints may or may not have deadlines.
As an example, we consider the display of video frames and the accompanying audio when the video is that of a person speaking. To have lip synchronization, the time between the display of each frame and the generation of the corresponding audio segment must be no more than 160 msec [StNa]. Another example is the visual and audio displays of a passive sonar system [MoMW]. The synthesized audio signal and the accompanied visual display must be presented to the operator no more than 100 msec apart. These timing requirements can be stated more naturally in terms of temporal distance constraints than in terms of deadlines of jobs.
In a task graph, temporal distance constraints among jobs are represented by temporaldependency edges. There is a temporal-dependency edge from a vertex Ji to a vertex Jk if the job Jk must be completed within a certain time after Ji completes. The temporal distance between the jobs is given by the temporal distance parameter of the edge. The value of this parameter is infinite if the jobs have no temporal distance constraint, or equivalently, there is no temporal-dependency edge between the jobs.
AND/OR Precedence Constraints: In the classical model, a job with more than one immediate predecessor must wait until all its immediate predecessors have been completed before its execution can begin. Whenever it is necessary to be specific, we call such jobs AND jobs and dependencies among them AND precedence constraints. AND jobs are represented by unfilled circles in the task graph in Figure 3–1. An example is the job labeled J in this figure. All three of its immediate predecessors must be completed before J can begin execution. An AND job such as J may be the transmission of a message to a user. Its immediate predecessors are the jobs that set up a connection for the message, encrypt the message to safeguard privacy, and check the user’s account for the requested quality of the delivery service. These predecessors may execute in any order relative to each other, but they must all be completed before the message transmission job can begin.
In contrast, an OR job is one which can begin execution at or after its release time provided one or some of its immediate predecessors has been completed. In Figure 3–1, we represent OR jobs by square vertices, as exemplified by the two square vertices at the bottom of the graph. The one labeled 2/3 can begin execution as soon as two out of its three immediate predecessors complete. In a system that uses triple redundancy to increase fault tolerance, a voter can be modeled as a 2/3 job. Its predecessors are three replicated jobs that implement a critical function. The voter executes and in turn allows its successors to begin whenever two out of the three predecessors complete (and produce correct results). Similarly, we can model a two-version computation as the two immediate predecessors of a 1/2 OR job. The operating system chooses one of the versions depending on factors such as their resource requirements and quality of their results. Only one of them needs to be completed before the OR job can begin execution.
In the task graph, the in-type of job (i.e., the vertex representing the job) tells us whether all its immediate predecessors must complete before its execution can begin. By default, the value of this job parameter is AND. It can have the value OR, if only one of its immediate predecessors must be completed, or k-out-of-l, if only k out l of its immediate predecessor must be completed before its execution can begin.
Conditional Branches: Similarly, in the classical model, all the immediate successors of a job must be executed; an outgoing edge from every vertex expresses an AND constraint. This convention makes it inconvenient for us to represent conditional execution of jobs, such as the example in Figure 3–2.
This system can easily be modeled by a task graph that has edges expressing OR constraints. Only one of all the immediate successors of a job whose outgoing edges express OR constraints is to be executed. Such a job is called a branch job. In a meaningful task graph, there is a join job associated with each branch job. In Figure 3–1, these jobs are represented by filled circles. The subgraph that begins from a vertex representing a branch job and ends at the vertex representing the associated join job is called a conditional block. Only one conditional branch in each conditional block is to be executed. The conditional block in Figure 3–1 has two conditional branches: Either the upper conditional branch, containing a chain of jobs, or the lower conditional branch, containing only one job, is to be executed. This natural extension allows us to use a task graph to characterize data-dependent conditional executions exemplified by the program segment in Figure 3–2. As an exercise, you may want to look at Problem 3.2 which asks you to draw a task graph of an application that has conditional branches and for comparison, use as many classical precedence graphs as
necessary to represent all of its possible execution paths. In general, we need to use a classical precedence graph for each branch in each conditional block. For example, the task graph in Figure 3–1 is equivalent to two precedence graphs: One contains only the upper conditional branch, and the other graph contains only the lower conditional branch. We need lk classical precedence graphs to represent an application system that contains k conditional blocks if each conditional blocks has l branches.
Similar to the parameter in-type, the job parameter out-type tells whether all the job’s immediate successors are to be executed. The default value of the out-type parameter of every job is AND, that is, all its immediate successors are to be executed. On the other hand, the outtype of a branch job is OR, because only one of its immediate successors must be executed.
Pipeline Relationship: A dependency between a pair of producer-consumer jobs that are pipelined can theoretically be represented by a precedence graph. In this graph, the vertices are the granules of the producer and the consumer. Each granule of the consumer can begin execution when the previous granule of this job and the corresponding granule of the producer job have completed.
In the task graph, we represent a pipeline relationship between jobs by a pipeline edge, as exemplified by the dotted edge between the jobs in the right-bottom corner of the graph in Figure 3–1. There is an edge from Ji to Jk if the output of Ji is piped into Jk and the execution of Jk can proceed as long as there are data for it to process.