Information Technology Reference
In-Depth Information
It is important to note that the time to communicate between processors is often very
large relative to the length of a CPU cycle. Thus, the assumption that it takes zero time to
communicate between processors, the basis of Brent's principle, holds only for tightly coupled
processors.
7.5
Multidimensional Meshes
In this section we examine multidimensional meshes. A
one-dimensional mesh
or
linear
array
of processors is a one-dimensional (1D) array of computing elements connected via
nearest-neighbor connections.
(See Fig.
7.7
.)
If the vertices of the array are indexed with
integers from the set
{
1, 2, 3,
...
,
n
}
,thenvertex
i
,2
≤
i
≤
n
−
1, is connected to vertices
i
1and
i
+
1. If the linear array is a
ring
,vertices1and
n
are also connected. Such an
end-to-end connection can be made with short connections by folding the linear array about
its midpoint.
The linear array is an important model that finds application in very large-scale integrated
(VLSI) circuits. When the processors of a linear array operate in synchrony (which is the
usual way in which they are used), it is called a linear
systolic array
(a systole is a recurrent
rhythmic contraction, especially of the heart muscle). A systolic array is any mesh (typically
1D or 2D) in which the processors operate in synchrony. The computing elements of a systolic
array are called
cells
. A linear systolic array that convolves two binary sequences is described
in Section
1.6
.
A
multidimensional mesh
(see Fig.
7.8
)(or
mesh
) offers better connectivity between pro-
cessors than a linear array. As a consequence, a multidimensional mesh generally can compute
functions more quickly than a 1D one. We illustrate this point by matrix multiplication on
2D meshes in Section
7.5.3
.
Figure
7.8
shows 2D and 3D meshes. Each vertex of the 2D mesh is numbered by a pair
(
r
,
c
)
,where0
−
≤
r
≤
n
−
≤
c
≤
n
−
1and0
1 are its row and column indices. (If the cell
A
3,1
0
0
0
A
3,2
0
A
2,1
A
3,3
0
A
2,2
0
0
A
1,1
A
2,3
0
0
A
1,2
0
A
1,3
0
0
0
x
1
S
1
x
2
S
2
x
3
S
3
Figure 7.7
A linear array to compute the matrix-vector product
A
x
,where
A
=[
a
i
,
j
]
and
T
x
=(
x
1
,
...
,
x
n
)
.Oneachcycle,the
i
th processor sets its current sum,
S
i
,tothesumtoits
right,
S
i
+
1
, plus the product of its local value,
x
i
, with its vertical input.
Search WWH ::
Custom Search