1 of 27

Sharp Waiting-Time Bounds for Multiserver Jobs

Weina Wang

Carnegie Mellon University

SNAPP 2021

2 of 27

Joint work with

1

Qiaomin Xie

University of Wisconsin–Madison

Mor Harchol-Balter

Carnegie Mellon University

Yige Hong

Carnegie Mellon University

[1] Y. Hong, and W. Wang. 2021. Sharp waiting-time bounds for multiserver jobs. arXiv.

[2] W. Wang, Q. Xie, and M. Harchol-Balter. 2021. Zero queueing for multi-server jobs. SIGMETRICS.

Sharp Waiting-Time Bounds for Multiserver Jobs

Weina Wang (CMU)

3 of 27

What is a multiserver job?

2

single-server job

multi-server job

servers

👩🏻

👨🏻

👧🏻

😼

“server need = 4”

requires 4 servers to run

Sharp Waiting-Time Bounds for Multiserver Jobs

Weina Wang (CMU)

4 of 27

Why multiserver jobs?

  • Modern cloud clusters run workloads as containers

3

container requires certain resources to run

🡪 multiserver job

Google Borg

Sharp Waiting-Time Bounds for Multiserver Jobs

Weina Wang (CMU)

5 of 27

Server needs grow as datacenters grow

4

Google Borg trace 2019

[Tirmazi et al. 2020], [Wilkes 2019]

(server need)

Figure taken from [Grosof, Harchol-Balter, Scheller-Wolf 2020]

Sharp Waiting-Time Bounds for Multiserver Jobs

Weina Wang (CMU)

6 of 27

Model

5

 

K jobs classes

 

 

 

 

Servers idle when next job does not fit

Departure of red job

  • 3 jobs in the queue enter service

Departure of blue job

  • no jobs in the queue enter service

 

e.g., FCFS

❓

Sharp Waiting-Time Bounds for Multiserver Jobs

Weina Wang (CMU)

7 of 27

Load

6

 

K jobs classes

 

 

 

 

 

 

(traditional)

 

 

 

…

 

 

Sharp Waiting-Time Bounds for Multiserver Jobs

Weina Wang (CMU)

8 of 27

Goal

7

What is the queueing probability?

What is the queueing/waiting time?

Which scheduling policy minimizes queueing time?

 

Sharp Waiting-Time Bounds for Multiserver Jobs

Weina Wang (CMU)

9 of 27

Related work

  • Exact solutions are unknown
    • Only known for two-server systems [Brill, Green 1984], [Filippopoulos, Karatza 2007]
  • Stability of FCFS is hard
    • All classes have the same service rate [Rumyantsev, Morozov 2017], [Afanaseva, Bashtova, Grishunina 2019]
    • Two-class system [Grosof, Harchol-Balter, Scheller-Wolf 2020]
  • Bounds in exponential/divisible setting
    • [Grosof, Harchol-Balter, Scheller-Wolf 2021]

​

8

Sharp Waiting-Time Bounds for Multiserver Jobs

Weina Wang (CMU)

10 of 27

Related work (cont’d): related models

  • Dropping model
    • [Arthurs, Kaufman 1979], [Hunt, Kurtz 1993], [Bean, Gibbens, Zachary 1995], [Dasylva, Srikant 1999]…
  • VM (Virtual Machine) scheduling
    • [Maguluri, Srikant, Ying 2012, 2014], [Xie, Dong, Lu, Srikant 2015], [Psychas, Ghaderi 2017, 2019], …
  • Multi-task jobs/batch jobs
    • [Wang, Harchol-Balter, Jiang, Scheller-Wolf, Srikant 2018], [Daw, Pender 2019], [Daw, Fralix, Pender 2020], [Hampshire, Bao, Lasecki, Daw, Pender 2020], [Zubeldia 2020], [Weng, Wang 2021], …

​

9

Sharp Waiting-Time Bounds for Multiserver Jobs

