Self-adjusting Mapping: A Heuristic Mapping Algorithm for Mapping Parallel Programs on to Transputer Networks

Open Access
Publisher Website
Google Scholar
Abstract
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 {n2, m5}) under full adjusting, O(max {n2, m4}) under semi-adjusting and O(max {n2, m2}) 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.

This publication has 0 references indexed in Scilit: