A Solution for the Processor Allocation Problem: Topology Conserving Graph Mapping by Self-Organization

We consider the problem of how to allocate the tasks of a parallel program to the processor elements of a multicomputer system such that the communication overhead of the program is minimized. This problem basically amounts to a graph embedding problem since both the program and the multicomputer can be modeled as graphs. The embedding problem can be characterized as the search for a topology conserving mapping of the source graph to the target graph.To find such mappings we apply the Kohonen selforganization process. Our main concern in this article is to show how this graph embedding problem can be fitted to the Kohonen technique. To that end, we introduce feature vectors for each node of the source graph to provide topological information exceeding direct neighborhood and considering larger surroundings.The particular optimization goal of the task mapping problem is being related to known results of the Kohonen process. The behavior and performance of our approach is illustrated by some sample graphs.