Toward a realistic task scheduling model
Oliver Sinnen, Leonel A. Sousa, Frode Eika Sandnes · IEEE Transactions on Parallel and Distributed Systems · 2006
Task scheduling is an important aspect of parallel programming. Most of the heuristics for this NP-hard problem are based on a very simple system model of the target parallel system. Experiments revealed the inappropriateness of this classic model to obtain accurate and efficient schedules for real-systems. In order to overcome this shortcoming, a new scheduling model was proposed that considers the contention for communication resources. Even though the accuracy and efficiency improved with the consideration of contention, the new contention model is still not good enough. The crucial aspect is the involvement of the processor in communication. This paper investigates the involvement of the processor in communication and its impact on task scheduling. A new system model is proposed based on the contention model that is aware of the processor involvement. The challenges for the scheduling techniques are analyzed and two scheduling algorithms are proposed. Experiments on real parallel systems show the significantly improved accuracy and efficiency of the new model and algorithms.
Cited by 82 works. doi:10.1109/tpds.2006.40
Authors
References
- Handbook of Genetic Algorithms
- Active messages
- Parallel Computer Architecture: A Hardware/Software Approach
- NP-complete scheduling problems
- LogP: towards a realistic model of parallel computation
- Active Messages: A Mechanism for Integrated Communication and Computation
- A comparison of list schedules for parallel processing systems
- A compile-time scheduling heuristic for interconnection-constrained heterogeneous processor architectures
- Hypertool: a programming aid for message-passing systems
- Scheduling Precedence Graphs in Systems with Interprocessor Communication Times