Processor Management Techniques for Mesh-Connected Multiprocessors.
Byung S. Yoo, Chita R. Das, Chansu Yu · 1995
This paper investigates various processor management techniques for improving the performance of mesh-connected multiprocessors. Three different techniques are analyzed. First, we use the smallest job first (SJF) policy to improve the spatial parallelism in a mesh. Next, a policy called multitasking and multiprogramming (M²) is introduced. The M² scheme allows multiprogramming of jobs on various submeshes. Finally, a novel approach, called "limit allocation" is used for job allocation. With this policy, a job (submesh) size is reduced if the job cannot be allocated. While all of the three approaches are viable alternatives, which in conjunction with any allocation algorithm can improve system performance beyond what is achievable with a complex allocation scheme and the usually assumed FCFS scheduling, the M² and limit allocation techniques are especially attractive for providing some additional features. The M² policy brings in the concept of time-sharing execution for better efficiency and the limit allocation shows how job size restriction can be beneficial for performance and faulttolerance in a mesh topology. Moreover, the limit allocation scheme can outperform any other approach even using the simplest allocation policy.