Information Technology Reference
In-Depth Information
ing policy the objects from a weighted DAG are assigned to multiple channels in
such a fashion that (i) dependency implied by the edges are preserved, (ii) the overall
broadcast time (load balancing), and (iii) clustering related objects close to one an-
other. This problem can be mapped to the static task scheduling in a multiprocessor
environment
[31]
.
3 . 4 P a r a l l e l B r o a d c a s t C h a n n e l O r g a n i z a t i o n
A static scheduling protocol within a multiprocessor environment attempts to find
the minimum time in which
n
dependent tasks can be completed on
m
PEs. An
optimal solution to such a problem is proven to be
NP
hard. However, heuristic rules
can be employed to find sub-optimal solutions. Similar techniques can be developed
to assign interrelated objects closely over parallel channels.
As one could conclude, distribution of objects over the broadcast parallel air chan-
nels reduces the broadcast length and hence could reduce the average access time.
In addition, shorter access time could translate into lower power consumption. How-
ever, application of parallel channels brings the issue of access conflicts between
requested objects that are distributed among different channels. Access conflicts re-
quire multiple passes over the broadcast channels and this has adverse impact on the
response time and power consumption.
3 . 5 A c c e s s C o n fl i c t
Definition 1.
A
K
-object request is an application request intended to retrieve
K
objects from a broadcast.
Without loss of generality, we assume that each channel has the same number
of pages (frames) of equal length and each object resides on only a single page.
Consequently, a parallel broadcast can be viewed as a two-dimensional array
N × M
,
where
N
is the number of pages per broadcast, and
M
is the number of channels. In
this grid,
K
objects (0
K
MN
) are randomly distributed throughout the
MN
positions of the grid. The mobile unit can only tune into one channel at a time and
can switch channels with time and power penalties. Based on the common page size
and the network speed, the time required to switch from one channel to another
is equivalent to the time it takes for one page to pass in the broadcast. Thus, it is
impossible for the mobile unit to retrieve both the
i
th page on channel
A
and
(i +
1
)
th
page on channel
B
(where
A = B
).
Definition 2.
Two objects are defined to be in conflict if it is impossible to retrieve
both objects on the same broadcast.
