Information Technology Reference
In-Depth Information
as the summing operator. That is,
y
j
=
x
1
x
2
···
x
j
for 1
≤
j
≤
n
.Thus,if
(
n
)
+
on the input
x
=(
x
1
,
x
2
,
...
,
x
n
)
produces the output
y
,where
y
1
=
x
1
,
y
2
=
x
1
+
x
2
,
y
3
=
x
1
+
x
2
+
x
3
,
...
,
y
n
=
x
1
+
x
2
+
the set
A
is
, the natural numbers, and
is the integer addition operator
+
,then
P
+
x
n
. For example, shown below is the prefix
function on a 6-vector of integers under integer addition.
···
x
=(
2, 1, 3, 7, 5, 1
)
(
6
)
+
(
x
)=(
2, 3, 6, 13, 18, 19
)
A prefix function is defined only for operators
P
A
that are associative over the set
.An
A
is associative
if a) for all
a
and
b
in
A
,
a
b
is in
A
, and b) for all
a
,
b
,and
operator over
c
in
A
,
(
a
b
)
c
=
a
(
b
c
)
—that is, if all groupings of terms in a sum with the operator
have the same value. A pair
(
A
)
in which
is associative is called a
semigroup
.Three
semigroups on which a prefix function can be defined are
,
•
(
,
+)
where
are the natural numbers and
+
is integer addition.
}
∗
,
}
∗
is the set of binary strings and
•
(
{
0, 1
·
)
where
{
0, 1
·
is string concatenation.
•
(
A
,
copy
)
where
A
is a set and
copy
is defined by
a
copy
b
=
a
.
}
∗
It is easy to show that the concatenation operator
are
associative. (See Problem
2.20
.) Another important semigroup is the set of matrices under
matrix multiplication (see Theorem
6.2.1
).
Summarizing, if
(
·
on
{
0, 1
and
copy
on a set
A
(
n
)
n
n
on input
A
,
)
is a semigroup, the prefix function
P
:
A
→A
x
=(
x
1
,
x
2
,
...
,
x
n
)
produces as output
y
=(
y
1
,
y
2
,
...
,
y
n
)
,where
y
j
=
x
1
x
2
···
x
j
n
.
Load balancing
on a parallel machine is an important application of prefix computation.
A simple example of load balancing is the following: We assume that
p
processors, numbered
from 0 to
p
≤
j
≤
for 1
−
1, are running processes in parallel. We also assume that processes are born
and die, resulting in a possible imbalance in the number of processes active on processors.
Since it is desirable that all processors be running the same number of processes, processes
are periodically redistributed among processors to balance the load. To rebalance the load, a)
processors are given a linear order, and b) each process is assigned a Boolean variable with value
1 if it is alive and 0 otherwise. Each processor computes its number of living processes,
n
i
.A
prefix computation is then done on these values using the linear order among processors. This
computation provides the
j
th processor with the sum
n
j
+
n
j−
1
+
···
+
n
1
which it uses to
give each of its living processes a unique index. The sum
n
=
n
p
+
···
+
n
1
is then broadcast
to all processors. When the processors are in balance all have
processes except possibly
one that has fewer processes. Assigning the
s
th process to processor
(
s
mod
p
)
insures that
the load is balanced.
Another important type of prefix computation is the
segmented prefix computation
.In
this case two
n
-vectors are given, a
value vector
x
and a
flag vector
φ
. The value of the
i
th
entry
y
i
in the result vector
y
is
x
i
if
φ
i
is 1 and otherwise is the associative combination with
n/p
of
x
i
and the values between it and the first value
x
j
to the left of
x
i
for which the flag
φ
j
=
1. The first bit of
φ
is always 1. An example of a segmented prefix computation is shown
below for integer values and integer addition as the associative operation:
x
=(
2, 1, 3, 7, 5, 1
)
Search WWH ::
Custom Search