Information Technology Reference
In-Depth Information
(
0, 0
)
(
0, 1
)
(
0, 2
)
(
0, 3
)
(
1, 0
)
(
1, 1
)
(
1, 2
)
1, 3
)
(
2, 0
)
(
2, 1
)
(
2, 2
)
(
2, 3
)
(
3, 0
)
(
3, 1
)
3, 2
)
3, 3
)
(a)
(b)
Figure 7.8
(a) A two-dimensional mesh with optional connections between the boundary
elements shown by dashed lines. (b) A 3Dmesh (a cube) in which elements are shown as subcubes.
(
r
,
c
)
is associated with the integer
rn
+
c
,thisisthe
row-major order
of the cells. Cells are
numbered left-to-right from 0 to 3 in the first row, 4 to 7 in the second, 8 to 11 in the third,
and 12 to 15 in the fourth.) Vertex
(
r
,
c
)
is adjacent to vertices
(
r
−
1,
c
)
and
(
r
+
1,
c
)
for
≤
r
≤
n
−
2. Similarly, vertex
(
r
,
c
)
is adjacent to vertices
(
r
,
c
−
1
)
and
(
r
,
c
+
1
)
for
1
≤
c
≤
n
−
1
2. Vertices on the boundaries may or may not be connected to other boundary
vertices, and may be connected in a variety of ways. For example, vertices in the first row
(column) can be connected to those in the last row (column) in the same column (row) (this is
a
toroidal mesh
) or the next larger column (row). The second type of connection is associated
with the dashed lines in Fig.
7.8
(a).
Each vertex in a 3D mesh is indexed by a triple
(
x
,
y
,
z
)
,0
1, as suggested
in Fig.
7.8
(b). Connections between boundary vertices, if any, can be made in a variety of
ways. Meshes with larger dimensionality are defined in a similar fashion.
A
d
-dimensional mesh consists of processors indexed by a
d
-tuple
(
n
1
,
n
2
,
...
,
n
d
)
in
which 0
≤
x
,
y
,
z
≤
n
−
d
. If processors
(
n
1
,
n
2
,
...
,
n
d
)
and
(
m
1
,
m
2
,
...
,
m
d
)
are adjacent, there is some
j
such that
n
i
=
m
i
for
j
≤
n
j
≤
N
j
−
1for1
≤
j
≤
=
i
and
|
n
j
−
m
j
|
=
1. There may also
be connections between boundary processors, that is, processors for which one component of
their index has either its minimum or maximum value.
7.5.1 Matrix-Vector Multiplication on a Linear Array
As suggested in Fig.
7.7
, the cells in a systolic array can have external as well as nearest-neighbor
connections. This systolic array computes the matrix-vector product
A
x
of an
n
n
matrix
with an
n
-vector. (In the figure,
n
=
3.) The cells of the systolic array beat in a rhythmic
fashion. The
i
th processor sets its current sum,
S
i
,totheproductof
x
i
with its vertical input
plus the value of
S
i
+
1
to its right (the value 0 is read by the rightmost cell). Initially,
S
i
=
0for
1
×
n
. Since alternating vertical inputs are 0, the alternating values of
S
i
are 0. In Fig.
7.7
the successive values of
S
3
are
A
1,3
x
3
,0,
A
2,3
x
3
,0,
A
3,3
x
3
, 0, 0. The successive values of
S
2
≤
i
≤
Search WWH ::
Custom Search