NONCONTIGUOUS PROCESSOR ALLOCATION ALGORITHMS FOR MESH-CONNECTED MULTICOMPUTERS

Current processor allocation techniques for highly parallel systems ar e typically restricted to contiguous allocation strategies for which p erformance suffers significantly due to the inherent problem of fragme ntation. As a result, message-passing systems have yet to achieve the high utilization levels exhibited by traditional vector supercomputers . We are investigating processor allocation algorithms which lift the restriction on contiguity of processors in order to address the proble m of fragmentation. Three noncontiguous processor allocation strategie s-Paging allocation, Random allocation, and the Multiple Buddy Strateg y (MBS)-are proposed and studied in this paper. Simulations compare th e performance of the noncontiguous strategies with that of several wel l-known contiguous algorithms. We show that noncontiguous allocation a lgorithms perform better overall than the contiguous ones, even when m essage-passing contention is considered. We also present the results o f experiments on an Intel Paragon XP/S-15 with 208 nodes that show non contiguous allocation is feasible with current technologies.