Scheduling independent jobs for torus connected networks with/without linkcontention

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 to quantify the effect of contention for communication links on the dilation of job execut ion time when multiple jobs share communication links; we then design an ef ficient algorithm to schedule a set of n independent jobs with different to rus size requirements on a given torus with ari objective to minimize the t otal schedule length. We also develop a feasibility algorithm for pre-empti vely scheduling a given set of jobs on a torus of given size with a given d eadline. We provide analysis for both the algorithms. (C) 2000 Elsevier Sci ence Ltd. All rights reserved.