Task Assignment on Distributed-Memory Systems with Adaptive Wormhole Routing

Assignment of tasks of a parallel program onto processors of a distributed-memory system is critical to obtain minimal program completion time by minimizing communication overhead. This paper presents task assignment heuristics for wormhole-routed systems. A Temporal Communication Graph is used to model task graphs and to identify spatial and temporal link contention. The interplay between degree of routing adaptivity, topology, application characteristics, and task assignment is studied by evaluating random task graphs using an event-driven simulator. The study indicates that even for systems supporting fully-adaptive routing, efficient task assignment is necessary to reduce program completion time especially for communication-bound applications. 1 Introduction Task assignment problem is defined as mapping tasks of a parallel program onto processors of a multiprocessor system such that the program gets executed with minimal time [1, 9]. If the number of tasks exceeds the number of pr..