Greedy-Available Non-contiguous Processor Allocation Strategy and Job Scheduling for 2D Mesh Connected Multicomputers

Contiguous allocation of parallel jobs usually suffers from the degrading effects of fragmentation as it requires that the allocated processors be contiguous and have the same topology as the network connecting these processors. In this paper, noncontiguous processor allocation strategy, referred to as Greedy- Available, is suggested for the 2D mesh network, and is compared using simulation against the well-known noncontiguous Paging strategy and well known contiguous First Fit trategy. In addition to allocation strategies, two job scheduling strategies, referred to as first-come-first-served (FCFS) and outof- order (OO) are studied, and they are used to compare the performance of allocation strategies. The results reveal that the proposed non-contiguous strategy exhibits superior performance properties despite the added contention that results from noncontiguity. The results also reveal that the OO scheduling strategy is much better than the FCFS scheduling strategy, therefore, the scheduling and allocation strategies both have substantial effect on the performance of contiguous and noncontiguous allocation strategies in 2D mesh.

Keywords:

Multicomputers , Fragmentation , Scheduling Effectiveness , Turnaround Time , External Message Interference , Dispersal Ratio , Performance Comparison , Simulation