Question

We would like to execute the loop below as efficiently as possible. We have two different machines, a MIMD machine and a SIMD machine.

for (i=0;i<2000;i++)

for(j=0;j<3000;j++)

X_array[i][j] = Y_array[j][i] + 200;

6.11.1 [10] For a 4 CPU MIMD machine, show the sequence of MIPS instructions that you would execute on each CPU. What is the speedup for this MIMD machine?

6.11.2 [10] For an 8-wide SIMD machine (i.e.,8 parallel SIMD functional units), write an assembly program in using your own SIMD extensions to MIPS to execute the loop. Compare the number of instructions executed on the SIMD machine to MIMD machine.

Short answer

(6.11.1)–

for i := 0 step 1 until 2000

begin

for j := 0 step 1 until 3000

for ADD;

ADD:

X_array[i][j]:=Y_array[j][i]+200;

join;

end;

(6.11.2)

for j := 0 step 1 until 3000

begin

X_array[i][j] := Y_array[j][i] + 200, (0<i<2000);

end;

Step-by-step solution

SIMD and MIMD

SIMD means Single Instruction Multiple Data. In this type of architecture all the units work parallely on the same single instruction but with different data inputs.

MIMD means Multiple Instruction Multiple Data:- In this type of architecture all the processor units works on different instructions but to achieve the common task.

MISD and SMID are said to have only one similarity which is both the two architectures support vector processing.

There are several between the two architectures. In SIMD, single instruction is applied to different data simultaneously while in MISD, several instructions operate on a single piece of data. SIMD produces immediate results, while MISD does not. SIMD uses array processor, while MISD uses pipelined vector and systolic array processor. SMID follows parallel processing while MISD follows series processing.

Loop for MIMD Machine.

for i := 0 step 1 until 2000 #loop runs until i value less than 2000

begin

for j := 0 step 1 until 3000 #loop runs until j value less than 3000

for ADD;

ADD:

X_array[i][j]:=Y_array[j][i]+200; #Calculate value of X using array addition

join;

end;

Loop for SIMD Machine.

for j := 0 step 1 until 3000 #loop runs for j value less than 3000

begin

X_array[i][j] := Y_array[j][i] + 200, (0<i<2000); #Calculate value of X using array addition.

end;

The number of instructions executed on the SIMD Machine is lesser than that of on the MIMD Machine.