An Application of a Game of Discrete Generalised Pursuit Automata to Solve a Multi-Constraint Partitioning Problem

This paper presents a Learning Automaton (LA) solution to the Multi-Constrained Mapping problem, which has its applications in the allocation of processes on processors so as to satisfy multiple (possibly conflicting) constraints. Mathematically, it considers the problem of partitioning a set of elements (or objects) into mutually exclusive classes (or groups), where elements which are "similar" to each other are, hopefully, located in the same class. This problem has been shown to be NP-Hard, and the literature reports solutions in which the similarity constraint consists of a single index. For example, typical "similarity" conditions that have been used in the literature include those in which "similar" objects are accessed together (as in the context of query systems), or when they communicate (as processes do) with each other. The application at hand is the static mapping problem (SMP) of distributing the processes of a parallel application onto a set of computing nodes. Such an application may run on multiple GRID sites where it is desirable avoid centralised control and mapping. This paper proposes a solution to this combinatorial optimization problem resulting from the collective behaviour of independent Discrete General Pursuit Automata (DGPA) that tries to learn the digraph of the communication among the processes of the application, and group together processes with strong mutual dependencies. Earlier learning solutions to the problem were either based on centralised mapping with full system knowledge. In this paper, we attempt to relax this assumptions, thus rendering the problem more complex. The present solution performs very well when the system size is small. However, the simulated results demonstrate that the quality of the final solution decreases with the number of elements. Thus, although this is the first reported solution to the problem which incorporates the specific digraph properties of the objects, the scalability of the solution to the prob- lem which incorporates the specific digraph properties of the objects, the scalability of the solution remains open.