Information Technology Reference
In-Depth Information
F
IG
. 19. Multiple children with in-degree 1.
tion of the two children
C
and
D
. Assume that at the starting point only one channel
is available. As can be seen allocating
C
first produces better load balancing.
5.2.2
Related Objects Clustering
The weight of a node should be made a function of the weights of the incoming
and outgoing edges. Based on the aforementioned discussion, the weight of each
node is calculated based on the: (i) size of the node, (ii) the maximum weight of its
children, (iii) the number of children with in-degree 1 and in-degree
>
1, and (iv) the
degree of connectivity among objects
[31]
.
The critical-path clustering algorithm (CCP) takes a DAG as its input and calls the
AssignWeights Algorithm.
CCP(DAG) Algorithm
1)
AssignWeights(
DAG
)
2)
repeat
until all the nodes have been processed
3)
Select the free node
N
with the largest weight
4)
if
all parents of
N
are fully allocated on the channels
5)
place it on the currently least-loaded channel
6)
else
7)
fill up the least-loaded channel(s) with nulls up to the end of the last
allocated parent of
N
then place
N
on it.
The
repeat
loop starting on line 2 implements the critical path heuristics by select-
ing the free node with the largest weight and placing it on the least-loaded channel,
after all its parents have been fully allocated. The running time of the CCP algorithm
is equal to the running time of AssignWeights plus the running time of the
repeat
loop. The loop has to be repeated
n
times and line 4 can be done in O
(n)
. Therefore,
the overall running time of the CCP algorithm is O
(n
2
)
.
