Communication overhead in non-contiguous processor allocation policies for 3D mesh-connected multicomputers

الملخص EN

Various contiguous and non-contiguous processor allocation policies have been proposed for two-dimensional mesh-connected multicomputer.

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-contiguous allocation, 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-contiguous allocation 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-contiguous schemes 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-contiguous allocation is expected to improve system performance in three-dimensional mesh-connected multicomputer substantially.