In this paper, we propose the first variable-structure Learning-Automata (LA) based approach to solve the Stochastic Static Mapping Problem (SMP). The prob1cm is known to be NP-hard and involves distributing the processes of a parallel application onto a set of computing nodes. Our solution has salient characteristics novel to both the fields of LA and process allocation. Thus, while the solution attempts to optimise the inter-process communication costs and the workload allocated to each machine, it achieves this without artificially generating potential pairings which are to be used by our previous fixed-structure LA-based solution. Furthermore, unlike all the reported estimator-based LA, we propose the utilization of the recently introduced weak estimators suitable for non-stationary environments. We report the results obtained by simulating our algorithm on various problems where the number of processes and nodes is small. In each case, the accuracy of the strategy to converge to a feasible partitioning is remarkable - sometimes even as high as 96%. We are currently investigating how the current solution can be enhanced to be rendered scalable.

Additional Metadata
Keywords Learning Automata, Parallel Computing, Static Mapping, Task assignment
Conference 2nd International Conference on Cybernetics and Information Technologies, Systems and Applications, CITSA 2005, Jointly with the 11th International Conference on Information Systems Analysis and Synthesis, ISAS 2005
Citation
Horn, G. (Geir), & Oommen, J. (2005). Generalised pursuit learning automata for non-stationary environments applied to the stochastic static mapping problem. In 2nd International Conference on Cybernetics and Information Technologies, Systems and Applications, CITSA 2005, 11th International Conference on Information Systems Analysis and Synthesis, ISAS 2005 (pp. 91–97).