Understanding the definition of SPMD

Question

From Wikipedia

SPMD (single program, multiple data) is a technique employed to achieve parallelism; it is a subcategory of MIMD. Tasks are split up and run simultaneously on multiple processors with different input in order to obtain results faster.

1. Does a program running on SPMD runs as either multiple processes or a process with multiple threads? If former, are the multiple processes runs the same program?

2. Wikipedia tries to compare SPMD with SIMD:

   In SPMD, multiple autonomous processors simultaneously execute the same program at independent points, rather than in the lockstep that SIMD imposes on different data. With SPMD, tasks can be executed on general purpose CPUs; SIMD requires vector processors to manipulate data streams. Note that the two are not mutually exclusive.

   What does "at independent points" mean? Does point means time? If yes, isn't "at independent points" contradict "simultaneously"?

3. Wikipedia also compares SPMD with SMP:

   Unlike SPMD, shared memory multiprocessing, also called symmetric multiprocessing or SMP, presents the programmer with a common memory space and the possibility to parallelize execution by having the program take different paths on different processors. The program starts executing on one processor and the execution splits in a parallel region, which is started when parallel directives are encountered. In a parallel region, the processors execute a single program on different data. A typical example is the parallel DO loop, where different processors work on separate parts of the arrays involved in the loop. At the end of the loop, execution is synchronized, only one processor continues, and the others wait. The current standard interface for shared memory multiprocessing is OpenMP. It is usually implemented by lightweight processes, called threads.

   From Section 6.3 of Computer Organization and Design, Fifth Edition: The Hardware/Software interface by David A. Patterson, John L. Hennessy:

   programmers normally write a single program that runs on all processors of an MIMD computer, relying on conditional statements when different processors should execute different sections of code. This style is called Single Program Multiple Data (SPMD), but it is just the normal way to program a MIMD computer.

   I don't quite understand how SPMD and SMP are different as stated in Wikipedia, and maybe some paraphrasing may help? In particular, Wikipedia says in SMP, a program can take different paths on different processors. In Patterson's book, in SPMD, a program can also run different sections of code on different processors.

   Wikipedia says "The current standard interface for shared memory multiprocessing is OpenMP". Is multithreading by OpenMP or PThread on multiple processors SPMD or SMP?

Thanks.

Answer 1

You are taking these definitions too literally (as if they were mathematical definitions that could be used in a proof.) These terms all come from the "heroic" age of computer architecture when people were designing by the "seat of their pants" and kind of just getting a feel for what works and what doesn't. Treat them more like terms for writing poetry than mathematics.

1. a. SPMD might refer to either multiple threads sharing an address space or multiple processes with independent address spaces sharing only through message passing or through the file system.

   b. Typically with SPMD in an environment with separate processes each process would be loaded from the same executable file.

2. Each thread (or process) in a SPMD machine has its own instruction pointer (indicating what instruction should be executed next). Each thread in a SPMD program updates its instruction pointer independently. So the threads in a SPMD program execute simultaneously, but they are executing different instructions and there is no required correlation between the instructions those threads are executing.

   In a SIMD program there is only one instruction pointer. On every time step every execution unit is executing the same instruction simultaneously. (The term NVidia uses for SIMD execution unit is "core", the term most other people use is "vector lane.")

3. a. SMP is not part of Flynn's taxonomy. Flynn's taxonomy is SISD, SIMD, MISD, MIMD. That's it. "SPMD" is something that someone made up after the fact but is the same thing as MIMD (as pointed out by the Hennessy and Patterson quote you include.) "SMP" is part of a completely different poem. It might be best to think of SMP as a particular way of implementing SPMD computers. SMP typically stands for "Symmetric Multiprocessor" not "Symmetric Multiprocessing".

   b. Multithreading by OpenMP or Pthreads on multiple processors is SPMD (because you are running multiple independent threads on the same program executable.) You might use a SMP to execute your SPMD OpenMP or Pthreads program, or you might use some other implementation of SPMD.