Computing at Glasgow University
Paper ID: 8039
DCS Tech Report Number: TR-2005-194

A Simulation Study of Allocation Strategies on the Mesh Interconnection Networks
Bani Mohammad,S. Ould-Khaoua,M. Ababneh,I.

Publication Type: Tech Report (internal)
Appeared in:
Page Numbers :
Publisher: N/A
Year: 2005

Contiguous allocation of parallel jobs often suffers from severe fragmentation as it requires that the allocated processors be contiguous and have the same topology as the network connecting these processors. Lifting the contiguity condition could reduce fragmentation. However, this often lead to messages from different jobs to interfere with each other and increase contention inside the network, resulting in high communication delays, and thus in a low overall system speed-up. In this paper, two non-contiguous job allocation strategies, referred to as the Paging and Greedy-Available, are proposed for the 3D mesh network and compared using simulation against the well-known contiguous First Fit strategy. The results show that our proposed non-contiguous strategies exhibit superior performance properties despite the added contention that results from non-contiguity.

Keywords: Multicomputers, Meshes, Processor Fragmentation, Scheduling Effectiveness, Turnaround Time, Dispersal Ratio, Simulation.

Bibtex entry Endnote XML