Scheduling Adaptively Parallel Jobs
Bin Song · 1998
An adaptively parallel job is one in which the number of processors which can be used without waste changes during execution. When allocating processors to multiple adaptively parallel jobs, a job scheduler should attempt to be fair---meaning that no job gets fewer processors than another, unless it demands fewer---and efficient---meaning that the scheduler does not waste processors on jobs that do not need them. Moreover, the scheduler should adapt quickly and be implementable in a distributed fashion. In this thesis, I present and analyze a randomized processor allocation algorithm, the SRLBA algorithm, which allocates processors to adaptively parallel jobs in a distributed system of P processors and J jobs. The algorithm consists of rounds of load-balancing steps in which processor migration may occur. In the case that each job has a demand which is more than its fair share P=J of the processors, I show that after O(lg P ) rounds, the system is in an almost fair and efficient allo...