AuthorsG. Horn and J. B. Oommen
EditorsH. J. Siegel, D. A. Bader and J. Gaudiot
TitleA Fixed-Structure Learning Automaton Solution to the Stochastic Static Mapping Problem
Publication TypeProceedings, refereed
Year of Publication2005
Conference NameProceedings of the 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS 2005)
Date PublishedApril
Place PublishedDenver, Colorado, USA, April 3-8

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.

Citation KeyHorn.2005.1