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