Information Technology Reference
In-Depth Information
PARALLEL PREFIX
2.20 a) Let
copy
:
S
2
→
S
be the operation
a
copy
b
=
a
Show that
(
S
,
copy
)
is a semigroup for
S
an arbitrary non-empty set.
}
∗
of binary strings. Show that
b) Let
·
denote string concatenation over the set
{
0, 1
it is associative.
2.21 The segmented prefix computation with the associative operation
on a “value”
n
-
vector
x
over a set
S
, given a “flag vector”
φ
over
B
, is defined as follows: the value
of the
i
th entry
y
i
of the “result vector”
y
is
x
i
if its flag is 1 and otherwise is the
associative combination with
of
x
i
and the entries to its left up to and including the
first occurrence of a 1 in the flag array. The leftmost bit in every flag vector is 1. An
example of a segmented prefix computation is given in Section
2.6
.
Assuming that
(
S
,
)
is a semigroup, a segmented prefix computation over the set
S
×B
⊗
of pairs is a special case of general prefix computation. Consider the operator
on pairs
(
x
i
,
φ
i
)
of values and flags defined below:
(
x
2
,
φ
2
)) =
(
x
2
,1
)
φ
2
=
1
((
x
1
,
φ
1
)
⊗
(
x
1
x
2
,
φ
1
)
φ
2
=
0
Show that
((
S
,
B
)
,
⊗
)
is a semigroup by proving that
(
S
,
B
)
is closed under the oper-
is associative.
2.22 Construct a logic circuit of size
O
(
n
log
n
)
and depth
O
(log
2
n
)
that, given a binary
n
-
tuple
x
,computesthe
n
-tuple
y
containing the running sum of the number of 1's in
x
.
2.23 Given 2
n
Boolean variables organized as pairs 0
a
or 1
a
,designacircuitthatmovespairs
of the form 1
a
to the left and the others to the right without changing their relative
order. Show that the circuit has size
O
(
n
log
2
n
)
.
2.24 Linear recurrences play an important role in many problems including the solution
of a tridiagonal linear system of equations. They are defined over “near-rings,” which
are slightly weaker than rings in not requiring inverses under the addition operation.
(Rings are defined in Section
6.2.1
.)
A
near-ring
(
ator
⊗
and that the operator
⊗
·
and an associative and commutative addition operator
+
.(If
+
is commutative, then
for all
a
,
b
R
·
,
+)
is a set
R
,
together with an associative multiplication operator
∈R
,
a
+
b
=
b
+
a
.) In addition,
·
distributes over
+
;thatis,forall
a
,
b
,
c
c
.
A
first-order linear recurrence of length
n
is an
n
-tuple
x
=(
x
1
,
x
2
,
...
,
x
n
)
of vari-
ables over a near-ring
(
∈R
,
a
·
(
b
+
c
)=
a
·
b
+
a
·
R
,
·
,
+)
that satisfies
x
1
=
b
1
and the following set of identities
for 2
≤
j
≤
n
defined in terms of elements
{
a
j
,
b
j
∈R|
2
≤
j
≤
n
}
:
x
j−
1
+
b
j
Use the ideas of Section
2.7
on carry-lookahead addition to show that
x
j
can be written
x
j
=
a
j
·
x
1
+
d
j
where the pairs
(
c
j
,
d
j
)
are the result of a prefix computation.
x
j
=
c
j
·
Search WWH ::
Custom Search