Parallel Computation - Models of Computation: Exploring the Power of Computing - page 286

multiple-instruction, multiple-data (MIMD) model describes a parallel machine that runs
a potentially different program on potentially different data on each processor but can send
messages among processors.
The SIMD machine is generally designed to have a single instruction decoder unit that
controls the action of each processor, as suggested in Fig. 7.3 . SIMD machines have not been a
commercial success because they require specialized processors rather than today's commodity
processors that benefit from economies of scale. As a result, most parallel machines today are
MIMD. Nonetheless, the SIMD style of programming remains appealing because programs
having a single thread of control are much easier to code and debug. In addition, a MIMD
model, the more common parallel model in use today, can be programmed in a SIMD style.
While the MIMD model is often assumed to be much more powerful than the SIMD
one, we now show that the former can be converted to the latter with at most a constant
factor slowdown in execution time. Let K be the maximum number of different instructions
executable by a MIMD machine and index them with integers in the set

{

1, 2, 3, ... , K

}

.
Slow down the computation of each machine by a factor K as follows: 1) identify time intervals
of length K ,2)onthe k th step of the j th interval, execute the k th instruction of a processor if
this is the instruction that it would have performed on the j th step of the original computation.
Otherwise, let the processor be idle by executing its NOOP instruction. This construction
executes the instructions of a MIMD computation in a SIMD fashion (all processors either
are idle or execute the instruction with the same index) with a slowdown by a factor K in
execution time.
Although for most machines this simulation is impractical, it does demonstrate that in the
best case a SIMD program is at worst a constant factor slower than the corresponding MIMD
program for the same problem. It offers hope that the much simpler SIMD programming style
can be made close in performance to the more difficult MIMD style.

7.3.2 The Data-Parallel Model
The data-parallel model captures the essential features of the SIMD style. It has a single
thread of control in which serial and parallel operations are intermixed. The parallel opera-
tions possible typically include vector and shifting operations (see Section 2.5.1 ), prefix and
segmented prefix computations (see Sections 2.6 ), and data-movement operations such as are
realized by a permutation network (see Section 7.8.1 ). They also include conditional vector
operations , vector operations that are performed on those vector components for which the
corresponding component of an auxiliary flag vector has value 1 (others have value 0).
Figure 7.4 shows a data-parallel program for radix sort .Thisprogramsorts nd -bit inte-
gers,

, represented in binary. The program makes d passes over the integers.
On each pass the program reorders the integers, placing those whose j th least significant bit
( lsb ) is 1 ahead of those for which it is 0. This reordering is stable ;thatis,thepreviousor-
dering among integers with the same j th lsb is retained. After the j th pass, the n integers are
sorted according to their j least significant bits, so that after d passes the list is fully sorted.
The prefix function

{ x [ n ] , ... , x [ 1 ] }

( n )
+ computes the running sum of the j th lsb on the j th pass. Thus, for
k such that x [ k ] j = 1 ( 0 ) , b k ( c k ) is the number of integers with index k or higher whose
j th lsb is 1 (0). The value of a k = b k x [ k ] j +( c k + b 1 ) x [ k ] j is b k or c k + b 1 , depending on
whether the lsb of x [ k ] is 1 or 0, respectively. That is, a k is the index of the location in which
the k th integer is placed after the j th pass.

P