Mapping

Definition and examples

• assignment of tasks to processors
  e.g. in distributed computing systems (tasks = program modules)
• distributing computation across the computation resources
  e.g. mapping parallel algorithms to parallel architectures

The model used

• k tasks t_i and n processors p_j
• model of tasks: static task graph
• model of processors: network graph

• model of costs:

  X_ij=cost of executing task t_i on processor p_j

  C_{i1 i2}=communication costs if tasks t_i1 and t_i2 assigned to different processors

• goal: minimize costs such as execution cost + communication cost
  

Examples of algorithms

• Stone [1] uses a network flow algorithm (Ford-Fulkerson method "mincut")
  cost of cut = total sum of execution and communication costs
  

• Berman&Snyder [2] use three steps:

  contraction (using edge grammer, truncation)
  

  layout/embedding (edges mapped to paths)
  

  multiplex
  

  cost function: # nodes + edges mapped to a node, # edges mapped to an edge

Known results

Problem	optimal polynomial time algorithm	suboptimal algorithm
2 processor systems	yes
2 proc. with varying load	yes
tree-structured graph	yes
series parallel graph	yes
3 processor systems		yes
2 proc. with load balancing		yes
2 proc. with memory constraint on one		yes

Tools

References

• H. S. Stone, Multiprocessor Scheduling with the Aid of Network Flow Algorithms, IEEE Transactions on Software Engineering, January 1977
• F. Berman and L. Snyder, On Mapping Parallel Algorithms into Parallel Architectures, Journal of Parallel and Distributed Computing, April 1987
• S. H. Bokhari, Assignment Problems in Parallel and Distributed Computing, Kluwer Academic Publishers, 1987
• M. G. Norman and P. Thanisch, Models of Machines and Computation for Mapping in Multicomputers, ACM Computing Surveys, September 1993