Precedence and Data Dependencies

Precedence Constraints and Data Dependency

The jobs in a task may be constrain to execute in a particular order and it is known as precedence constraint. The partial order relation, < is used to specify the precedence constraint among the jobs and is called precedence relation. A job J_i is a precedence of another J_k (J_k is a successor of J_k) if J_k cannot begin until the execution of J_i completes. It is denoted as J_i < J_k. In this case, Ji is an immediate predecessor of J_k if J_i < J_k if there is no other job in between. J_i and J_k are said to be independent when neither of J_i < J_k nor J_k < J_i. It means they can execute in any order. A job with precedence constraint becomes ready for execution once when its release time has passed and when all the predecessors have completed.

Precedence Graph and Task Graph

We can represent the precedence constraints among the jobs in a set J using a directed graph G = (J, <). Each node represents a job, a directed edge from J_i to J_k if J_i is an immediate predecessor of J_k. This graph is called precedence graph. Many types of interactions and communications are not captured by a task graph.

A task graph is an extended precedence graph, the vertices in the task graph represents jobs, number in brackets above each job represents feasible interval and the edges represent dependencies among the jobs but if all the edges are precedence edges representing precedence constraints then the task graph also becomes a precedence graph.

The top row in the graph represents independent jobs as there is no edge to or from these jobs. It means the jobs are ready for execution once released even though other jobs released earlier are not complete.

The precedence graph and task graph also contain different types of edges that represents different types of dependencies. The type of dependencies represented by an edge is given by the type of edge.

Data Dependency

The data dependency can’t be captured by the precedence graph. In the real time system, the jobs communicate through shared data and the producer and consumer jobs are not synchronized. The producer places the data generated by it in a shared address space to be used by the consumer at any time. The jobs are not constraints to be executed in order. In a task graph, the data dependencies among the jobs are represented explicitly by the data dependency edges among the jobs. There is a data dependency edge from a vertex J_i to J_k if the job J_k consumes data generated by Ji. The parameter of an edge from J_i to J_k represents volume of data from J_i to J_k and is called data volume parameter.

Other Dependency

Temporal Dependency

Sometimes it is constraint to complete some jobs within a certain amount of time relative to one another. The difference in the completion time of two jobs is called temporary distance between them, jobs are said to be temporal distance constraint if their temporal distance must be not more than some finite value. Such jobs may or may not have deadlines. Temporal dependencies edges from vertex J_i to J_k if the job J_k must be completed within a certain time after J_i completes. The temporal distance between jobs is given by temporal distance parameter of the edge, the value of this parameter is infinite if the jobs have no temporal distance constraint or no temporal dependencies as between jobs.

AND/OR Precedence Graph

Normally, a job must wait for the completion of all the immediate predecessors and it is called AND precedence constraints and the jobs are called AND jobs. It is represented by unfilled circle in the task graph.

OR constraints indicate that a job may begin at or after its release time if only one or some of the immediate predecessors have completed. It is represented by unfilled square in the task graph.

The line joining two filled circles are represents the conditional block and dotted edge represents the producer consumer relationship in the task graph.

Conditional Branch

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.

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 1, these jobs are represented by ï¬Âlled 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 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. (Liu 46)

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. Problem 3.3 gives an example of how this representation works, but the example also illustrates how inconvenient the representation is. For this reason, we introduce the pipeline relation between jobs. In the task graph, we represent a pipeline relationship between jobs by a pipeline edge, as exempliï¬Âed by the dotted edge between the jobs in the right-bottom corner of the graph in Figure 1.There is an edge from J_i to k if the output of J_i is piped into J_k and the execution of J_k can proceed as long as there are data for it to process. (Liu 47)

References

Liu, Jane W. S. Real Time Systems. Integre Technical Publishing Co., Inc, January 10, 2000. Print.