Abstract
In this paper, we study an online scheduling problem with moldable parallel tasks on m processors. Each moldable task can be processed simultaneously on any number of processors of a parallel computer, and the processing time of a moldable task depends on the number of processors allotted to it. Tasks arrive one by one. Upon arrival of each task, the scheduler has to determine both the number of processors and the starting time for the task. Moreover, these decisions cannot be changed in the future. The objective is to attain a schedule such that the longest completion time over all tasks, i.e., the makespan, is minimized. First, we provide a general framework to show that any \(\rho \)-bounded algorithm for scheduling of rigid parallel tasks (the number of processors for a task is fixed a prior) can be extended to yield an algorithm for scheduling of moldable tasks with a competitive ratio of \(4\rho \) if the ratio \(\rho \) is known beforehand. As a consequence, we achieve the first constant competitive ratio, 26.65, for the moldable parallel tasks scheduling problem. Next, we provide an improved algorithm with a competitive ratio of at most 16.74.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Aspnes, J., Azar, Y., Fiat, A., Plotkin, S., & Waarts, O. (1997). On-line routing of virtual circuits with applications to load balancing and machine scheduling. Journal of the ACM, 44(3), 486–504.
Baker, B., & Schwartz, J. (1983). Shelf algorithms for two-dimensional packing problems. SIAM Journal on Computing, 12, 508–525.
Belkhale, K., & Banerjee, P. (1990). Approximate algorithms for the partitionable independent task scheduling problem. In Proceedings of the international conference on parallel processing (ICPP) (pp. 72–75).
Borodin, A., & El-Yaniv, R. (1998). Online computation and competitive analysis. Cambridge: Cambridge University Press.
Cirne, W., & Berman, F. (2001). A model for moldable supercomputer jobs. In Proceedings of the 15th international parallel and distributed processing symposium (IPDPS) (pp. 59–66).
Decker, T., Lücking, T., & Monien, B. (2006). A 5/4-approximation algorithm for scheduling identical malleable tasks. Theoretical Computer Science, 361(2), 226–240.
Dutot, P., Mounié, G., & Trystram, D. (2004). Scheduling parallel tasks approximation algorithms, Chapter 26. In J. Y.-T. Leung (Ed.), Handbook of scheduling: Algorithms, models and performance analysis. Boca Raton: CRC Press.
Dutton, R., & Mao, W. (2007). Online scheduling of malleable parallel jobs. In Proceedings of the IASTED international conference on parallel and distributed computing and systems (pp. 1–6).
Guo, S., & Kang, L. (2010). Online scheduling of malleable parallel jobs with setup times on two identical machines. European Journal of Operational Research, 206(3), 555–561.
Havill, J., & Mao, W. (2008). Competitive online scheduling of perfectly malleable jobs with setup times. European Journal of Operational Research, 187, 1126–1142.
Hochbaum, D., & Shmoys, D. (1987). Using dual approximation algorithms for scheduling problems: Theoretical and practical results. Journal of the ACM, 34(1), 144–162.
Hurink, J., & Paulus, J. (2007). Online algorithm for parallel job scheduling and strip packing. In Proceedings of the 5th international workshop in approximation and online algorithms (WAOA) (pp. 67–74).
Jansen, K. (2012). A (3/2 + \(\varepsilon \)) approximation algorithm for scheduling moldable and non-moldable parallel tasks. In Proceedings of the 24th ACM symposium on parallelism in algorithms and architectures (SPAA) (pp. 224–235).
Jansen, K., & Porkolab, L. (2002). Linear-time approximation schemes for scheduling malleable parallel tasks. Algorithmica, 32(3), 507–520.
Jansen, K., & Thöle, R. (2010). Approximation algorithms for scheduling parallel jobs. SIAM Journal on Computing, 39(8), 3571–3615.
Kalé, L. (2002). The virtualization model of parallel programming: Runtime optimizations and the state of art. In Proceedings of Los Alamos computer science institute symposium (LACSI) (pp. 347–364).
Kell, N., & Havill, J. (2015). Improved upper bounds for online malleable job scheduling. Journal of Scheduling, 18(4), 393–410.
Ludwig, W., & Tiwari, P. (1994). Scheduling malleable and nonmalleable parallel tasks. In Proceedings of the 15th annual ACM-SIAM symposium on discrete algorithms (SODA) (pp. 167–176).
Mounié, G., Rapine, C., & Trystram, D. (1999). Efficient approximation algorithms for scheduling malleable tasks. In Proceedings of the 11th annual ACM symposium on parallel algorithms and architectures (SPAA) (pp. 23–32).
Mounié, G., Rapine, C., & Trystram, D. (2007). A \(\frac{3}{2}\)-approximation algorithm for scheduling independent monotonic malleable tasks. SIAM Journal on Computing, 37, 401–412.
Rapine, C., Scherson, I., & Trystram, D. (1998). On-line scheduling of parallelizable jobs. In Proceedings of the 4th international euro-par conference on parallel processing (Euro-Par) (pp. 322–327).
Saule, E., Bozdağ, D., & Catalyurek, U. (2010). A moldable online scheduling algorithm and its application to parallel short sequence mapping. In Proceedings of the 15th international conference on job scheduling strategies for parallel processing (JSSPP) (pp. 93–109).
Turek, J., Wolf, J., & Yu, P. S. (1992). Approximate algorithms scheduling parallelizable tasks. In Proceedings of the 4th annual ACM symposium on parallel algorithms and architectures (SPAA) (pp. 323–332).
Ye, D., Han, X., & Zhang, G. (2009). A note on online strip packing. Journal of Combinatorial Optimization, 17(4), 417–423.
Yu, G., Mao, Y., & Xiao, J. (2016). A new lower bound for online strip packing. European Journal of Operational Research, 250(3), 754–759.
Acknowledgements
We would like to thank the anonymous referees for their valuable comments to improve the presentation of this paper. The research of D. Ye was supported in part by NSFC (11671355) and China Scholarship Council. The research of D.Z. Chen was supported in part by NSF under Grants CCF-1217906 and CCF-1617735. The research of G. Zhang was supported in part by NSFC (11271325).
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Ye, D., Chen, D.Z. & Zhang, G. Online scheduling of moldable parallel tasks. J Sched 21, 647–654 (2018). https://doi.org/10.1007/s10951-018-0556-2
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10951-018-0556-2