Techniques for Multiserver Job Analysis
Modeling large computing systems with multiserver jobs analyzed using the RESET and MARC techniques. Prior work on mean response time, stability, and key insights discussed at the INFORMS Annual Meeting.
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.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
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.
E N D
Presentation Transcript
The RESET and MARC Techniques for Multiserver Job Analysis Isaac Grosof (CMU GATech UIUC Northwestern) Yige Hong (CMU) Mor Harchol-Balter (CMU) Alan Scheller-Wolf (CMU) 1 INFORMS Annual Meeting, 10/16/23
Multiserver-job Model Modeling large computing systems: Many servers/job. Job: (duration, server need) FCFS Server need 2 2 ? Poisson(?) Sampled i.i.d. from joint distribution 3 2 1 4 1 Idle server Response time ? Q: What is the mean response time ?[?]? Paper in IFIP Performance 23 2 INFORMS Annual Meeting, 10/16/23
Prior work on MSJ FCFS Mean response time ?[?] Stability Only: ? = 2 servers, independent exponential duration [BG 84], [FK 07]. Stable arrival rates ? [0,? ) Independent exponential duration [RM 17] Two-class: MAMA 23 talk No general analysis! Key idea: Saturated System [BF 95] Also E[T] analysis for MSJ with scheduling [GHS 22], [GSHS 23], scaling MSJ models [WXH 21], [HW 22]. 3 INFORMS Annual Meeting, 10/16/23
External service process Result & Key Insight 2? Result: First Analysis of MSJ FCFS ? ? Tight in heavy traffic (? ? ) Key idea: MSJ Markovian Service Rate 2 1 3 2 1 4 4 INFORMS Annual Meeting, 10/16/23
External service process Result & Key Insight Saturated System New job Result: First Analysis of MSJ FCFS ? ? Tight in heavy traffic (? ? ) Key idea: MSJ 2 1 2 1 Markovian Service Rate 2 1 3 2 1 4 Solve ? ???? ???, Solve ?[????]! MARC RESET ?[???? ???]? ?[????]? 5 INFORMS Annual Meeting, 10/16/23
Saturated Markovian Service MSJ New job 2 1 RESET Theorem 2 1 3 2 1 4 2 1 RESET: Reduction to Saturated for Expected Time RESET Theorem: ? ????= ? ???? ???+ ??1 Intuition: MSJ and MSR-Sat couple perfectly, except if ? jobs present. 6 INFORMS Annual Meeting, 10/16/23
Saturated Markovian Service MSJ New job 2 1 RESET Proof Intuition 2 1 3 2 1 4 2 1 Call MSJ & MSR-Sat merged if ? oldest jobs in MSJ match jobs in Sat. Coupling: If merged, identical arrivals & completions. Else independent. Once merged, stay merged until ? jobs 1 1 ?/? ) time Lemma: Become merged in ?(1) time Lemma: Merged with probability 1 ?(1 ?/? ). Theorem: ? ????= ? ???? ???+ ??1 Generalizes to all near-MSR-? systems! Unmerged Merged Lemma: Stay merged for ( 1 ?(1) ( 1 ?/? ) 7 INFORMS Annual Meeting, 10/16/23
MARC: Analyze Markovian Service Rate system MARC: Markovian Relative Completions MSR-? Service process ? ?? Independently important model. Lots of prior work, lots of computational methods, no closed-form heavy-traffic results. MARC Theorem: Characterize ?[???? ?] for any service process ? New drift method: Relative completions See SNAPP talk for more! INFORMS Annual Meeting, 10/16/23
MMSR-? Service process ? ?? MARC: New drift method Drift method: Pick a test function ?(?,?), compute drift ? f ?,? . 1 ?? ? ? ? ,? ? Use fact: ? ? ? ?,? = 0 Key ingredient: Need function ?(?,?) with constant drift. M/M/1: ? has constant drift. M/G/1: ? has constant drift. MSR-?: ? ? = ? ??+ ??? ? = 0 Idea: Find a correction term (?) such that ? (?) has constant drift ? : Relative Completions ? ? ?,? = lim ? ?,? ? 0 = ?,? 0 = ? ? 0 9 INFORMS Annual Meeting, 10/16/23
MMSR-? Service process ? ?? Relative Completions Relative Completions: ? lim ? ? ? ?,? ?? Expected completions, starting at ? Drift: ? Drift: ?? Completions ? ? = ? ?? ? ? = ? ??+ ??? ? = 0 ??: Long-term rate ? ? ? = ? ? + ??? ? = 0 ?? Constant drift! (?) is a relative value function, can characterize with Poisson equation Time ? 10 INFORMS Annual Meeting, 10/16/23
MARC Result and Main Result 2, use ?[? f ?,? ] = 0 ??: Departure-average distribution MARC: Use ? ?,? = ? ? MARC Theorem: ?] + 1 1 ?? ?[ ??? 1 ?/?? ?[???? ?] = + ??(1) Combine RESET + MARC: ???+ 1 ????? 1 ?/???? 1 ? ????= ? ???? ?+ ??(1) = + ??(1) ???? First analysis of ?[?] in MSJ FCFS and MSR-?! 11 INFORMS Annual Meeting, 10/16/23
External service process Conclusion Saturated System New job First analysis of MSJ FCFS ?[?]: 2 1 2 1 Markovian Service Rate MSJ RESET 2 1 = ??(1) 3 2 1 4 MARC: Analyze ? ???? ?using relative completions (?) ???+1 ????? 1 ?/???? 1 RESET + MARC: ? ????= + ??(1) ???? 12 INFORMS Annual Meeting, 10/16/23
Bonus: Extensions Multidimensional resources Variable server need Alternative scheduling policies: Limited backfilling Job locality/contention Server affinity/heterogeneous servers Markovian arrival rates 13 INFORMS Annual Meeting, 10/16/23
Bonus: Empirical Validation via Simulation Setting: 2 servers. Jobs: , 1 2 100 Within 1% at every point simulated! Theory Simulation 75 1 + ? ?? 1 ??? 1.74 ? ??? Mean queue length ? ??? 50 25 0 0.8 0.85 0.9 0.95 1 ? Load ???= ??? 14
