Delimitrou and Kozyrakis (CACM 2018) combined Amdahl-style silicon-budget analysis with M/M/k queueing to give first-order guidance on resource allocation for tail-latency-constrained cloud services, validated only on memcached. They explicitly left open the extension of this framework to non-Poisson arrivals and non-exponential service times (G/G/k-class models), request dependencies and multi-tier structure (queueing networks), hard service-time lower bounds from system-call/RPC overheads, hardware-realistic performance scaling of cores, and validation across real services. Substantial progress on adjacent mechanisms and partial progress on dependency modeling (queueing-network simulation, black-box fork-join prediction) have been reported, but the validated analytical extension of the queueing-Amdahl resource-allocation framework itself remains open.

Background

Amdahl's law describes the speedup of a system when only a fraction of the work can be parallelized; in the multicore era Hill and Marty (2008) recast it as a resource-budget analysis in which a chip holds a fixed number of base core equivalents (BCEs), an abstract area/power cost unit, and architects choose how many BCEs to spend per core, with a core given rr BCEs achieving performance perf(r)\text{perf}(r) (typically sublinear, e.g. perf(r)=r\text{perf}(r)=\sqrt{r}). Modern interactive cloud services, however, are judged not by mean throughput but by tail latency — e.g. the 99th percentile of request response time — because a single slow request slows a user-facing fanout computation (Dean and Barroso, 'The tail at scale', CACM 2013). To connect silicon budgets to tail latency, Delimitrou and Kozyrakis ('Amdahl's law for tail latency', CACM 61(8), 2018) modeled a server as an M/M/k queue — kk servers, Poisson (memoryless) request arrivals, exponentially distributed service times — where the service rate μ\mu of a core equals perf(r)\text{perf}(r) and the mean service time is Ts=1/μT_s=1/\mu. Under a quality-of-service (QoS) target that caps a tail percentile of latency at αTs\alpha T_s, they numerically swept a 100-BCE budget across core sizes, homogeneous and heterogeneous mixes, and core-versus-cache splits, validating against a real memcached key-value store. Their first-order findings: strict QoS targets demand brawny cores (large, high-performance cores); moderate targets favor medium cores; mid-range targets favor heterogeneous big/little mixes — pairing large high-performance cores with smaller, more efficient ones — but only if the system tracks the input workload mix; and caching is critical under strict QoS. The authors themselves stress the model's limits: the sidebar notes that non-Poisson arrivals and non-exponential service times require more general models such as the G/G/k queue (the same k-server model with arbitrary, not-necessarily-exponential arrival and service-time distributions), and multi-tier services require queueing networks (networks of queues whose departures feed further queues, e.g. fork-join structures in which a request fans out to parallel backends and waits for all responses); the discussion notes that system-call and remote-procedure-call (RPC) overheads impose hard lower limits on achievable service time, and that real cores cannot scale arbitrarily with resources because of locality, cache coherence, and memory scheduling. Validation was confined to memcached with synthetic exponential load.

Problem Statement

Extend the queueing-Amdahl framework of Delimitrou and Kozyrakis (2018) — the M/M/k queueing analysis coupled to a fixed base-core-equivalent (BCE) silicon budget described in the Background — into a validated model of tail-latency-constrained resource allocation that captures the realities their analysis omits, and establish which of their original design findings survive. The common objective uniting the requested results is a trustworthy analytical account of how a fixed hardware/resource budget should be spent (core size versus core count, big/little heterogeneity, cache versus compute) when the binding constraint is a tail percentile of request latency. Concretely, per the source article's stated open items and the operational caveat attached to its heterogeneity finding, the extension should: (1a) handle non-Poisson arrival processes and non-exponential service-time distributions — G/G/k-class or equivalent — instead of assuming exponential service times, and (1b) capture request dependencies and multi-tier/fanout structure, e.g. via queueing networks or fork-join models, instead of assuming independent requests to a single queue; (2) quantify how hard lower limits on service time imposed by system-call and RPC overheads bound what caching or core microarchitecture can achieve, rather than allowing TsT_s to scale arbitrarily; (3) replace the abstract perf(r)\text{perf}(r) scaling with hardware-aware scaling that accounts for locality, coherence protocols, and memory scheduling constraints on how core performance grows with invested resources; (4) address the operational consequence that heterogeneous big/little mixes remain beneficial only if the system tracks the workload mix, by deriving or evaluating model-guided adaptation; and (5a) validate the extended model beyond memcached, across real services and realistic arrival/service distributions and degrees of serialization, and (5b) verify whether the original trade-offs (brawny cores for strict QoS, medium cores and heterogeneity for moderate QoS, cache criticality under strict QoS) persist, shift, or reverse. These strands jointly constitute the full extension: a complete resolution addresses all of them, whereas a result confined to a subset is a partial resolution that settles the strands it covers and leaves the remainder open.

