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

Mapping of parallel programs onto parallel computers for efficient executio n is a fundamental problem of great significance in parallel processing. Th is paper presents an architecture-independent software tool for contention- free mapping of arbitrary parallel programs onto parallel computers with ar bitrary configurations. This mapping tool is based on an efficient heuristi c algorithm that runs in time O(n(3) + m(4)) in the worst case for mapping n tasks onto m processors, where m << n in most practical cases. It is full y implemented and incorporated into a graph editing system to produce a gra phical mapping tool which enables its user to monitor and control the mappi ng 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 us er intuition and mapping heuristics effectively to make it a powerful mappi ng 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.