Intra-job Communication Contention and Request-Partitioning-Based Allocation Strategies in 2D-Mesh Multicomputers
Sulieman Bani‐Ahmad · International Symposium on Parallel Architectures, Algorithms and Programming · 2010
We use simulation to characterize the performance of previous non-contiguous Gradual-Request-Partitioning (GRP-) based processor allocation strategies for 2D mesh multi computers under various intra-job communication loads. GRP-based allocation strategies try to make contiguous allocation to the request at hand using some contiguous algorithm, if it fails, it tries to divide the request into multiple sub-requests and allocates them using the same contiguous allocation strategy. In this paper, we characterize the impact of intra-job communication density on the performance of GRP-based allocation strategies in space-shared parallel systems with two-dimensional mesh topology. We show that the relative performance of GRP-based allocation strategies considerably vary with communication density due to inter-job communication contention caused by requests’ over-partitioning. To remedy this problem, we propose and evaluate Bounded GRP-based that enforces an upper bound on the maximum number of partitions into which any request can be sub-divided. We show the importance of bounding partitioning level in GRP-based allocation strategies, partitioning level is the maximum number of partitions allowed before allocating any request.