Information Technology Reference
In-Depth Information
9
10 11
f
+
,
ω
2
12
f
+
,
ω
0
f
+
,
ω
1
f
+
,
ω
3
c
j
+
1
s
j
g
j
5
6
7
8
f
+
,
ω
0
f
+
,
ω
2
f
+
,
ω
0
f
+
,
ω
2
p
j
v
j
u
j
c
j
1
2
3
4
a
0
a
2
a
1
a
3
(a)
(b)
Figure 7.1
Examples of Boolean and algebraic circuits.
circuits, these values are drawn from the set
and are called Boolean.) The function
computed at a vertex is defined through functional composition with values associated with
computational and input vertices on which the vertex depends. Boolean logic circuits are dis-
cussedatlengthinChapters
2
and
9
. Algebraic and combinatorial circuits are the subject of
Chapter
6
.(SeeFig.
7.1
.)
A circuit is a form of
unstructured parallel computer
. No order or structure is assumed
on the operations that are performed. (Of course, this does not prevent structure from being
imposed on a circuit.) Generally circuits are a form of
fine-grained parallel computer
;that
is, they typically perform low-level operations, such as
AND
,
OR
,or
NOT
in the case of logic
circuits, or addition and multiplication in the case of algebraic circuits. However, if the set
of values on which circuits operate is rich, the corresponding operations can be complex and
coarse-grained.
The
dataflow computer
is a parallel computer designed to simulate a circuit computation.
It maintains a list of operations and, when all operands of an operation have been computed,
places that operation on a queue of runnable jobs.
We now examine a variety of structured computational models, most of which are coarse-
grained and synchronous.
B
=
{
0, 1
}
7.3
Parallel Computers with Memory
Many coarse-grained, structured parallel computational models have been developed. In this
section we introduce these models as well as a variety of performance measures for parallel
computers.
Search WWH ::
Custom Search