Efficient processor allocation is crucial for obtaining high performance in space-shared parallel computers. A good processor allocation algorithm should find available processors for incoming jobs, if they exist, with minimum overhead. In this paper, we propose such a fast and efficient processor allocation scheme for mesh-connected multicomputers. By using simple coordinate calculation and spatial subtraction, the proposed scheme reduces the search space drastically and, hence, can locate a free submesh very quickly. The algorithm is implemented efficiently using a stack and therefore is called the stack-based allocation (SBA) algorithm. Extensive simulation reveals that our scheme incurs much less allocation overhead than all of the existing allocation algorithms, while delivering competitive performance.

Modeling the perfomance of space-shared multicomputers is a non-trivial task mainly due to difficulty in modeling the effect of external fragmentation on system performance. Mesh-connected multicomputers are hard to model in particular because of great variance in job sizes. Therefore, researchers have relied on simulation method to evaluate the mesh performance. We propose a novel modeling technique called hybrid method in this paper. The proposed technique utilizes simulation method to estimate the capacity of a system. Then, a queueing model with multiple servers is constructed using the system capacity as the number of servers in the queueing system. The technique is validated through simulation experiments. The results reveal that the hybrid method provides very close estimation of the mesh performance with very little overhead. The proposed technique can also be used for performance modeling of other multicomputers with different topologies.

Fast and efficient processor allocation and job scheduling algorithms are essential components of a multi-user multicomputer operating system. In this paper we propose two novel processor management schemes which meet such demands for mesh-connected multicomputers. A stack-based allocation algorithm that can locate a free sub-mesh for a job very quickly using simple coordinate calculation and spatial subtraction is proposed. Simulation results show that the stack-based allocation algorithm outperforms all the existing allocation policies in terms of allocation overhead while delivering competitive performance. Another technique, called group scheduling, schedules jobs in such a way that the jobs belonging to the same group do not block each other. The groups are scheduled in an FCFS order to prevent starvation. This simple but efficient scheduling policy reduces the response rime significantly by minimizing the queueing delay for the jobs in the same group. These two schemes, when used together can provide faster service to users with very little overhead.