Definitions, Assumptions and Scheduling Model

Definitions - Processor types

Multiprocessor types usually considered

Identical

Processors are of the same type and have the same speed. Each task has the same WCET on each processor.

Uniform

Processors are of the same type but may have different speeds. Task WCETs are smaller on faster processors.

Heterogeneous

Processors can be of different types. The WCET of a task depends on the processor type and the task itself.

Task Models - DAG

Representing parallel code requires more complex structures than for sequential tasks.

A Directed Acyclic Graphs (DAG) is a graph in which links have a direction and there are no cycles

Fork-Join Model Task Model

A special type of Directed Acyclic Graph.

Nodes represent processing.

After a Fork node, all successors have to be executed. The order is not relevant (nor defined).

Join nodes only execute after the completion of all their predecessors.

Nesting is allowed.

And-Or Graphs

The most general graph representation.

• OR nodes represent conditional statements.

• AND nodes represent parallel computations.

Application Model

An application can be modeled as a set of tasks, each described by a task graph.

Assumptions

Task and system characteristics

Arrival pattern.

• Periodic or Sporadic (period or mit is T).

Preemption.

• Allowed, but eventually with critical sections.

Task migration allowed?

• May or may not. We will see ...

Task parameters.

• τi = {{i, ci, ...i m }, Di , Ti }

• ci : WCET of a segment

• m: number of segments of τi

• dependencies (in form of list(s)).

Example

Consider the following example:

• Compute the minimum WCET of task τ1 in isolation, considering the intra-task (segment) precedence relations.

• Number of cores is not restricted.

• Task attributes.

  • τ1 = {{2, 3, 1, 1, 2, 3}, 8, 12}

  • Dependencies: τ1,3 ← {τ1,1 , τ1,2 } and {τ1,4 , τ1,5 , τ1,6 } ← τ1,3

WCET = 7 tu for a number of cores greater or equal to 3.

More processors are not always helpful ...

Additional definitions and observations

Sequential Computation time:

CPU utilization of a task:

Immediate results:

• If the task is schedulable in a single core
• If where K is the number of cores, then the task is not schedulable.

Critical path

Critical path length length of the longest path in the graph.

What is the critical path length?

If follows immediately that if for any task Cip > Di then the application is not feasible in any number of cores