Data Parallelism - Example

Example

The program below expressed in pseudocode—which applies some arbitrary operation, foo, on every element in the array d—illustrates data parallelism:

if CPU = "a" lower_limit := 1 upper_limit := round(d.length/2) else if CPU = "b" lower_limit := round(d.length/2) + 1 upper_limit := d.length for i from lower_limit to upper_limit by 1 foo(d)

If the above example program is executed on a 2-processor system the runtime environment may execute it as follows:

• In an SPMD system, both CPUs will execute the code.
• In a parallel environment, both will have access to d.
• A mechanism is presumed to be in place whereby each CPU will create its own copy of lower_limit and upper_limit that is independent of the other.
• The if clause differentiates between the CPUs. CPU "a" will read true on the if; and CPU "b" will read true on the else if, thus having their own values of lower_limit and upper_limit.
• Now, both CPUs execute foo(d), but since each CPU has different values of the limits, they operate on different parts of d simultaneously, thereby distributing the task among themselves. Obviously, this will be faster than doing it on a single CPU.

This concept can be generalized to any number of processors. However, when the number of processors increases, it may be helpful to restructure the program in a similar way (where cpuid is an integer between 1 and the number of CPUs, and acts as a unique identifier for every CPU):

for i from cpuid to d.length by number_of_cpus foo(d)

For example, on a 2-processor system CPU A (cpuid 1) will operate on odd entries and CPU B (cpuid 2) will operate on even entries.