Information Technology Reference
In-Depth Information
signed to each node. A simple approach would set the weight proportional to the
size of an object and the size of its largest descendant node. However, such a scheme
fails to consider parameters such as the total size and number of children and the
degree of connectivity among related nodes. Therefore, a critical-path algorithm that
uses a more sophisticated set of heuristics in determining the weight of the node is
represented here.
Definition 4.
A critical node is a node that has a child with an in-degree greater
than 1.
5.2.1 Load Balancing
5.2.1.1 Critical Node Effect.
Allocate a critical node with the high-
est number of children with in-degree
>
1 first. Consider the subDAG shown in
Fig. 18
—
A
,
B
, and
C
are all critical nodes. However,
A
has priority over
B
and
C
(it has precedence over two nodes whereas
B
and
C
have precedence over one
node each). Assume that there are two parallel channels. As can be seen from the
figure, regardless of the sizes of
A, B
, and
C
, allocating
A
first results in a better
load balancing.
5.2.1.2 Number of Children with In-Degree 1.
Allocate nodes with
the highest number of children with in-degree 1 first. This could free up more nodes
to be allocated in parallel. Consider the allocation shown in
Fig. 19
, and the alloca-
F
IG
. 18. Critical-node effect.
