More Web Proxy on the site http://driver.im/

research-article

Scheduling Multi-Server Jobs is Not Easy

Author:

Rahul VazeAuthors Info & Claims

MOBIHOC '24: Proceedings of the Twenty-fifth International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing

Pages 171 - 180

https://doi.org/10.1145/3641512.3686374

Published: 01 October 2024 Publication History

Abstract

The problem of online scheduling of multi-server jobs is considered, where there are a total of K servers, and each job requires concurrent service from multiple servers for it to be processed. Each job on its arrival reveals its processing time, the number of servers from which it needs concurrent service, and an online algorithm has to make scheduling decisions at each time using only information revealed so far with the goal of minimizing the response/flow time. The worst case input model is considered and the performance metric is the competitive ratio. For the case when all job processing time (sizes) are the same, we show that the competitive ratio of any deterministic/randomized algorithm is at least Ω(K) and propose an online algorithm whose competitive ratio is at most K + 1. With unequal job sizes, we propose an online algorithm whose competitive ratio is at most 2K log(Kw_max), where w_max is the maximum size of any job. With equal job sizes, we also consider the resource augmentation regime where an online algorithm has access to more servers than an optimal offline algorithm. With resource augmentation, we propose a simple online algorithm and show that it has a competitive ratio of 1 when provided with 2K servers with respect to an optimal offline algorithm with K servers.

References

[1]

M. Tirmazi, A. Barker, N. Deng, M. E. Haque, Z. G. Qin, S. Hand, M. Harchol-Balter, J. Wilkes, Borg: the next generation, in: Proceedings of the fifteenth European conference on computer systems, 2020, pp. 1--14.

Digital Library

[2]

J. Wilkes, et al., Google cluster-usage traces v3, Google Inc., Mountain View, CA, USA, Technical Report (2020).

[3]

I. Grosof, M. Harchol-Balter, A. Scheller-Wolf, Wcfs: A new framework for analyzing multiserver systems, Queueing Systems 102 (1) (2022) 143--174.

Digital Library

[4]

I. Grosof, Z. Scully, M. Harchol-Balter, A. Scheller-Wolf, Optimal scheduling in the multiserver-job model under heavy traffic, Proceedings of the ACM on Measurement and Analysis of Computing Systems 6 (3) (2022) 1--32.

Digital Library

[5]

D. Carastan-Santos, R. Y. De Camargo, D. Trystram, S. Zrigui, One can only gain by replacing easy backfilling: A simple scheduling policies case study, in: 2019 19th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing (CCGRID), IEEE, 2019, pp. 1--10.

[6]

P. H. Brill, L. Green, Queues in which customers receive simultaneous service from a random number of servers: a system point approach, Management Science 30 (1) (1984) 51--68.

Digital Library

[7]

N. Zychlinski, C. W. Chan, J. Dong, Scheduling queues with simultaneous and heterogeneous requirements from multiple types of servers, in: 2020 Winter Simulation Conference (WSC), IEEE, 2020, pp. 2365--2376.

[8]

N. Zychlinski, C. W. Chan, J. Dong, Managing queues with different resource requirements, Operations Research 71 (4) (2023) 1387--1413.

Digital Library

[9]

S. Srinivasan, R. Kettimuthu, V. Subramani, P. Sadayappan, Characterization of backfilling strategies for parallel job scheduling, in: Proceedings. International Conference on Parallel Processing Workshop, IEEE, 2002, pp. 514--519.

[10]

I. Grosof, Y. Hong, M. Harchol-Balter, A. Scheller-Wolf, The reset and marc techniques, with application to multiserver-job analysis, Performance Evaluation 162 (2023) 102378.

Digital Library

[11]

I. Grosof, M. Harchol-Balter, A. Scheller-Wolf, New stability results for multiserver-job models via product-form saturated systems, ACM SIGMETRICS Performance Evaluation Review 51 (2) (2023) 6--8.

Digital Library

[12]

M. Harchol-Balter, The multiserver job queueing model, Queueing Systems 100 (3) (2022) 201--203.

Digital Library

[13]

W. Wang, Q. Xie, M. Harchol-Balter, Zero queueing for multi-server jobs, Proceedings of the ACM on Measurement and Analysis of Computing Systems 5 (1) (2021) 1--25.

Digital Library

[14]

H. Zhao, S. Deng, F. Chen, J. Yin, S. Dustdar, A. Y. Zomaya, Learning to schedule multi-server jobs with fluctuated processing speeds, IEEE Transactions on Parallel and Distributed Systems 34 (1) (2022) 234--245.

[15]

Y. Hong, Sharp zero-queueing bounds for multi-server jobs, ACM SIGMETRICS Performance Evaluation Review 49 (2) (2022) 66--68.

Digital Library

[16]

H. Zhao, S. Deng, Z. Xiang, X. Yan, J. Yin, S. Dustdar, A. Y. Zomaya, Scheduling multi-server jobs with sublinear regrets via online learning, IEEE Transactions on Services Computing (2023).

[17]

D. Olliaro, M. A. Marsan, S. Balsamo, A. Marin, The saturated multiserver job queuing model with two classes of jobs: Exact and approximate results, Performance Evaluation 162 (2023) 102370.

Digital Library

[18]

