Parallel algorithm design is not easily reduced to simple recipes. Rather, it requires the sort of integrative thought that is commonly referred to as “creativity.” However, it can benefit from a methodical approach that maximizes the range of options considered, that provides mechanisms for evaluating alternatives, and that reduces the cost of backtracking from bad choices. We describe such an approach and illustrate its application to a range of problems. Our goal is to suggest a framework within which parallel algorithm design can be explored.
This framework of design parallel algorithm is helpful to design simple parallel algorithms in a methodical fashion and recognize design flaws that compromise efficiency or scalability. Most programming problems have several parallel solutions. The best solution may differ from that suggested by existing sequential algorithms. The design methodology that we describe is intended to foster an exploratory approach to design in which machine-independent issues such as concurrency are considered early and machine-specific aspects of design are delayed until late in the design process. This methodology structures of parallel computing design process focuses on main four distinct stages:
- Partitioning,
- Communication,
- Agglomeration, and
- Mapping
Note: The acronym (PCAM) may serve as a useful reminder of this structure. In the first two stages of this methodological structure, we focus on concurrency and scalability and seek to discover algorithms with these qualities while in the third and fourth stages, attention shifts to locality and other performance-related issues. The four stages are illustrated in Figure 2.1 and can be summarized as follows:
Figure 2.1: PCAM: A design methodology for parallel programs or parallel algorithm. Starting with a problem specification, we develop a partition, determine communication requirements, agglomerate tasks, and finally map tasks to processors.
Also Check: PRAM Model of Computation
Partitioning: The computation that is to be performed and the data operated on by this computation are decomposed into small tasks. Practical issues such as the number of processors in the target computer are ignored, and attention is focused on recognizing opportunities for parallel execution.
Communication: The communication required to coordinate task execution is determined, and appropriate communication structures and algorithms are defined.
Agglomeration: The task and communication structures defined in the first two stages of a design are evaluated with respect to performance requirements and implementation costs. If necessary, tasks are combined into larger tasks to improve performance or to reduce development costs.
Mapping: Each task is assigned to a processor in a manner that attempts to satisfy the competing goals of maximizing processor utilization and minimizing communication costs. Mapping can be specified statically or determined at runtime by load-balancing algorithms.
