PaperlayerView exact revision on arXiv

Source-linked AI summary

PREMA: A Predictive Multi-task Scheduling Algorithm For Preemptible Neural Processing Units

Yujeong Choi, Minsoo Rhu

arXiv:1909.04548v1cs.DCcs.LGcs.NE

TL;DR

Cloud DNN inference must share accelerator resources without sacrificing responsiveness for high-priority requests. The paper develops preemptible NPU mechanisms and PREMA, a predictive multi-task scheduler, and reports improvements in latency, throughput, and SLA satisfaction over non-preemptive scheduling.

  • Problem

    Shared DNN inference must maintain high resource utilization and throughput while meeting low-latency demands for high-priority tasks.

  • Method

    The paper develops NPU preemption mechanisms and PREMA, which uses estimated end-to-end DNN execution times to schedule multi-tasked inference.

  • Results

    Compared to a baseline non-preemptive scheduler, PREMA improves ANNT by 7.8×, fairness by 19.6×, and throughput by 1.4× while significantly reducing SLA violations.

  • Takeaways & Limitations

    Preemptible NPU multi-tasking can balance latency, fairness, throughput, and SLA satisfaction for consolidated DNN inference.

Abstract

from arXiv · show

To amortize cost, cloud vendors providing DNN acceleration as a service to end-users employ consolidation and virtualization to share the underlying resources among multiple DNN service requests. This paper makes a case for a "preemptible" neural processing unit (NPU) and a "predictive" multi-task scheduler to meet the latency demands of high-priority inference while maintaining high throughput. We evaluate both the mechanisms that enable NPUs to be preemptible and the policies that utilize them to meet scheduling objectives. We show that preemptive NPU multi-tasking can achieve an average 7.8x, 1.4x, and 4.8x improvement in latency, throughput, and SLA satisfaction, respectively.

I. INTRODUCTION

Cloud inference must combine low latency for high-priority requests with high utilization and throughput when multiple DNNs share an NPU. PREMA addresses this trade-off with NPU preemption and predictive scheduling.

  • Motivation: Co-locating DNN instances can improve accelerator utilization and throughput, but shared execution can worsen inference latency.Cloud serving frameworks therefore support multiple DNN queries on one GPU or NPU.
  • Motivation: 51% higher throughput comes with 23% worse average latency when GoogLeNet and ResNet share one V100 under NP-FCFS.More co-located DNNs cause further latency degradation.
  • Scheduling challenge: NP-FCFS delays a time-critical high-priority task until previously issued tasks finish, aggravating average response time.NP-HPF adds priority awareness but remains non-preemptive.
  • Proposed approach: Preemptible NPU hardware can proactively terminate a low-priority task so a higher-priority inference finishes earlier.The paper separates preemption mechanisms from scheduling policies that use them.
  • Contributions: The paper presents multi-tasked DNN scheduling as an important problem space and analyzes the architectural support required for NPU preemption.It describes the work as the first to explore multi-tasked DNNs and provide an in-depth quantitative analysis of NPU preemption support.
  • Proposed approach: PREMA combines preemption with end-to-end DNN execution-time estimates to balance latency, throughput, fairness, and SLA satisfaction.Its prediction model exploits deterministic DNN memory behavior and NPU execution.

II. BACKGROUND

The baseline NPU executes layered CNNs and RNNs through compiled instructions on a systolic-array GEMM unit. Its weight-stationary dataflow keeps weights in processing elements while activations stream through tiled operations.

  • DNN execution: CNNs and RNNs are represented as layer DAGs, and inference computes layers sequentially from the first layer to the last.The considered layers include convolution, activation, pooling, fully connected, and recurrent operations.
  • NPU interface: The NPU is a CPU-loaded coprocessor whose compiled CISC instructions operate on tiles moved between DRAM, buffers, the GEMM unit, and the accumulator queue.The instruction set includes LOAD_TILE, GEMM_OP, CONV_OP, VECTOR_OP, and STORE_TILE.
  • Tiled GEMM: Tiled GEMM partitions weight and activation matrices into inner and outer tiles compatible with the systolic array.Rightmost and bottommost outer tiles may be smaller than inner tiles.
  • Microarchitecture: The systolic-array GEMM unit contains 128 × 128 processing elements, each performing one 16-bit MAC operation per cycle.Each processing element has a weight register loaded through the weight buffer.
  • Dataflow: Weight-stationary execution keeps PE weights fixed while input activations stream through the GEMM unit and outputs accumulate in ACCQ.Outputs may return to the unified activation buffer or remain in ACCQ for tiled accumulation.

C. Research Scope

