TY - GEN
T1 - Non-contiguous processor allocation strategy for 2D mesh connected multicomputers based on sub-meshes available for allocation
AU - Bani-Mohammad, S.
AU - Ould-Khaoua, M.
AU - Ababneh, I.
AU - Mackenzie, Lewis M.
PY - 2006
Y1 - 2006
N2 - Contiguous allocation of parallel jobs usually suffers from the degrading effects of fragmentation as it requires that the allocated processors be contiguous and has the same topology as the network topology connecting these processors. In non-contiguous allocation, a job can execute on multiple disjoint smaller sub-meshes rather than always waiting until a single sub-mesh of the requested size is available. Lifting the contiguity condition in non-contiguous allocation is expected to reduce processor fragmentation and increase processor utilization. However, the communication overhead is increased because the distances traversed by messages can be longer. The extra communication overhead depends on how the allocation request is partitioned and allocated to free sub-meshes. In this paper, a new non-contiguous processor allocation strategy, referred to as Greedy-Available-Busy-List, is suggested for the 2D mesh network, and is compared using simulation against the well-known non-contiguous and contiguous allocation strategies. To show the performance improved by proposed strategy, we conducted simulation runs under the assumption of wormhole routing and all-to-all communication pattern. The results show that the proposed strategy can reduce the communication overhead and improve performance substantially in terms of turnaround times of jobs and finish times.
AB - Contiguous allocation of parallel jobs usually suffers from the degrading effects of fragmentation as it requires that the allocated processors be contiguous and has the same topology as the network topology connecting these processors. In non-contiguous allocation, a job can execute on multiple disjoint smaller sub-meshes rather than always waiting until a single sub-mesh of the requested size is available. Lifting the contiguity condition in non-contiguous allocation is expected to reduce processor fragmentation and increase processor utilization. However, the communication overhead is increased because the distances traversed by messages can be longer. The extra communication overhead depends on how the allocation request is partitioned and allocated to free sub-meshes. In this paper, a new non-contiguous processor allocation strategy, referred to as Greedy-Available-Busy-List, is suggested for the 2D mesh network, and is compared using simulation against the well-known non-contiguous and contiguous allocation strategies. To show the performance improved by proposed strategy, we conducted simulation runs under the assumption of wormhole routing and all-to-all communication pattern. The results show that the proposed strategy can reduce the communication overhead and improve performance substantially in terms of turnaround times of jobs and finish times.
KW - Contiguous allocation
KW - Finish time
KW - Fragmentation
KW - Multicomputers
KW - Non-contigous allocation
KW - Performance Comparison
KW - Simulation
KW - System utilization
KW - Turnaround time
UR - http://www.scopus.com/inward/record.url?scp=33947407404&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=33947407404&partnerID=8YFLogxK
U2 - 10.1109/ICPADS.2006.68
DO - 10.1109/ICPADS.2006.68
M3 - Conference contribution
AN - SCOPUS:33947407404
SN - 0769526128
SN - 9780769526126
T3 - Proceedings of the International Conference on Parallel and Distributed Systems - ICPADS
SP - 41
EP - 48
BT - Proceedings - 12th International Conference on Parallel and Distributed Systems, ICPADS 2006
T2 - 12th International Conference on Parallel and Distributed Systems, ICPADS 2006
Y2 - 12 July 2006 through 15 July 2006
ER -