Performance Evaluation of Noncontiguous Allocation Algorithms for 2D Mesh Interconnection Networks
تاريخ النشر |
2011-12-01 |
الباحث |
|
الكلمات المفتاحية |
Mesh, Contention, Processor Fragmentation, Noncontiguous Submesh Allocation, Average Turnaround Time, System Utilization. |
| |
الملخص بالانجليزي |
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. |
|
|