The paper focuses on scheduling user requests after Kubernetes routes them to an individual NPU, while distinguishing NPU-specific preemption from GPU-oriented approaches. Multi-NPU node-level scheduling remains outside its scope.

  • Scope: The study examines scheduling requests after Kubernetes routes them to each inference server’s GPU or NPU.Efficient system-node-level scheduling across multiple NPUs is left for future work.
  • Scope: Direct quantitative comparison with prior GPU preemption work is limited because GPU and NPU execution models, microarchitectures, and scheduling granularities differ.Prior GPU mechanisms target SIMT thread-block execution, whereas NPUs use single-threaded, vector/matrix-based execution.
  • Evaluation setting: The paper situates its evaluation on an NPU configuration specified by a dedicated configuration-parameter table.The supplied table passage provides the table label but no parameter values.
  • Related work: GPU preemption can incur high latency because massively sized thread contexts may require preserving tens of megabytes of state.The cited prior work reports preemption latency of several tens of microseconds and explores mechanisms to reduce that overhead.

III. METHODOLOGY

The methodology combines a cycle-level TPU-based performance model with representative CNN and RNN inference workloads and metrics capturing slowdown, throughput, and fairness. PREMA’s inference-task context table supports the scheduler’s task representation.

  • Simulation methodology: The evaluation uses a cycle-level performance model based on Google’s TPU architecture and cross-validates it against SCALE-Sim and Google Cloud TPUv2.The model relies on deterministic DNN computation and memory-access behavior.
  • Benchmarks: The workload includes four CNNs—AlexNet, GoogLeNet, VGGNet, and MobileNet—and four cloud-inference LSTM RNN models.The selected CNNs span diverse convolution configurations, while the RNNs include sentiment-analysis and machine-translation models.
  • Metrics: The metrics include normalized turnaround time, Average NTT, system throughput, and fairness.NTT measures slowdown relative to isolated execution, while fairness measures equal progress relative to isolated execution.
  • Scheduler representation: PREMA uses an inference task context table whose entries support scheduler decisions for multi-task execution.The figure caption identifies the table and directs readers to the scheduler section for field usage.

IV. DESIGNING A PREEMPTIBLE NPU ARCHITECTURE

The proposed architecture tracks task context and supports several NPU preemption mechanisms with different tradeoffs in checkpointing, latency, fairness, and throughput. Its design preserves the state needed to resume inference while enabling scheduler-selected preemption behavior.

  • Architecture: The preemptible NPU adds a preemption module and task-context table to track multiple DNN tasks and scheduler state.The module receives inference requests from the CPU and acts according to the selected mechanism and scheduling policy.
  • Checkpointing requirements: Inference preemption checkpoints newly derived output activations in UBUF and ACCQ, because weights remain unchanged and activation storage depends on layer operation.The major checkpointing overhead comes from output activations derived before the request is serviced.
  • Preemption mechanisms: CHECKPOINT preserves the preempted task’s execution context in memory before switching to the preempting task.A software trap routine performs context preservation, restoration, and task switching.
  • Preemption mechanisms: KILL immediately terminates the current task without checkpointing, reducing responsiveness delay but requiring execution to restart from scratch.It may trade favorably against CHECKPOINT when invoked early, although wasted computation can harm throughput.
  • Preemption mechanisms: DRAIN delays the preempting task until the current inference finishes its remaining network-wide computation.Although not strictly preemption, PREMA uses DRAIN as a scheduling tool and evaluates it with the other mechanisms.
  • Portability: The proposed mechanisms are intended to apply beyond the baseline NPU by placing preemption points at tile boundaries in task-level parallel, double-buffered designs.The cited scope covers other NPU designs with comparable tiling behavior.
  • Evaluation: Figure 5 evaluates preemption latency and preempting-task wait time across mechanisms, DNNs, and batch sizes.Results are averaged over random high-priority tasks and batch sizes 1, 4, and 16.

D. Effect of the Preemption Mechanisms

The evaluation isolates how preemption mechanisms affect multi-task NPU scheduling, showing that their overhead is small for latency but consequential for throughput and waiting time. CHECKPOINT is selected for PREMA because it preserves latency guarantees while improving system throughput over KILL.

  • Mechanism Evaluation: 3.08× and 3.06× NTT improvement is observed for KILL and CHECKPOINT, respectively, despite their different preemption overheads.Preemption latency is typically microseconds and remains below 2.6% of overall inference time.
  • Mechanism Evaluation: Preemption latency has only secondary effects on preempted and preempting tasks because DNN inference is relatively long-running.The studied network-wide inference times range from 0.5 to 45 milliseconds.
  • Mechanism Evaluation: The preemption mechanism substantially affects the preempting task’s waiting time and system throughput, so schedulers must account for that trade-off.The mechanism’s impact extends beyond checkpointing overhead to scheduling outcomes.
  • Mechanism Evaluation: CHECKPOINT provides comparable latency guarantees to KILL while achieving much higher STP across the evaluations.The paper therefore uses CHECKPOINT as PREMA’s primary preemption mechanism and revisits KILL sensitivity later.
  • Scheduling Implication: PREMA addresses starvation under preemptive high-priority-first scheduling by using estimated job length to let short-running low-priority tasks finish quickly.This can lengthen the current task’s latency while reducing severe slowdown for the short task.

B. PREMA Prediction Model

