Occam implementation of process-to-processor mapping on the Hathi-2 transputer system

This paper presents a polynomial-time Occam program for automatically mapping parallel programs onto multiprocessor systems. Based on the heuristic strategy of self-adjusting mapping, our program consists of grouping, placement, routing and self-adjusting procedures. Grouping groups the user-defined processes in a parallel program into target tasks with a possible load-balancing. Placement places the target tasks onto the processors in a transputer network. Routing produces edge-disjoint physical communication paths for the logical communication requirements among the placed tasks in the network. Self-adjusting adjusts first the placement scheme when the routing fails and then the grouping scheme when the necessary adjusting for placement is unable to make the routing succeed. These four procedures work co-operatively until a successful process-to-processor mapping has been finally achieved after a series of progressive self-adjustments. For the problem of mapping n processes in an arbitrary task graph onto m processors in a transputer network configured into a torus, the program needs time O(max{n²,m⁵}) in the worst case on one processor under full adjusting. The time is reduced to O(max{n²,m⁴}) if the adjusting heuristic is degraded into semi-adjusting, and to O(max{n²,m²}) when the adjusting heuristic is completely eliminated. The latter result holds only for the transputer networks providing message routing and multiplexing. We demonstrate the implementation result and performance evaluation of the program on the Hathi-2 transputer system. The implementation shows that for both regular and irregular task graphs the program works very well and produces satisfactory results.