A layered method for process and code mapping (Q578904)

The mapping problem has been shown to be computationally equivalent to the graph isomorphism problem; as such it is unlikely that a polynomial time algorithm exists for its solution. Practical algorithms of general applicability and low computational complexity have not been found and are unlikely to appear. This paper describes a layered method to support specialised process and code mapping strategies. The method separates the task of mapping a problem to a virtual machine from the task of mapping a virtual machine to a physical machine. It allows multiple virtual machines to execute concurrently and many applications to run on a single virtual machine. The method is in use on a parallel implementation of Flat Concurrent Prolog which runs on an Intel iPSC Hypercube; for concreteness the description is based on this implementation.