Abstract
In this paper, we investigate the problem of how to schedule n independent jobs on an m x m torus based network. We develop a model to quantify the effect of contention for communication links on the dilation of job execution time when multiple jobs share communication links; we then design an efficient algorithm to schedule a set of n independent jobs with different torus size requirements on a given torus with an objective to minimize the total schedule length. We also develop a feasibility algorithm for pre-emptively scheduling a given set of jobs on a torus of given size with a given deadline. We provide analysis for both the algorithms. (C) 2000 Elsevier Science Ltd.
Original language | English (US) |
---|---|
Pages (from-to) | 131-145 |
Number of pages | 15 |
Journal | Mathematical and Computer Modelling |
Volume | 31 |
Issue number | 2-3 |
DOIs | |
State | Published - Jan 2000 |
Externally published | Yes |
Keywords
- Deadline
- Independent jobs
- Job scheduling
- Link contention
- Torus networks
ASJC Scopus subject areas
- Modeling and Simulation
- Computer Science Applications