AuthorsG. Horn and J. B. Oommen
EditorsJ. Aguilar, H. Chu, J. St-Amand, I. Galkin and P. Chantzimisios
TitleGeneralised Pursuit Learning Automata for Non-Stationary Environments Applied to the Stochastic Static Mapping Problem
Publication TypeProceedings, refereed
Year of Publication2005
Conference NameThe 11th International onference on Information Systems Analysis and Synthesis (ISAS 2005) and The 2nd International Conference on Cybernetics and Information Technologies, Systems and Applications (CITSA 2005)
EditionVolume 1
Date PublishedJuly
PublisherInternational Institute of Informatics and Systemics (IIIS)
Place PublishedOrlado, Florida, USA July 14-17

In this paper, we propose the first variable-structure Learning-Automata (LA) based approach to solve the Stochastic Static Mapping Problem (SMP). The problem 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.


ISBN 980-6560-42-6

Citation KeyHorn.2005.6