S. Ghanbarian, A. Mukhopadhyay, F. M. Guillemin, R. R. Mazumdar, On the performance of large loss systems with adaptive multiserver jobs, arXiv preprint arXiv:2309.00060 (2023).

[19]

R. Vaze, Online Algorithms, Cambridge University Press, 2023.

[20]

D. Shah, J. N. Tsitsiklis, Bin packing with queues, Journal of Applied Probability 45 (4) (2008) 922--939.

[21]

S. H. H. Madni, M. S. Abd Latiff, M. Abdullahi, S. M. Abdulhamid, M. J. Usman, Performance comparison of heuristic algorithms for task scheduling in iaas cloud computing environment, PloS one 12 (5) (2017) e0176321.

[22]

H. You, H. Zhang, Comprehensive workload analysis and modeling of a petascale supercomputer, in: Job Scheduling Strategies for Parallel Processing: 16th International Workshop, JSSPP 2012, Shanghai, China, May 25, 2012. Revised Selected Papers 16, Springer, 2013, pp. 253--271.

[23]

D. G. Feitelson, L. Rudolph, Toward convergence in job schedulers for parallel supercomputers, in: Workshop on job scheduling strategies for parallel processing, Springer, 1996, pp. 1--26.

Digital Library

[24]

A. Beloglazov, R. Buyya, Energy efficient allocation of virtual machines in cloud data centers, in: 2010 10th IEEE/ACM International Conference on Cluster, Cloud and Grid Computing, IEEE, 2010, pp. 577--578.

Digital Library

[25]

S. T. Maguluri, R. Srikant, L. Ying, Stochastic models of load balancing and scheduling in cloud computing clusters, in: 2012 Proceedings IEEE Infocom, IEEE, 2012, pp. 702--710.

[26]

E. Arthurs, J. S. Kaufman, Sizing a message store subject to blocking criteria, in: Proceedings of the third international symposium on modelling and performance evaluation of computer systems: Performance of computer systems, 1979, pp. 547--564.

Digital Library

[27]

W. Whitt, Blocking when service is required from several facilities simultaneously, AT&T technical journal 64 (8) (1985) 1807--1856.

[28]

N. M. Van Dijk, Blocking of finite source inputs which require simultaneous servers with general think and holding times, Operations research letters 8 (1) (1989) 45--52.

[29]

N. Garg, A. Kumar, Minimizing average flow time on related machines, in: Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing, 2006, pp. 730--738.

Digital Library

[30]

R. Vaze, Scheduling multi-server jobs is not easy, arXiv preprint arXiv:22404.05271 (2024). arXiv:2404.05271.

[31]

C. A. Phillips, C. Stein, E. Torng, J. Wein, Optimal time-critical scheduling via resource augmentation, in: Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, 1997, pp. 140--149.

Digital Library

[32]

S. Anand, N. Garg, A. Kumar, Resource augmentation for weighted flow-time explained by dual fitting, in: Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms, SIAM, 2012, pp. 1228--1241.

Cited By

Olliaro DAnggraito AMarsan MBalsamo SMarin A(2025)The Impact of Service Demand Variability on Data Center PerformanceIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2024.349779236:2(120-132)Online publication date: Feb-2025
https://doi.org/10.1109/TPDS.2024.3497792

Index Terms

Scheduling Multi-Server Jobs is Not Easy
1. Networks
  1. Network algorithms
    1. Control path algorithms
      1. Network resources allocation
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
      1. Scheduling algorithms

Recommendations

Scheduling parallel jobs to minimize the makespan

We consider the NP-hard problem of scheduling parallel jobs with release dates on identical parallel machines to minimize the makespan. A parallel job requires simultaneously a prespecified, job-dependent number of machines when being processed. We ...
Online scheduling with linear deteriorating jobs to minimize the total weighted completion time

In this paper, we study the online scheduling of linear deteriorating jobs on a single machine to minimize the total weighted completion time. In the problem, a set of n independent linear deteriorating jobs arriving online over time has to be scheduled ...
Scheduling of deteriorating jobs with release dates to minimize the maximum lateness

In this paper, we consider the problem of scheduling n deteriorating jobs with release dates on a single (batching) machine. Each job's processing time is a simple linear function of its starting time. The objective is to minimize the maximum lateness. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

MobiHoc '24: Proceedings of the Twenty-fifth International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing

October 2024

511 pages

ISBN:9798400705212

DOI:10.1145/3641512

General Chair:
Symeon Papavassiliou,
Program Chair:
Stefan Schmid

Copyright © 2024 Copyright is held by the owner/author(s). Publication rights licensed to ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGMOBILE: ACM Special Interest Group on Mobility of Systems, Users, Data and Computing

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 October 2024

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Department of Atomic Energy, Government of India

Conference

MobiHoc '24

Sponsor:

SIGMOBILE

MobiHoc '24: Twenty-fifth International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing

October 14 - 17, 2024

Athens, Greece

Acceptance Rates

Overall Acceptance Rate 296 of 1,843 submissions, 16%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
44
Total Downloads

Downloads (Last 12 months)44
Downloads (Last 6 weeks)16

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Olliaro DAnggraito AMarsan MBalsamo SMarin A(2025)The Impact of Service Demand Variability on Data Center PerformanceIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2024.349779236:2(120-132)Online publication date: Feb-2025
https://doi.org/10.1109/TPDS.2024.3497792

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents