Optimizing Scheduling Policies for M/G/k Systems Under Various Load Conditions

Slide Note

Explore the effectiveness of different scheduling policies, such as SRPT and SEK, in minimizing response times in M/G/k systems under moderate and heavy traffic loads. Learn about the benefits and limitations of these policies and discover new lower bounds for optimal performance.

gkol Follow

Uploaded on Sep 27, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

E N D

Presentation Transcript

Bounds on M/G/k Scheduling Under Moderate Load Izzy Grosof (Isaac) (they/she) CMU Georgia Tech UIUC Northwestern IEMS Ziyuan Wang (Northwestern IEMS) Ziyuan Wang 1 MAMA 2024 - June 14

M/G/k Scheduling Load ? = ??[?] < 1 Job duration ~ ?, i.i.d. Scheduling w/ known sizes 1/k ? Poisson(?) 1/k Response time ? Shortest Remaining Processing Time? Q: What scheduling policy minimizes ?[?]? 2 MAMA 2024 - June 14

SRPT: Optimal? SRPT-k SRPT-k: k jobs with least remaining size. SRPT-1 is always optimal [Schrage 68]. What about SRPT-k? 0 1 Load ? Heavy Traffic: ? 1 SRPT-k is asymptotically optimal! [GSH 18] No arrivals: SRPT-k is optimal! [McNaughton 59] + [Conway et al. 67] Medium load: ?????? 3 MAMA 2024 - June 14

Questions of This Talk Q: Is SRPT-? optimal at medium load? A: No! We do better! SRPT-Except-? + 1! Q: How much better is possible? A: We give new lower bounds: WINE formula + Increasing Speed Queue (ISQ) 4 MAMA 2024 - June 14

SRPT-Except-? + 1 (SEK) SRPT-k SEK(5) 3 3 10 4 10 4 SEK: If ? jobs or > ? + 1, same as SRPT-?. Remaining case: ? + 1 jobs SEK parameterized by size threshold ?. Example: ? = 5. If ? jobs with size ? and one job with size > ?, then SEK serves largest, leaves out second-largest. Otherwise, same as SRPT-?. 5 MAMA 2024 - June 14

SEK Intuition SRPT-k SEK(5) 3 3 10 4 10 4 13 10 7 3 0 10 Time 4 3 0 4 Time 10 4 3 Servers 3 Servers Total response time, no arrivals: SRPT: 3 + 4 + 13 = 20. SEK: 3 + 7 + 10 = 20 Time of first wasted capacity: SRPT: 4. SEK: 7. SEK: Same response time, might as well waste less . 6 MAMA 2024 - June 14

Further SEK Intuition SRPT-k SEK(5) 3 3 10 4 10 4 13 10 7 3 0 10 Time 4 3 0 4 Time 10 4 3 Servers 3 Servers SRPT-?: Better if arrival before time 4: Progress on size 4 job more valuable than progress on size 10 job. SEK: Better if arrival between times 4 and 13: Less wasted capacity. Empirically, latter is more important. 7 MAMA 2024 - June 14

SEK Plot: Improvement over SRPT-? ? ???? ? ????? Setting: M/M/2, size Exp(1). Improvement ratio: 1 ? 0.996 simulated 8 MAMA 2024 - June 14

SEK Proof: Open Want to show: For all size distributions ?, exists ?,? such that E ????< ?[?????] Idea: Use a Nudge-type proof. Very small ? should make for a cleaner proof, might need 2 jobs < ??????, 1 job > ??????. Interested in discussion and/or collaboration! 9 MAMA 2024 - June 14

Lower bounds on M/G/k scheduling: Prior Prior work: Simple bounds. Resource-pooled SRPT-1, service time. Resource pooling bound: Thm: ? ?,? ?? ? ?[????? 1] Service time bound: Thm: ? ?,? ?? ? ?? ? 10 MAMA 2024 - June 14

Lower Bounds: Prior - Drawbacks Resource pooling: ? ?,? ?? ? ?[????? 1] Tight as ? 1! Drawback: Doesn t scale with number of servers ?. Service time: ? ?,? ?? ? ?? ? Tight as ? 0! Drawback: Doesn t scale with load ?. Need new lower bounds if we want tight at moderate load! 11 MAMA 2024 - June 14

