Efficient processor management schemes for mesh-connected multicomputers

This paper investigates various processor management techniques for improvi ng the performance of mesh-connected multicomputers. Unlike almost all prio r work where the focus was on improving the submesh recognition ability of the processor allocation algorithms, this research examines other alternati ves to improve system performance beyond what is achievable with usually as sumed first come first served (FCFS) scheduling and any allocation. First, we use the smallest job first (SJF) policy to improve the spatial paralleli sm in a mesh. Next. we introduce a generic processor management scheme call ed multitasking and multiprogramming (M-2). Then, an M-2 policy for mesh-co nnected multicomputers called virtual mesh (VM) is proposed and analyzed. T he proposed VM scheme allows multiprogramming of jobs on several VMs. Final ly, a novel approach called limit allocation is used for job allocation. Wi th this scheme, a job (submesh) size is reduced if the job cannot be alloca ted. The objective here is to reduce the job waiting time and hence improve the overall performance. While all of the three approaches are viable alte rnatives to reduce the average job response time under various workloads, t he VM and the limit allocation techniques are especially attractive for pro viding some additional features. The VM scheme brings in the concept of tim e-sharing execution for better efficiency and limit allocation shows how jo b size restriction can be beneficial for performance and fault-tolerance in a mesh topology. Moreover, the limit allocation scheme using even the simp lest allocation policy can outperform any other approach. (C) 2001 Publishe d by Elsevier Science B.V.