Orloj: Predictably Serving Unpredictable DNNs

Peifeng Yu, Yuqing Qiu, Xin Jin, Mosharaf ChowdhuryarXiv 2022 · OpenReview

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

Abstract

Existing DNN serving solutions can provide tight latency SLOs while maintaining high throughput via careful scheduling of incoming requests, whose execution times are assumed to be highly predictable and data-independent. However, inference requests to emerging dynamic DNNs -- e.g., popular natural language processing (NLP) models and computer vision (CV) models that skip layers -- are data-dependent. They exhibit poor performance when served using existing solutions because they experience large variance in request execution times depending on the input -- the longest request in a batch inflates the execution times of the smaller ones, causing SLO misses in the absence of careful batching. In this paper, we present Orloj, a dynamic DNN serving system, that captures this variance in dynamic DNNs using empirical distributions of expected request execution times, and then efficiently batches and schedules them without knowing a request's precise execution time. Orloj significantly outperforms state-of-the-art serving solutions for high variance dynamic DNN workloads by 51--80% in finish rate under tight SLO constraints, and over 100% under more relaxed SLO settings. For well-studied static DNN workloads, Orloj keeps comparable performance with the state-of-the-art.
BibTeX
@misc{yu2022orloj,
  author = {Peifeng Yu and Yuqing Qiu and Xin Jin and Mosharaf Chowdhury},
  title = {{Orloj: Predictably Serving Unpredictable DNNs}},
  year = {2022},
  eprint = {2209.00159},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2209.00159},
}
Figure