R.A. Dutton and W. Mao (USA)
parallel job scheduling, online algorithms, malleable jobs, competitive ratio, resource allocation
In this paper, we study a parallel job scheduling model which takes into account both computation time and the overhead from communication between processors. As suming that a job Jj has a processing requirement pj and is assigned to kj processors for parallel execution, then the execution time will be modeled by tj = pj/kj +(kj −1)·c, where c is the constant overhead cost associated with each processor other than the master processor. In this model, (kj −1)·c represents the cost for communication and coor dination among the processors. This model attempts to ac curately portray the actual execution time for jobs running in parallel on multiple processors. Using this model, we will study the online algorithm Earliest Completion Time (ECT) and show a lower bound for the competitive ratio of ECT for m ≥ 2 processors. For m ≤ 4, we show the matching upper bound to complete the competitive analysis for m = 2, 3, 4. For large m, we conjecture that the ratio approaches 30/13 ≈ 2.30769.
Important Links:
Go Back
