Paper Details

Mapping a process network onto a processor network

Authors: Lau, Francis C. M., Shea, K. M.

Abstract:

This paper addresses the problem of mapping an Occam program onto a transputer network. This mapping is essentially a graph embedding (or related) problem: i.e., find a function f: N -> { 1, 2.....| M |} such that certain performance criteria would be satisfied, where N is the set of processes in the Occam program (the graph) and M is the set of processors in the transputer network. Depending on the complexity of the graph as well as the target transputer network, many of these problems are NP-complete [1,2]. This paper addresses not the mapping algorithm and how it may achieve optimality, which is a policy matter, but the mechanism of mapping - that is, given a mapping algorithm, what exactly do we do to transform the program into an equivalent program that is ready to be downloaded onto the transputer network. Our answer is a precompiler which we have successfully implemented. We discuss several important problems that occurred in our construction of the mapping procedure, and briefly describe the actual implementation of the precompiler.

Proceedings:

OUG-9: Occam and the Transputer -- Research and Applications, Charlie Askew, 1988, pp 91 - 100 published by IOS Press, Amsterdam

This record in other formats: