Principles of Parallel Algorithm Design

Posted By on March 17, 2016


Download PDF
Impact of Process-Processor Mapping and Mapping Techniques
Preliminaries and Decomposition

Algorithm development is a critical component of problem solving using computers. A sequential algorithm is essentially a recipe or a sequence of basic steps for solving a given problem using a serial computer. Similarly, a parallel algorithm is a recipe that tells us how to solve a given problem using multiple processors. However, specifying a parallel algorithm involves more than just specifying the steps. At the very least, a parallel algorithm has the added dimension of concurrency and the algorithm designer must specify sets of steps that can be executed simultaneously. This is essential for obtaining any performance benefit from the use of a parallel computer. In practice, specifying a nontrivial parallel algorithm may include some or all of the following:

  • Identifying portions of the work that can be performed concurrently.

  • Mapping the concurrent pieces of work onto multiple processes running in parallel.

  • Distributing the input, output, and intermediate data associated with the program.

  • Managing accesses to data shared by multiple processors.

  • Synchronizing the processors at various stages of the parallel program execution.

Typically, there are several choices for each of the above steps, but usually, relatively few combinations of choices lead to a parallel algorithm that yields performance commensurate with the computational and storage resources employed to solve the problem. Often, different choices yield the best performance on different parallel architectures or under different parallel programming paradigms.

Impact of Process-Processor Mapping and Mapping Techniques
Preliminaries and Decomposition

Download PDF

Posted by Akash Kurup

Founder and C.E.O, World4Engineers Educationist and Entrepreneur by passion. Orator and blogger by hobby

Website: http://world4engineers.com