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

H. Shen

Research output: Contribution to journalArticlepeer-review

7 Citations (Scopus)


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.

Original languageEnglish
Pages (from-to)71-80
Number of pages10
JournalComputer Journal
Issue number1
Publication statusPublished - Feb 1992
Externally publishedYes


Dive into the research topics of 'Self-adjusting mapping: A heuristic mapping algorithm for mapping parallel programs on to transputer networks'. Together they form a unique fingerprint.

Cite this