Information Technology Reference
In-Depth Information
(a)
(b)
F
IG
. 37. Generation of unnecessary number of channel switches by the
Top Down Retrieval Approach
.
(a) Generation of access patterns when top down retrieval approach is employed. (b) Generation of access
patterns when row scan heuristic is employed.
4, 7, and 8 are scheduled in the first pass, objects 1 and 2 are scheduled in the second
pass, object 6 is scheduled in the third pass, and finally, object 5 is scheduled in the
forth pass), however, a simple row scan algorithm will retrieve these objects in three
passes.
Figure 37
shows an example where the
top down retrieval algorithm
requires un-
necessary number of channel switches.
The next section will introduce two new scheduling algorithms that can find the
minimum number of passes and the corresponding minimum number of switches
with reasonable costs
[61]
. Similar to our earlier discussion in Section
8
,atwo-
dimensional array of
N × M
is used to represent a parallel broadcast. In this array,
each cell
C
i,j
,1
i
N
,1
j
M
, represents a page. Without loss of generality,
we assume objects are not fragmented across adjacent pages, and if we request any
object in a page, we will retrieve the whole page. A row of cells represents a channel
on the broadcast, while a column of cells represents pages transmitted at the same
time on parallel channels. For a query requesting a set of objects
S
, if the cell
C
i,j
has
a requested object then
C
i,j
∈ S
. Finally, a query requests
K
objects
O
k
,1
k
K
.
Based on the aforementioned assumptions we have the following definitions with
respect to a given query (
Figs. 38 and 39
are intended to clarify these definitions).
A column without any requested objects occurring in
Definition 5
( Empty columns) .
it is empty.
Definition 6
( Sparse columns) .
A column containing requested objects without any
conflicts with others is sparse.
