Introduction to Multiprocessors - Fundamentals of Computer Organization and Architecture - page 246

ILLIAC-IV used such an interconnection scheme. The interconnection network in
the ILLIAC-IV allowed each processor to communicate directly with four neighbor-
ing processors in an 8

8 matrix pattern such that the ith processor can communicate

directly with the (i 2 8)th processors.

In the second SIMD scheme, processors and memory modules communicate with
each other via the interconnection network. Two processors can transfer data
between each other via intermediate memory module(s) or possibly via intermediate
processor(s). Assume, for example, that processor i is connected to memory modules
(i 2

1)th, (i þ 1)th, (i 2 8)th, and (i þ

1). In this case, processor 1 can communicate with processor 5 via
memory modules 2, 3, and 4 as intermediaries. The BSP (Burroughs' Scientific
Processor) used the second SIMD scheme.
In order to illustrate the effectiveness of SIMD in handling array operations, con-
sider, for example, the operations of adding the corresponding elements of two one-
dimensional arrays A and B and storing the results in a third one-dimensional array
C. Assume also that each of the three arrays has N elements. Assume also that SIMD
scheme 1 is used. The N additions required can be done in one step if the elements of
the three arrays are distributed such that M 0 contains the elements A(0), B(0), and
C(0), M 1 contains the elements A(1), B(1), and C(1), ... , and M N 2 1 contains the
elements A(N 2

1), i, and (i þ

1). In this case, all processors will execute
simultaneously an add instruction of the form C A þ B. After executing this
single step by all processors, the elements of the resultant array C will be stored
across the memory modules such that M 0 will store C(0), M 1 will store C(1),

1), B(N 2 1), and C(N 2

,

...

and M N 2 1 will store C(N 2 1).

It is customary to formally represent an SIMD machine in terms of five-tuples
(N, C, I, M, F). The meaning of each argument is given below.

2 k , k

1. N is the number of processing elements (N ¼ 1).

2. C is the set of control instructions used by the control unit, for example, do,
for, step.
3. I is the set of instructions executed by active processing units.
4. M is the subset of processing elements that are enabled.
5. F is the set of interconnection functions that determine the communication
links among processing elements.

11.4. MIMD SCHEMES

MIMD machines use a collection of processors, each having its own memory, which
can be used to collaborate on executing a given task. In general, MIMD systems
can be categorized based on their memory organization into shared-memory and
message-passing architectures. The choice between the two categories depends on
the cost of communication (relative to that of the computation) and the degree of
load imbalance in the application.