To design simple parallel algorithm in a sequence of methodology structures of parallel computing design process, some design issues are to be described that present the design process in explanatory approach.
Partitioning issues:
The partitioning stage of a design structure is intended to expose opportunities for parallel execution. Ignoring issues such as number of processors required and other resources etc. focus is on defining a large number of small tasks (fine-grained decomposition). A good partition divides both the computation and the data into small pieces. The partitioning methods are based on two approaches;
- Domain decomposition: It focuses on the data associated with a problem and then determines an appropriate computation with those data. Following focusing points under domain decomposition are as follows;
- First partition data; ideally divide data into small pieces of approximately equal size.
- Next partition computation, typically by associating each operation with the data on which it operates.
- Focus first on the largest data structure or on the data structure that is accessed most frequently.
- Functional decomposition: It focuses on decomposing the computation and after that works on associated data.
In parallel processing problem decomposes the computation into separate tasks before considering how to partition the data. Consequently these complementary techniques under first stage of parallel algorithm design structure i.e. partitioning seek to avoid replicating computation and data.
Communication issues:
Conceptualize to processed to computation, it is required that data must be transferred between tasks, on which one task can send messages and from which the other can receive. This is the outcomes of the communication phase of parallel algorithm design structure. Here, focus will be on the following two issues;
- Channel structure: Channel structure links (direct or indirect) tasks that require data (consumers) with tasks that possess those data (producers).
- Message-passing structure: We specify the message that must be sent and received on the channels.
Definition of a channel involves an intellectual cost and the sending of a message involves a physical cost—avoid introducing unnecessary channels and communication operations.
In general, the aim here is to optimize the performance by distributing communication operations over many tasks and organize communication operations in a way that permits concurrent execution.
Agglomeration issues:
The goal of agglomeration is to being making the parallel solution practical and as efficient as possible. This phase is intended to evaluate the tasks and required communication with respect to performance and implementation costs.
There are two main questions:
- Is it useful to combine, or agglomerate, tasks to reduce the number of tasks?
- Is it worthwhile to replicate data and/or computation?
In general, in the agglomeration phase we move from abstract to concrete.
Mapping:
Mapping phase is intended to specify where each task has to be executed i.e. each task is assigned to a processor in a manner to maximize processor utilization and minimize communication costs. The mapping problem does not arise on uniprocessors or on shared-memory computers that provide automatic task scheduling.
General-purpose mapping mechanisms have yet to be developed for scalable parallel computers.
Our goal in developing mapping algorithms is normally to minimize total execution time. We use two strategies to achieve this goal:
- We place tasks that are able to execute concurrently on different processors, so as to enhance concurrency.
- We place tasks that communicate frequently on the same processor, so as to increase locality.
The general-case mapping problem is NP-complete.
Two important issues involved in the mapping phase:
- Enhancing concurrency: It deals with placing tasks that can be executed simultaneously on different processors.
- Increasing locality: It refers to placing tasks that likely communicate frequently on the same processor.
Consequently, the outcomes of this process are a program that creates tasks and performs the mapping of tasks to individual processors.
Also Check: Parallel Algorithm Design Approach
