Optimizing the stretch of independent tasks on a cluster: From sequential tasks to moldable tasks

详细信息	查看全文 | 推荐本文 |

• 作者：Erik Saule^a ; ^{esaule@bmi.osu.edu}  ; [Author Vitae] ; Doruk Bozda臒^a ; ^{bozdag.1@osu.edu}  ; [Author Vitae] ; Ü ; mit V. Ç ; atalyü ; rek^a ; ^b ; ^{umit@bmi.osu.edu}  ; [Author Vitae]
• 关键词：Online scheduling ; Maximum stretch ; Approximation algorithm ; Resource augmentation ; Simulation ; Job scheduling ; Sequential task ; Moldable task
• 刊名：Journal of Parallel and Distributed Computing
• 出版年：2012
• 期刊代码：188_07437315
• 类别：et
• 出版时间：April, 2012
• 卷：72
• 期：4
• 页码：489-503
• 文件大小：846 K

摘要

This paper addresses the problem of scheduling non-preemptive moldable tasks to minimize the stretch of the tasks in an online non-clairvoyant setting. To the best of the authors鈥?knowledge, this problem has never been studied before. To tackle this problem, first the sequential subproblem is studied through the lens of the approximation theory. An algorithm, called DASEDF, is proposed and, through simulations, it is shown to outperform the first-come, first-served scheme. Furthermore, it is observed that machine availability is the key to getting good stretch values. Then, the moldable task scheduling problem is considered, and, by leveraging the results from the sequential case, another algorithm, DBOS, is proposed to optimize the stretch while scheduling moldable tasks. This work is motivated by a task scheduling problem in the context of parallel short sequence mapping which has important applications in biology and genetics. The proposed DBOS algorithm is evaluated both on synthetic data sets that represent short sequence mapping requests and on data sets generated using log files of real production clusters. The results show that the DBOS algorithm significantly outperforms the two state-of-the-art task scheduling algorithms on stretch optimization.