PREMA predicts end-to-end DNN inference time by combining layer-level latency estimates with estimates of total executed nodes. The model accounts for deterministic systolic-array execution and input-dependent sequence lengths in RNNs.

  • Prediction Architecture: PREMA’s predictor combines node-level execution-time estimation with prediction of the total number of executed nodes.Together, these components infer network-wide DNN latency.
  • Prediction Assumptions: The predictor relies on regular, deterministic algorithm and architecture behavior, while profiling measurements can estimate per-layer latency.The paper reports low latency variation for profiled GPU and TPU layer configurations.
  • CNN Prediction: Systolic-array layer latency is estimated from tiled GEMM compute and memory phases, including inner and edge outer tiles.The model accounts for overlap between computation and fetching input tiles, then aggregates tile costs across each layer.
  • RNN Prediction: CNN node counts are statically known, whereas RNN node counts vary with input-dependent time-unrolled recurrence length.This variability makes static network-wide latency estimation challenging for RNNs.
  • RNN Prediction: RNN output sequence length is highly correlated with input sequence length across translation applications and languages.The paper uses this relationship to support static prediction of dynamically determined seq2seq execution length.
  • RNN Prediction: A profile-driven characterization graph serves as a regression model for predicting time-unrolled output sequence length.PREMA implements this regression as a software lookup table indexed by input sequence length.

C. “Token”-based Scheduling Framework

PREMA uses token-based scheduling to balance priority, slowdown, fairness, throughput, and SLA objectives on a preemptible NPU. It selects eligible short jobs and dynamically chooses how to preempt the current task.

  • Framework: PREMA separates task selection from preemption-mechanism selection: it first chooses a candidate task, then selects the appropriate mechanism.This framework builds on the preemption mechanism and prediction model.
  • Token Policy: Each task receives initial tokens based on user-defined priority, determining its opportunity to be selected for execution.Priority levels and initial token assignments are statically configured.
  • Token Policy: Candidate tasks are those exceeding a dynamically determined threshold, which is rounded down to an available priority token value.The rounding prevents a threshold from excluding every task in the ready queue.
  • Token Policy: Periodic token increases are proportional to normalized slowdown and task priority, giving short-running tasks additional scheduling opportunity.Normalized slowdown compares ready-queue idle time with uninterrupted isolated execution time.
  • Mechanism Selection: The dynamic preemption mechanism compares normalized remaining-time degradation for the current and candidate tasks to choose DRAIN or CHECKPOINT.DRAIN is used when the current task is nearing completion relative to the candidate; otherwise CHECKPOINT is selected.

VI. EVALUATION

The evaluation models eight cloud-inference DNN workloads, including CNNs and RNNs, with dynamically selected RNN output lengths based on profiled input and output sequences.

  • Workload Construction: Eight DNN workloads are evaluated, with actual and predicted RNN recurrence lengths generated from profiled input lengths and possible output sequences.The workload includes CNN and RNN models discussed earlier in the paper.

A. Prediction Model Effectiveness

The evaluation isolates prediction-model effects by comparing six schedulers on a non-preemptive NPU. PREMA combines priority grouping with shortest-estimated-job-first scheduling to balance latency, fairness, and throughput.

  • 1.6% estimation error enables shorter jobs to finish sooner, improving average latency and fairness.
  • SJF achieves the highest ANTT because scheduling soonest-completing jobs minimizes average latency.
  • PREMA reaches 92% of SJF’s ANTT while retaining fairness and priority awareness.

B. Benefits of PREMA “and” Preemption

Dynamic preemption lets PREMA adapt both the preemption mechanism and scheduling policy to execution context. Across latency, fairness, throughput, SLA violations, and tail latency, it improves high-priority service while maintaining overall performance.

  • 7.8×, 19.6×, and 1.4× improvements in ANTT, fairness, and STP result from PREMA with dynamic preemption.
  • Dynamic preemption adaptively chooses between CHECKPOINT and DRAIN rather than always using CHECKPOINT.
  • PREMA reduces SLA violations below 10% at N=4, compared with 36% under NP-FCFS.
  • SJF can reduce SLA violations for all tasks but significantly worsens high-priority tail latency.
  • PREMA limits high-priority tail-latency overhead to an average 40% and no more than 60% over isolated execution.
  • Prediction accuracy reaches 99% of the oracle’s STP, ANTT, and SLA results, with 98% correlation to simulated inference time.

E. Sensitivity Study

The sensitivity study finds CHECKPOINT generally preferable to KILL, while preemption requires storage for per-task context and checkpointed activations. The paper reports these costs as manageable for the studied workloads and hardware configuration.

  • CHECKPOINT achieves 87%, 24%, and 77% improvement in average ANTT, STP, and fairness over KILL.
  • KILL improves ANTT and fairness in some cases but almost always performs worse than CHECKPOINT and harms STP.
  • Tracking one task requires 448 bits of SRAM, while 16 co-located tasks require only 0.01 mm^2 in 32 nm.
  • Checkpointed output activations consume hundreds of MBs for the studied DNNs at batch size 16.
  • If checkpoint state oversubscribes NPU memory, overflowing data can be migrated to CPU memory during service.
Loading 1909.04548v1…