2016/09/27 by Wu, Xiaohu, Loiseau, Patrick · 2 citations
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1609.08588
We study the problem of scheduling n independent moldable tasks on m processors that arises in large-scale parallel computations. When tasks are monotonic, the best known result is a ((3)/(2)+ε)-approximation algorithm for makespan minimization with a complexity linear in n and polynomial in logm and \frac1ε where ε is arbitrarily small. We propose a new perspective of the existing speedup models: the speedup of a task Tj is linear when the number p of assigned processors is small (up to a threshold δj) while it presents monotonicity when p ranges in [δj, kj]; the bound kj indicates an unacceptable overhead when parallelizing on too many processors. The generality of this model is proved to be between the classic monotonic and linear-speedup models. For any given integer δ≥ 5, let u=\lceil √[2]δ \rceil-1≥ 2. In this paper, we propose a (1)/(θ(δ)) (1+ε)-approximation algorithm for makespan minimization where θ(δ) = (u+1)/(u+2)( 1- (k)/(m) ) (m≫ k). As a by-product, we also propose a θ(δ)-approximation algorithm for throughput maximization with a common deadline.