Information Technology Reference
In-Depth Information
Definition 11.
The set of
empty cells
,
E
,is
{C
i,j
| C
i,j
∈ S}
.
Definition 12.
The set of
restrictive cells
,
R
,is
{C
i,j
| C
i,j
∈ S ∧ (C
i,j +
1
∈ S ∨
C
i,j −
1
∈ S)}
.
Definition 13.
The set of
free cells
,
F
,is
{C
i,j
| C
i,j
∈ E ∧ C
i,j
∈ R}
.
An important concept in our algorithms is the empty block which is a contiguous
sequence of empty cells in one row.
Definition 14.
An
empty block
,
B
i,j
, is the largest set of contiguous empty cells in
row
i
starting in column
j
.
Given a set of empty blocks all starting in the same column, a
rightmost empty
block
is a block in the set that is not smaller than any other block in the set, i.e., no
other empty block extends farther to the right of it.
Definition 15
( Overlapped empty blocks) .
Two empty blocks
B
and
B
′
overlap each
other, iff they each contain a cell from some column, i.e.,
∃j
, such that
C
i,j
∈ B ∧
C
i
′
,j
∈ B
′
∧ i = i
′
.
Definition 16.
The set of
obstacles
,
O
,is
{C
i,j
| C
i,j
∈ S ∧ C
i,j −
1
∈ E ∧
C
i,j −
2
∈ E}
.
8 . 1 P a r a l l e l O b j e c t S c a n
In this presentation, graphically, lines (access lines) are used to represent the ac-
cess patterns in different passes. Parallel Object Scan (POS) uses
MAX_cut
passes to
scan all requested objects on a broadcast. Starting from the leftmost column to the
right, POS in parallel constructs
MAX_cut
lines, column by column. It attempts to
use access lines to visit all the requested objects in the next column with the fewest
number of switches from the previous column. POS observes which cell
C
i,j
with
an access line has a less chance to have a requested object in the future on the same
channel and uses this line to make a channel switch when necessary. This strategy
minimizes the number of switches.
Definition 17
( Access line) .
A vector of length
M
representing one pass through the
matrix. The value
l[j ]
is the channel (row #) that the line reads at time (column)
j
.
We define
freeright
(i, j )
to be the rightmost column of the
Empty block
.
