An efficient non-contiguous processor allocation strategy for 2D mesh connected multicomputers

S. Bani-Mohammad*, M. Ould-Khaoua, I. Ababneh

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

21 Citations (Scopus)


In non-contiguous allocation, a job request can be split into smaller parts that are allocated possibly non-adjacent free sub-meshes rather than always waiting until a single sub-mesh of the requested size and shape is available. Lifting the contiguity condition is expected to reduce processor fragmentation and increase system utilization. However, the distances traversed by messages can be long, and as a result the communication overhead, especially contention, is increased. The extra communication overhead depends on how the allocation request is partitioned and assigned 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. Request partitioning in our suggested strategy is based on the sub-meshes available for allocation. To evaluate the performance improvement achieved by our strategy and compare it against well-known existing non-contiguous and contiguous strategies, we conduct extensive simulation runs under the assumption of wormhole routing and three communication patterns, notably one-to-all, all-to-all and random. The results show that the new strategy can reduce the communication overhead and substantially improve performance in terms of job turnaround time and system utilization.

Original languageEnglish
Pages (from-to)2867-2883
Number of pages17
JournalInformation Sciences
Issue number14
Publication statusPublished - Jul 15 2007
Externally publishedYes


  • Contiguous processor allocation
  • Fragmentation
  • Non-contiguous processor allocation
  • Performance evaluation
  • Simulation
  • System utilization
  • Turnaround time

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Theoretical Computer Science
  • Computer Science Applications
  • Information Systems and Management
  • Artificial Intelligence


Dive into the research topics of 'An efficient non-contiguous processor allocation strategy for 2D mesh connected multicomputers'. Together they form a unique fingerprint.

Cite this