Self-adjusting mapping: A heuristic mapping algorithm for mapping parallel programs on to transputer networks

The problem of mapping parallel programs on to multiprocessor systems is a fundamental problem of great significance in parallel processing. In this paper we propose a fast heuristic algorithm to solve this problem on transputer networks. Our mapping algorithm mainly contains three modules: grouping, placement and routeing, where grouping puts processes in the program into tasks which can be one-to-one placed on to processors in the transputer network, placement sets the grouped tasks on to the processors and routeing produces edge-disjoint physical communication paths for logical communication requirements. The algorithm works by combining three modules under a self-adjusting scheme towards a successful mapping result. For mapping n processes in an arbitrary parallel program on to m processors in a transputer network of grid structure, our algorithm has a worst-case time complexity O(max {n², m⁵}) under full adjusting, O(max {n², m⁴}) under semi-adjusting and O(max {n², m²}) under no adjusting, where the last holds only for the transputer networks providing message routeing and multiplexing. The algorithm has been implemented in Occam on the Hathi-2 transputer system.