Algorithms and Parallel Computing

1.6 RELATING PARALLEL ALGORITHM AND PARALLEL ARCHITECTURE

The IEEE Standard Dictionary of Electrical and Electronics Terms [4] defines “parallel” for software as “simultaneous transfer, occurrence, or processing of the individual parts of a whole, such as the bits of a character and the characters of a word using separate facilities for the various parts.” So in that sense, we say an algorithm is parallel when two or more parts of the algorithms can be executed independently on hardware. Thus, the definition of a parallel algorithm presupposes availability of supporting hardware. This gives a hint that parallelism in software is closely tied to the hardware that will be executing the software code. Execution of the parts can be done using different threads or processes in the software or on different processors in the hardware. We can quickly identify a potentially parallel algorithm when we see the occurrence of “FOR” or “WHILE” loops in the code.

On the other hand, the definition of parallel architecture, according to The IEEE Standard Dictionary of Electrical and Electronics Terms [4], is “a multi-processor architecture in which parallel processing can be performed.” It is the job of the programmer, compiler, or operating system to supply the multiprocessor with tasks to keep the processors busy. We find ready examples of parallel algorithms in fields such as

• scientific computing, such as physical simulations, differential equations solvers, wind tunnel simulations, and weather ...