TL;DR
This paper introduces ORLOJ, a novel DNN serving system designed to handle the unpredictable execution times of dynamic DNNs. By modeling request execution times as probability distributions and employing a batch-aware priority score, ORLOJ significantly improves request completion rates under strict latency requirements, outperforming existing solutions by up to 80%.
What Problem Does This Paper Address?
Modern deep neural network (DNN) serving systems typically assume that each inference request takes a predictable, fixed amount of time. This assumption works well for "static" DNNs where the computation is the same regardless of the input. However, a new class of "dynamic" DNNs, common in NLP and computer vision, adapt their internal structure based on the input data. This leads to highly variable execution times for individual requests. Existing serving systems struggle with this variability because they rely on single-point estimates (like average or P99 latency) for scheduling. When requests with vastly different execution times are batched together, the longest request dictates the batch's completion time, causing many requests to miss their latency Service Level Objectives (SLOs). This paper addresses the challenge of efficiently serving these dynamic DNNs while meeting strict latency guarantees.
Methods
ORLOJ tackles the problem by moving away from fixed execution time estimates to a probabilistic approach. Key innovations include:
- Distribution-Aware Scheduling: Instead of a single latency value, ORLOJ models the execution time of each request as an empirical probability distribution learned from historical data.
- Batch-Aware Priority Score: A novel priority score is introduced that considers not just individual request deadlines but also the combined execution time distribution of potential batches. This score helps in deciding which requests to group together to minimize SLO misses.
- Handling Multimodal Distributions: ORLOJ accounts for scenarios where requests from different applications or use cases, served by the same model, have distinct execution time distributions. It uses probability theory to estimate the batch execution time even when these distributions are multimodal.
- Dynamic Convex Hull for Priority Queue: To efficiently manage and re-prioritize requests in real-time, ORLOJ employs a dynamic convex hull algorithm, achieving logarithmic complexity for updates and constant time for queries.
Datasets
The paper evaluates ORLOJ using a combination of:
- Synthesized Datasets: Used to control and explore various execution time distributions (e.g., simple normal, bimodal, multimodal with varying peak separation).
- Real-World Workloads: A comprehensive set of tasks including image classification (RDI-Nets, SkipNet), chatbot (Blenderbot, GPT), summarization (BART, T5), and translation (FSMT, mBART), using datasets like CIFAR, ImageNet, convAI, Cornell, and WMT.
Key Insights and Ideas
- The "Straggler" Problem is Critical: The core issue with dynamic DNNs in existing systems is that a single long-running request can derail an entire batch, leading to widespread SLO violations.
- Probabilistic Modeling is Essential: Treating execution times as distributions, rather than fixed points, is crucial for accurately predicting and managing batch latency.
- Batching is a Double-Edged Sword: While essential for throughput, batching exacerbates the straggler problem for dynamic DNNs. ORLOJ's batch-aware priority score is key to mitigating this.
- Application-Specific Distributions Matter: Different applications using the same model can have vastly different request patterns, leading to multimodal distributions that ORLOJ is designed to handle.
Key Results
- Significant Performance Gains for Dynamic DNNs: ORLOJ improves the finish rate by 51-80% under tight SLO constraints and by over 100% under more relaxed SLOs compared to state-of-the-art systems like Clipper, Nexus, and Clockwork.
- Comparable Performance for Static DNNs: For traditional, static DNN workloads, ORLOJ maintains performance comparable to existing systems.
- Efficient Priority Queue: ORLOJ's priority queue can handle thousands of pending requests with very low insertion times (sub-millisecond per request), demonstrating scalability.
- Robustness to Distribution Parameters: The system's performance is not overly sensitive to the exact parameters of the anticipated delay distribution, making it practical.
Limitations and Future Work
- Assumptions on Execution Time: While ORLOJ uses empirical distributions, it assumes these distributions can be learned and are representative of future requests. Drastic shifts in request patterns might require re-calibration.
- Non-Preemption: Like most DNN serving systems, ORLOJ operates under a non-preemptive model for batch execution, meaning a batch, once started, cannot be interrupted.
- Future Work: The authors suggest exploring complementary concepts like model selection and inference pipelines, and further investigating dynamic DNN lifecycle aspects beyond inference serving.
Summary updated