Information Technology Reference
In-Depth Information
objects. The ApproximateLinearOrder algorithm is a greedy-based approximation
algorithm that guarantees the linearity property and provides a solution in polyno-
mial time. The PartiallyLinearOrder algorithm guarantees the linearity property for
the strongest related objects and relaxes the linearity requirement for objects con-
nected through looser links. Finally, it was shown that the proposed algorithms offer
higher performance than the traditional children-depth first algorithm.
5.
Parallel Channels Object Organization
Section
4
addressed the methods by which objects should be placed on a sin-
gle air channel. However, as noted before, reducing the broadcast length is one
way to provide timely access to information, i.e., broadcasting objects along par-
allel air channels. Realizing the similarity between this goal and scheduling tasks in
a multiprocessor environment, two heuristic-based static scheduling algorithms are
discussed and analyzed in this section
[31]
.
5 . 1 L a r g e s t O b j e c t F i r s t ( L O F )
This algorithm relies on a simple and localized heuristic by giving priority to
larger objects. Consider a 2-channel allocation and three objects
A
,
B
, and
C
. Fur-
ther assume the following relationships among the sizes of the objects
A>B>C
(
Fig. 17
).
Figure 17
(a) shows a random allocation, whereas,
Fig. 17
(b) shows the al-
location based on the aforementioned heuristic. As can be seen, this heuristic has the
advantage of achieving better load balancing. The algorithm follows the following
procedure: Recursively, the largest node with in degree of zero is chosen (initially
the root) and assigned to the least loaded channel. The assigned node along with all
of its out-edges are eliminated from the object DAG.
5 . 2 C l u s t e r i n g C r i t i c a l - P a t h ( C C P )
A critical path is defined as the longest sequence of dependent objects that are
accessed serially. Traditionally, a critical path is defined based on the weights as-
F
IG
. 17. Load balancing using Largest-Object First heuristic.
