Computing at Glasgow University
Paper ID: 7869
DCS Tech Report Number: TR-2005-189

Noncontiguous Processor Allocation for Three-Dimensional Mesh Multicomputers
Ababneh,I. Bani Mohammad,S.

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

We study noncontiguous processor allocation for three-dimensional mesh multicomputers, and compare it to contiguous allocation. Contiguous allocation suffers from severe processor fragmentation because it requires that the allocated processors have the same topology as the multicomputer, and that they be contiguous. The goal of lifting the contiguity condition is to reduce fragmentation. However, messages from different parallel applications may interfere with each other and increase contention in the interconnection network. Two contiguous allocation policies, the Paging and Greedy Available policies, are proposed and compared, using simulation, to the well-known contiguous First Fit policy. The results show that the noncontiguous policies are superior to First Fit, despite the added contention that results from noncontiguity.

Keywords: 3D Mesh, processor fragmentation, scheduling effectiveness, turnaround time, external message interference, dispersal ratio.

Bibtex entry Endnote XML