Performance evaluation of noncontiguous allocation algorithms for 2D mesh interconnection networks

Several noncontiguous allocation strategies have been proposed for 2D mesh-connected multicomputers. These allocation strategies differ in their ability to detect free submeshes and in the degree of contiguity that exists among the submeshes they allocate to the same job. The previous Adaptive Noncontiguous Allocation (ANCA) policy was evaluated based on a proposed formula that estimates the job execution time when the job is allocated noncontiguous submeshes. Using this formula, simulation results had shown that ANCA could outperform the preceding Multiple Buddy Strategy (MBS). However, the execution times of jobs under noncontiguous allocation depend on message sizes, the number of messages sent, message contention and distances messages traverse. In this paper, we evaluate ANCA for different communication patterns using an event-driven simulator operating at the flit level, which allows for a more realistic evaluation that takes into account the shape of allocation and contention among messages. Moreover, we compare the performance of ANCA with that of other noncontiguous allocation strategies, MBS, Greedy Available Busy List (GABL), and Paging(0). The results show that ANCA is inferior to the remaining strategies, and that GABL has the best performance results, expressed in terms of the average turnaround time and mean system utilization performance parameters.

► We have compared the performance of well-known noncontiguous allocation strategies proposed for 2D mesh-connected multicomputers.
► We have evaluated ANCA using flit-level simulation, which allows for a more realistic evaluation of this scheme than the one carried out originally.
► ANCA performs relatively poorly in most cases because it suffers from external fragmentation.
► The performance of GABL is superior to all other strategies due to its ability to alleviate the contention inside the network by maintaining a large degree of contiguity among allocated processors.