Hardware Reference
In-Depth Information
J
1
J
1
J
2
J
J
2
1
J
2
J
3
J
1
J
4
J
1
J
4
J
J
5
4
Figure 2.6
Precedence relations among five tasks.
are represented by nodes and precedence relations by arrows. A precedence graph
G
induces a partial order on the task set.
The notation
J
a
≺
J
b
specifies that task
J
a
is a
predecessor
of task
J
b
, meaning
that
G
contains a directed path from node
J
a
to node
J
b
.
The notation
J
a
→
J
b
specifies that task
J
a
is an
immediate predecessor
of
J
b
,
meaning that
G
contains an arc directed from node
J
a
to node
J
b
.
Figure 2.6 illustrates a directed acyclic graph that describes the precedence constraints
among five tasks. From the graph structure we observe that task
J
1
is the only one that
can start executing since it does not have predecessors. Tasks with no predecessors
are called
beginning tasks
.As
J
1
is completed, either
J
2
or
J
3
can start. Task
J
4
can
start only when
J
2
is completed, whereas
J
5
must wait for the completion of
J
2
and
J
3
. Tasks with no successors, as
J
4
and
J
5
, are called
ending tasks
.
In order to understand how precedence graphs can be derived from tasks' relations,
let us consider the application illustrated in Figure 2.7. Here, a number of objects
moving on a conveyor belt must be recognized and classified using a stereo vision
system, consisting of two cameras mounted in a suitable location. Suppose that the
recognition process is carried out by integrating the two-dimensional features of the
top view of the objects with the height information extracted by the pixel disparity on
the two images. As a consequence, the computational activities of the application can
be organized by defining the following tasks:
Search WWH ::
Custom Search