This paper studies the resource allocation of parallel jobs on SMP clusters. Previous parallel job scheduling algorithms‚ such as EASY (Extensible Argonne Scheduling sYstem), a backfilling algorithm‚ focus only on the allocation of CPUs. As communication cost becomes a bottleneck and gradually dominates the performance of program executions on multicomputers, some processor allocation policies suggest that as processors are allocated to a job, the allocated processors must be as continuous as possible. However, some of the mentioned algorithms will lead to another external fragmentation problem. The problem occurs as sufficient processors become available for the requested job; however, these processors are dispersed throughout the system. Thus jobs must wait for some time until there are sufficient contiguous processors. In summary, as adjacent processors are allocated, we
may improve the run time of jobs, however, this will increase the wait-time of jobs.
In this paper, we suggest that an effective processor allocation policy should well balance communication cost and waiting delay. The principal is simple. When a network is busy or the communication cost is high‚ the processors must be allocated as continuously as possible. On the other
hand‚ when the communication cost is light‚ to shorten the waiting time‚ the processors should be allocated as soon as possible.