Communication Overhead in Non-Contiguous Processor Allocation Policies for 3D Mesh-Connected Multicomputers

Various contiguous and non-contiguousprocessor allocation policies have been proposed for two-dimensional mesh-connected multicomputers. Contiguous allocation suffers from high processor fragmentation because it requires that a parallel job be allocated a single contiguous processor subset of the exact shape and size requested. In non-contiguousallocation, a job may be allocated multiple dispersed processor subsets. This can reduce processor fragmentation, however it may increase the communication overhead because inter-processor distances can be longer and messages from different jobs can contend for communication resources. The extra communication overhead depends on how allocation requests are partitioned and assigned processors. In this paper, we investigate non-contiguousallocation for three-dimensional meshes. A greedy policy where partitioning is based on the processors available is proposed and compared, using simulation, to contiguous first-fit allocation, and to non-contiguousschemes adapted from previous two-dimensional schemes. In the detailed flit-level simulator, developed for this research, several common communication patterns are considered. The results show that non-contiguousallocation is expected to improve system performance in three-dimensional mesh-connected multicomputers substantially