Architecture-independent graphical tool for automatic contention-free process-to-processor mapping

Hong Shen, Sam Lor, Piyush Maheshwari

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)


Mapping of parallel programs onto parallel computers for efficient execution is a fundamental problem of great significance in parallel processing. This paper presents an architecture-independent software tool for contention-free mapping of arbitrary parallel programs onto parallel computers with arbitrary configurations. This mapping tool is based on an efficient heuristic algorithm that runs in time O(n3 + m4) in the worst case for mapping n tasks onto m processors, where m ≪ n in most practical cases. It is fully implemented and incorporated into a graph editing system to produce a graphical mapping tool which enables its user to monitor and control the mapping process. The user can assist the mapping process or employ the algorithm to map automatically. Our mapping tool has been tested and its performance evaluated extensively. Experimental results show that our tool combines user intuition and mapping heuristics effectively to make it a powerful mapping tool which is practical to use. Our mapping tool can be easily extended for use in the more general case when the link contention-degree is bounded to a fixed system-specified value without increasing its complexity.

Original languageEnglish
Pages (from-to)115-139
Number of pages25
JournalJournal of Supercomputing
Issue number2
Publication statusPublished - Feb 2001
Externally publishedYes


Dive into the research topics of 'Architecture-independent graphical tool for automatic contention-free process-to-processor mapping'. Together they form a unique fingerprint.

Cite this