Paper Details

%T Mapping a process network onto a processor network
%A Francis C. M. Lau, K. M. Shea
%E Charlie Askew
%B OUG\-9: Occam and the Transputer \-\- Research and Applications
%X 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.

If you have any comments on this database, including inaccuracies, requests to remove or add information, or suggestions for improvement, the WoTUG web team are happy to hear of them. We will do our best to resolve problems to everyone's satisfaction.

Copyright for the papers presented in this database normally resides with the authors; please contact them directly for more information. Addresses are normally presented in the full paper.