A fixed-structure learning automaton solution to the stochastic static mapping problem

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 provides a promising tool that can effectively solve the mapping problem.