loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
19th IEEE International Parallel and Distributed Processing Symposium (IPDPS'05) - Workshop 18
A Fixed-Structure Learning Automaton Solution to the Stochastic Static Mapping Problem
Denver, Colorado
April 04-April 08
ISBN: 0-7695-2312-9
Geir Horn, SIMULA Research Laboratory, Norway
B. John Oommen, Carleton University, Ottawa, ON, Canada
This paper considers the problem of distributing the processes of a parallel application onto a set of computing nodes. This problem called the Static Mapping Problem (SMP) is known to be NP-Hard, and has been tackled using heuristic solutions. The objective of this paper is to present the first reported Learning Automaton (LA) based solution to the SMP, generated by the close resemblance of the SMP to the equipartitioning problem. The LA in question is of the so-called Fixed-Structure family, solution to the equipartitioning problem is then modified to solve the SMP. Several algorithmic variants of this solution have been implemented, and these have all been rigorously tested and evaluated through extensive simulations on randomly generated parallel applications. The focus in this work is to demonstrate the applicability of LA to the SMP, not to optimise and evaluate the performance of the proposed strategy. The results presented here clearly demonstrate that LA provide a promising tool that can effectively solve the mapping problem.
Index Terms:
Static Mapping; Learning Automata; Task assignment; Parallel Computing
Citation:
Geir Horn, B. John Oommen, "A Fixed-Structure Learning Automaton Solution to the Stochastic Static Mapping Problem," ipdps, vol. 19, pp.297b, 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS'05) - Workshop 18, 2005
Usage of this product signifies your acceptance of the Terms of Use.