Weina Wang (CMU)

11 of 27

 

10

Queueing probability and time

in scaling regimes?

 

 

 

[Halfin and Whitt 1981], …

queue. prob.

 

 

 

 

 

 

 

 

queue. time

 

 

 

 

Sharp Waiting-Time Bounds for Multiserver Jobs

Weina Wang (CMU)

12 of 27

 

11

 

 

 

 

queue. prob.

 

 

 

 

queue. time

 

 

 

 

 

 

 

 

 

❓

Sharp Waiting-Time Bounds for Multiserver Jobs

Weina Wang (CMU)

13 of 27

 

12

12

 

and heterogeneous

New scaling regimes!

Load:

 

Sharp Waiting-Time Bounds for Multiserver Jobs

Weina Wang (CMU)

14 of 27

Goal

13

What is the queueing probability?

What is the queueing/waiting time?

Which scheduling policy minimizes queueing time?

Can we answer these under NEW scaling regimes?

Sharp Waiting-Time Bounds for Multiserver Jobs

Weina Wang (CMU)

15 of 27

NEW joint scaling

14

 

 

Sharp Waiting-Time Bounds for Multiserver Jobs

Weina Wang (CMU)

16 of 27

Our results

15

 

 

 

 

 

 

 

very heavy

 

 

 

 

 

rest of talk

Under work-conserving policies:

Sharp Waiting-Time Bounds for Multiserver Jobs

Weina Wang (CMU)

17 of 27

Queueing time results

16

 

 

 

 

 

 

 

 

 

FCFS

 

Optimal policy

Sharp Waiting-Time Bounds for Multiserver Jobs

Weina Wang (CMU)

18 of 27

FCFS

  •  

17

 

 

 

 

 

 

 

 

 

Sharp Waiting-Time Bounds for Multiserver Jobs

Weina Wang (CMU)

19 of 27

Lower bound

  •  

18

 

 

 

 

 

 

 

 

 

Sharp Waiting-Time Bounds for Multiserver Jobs

Weina Wang (CMU)

20 of 27

Optimal policy

  •  

19

 

 

 

 

 

 

 

 

 

 

high priority

low priority

Sharp Waiting-Time Bounds for Multiserver Jobs

Weina Wang (CMU)

21 of 27

Optimal policy

  •  

20

 

 

 

 

 

 

 

 

 

Sharp Waiting-Time Bounds for Multiserver Jobs

Weina Wang (CMU)

22 of 27

Proof sketch

  •  

21

FCFS

 

Optimal policy

Workload:

 

Sharp Waiting-Time Bounds for Multiserver Jobs

Weina Wang (CMU)

23 of 27

Proof sketch through workload

22

FCFS

 

Optimal policy

Workload:

 

 

 

 

Different priority classes in different traffic regimes

Sharp Waiting-Time Bounds for Multiserver Jobs

Weina Wang (CMU)

24 of 27

Tight workload bounds

  • Lower bound: drift analysis + coupling with infinite-server systems
  • Upper bound: drift analysis + iterative state space collapse

23

Workload:

 

 

Sharp Waiting-Time Bounds for Multiserver Jobs

Weina Wang (CMU)

25 of 27

Summary

24

 

 

 

 

 

 

 

 

What is the queueing probability?

What is the queueing/waiting time?

Which scheduling policy minimizes queueing time?

Diminishes in blue regime for work-conserving policies

 

P-Priority has the optimal order in red regime

Sharp Waiting-Time Bounds for Multiserver Jobs

Weina Wang (CMU)

26 of 27

Open questions

  • Policies that degrade gracefully in even heavier traffic regimes?
  • Preemption or not?
  • Other types of resources?
  • Container utilization
  • …

​

25

Sharp Waiting-Time Bounds for Multiserver Jobs

Weina Wang (CMU)

27 of 27

THANK YOU!��weinaw@cs.cmu.edu