Contemporary processor allocation schemes for multicomputers suffer from a fragmentation problem which causes underutilization of the processing nodes. The RSR and ANCA schemes, based on the concepts of size-reduction and non-contiguous allocation, show considerable performance improvement. However the penalties associated with these schemes limit their usage in environments with memory-bounded or communication-intensive jobs. We propose to use simple directives provided by the users to apply the appropriate allocation scheme and thus maximize the performance benefit. We present such a hybrid processor allocation scheme which combines the previously proposed conventional allocation, RSR and ANCA schemes. The hybrid allocation scheme is evaluated via extensive simulation. It outperforms the conventional allocation scheme and can be implemented easily while maximizing the resource utilizations.

An analytical model for submesh reliability of mesh-connected systems is proposed in this paper. A mesh is considered operational as long as a functional submesh of the required size is available. We use the principle of inclusion and exclusion to find the exact probability of having a functional submesh within a partition of the mesh. The partitions are taken along either dimension of the mesh. The partitions along the rows are called row partitions (RPs) and along the columns are called column partitions (CPs). The reliability of a partition is then used to approximate the submesh reliability of the system and, thus, this model is called partitioned mesh (PM) model. Instead of using a computationally intensive recursive algorithm as done in the previous work, a closed form approximation of the submesh reliability is derived in this paper. The PM model is validated through simulation and compared with the earlier proposed approximation techniques. It is shown that the PM model provides better approximations for submesh reliability with constant computational complexity.

The performance of a multicomputer system depends on the processor management strategy. Processor management deals with processor allocation and job scheduling. Most of the processor allocation and job scheduling schemes proposed in the literature incur high implementation complexity and are therefore impractical to be integrated. In this paper, we propose an integrated processor management scheme that includes a bypass-queue scheduling policy and a fixed-orientation allocation algorithm. Both policies have very low complexities and are hence suitable to be integrated. Both policies improve the system performance considerably when applied in isolation. The integrated scheme provides even better performance.

The fragmentation problem in multicomputer systems reduces the system utilization and prohibits the systems from performing at their full capacity. In this paper, we propose a generic job allocation method for multicomputer systems based on job size reduction. We reduce the subsystem size requirement adaptively according to the availability of processors. The fragmentation problem is greatly alleviated by this approach. To ensure that the benefit of reducing fragmentation is not outweighed by the penalty of executing jobs on less number of processors, we restrict the number of times the size of a job can be reduced; hence the name restricted size reduction (RSR). Extensive simulations are conducted to validate the RSR method for hypercubes and mesh-based systems with different allocation algorithms. It is observed in both mesh and hypercube that by using the RSR method a simple algorithm can provide better performance than the more sophisticated allocation algorithms. We have also compared RSR method with the limit allocation that is based on a similar idea. Our method outperforms the limit allocation and provides better fairness to different size jobs. The performance gain, fairness, and low complexity makes the RSR method highly attractive.