Mapping Techniques for Load Balancing | Static, Dynamic, Block Distribution, Cyclic, Block Cyclic

                       Mapping Techniques for Load Balancing | Static, Dynamic, Block Distribution, Cyclic, Block Cyclic | mapping techniques for load balancing,Schemes for Static Mapping,Mappings Based on Data Partitioning,Array Distribution Schemes,Block Distributions,Cyclic and Block-Cyclic Distributions,Randomized Block Distributions,Graph Partitioning,Mappings Based on Task Partitioning,Hierarchical Mappings,Schemes for Dynamic Mapping,Centralized Schemes,Master Process,Slave Processes,Distributed Schemes

Watch this video to know about Mapping Techniques for Load Balancing.

Watch following Video:



Watch on YouTube: https://www.youtube.com/watch?v=R7jQew9S0J4

Reference:

                 Introduction to Parallel Computing, Second Edition, by Ananth Grama, Anshul Gupta, George Karypis, Vipin Kumar.

1. Decomposition

Objectives:
1. Small execution time
2. Reduce overheads of executing the tasks in parallel
Two key sources of overhead:
 -- i. The time spent in inter-process interaction
-- ii. Time that some processes may spend being idle.

Mapping techniques used in parallel algorithms can be broadly classified into two categories:

1. Static
                   Static mapping techniques distribute the tasks among processes prior to the execution of the algorithm.
                    The choice of a good mapping in this case depends on several factors:
i. knowledge of task sizes 
ii. size of data associated with tasks 
iii. characteristics of inter-task interactions
iv. parallel programming paradigm.

                    Algorithms that make use of static mapping are in general easier to design and program.

2. Dynamic
                   Dynamic mapping techniques distribute the work among processes during the execution of the algorithm.
                   If tasks are generated dynamically, then they must
be mapped dynamically too. If task sizes are unknown, then a static mapping can potentially lead to serious load-imbalances and dynamic mappings are usually more effective.


Schemes for Static Mapping:
1. Mappings Based on Data Partitioning
--Array Distribution Schemes 
     i. Block Distributions
     ii. Cyclic and Block-Cyclic Distributions
     iii. Randomized Block Distributions
--Graph Partitioning
2. Mappings Based on Task Partitioning
3. Hierarchical Mappings

Schemes for Dynamic Mapping:
1. Centralized Schemes
      --Master Process
      --Slave Processes
2. Distributed Schemes       
      Critical parameters of a distributed load balancing scheme are as follows:
       1. How are the sending and receiving processes paired together?
       2. Is the work transfer initiated by the sender or the receiver?
       3. How much work is transferred in each exchange?
       4. When is the work transfer performed?