Information Technology Reference
In-Depth Information
It is assumed that the components of a and b are drawn from a set over which the operations
of
(multiplication) and (addition) are defined, such as the integers.
Shown schematically in Fig. 1.12 on page 28 is the one-dimensional systolic array for the
convolution c = a
b at the second, fourth, fifth, and sixth steps of execution on input
vectors a =( a 0 , a 1 , a 2 ) and b =( b 0 , b 1 , b 2 ) . The components of these vectors are fed from
the left and right, respectively, spaced by zero elements. The first component of a enters the
array one step ahead of the first component of b . The result of the convolution is the vector
c =( c 0 , c 1 , c 2 , c 3 , c 4 ) . There is one more cell in the array than there are components in the
result. At each step the components of a and b in each cell are multiplied and added to the
previous value of the component of c in that cell. After all components of the two input vectors
pass through the cell, the convolution is computed.
The processors of a parallel computer generally do not communicate only with nearest
neighbors, as in the systolic array. Instead, processors often can communicate with remote
neighbors via a network. The type of networks chosen for a parallel computer can have a large
impact on their effectiveness.
The processors of the PRAM mentioned in Section 1.1 operate synchronously, alternating
between accessing a global memory and computing locally. Since the processors communicate
by writing and reading values to and from the global memory, all processors are at the same
distance from one another. Although the PRAM model makes two unrealistic assumptions,
namely that processors a) can act in synchrony and b) they can communicate directly via global
memory, it remains a good model in which to explore problems that are hard to parallelize,
even with the flexibility offered by this model.
.......................................
Problems
MATHEMATICAL PRELIMINARIES
1.1 Show that the sum S ( k ) below has value S ( k )= 2 k
1:
S ( k )= 2 k− 1 + 2 k− 2 +
+ 2 1 + 2 0
···
SETS, LANGUAGES, INTEGERS, AND GRAPHS
1.2 Let A =
{
}
, B =
{
}
,and C =
{
}
red, green, blue
green, violet
red, yellow, blue, green
.
Determine the elements in ( A
C )
×
( B
C ) .
1.3 Let the relation R
be defined by pairs ( a , b ) such that a and b have the same
remainder on division by 3. Show that R is an equivalence relation.
1.4 Let R
×
A be an equivalence relation. Let the set E [ a ] be the elements in A
equivalent under the relation R to the element a . Show that for all a , b
A
×
A the
equivalence classes E [ a ] and E [ b ] are either equal or disjoint. Also show that A is the
union of all equivalence classes.
1.5 In terms of the Kleene closure and the concatenation of sets, describe the languages
containing the following:
a)
beginning with 01.
b) Strings beginning with 0 that alternate between 0 and 1.
Strings over
{
0, 1
}
Search WWH ::




Custom Search