Download as PDF, PPTX
Parallel and Distributed Computing Chapter 4
- 1.
- 2.
- 3. Parallel algorithm models Themodels of parallel algorithm are developed by considering a strategy for dividing the data and processing method and also applying a suitable strategy to reduce interaction. Following are some parallel algorithm models are Data parallel models Task Graph Model Work Pool Model Master Slave Model Pipeline Model /Producer-Consumer Model Hybrid Model
- 4. Data parallel model Tasksare assigned to processes and each task performs similar types of operations, so that data parallelism is achieved by applying single operation on multiple data Overhead is reduced by overlapping computation and interaction Characteristics 1. Single address space 2. Message passing mechanism 3. Large problem encourages data parallelism because we can use more processors to solve large problems, similar to SIMD
- 6. Data parallel model 1.Simple algorithm model 2. Tasks are statistically mapped into processors and each task perform similar operations 3. Identical operations being operate on different data item so called data parallelism 4. Can be implement in both shared address space and message passing paradigm 5. The degree of parallelism is increase as the size of problem size increase hence effective for big problems
- 7. TASK GRAPH MODEL Parallelismis expressed by a task graph which is either trivial or non trivial. Suitable in situation where large amount of data but comparatively less computations Tasks are mapped statistically to in order to reduce interaction Different problems are divided into different tasks to implement a graph, each Problem is represented by vertex/task Each task is independent but dependent with its predecessor. Dependent task start executions when previous task has been completed.
- 9. Work pool model Tasksare assigned among processes to balance the load so any process execute any process. In this model operations are large but data is small No pre assigning of tasks to process so assigning can be centralized or decentralized Task may be available in the beginning or may be generated dynamically. If the task is generated dynamically and decentralized assigning of task is done the termination detection algorithm is required.
- 11. Master/slave method One ormore process that generate tasks and assign those tasks to slave for processes Tasks are assigned before if: 1. Master can estimate the number of operations 2. Slaves are assigned smaller tasks 3. Shared address space and message passing scheme This model is suitable in share memory system
- 13. Master/slave method -precautions Master processes generate work and allocate to worker processors hence no pre-mapping is needed Care should be taken to assure that the master does not become a congestion point. It may happen if tasks are too small or processors are comparatively fast. Tasks should be selected in a way that the cost of performing a task dominates the cost of communications.
- 14. Pipeline model /Producer Consumer Model Stream of data is passed on through processors Data is passed through a series of processes New data generate new tasks that is to be processed by process in the queue A queue Is built, by using either array, tree graph
- 16. Hybrid model •When morethan one model is required for solving a problem, hybrid algorithm model is used. •A hybrid model consists of multiple models either applied hierarchically or multiple models applied sequentially to different phases of the parallel algorithm.