Information Technology Reference
In-Depth Information
blocks marked no obstacle (in the function
nextblock
) minimizes the number of in-
side switches. Choosing the rightmost empty block, at each step also contributes to
minimizing the number of inside switches of a scan.
The SES algorithm has complexity O
(N
2
M)
. The functions
rightmost
and
nextblock
are both bounded by the number of rows, hence they are both O
(N )
.
The SES algorithm's outer loop iterates at most
N
times and its inner loop iterates at
most
M
times. Finally, the body of the inner loop takes O
(N )
times due to the call
to
nextblock
. Consequently, the inner loop has complexity O
(N M)
and so does the
body of the outer loop.
Figure 41
depicts the snap shots of a running example of SES algorithm to re-
trieve fourteen objects from a five-parallel channel configuration. For this request,
MAX
_
cut
is 3,
MAX
_
total
is 5 and at least 3 passes with at least 7 switches are re-
quired to retrieve the requested objects (numbers in the captions represent the line
number in SES algorithm).
SES Algorithm
1. if
(
MAX
_
total
=
MAX
_
cut
)
2.
use Row Scan;
3. else
4.
Rows
={
1
,...,N}
/* Rows we can compress */
5.
repeat until (
MAX
_
total
=
MAX
_
cut
){
6.
j =
1;
7.
i =
nextblock
(
Rows
,j)
8.
k =
freeright
(i, j )
/* free block is
C
ij
to
C
ik
*/
9.
repeat until
k = M
{
i
′
=
nextblock
(
Rows
,k)
10.
k =
freeright
(i
′
,j)
11.
12.
C
ia
= C
i
′
a
for 1
a<k
/* compress channels */
13.
C
i
′
k
=
no obstacle
/* indicate a switch occurs */
i = i
′
14.
15.
j = k
16.
}
17.
MAX
_
total
=
MAX
_
total
−
1
18.
Rows
=
Rows
−{i}
/* delete the empty row */
19.
}
An Empty block without an obstacle (
Definition 14
) represents a channel switch.
As one can conclude, in the first pass, objects 1, 3, 5, and 3 are retrieved. During
the second pass, objects 4, 7, 8, 9, and 10 are fetched. Finally, during the third pass,
objects 11, 13, 12, 14, and 6 are retrieved.