WINE for Lower Bounds Work Integral Number Equality (WINE): [SGH 21] ? ? =? ? ? ? ?? ? =1 ?? ?2 ? ?=0 Relevant work ??: Total remaining size of jobs with remaining size ?. Idea: Lower bound relevant work ?[??], lower bound response time ? ? Resource pooled bound: ? ?? ? ? min ?,?2 2 1 ?? Service time bound: ? ?? ?? 2? min ?,?2 Combine using WINE! 12 MAMA 2024 - June 14

WINE Lower Bound: Plot Resource pooled SRPT-1 Service time WINE combination Big improvement! WINE SRPT-1 Service M/M/2, ? ? = 1 13 MAMA 2024 - June 14

Increasing Speed Queue (ISQ) (? = 2.4,? = 1/2) Single-server queue. State: Amount of work, server speed ?,? . Lower bound on work in the M/G/k. At the beginning of the busy period, system starts at speed 1/?, for some integer ?. Same speed as M/G/k at start of busy period. 14 MAMA 2024 - June 14

Increasing Speed Queue (ISQ) (? = 1.9,? = 1/2) Single-server queue. State: Amount of work, server speed ?,? . Lower bound on work in the M/G/k. At the beginning of the busy period, system starts at speed 1/?, for some integer ?. Same speed as M/G/k at start of busy period. When another job arrives, speed increases to 2/?, 3/?, up to 1. 15 MAMA 2024 - June 14

Increasing Speed Queue (ISQ) (? = 4.2,? = 1) Single-server queue. State: Amount of work, server speed ?,? . Lower bound on work in the M/G/k. At the beginning of the busy period, system starts at speed 1/?, for some integer ?. Same speed as M/G/k at start of busy period. When another job arrives, speed increases to 2/?, 3/?, up to 1. Stays at speed 1 until end of busy period. 16 MAMA 2024 - June 14

ISQ: Drift-based Analysis Idea from tutorial: Find a test function with linear drift. Here, goal is linear in work ?. Test function ?(?,?): ? 0,0 = 0 ? ?,1 = ?2 ? ?,1 2 If ? > 0, ? = 1 or , ? ? ?,? = ?? ?2+ 2?( 1 + ?) ? 1 ? 2?? = ?2+? 2?2 17 MAMA 2024 - June 14

ISQ: Mean Work If ? > 0, ? = 1 or , ? ? ?,? = ?? ?2+ 2?( 1 + ?) Thm: +? ? 1 ? 2? /2? 3 ? 2? ?? ?2 2 1 ? ? ? = Exact characterization of mean work! Similar results for ISQ-?. Lower bound on total work in M/G/k 18 MAMA 2024 - June 14

ISQ: Relevant Work Bounds More effort to use ISQ to lower bound relevant work, because of recycled jobs. ? From the perspective of relevant work ?, size ? jobs appear in the system. recycle 19 MAMA 2024 - June 14

ISQ: Relevant Work Bounds More effort to use ISQ to lower bound relevant work, because of recycled jobs. ? =x From the perspective of relevant work ?, size ? jobs appear in the system. recycle Simple ISQ-based bound: Use size distribution ??= [?1 ? ? ], and ? jobs recycle on separate servers. Fancier ISQ-based bound: Worst-case jump in test function ?(?,?). 20 MAMA 2024 - June 14

ISQ: Detailed relevant work bounds Definitions: ??= ???? ,??= ? S ? , ??= ??? ?? ,? ?= ??[min ?,? ] Separate-servers ISQ: ISQ ? ?? 1 ??2?? 2?? Recycling 2 ??? ?? 2 1 ?? + ? ???2 ? ?? + 3 ??2?? ISQ Worst-case jump (recycling) ISQ: ? ?? 1 Recycling ??2?? 2?? 2 ? ???2 2 1 ?? ??? ?? 2 1 ?? 1 ? ? 1 ?? ? ?? + + 3 ??2?? 21 MAMA 2024 - June 14

Stronger response time lower bounds Red: Simple ISQ bound. Purple: Combine all 3 with WINE. Improvement of WINE 3 over WINE 2. WINE 4: Add in fancy ISQ bound. 22 MAMA 2024 - June 14

Future Directions Prove for all size dists. ?, exists load ? and threshold ? such that ? ????< ? ?????? Use lower bounding framework to prove optimality in some medium load setting? Generalize ISQ relevant work lower bounds to all ?. 23 MAMA 2024 - June 14