8.6 EXTRACTING SERIAL AND PARALLEL ALGORITHM PERFORMANCE PARAMETERS
In order to extract the D and P properties of an algorithm, we construct a W component nonnegative sequence vector S, such that the component of the vector at the ith location S(i) ≥ 0 indicates the order or priority of execution assigned to node i. The value S(i) = k indicates that node i belongs to the execution sequence k.
We outline some basic definitions that we will need in our technique.
Definition 8.1
Parents of a node n: the source nodes for the directed edges terminating at node n.
Definition 8.2
Sequence of a node n: when a node can be executed by the processors.
Definition 8.3
Parallel set Ts: the set of all nodes/tasks that can be executed at sequence s.
The process of evaluating the algorithm starts with all the nodes that have sequence value 0, then when all the processing is done, the nodes with sequence value 1 are executed, and so on. We populate the sequence vector according to the iterative procedure shown in Algorithm 8.1.
Algorithm 8.1
Algorithm to assign execution sequences or levels to the nodes
Require: Input: W × W adjacency matrix A
1:
= ϕ // initialize parents set to empty set
2:
= 
// initialize nodes set to include all the nodes of the algorithm
3: s = 0 // Initial sequence has zero value (0).
4:
0 = ϕ // initialize set of concurrent tasks at level s = 0
5:
for node ∈ do
6: if node is input node then
7: S(node) = s // Components of S associated with each input node have value s = 0.
8:
insert node in // start defining the parents node set
9:
delete node from // leave unassigned nodes in
10: end if
11: end for
12:
while ≠ ϕ do
13: s = s + 1 // increment sequence value to be allocated to newly assigned nodes
14:
= ϕ // initialize temporary set to contain nodes in new level
15:
s = ϕ // initialize set of concurrent tasks at level s
16:
for node ∈ do
17:
if all parents of node ∈ then
18:
insert node in
19:
delete node from
20: S(node) = s
21: end if
22: end for
23:
append to // update nodes in to include newly assigned nodes
24:
append to s
25: end while
After implementing Algorithm 8.1, all nodes will be assigned to an execution level. Figure 8.4 shows the levels of execution of the algorithm in Fig. 8.1 and the allocation of nodes to levels.
Figure 8.4 The assignment of the nodes in Fig. 8.1 according to the procedure in Algorithm 8.1.
