Subtorii Allocation Strategies for Torus Connected Networks

In this paper we investigate the problem of how to schedule n independent jobs on an m \Theta m torus based network. We develop a model to 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 preemptively scheduling a given set of jobs on a torus of given size with a given deadline. We provide analysis for both the algorithms. 1 Introduction The mesh and torus networks have been recognized as versatile interconnection networks for massively parallel computing. Mesh/torus-like low-dimensional networks have recently received a lot of attention for their better scalability to larger networks, as opposed to more complex networks such as hypercubes [BP95]. Examples of ..