References

  1. Christina Delimitrou and Christos Kozyrakis, 'Amdahl's law for tail latency', Communications of the ACM 61(8):65-72, 2018. DOI: 10.1145/3232559, https://doi.org/10.1145/3232559
  2. Mark D. Hill and Michael R. Marty, 'Amdahl's Law in the Multicore Era', IEEE Computer 41(7):33-38, 2008. DOI: 10.1109/MC.2008.209, https://doi.org/10.1109/MC.2008.209
  3. Jeffrey Dean and Luiz André Barroso, 'The tail at scale', Communications of the ACM 56(2):74-80, 2013. DOI: 10.1145/2408776.2408794, https://doi.org/10.1145/2408776.2408794
  4. Mor Harchol-Balter, 'Open problems in queueing theory inspired by datacenter computing', Queueing Systems 97(1-2):3-37, 2021. DOI: 10.1007/s11134-020-09684-6, https://doi.org/10.1007/s11134-020-09684-6
  5. Yanqi Zhang, Yu Gan, and Christina Delimitrou, 'uqSim: Scalable and Validated Simulation of Cloud Microservices', arXiv:1911.02122, 2019. DOI: 10.48550/arXiv.1911.02122, https://arxiv.org/abs/1911.02122
  6. Yu Gan, Yanqi Zhang, Dailun Cheng, Ankitha Shetty, Priyal Rathi, Nayan Katarki, Ariana Bruno, Justin Hu, Brian Ritchken, Brendon Jackson, Kelvin Hu, Meghna Pancholi, Yuan He, Brett Clancy, Chris Colen, Fukang Wen, Catherine Leung, Siyuan Wang, Leon Zaruvinsky, Mateo Espinosa, Rick Lin, Zhongling Liu, Jake Padilla, and Christina Delimitrou, 'An Open-Source Benchmark Suite for Microservices and Their Hardware-Software Implications for Cloud & Edge Systems', ASPLOS 2019, pp. 3-18. DOI: 10.1145/3297858.3304013, https://doi.org/10.1145/3297858.3304013
  7. Minh Nguyen, Sami Alesawi, Ning Li, Hao Che, and Hong Jiang, 'A Black-Box Fork-Join Latency Prediction Model for Data-Intensive Applications', IEEE Transactions on Parallel and Distributed Systems 31(9):1983-2000, 2020. DOI: 10.1109/TPDS.2020.2982137, https://doi.org/10.1109/TPDS.2020.2982137
  8. Amirhossein Mirhosseini and Thomas F. Wenisch, 'The Queuing-First Approach for Tail Management of Interactive Services', IEEE Micro 39(4):55-64, 2019. DOI: 10.1109/MM.2019.2897671, https://doi.org/10.1109/MM.2019.2897671
  9. Amirhossein Mirhosseini, Akshitha Sriraman, and Thomas F. Wenisch, 'Enhancing Server Efficiency in the Face of Killer Microseconds', HPCA 2019, pp. 185-198. DOI: 10.1109/HPCA.2019.00037, https://doi.org/10.1109/HPCA.2019.00037
  10. Amirhossein Mirhosseini, Brendan L. West, Geoffrey W. Blake, and Thomas F. Wenisch, 'Q-Zilla: A Scheduling Framework and Core Microarchitecture for Tail-Tolerant Microservices', HPCA 2020, pp. 207-219. DOI: 10.1109/HPCA47549.2020.00026, https://doi.org/10.1109/HPCA47549.2020.00026
  11. Akshitha Sriraman, Abhishek Dhanotia, and Thomas F. Wenisch, 'SoftSKU: Optimizing Server Architectures for Microservice Diversity @Scale', ISCA 2019, pp. 513-526. DOI: 10.1145/3307650.3322227, https://doi.org/10.1145/3307650.3322227
  12. Qingyang Wang, Shungeng Zhang, Yasuhiko Kanemasa, and Calton Pu, 'Mitigating Tail Response Time of n-Tier Applications: The Impact of Asynchronous Invocations', ACM Transactions on Internet Technology 19(3):1-25, 2019. DOI: 10.1145/3340462, https://doi.org/10.1145/3340462
  13. Heng Zhuo and Mikko Herman Lipasti, 'TailWAG: Tail Latency Workload Analysis and Generation', 5th International Workshop on Benchmarking in the Data Center (BID@PPOPP), 2023, pp. 1-9. DOI: 10.1145/3583060.3583170, https://doi.org/10.1145/3583060.3583170
  14. Joseph Rogers, Lieven Eeckhout, and Magnus Jahre, 'HILP: Accounting for Workload-Level Parallelism in System-on-Chip Design Space Exploration', HPCA 2025, pp. 1275-1288. DOI: 10.1109/HPCA61900.2025.00097, https://doi.org/10.1109/HPCA61900.2025.00097