Information Technology Reference
In-Depth Information
The SES algorithm is serial since it finds the (
MAX
_
total
−
MAX
_
cut
)empty
paths one by one. The SES algorithm constructs an empty path by starting with the
rightmost empty block
B
i
′
,
1
in some row
i
′
. The path starts in row
i
′
at column 1
and continues to column
k
, where
k
is the length of
B
i
′
,
1
. Next it finds a rightmost
overlapping empty block
B
i
′′
,k
. The path continues on row
i
′′
for the length of this
empty block and so forth. Additionally, the SES algorithm begins to create a logical
channel by moving all requested objects
C
i
′′
,a
,to
C
i
′
,a
,for1
a<k
. Finally it
marks the empty cell
C
i
′
,lk
as
no obstacle
, indicating a physical switch occurs at this
point in the logical channel. This end marker is used during the construction of sub-
sequent empty paths. By convention, we also define that
∀i
′
,
C
i
′
,M
=
no obstacle
,iff
C
i
′
,M
∈ E ∧ C
i
′
,M−
1
∈ E
. The SES algorithm repeats this construction of an empty
path until it reaches the right end. During subsequent scans, when choosing an over-
lapping empty block, the SES algorithm chooses the rightmost block ending with
the
no obstacle
marker, if one exists. If no such empty block exists, the algorithm
simply chooses the rightmost empty block. After every scan,
MAX
_
total
is decre-
mented by 1. The algorithm will terminate when
MAX
_
total
=
MAX
_
cut
, and all the
requested objects have been moved into
MAX
_
cut
logical channels, on each of which
the order of the requested objects gives the access pattern during each broadcast.
Since choosing the next empty block is a fundamental step in the SES algorithm,
we define it first. Given a set of row indices
Rows
and a column
j,
nextblock
(
Rows
,j)
returns the appropriate row
i
to add to the empty path being constructed. To define
this function we also define
rightmost
(
Rows
,j)
which returns the row index of the
rightmost free block in among
B
ij
for
i ∈
Rows
.
Definition 21.
rightmost
(
Rows
,j) = i
such that
i ∈
Rows
&
freeright
(i, j ) =
max
(
freeright
(i
′
,j) | i
′
∈
Rows
)
.
nextblock
(
Rows
,j) =
let EBs
={i | i ∈
Rows
&
C
ij
∈ E}
/* Empty Blocks */
let OBs
={i | i ∈
EBs &
k =
freeright
(i, j )
&
C
ik
=
no obstacle
}
if OBs
={}
then return
(
rightmost
(
OBs
,j))
else return
(
rightmost
(
EBs
,j))
Definition 22.
In the SES algorithm, an obstacle on a broadcast may result in an inside switch if
the empty block on the left of it is scanned. Those obstacles whose empty blocks on
the left are not chosen to scan will not result in a switch. Cells that are not obstacles
will not generate inside switches. It should be noted that if the algorithm moves re-
quested objects from channel
A
to channel
B
, a switch is indicated, but if they are
subsequently moved from channel
B
to channel
C
, it is equal to moving from chan-
nel
A
to channel
C
, and still only one switch occurs. Thus, the strategy of choosing
