PROCESSOR ALLOCATION USING PARTITIONING IN MESH-CONNECTED PARALLEL COMPUTERS

Several processor allocation schemes for mesh connected parallel compu ters have been proposed in the literature. These schemes aim at improv ing system performance by reducing internal fragmentation or by enhanc ing submesh recognition ability. In this paper, we propose a system pa rtitioning approach to reduce external fragmentation and thereby impro ve system performance. The target systems considered here are two-dime nsional meshes where the side lengths are powers of 2. Processors are allocated to a partitioned mesh based on their submesh size requiremen ts. The proposed scheme can be implemented in conjunction with any of the existing processor allocation schemes and thereby can also exploit the advantages offered by those schemes. The performance measurements are done through simulation experiments. Completion time for a fixed number of jobs, internal and external fragmentation, and system utiliz ation are measured as performance indicators. It is observed that, in most cases, the proposed scheme demonstrates better performance than t he previously proposed algorithms. Time complexity of the proposed sch eme is less by a factor of n than the corresponding allocation scheme without partitioning, where n = log(2){min(w, h)}, and w and h are the width and height of a two-dimensional mesh. (C) 1996 Academic Press, Inc.