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 ...
Get Algorithms and Parallel Computing now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
