Information Technology Reference
In-Depth Information
Connections between PRAMs and circuits can be derived that are similar to those stated
for Turing machines and circuits in Section
8.13.2
. In this section we consider only log-space
uniform families of circuits.
Given a PRAM, we now construct a circuit simulating it. This construction is based
onthatgiveninSection
3.4
. With a suitable definition of
log-space uniform family of
PRAMs
the circuits described in the following lemma constitute a log-space uniform family
of circuits. (See Problem
8.35
.) Also, this theorem can be extended to PRAMs that access
memory locations with addresses much larger than
O
(
p
(
n
)
t
(
n
))
, perhaps through indirect
addressing. (See Problem
8.37
.)
LEMMA
8.14.1
Consider a function on input words of total length
n
bits computed by a CREW
PRAM
P
in time
t
(
n
)
with a polynomial number of processors
p
(
n
)
in which the largest common
memory address is
O
(
p
(
n
)
t
(
n
))
. This function can be computed by a circuit of size
O
(
p
2
(
n
)
t
(
n
)
+
p
(
n
)
t
2
(
n
))
and depth
O
(log(
p
(
n
)
t
(
n
)))
.
Proof
Since
P
executes at most
t
(
n
)
steps, by a simple extension to Problem
8.4
(only one
RAMCPU at a time writes a word), we know that after
t
(
n
)
steps each word in the common
memory of the PRAM has length at most
b
=
t
(
n
)+
n
+
K
for some constant
K
≥
0,
because the PRAM can only compare or add numbers or shift them left by one position on
each time step. This follows because each RAM CPU uses integers of fixed length and the
length of the longest word in the common memory is initially
n
.
We exhibit a circuit for the computation by
P
by modifying and extending the circuit
sketched in Section
3.4
to simulate one RAM CPU. This circuit uses the next-state/output
circuit for the RAM CPU together with the next-state/output circuit for the random-access
memory of Fig.
3.21
(repeated in Fig.
8.22
). The circuit of Fig.
8.22
(a) either writes a new
value
d
j
for
w
i
,
j
,the
j
th component of the
i
th memory word of the random-access memory,
or it writes the old value
w
i
,
j
. The circuit simulating the common memory of the PRAM
is obtained by replacing the three gates at the output of the circuit in Fig.
8.22
(a) with a
subcircuit that assigns to
w
i
,
j
the value of
w
i
,
j
if
c
i
=
0foreachRAMCPUandthe
OR
of
the values of
d
j
supplied by each RAM CPU if
c
i
=
1forsomeCPU.Herewecountonthe
fact that at most one CPU addresses a given location for writing. Thus, if a CPU writes to
a location, all other CPUs cannot do so. Concurrent reading is simulated by allowing every
component of every memory cell to be used as input by every CPU.
Since the longest word that can be constructed by the CREW PRAM has length
b
=
t
(
n
)+
n
+
K
, it follows from Lemma
3.5.1
that the next-state/output circuit for the random-
access memory designed for one CPU has size
O
(
p
(
n
)
t
2
(
n
))
and depth
O
(log(
p
(
n
)
t
(
n
)))
.
The modifications described in the previous paragraph add size
O
(
p
2
(
n
)
t
(
n
))
(each of the
p
(
n
)
t
(
n
)
memory words has
O
(
p
(
n
))
new gates) and depth
O
(log
p
(
n
))
(each
OR
tree
has
p
(
n
)
inputs) to this circuit. As shown at the end of Section
3.10
,thesizeanddepth
of a circuit for the next-state/output circuit of the CPU are
O
(
t
(
n
)+log(
p
(
n
)
t
(
n
)))
and
O
(log
t
(
n
)+loglog(
p
(
n
)
t
(
n
)))
, respectively. Since these sizes and depths add to those
for the common memory, the total size and depth for the next-state/output circuit for the
PRAM are
O
(
p
2
(
n
)
t
(
n
)+
p
(
n
)
t
2
(
n
))
and
O
(log(
p
(
n
)
t
(
n
)))
, respectively.
We now show that the function computed by a log-space uniform circuit family can be
computed in poly-logarithmic time on a PRAM.
Search WWH ::
Custom Search