PaperlayerView exact revision on arXiv

Source-linked AI summary

Kernelet: High-Throughput GPU Kernel Executions with Dynamic Slicing and Scheduling

Jianlong Zhong, Bingsheng He

arXiv:1303.5164v1cs.DC

TL;DR

Shared GPUs can be underutilized even with concurrent-kernel support, while throughput matters for performance and ownership cost. Kernelet dynamically slices kernels and uses a Markov-chain performance model to guide scheduling; it improves performance by up to 31.1% on C2050 and 23.4% on GTX680.

  • Problem

    Concurrent kernels can leave shared GPUs underutilized, even though throughput matters for performance and total ownership cost.

    Source: §1 · p. 1

  • Method

    Kernelet dynamically slices kernels into tunable-occupancy pieces and uses a Markov-chain performance model to guide co-scheduling.

    Source: §1 · p. 2

  • Results

    31.1% and 23.4%: Kernelet improves performance by up to these amounts on Tesla C2050 and GTX680, respectively.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Experiments support Kernelet’s effectiveness for concurrent kernel execution on the evaluated C2050 and GTX680 workloads.

    Source: §7 · p. 13

    The study mainly addresses throughput when sharing a single GPU; multi-GPU use would require a workload dispatcher.

    Source: §2.2 · p. 3

Abstract

from arXiv · show

Graphics processors, or GPUs, have recently been widely used as accelerators in the shared environments such as clusters and clouds. In such shared environments, many kernels are submitted to GPUs from different users, and throughput is an important metric for performance and total ownership cost. Despite the recently improved runtime support for concurrent GPU kernel executions, the GPU can be severely underutilized, resulting in suboptimal throughput. In this paper, we propose Kernelet, a runtime system with dynamic slicing and scheduling techniques to improve the throughput of concurrent kernel executions on the GPU. With slicing, Kernelet divides a GPU kernel into multiple sub-kernels (namely slices). Each slice has tunable occupancy to allow co-scheduling with other slices and to fully utilize the GPU resources. We develop a novel and effective Markov chain based performance model to guide the scheduling decision. Our experimental results demonstrate up to 31.1% and 23.4% performance improvement on NVIDIA Tesla C2050 and GTX680 GPUs, respectively.

1 INTRODUCTION

The paper targets underutilization in shared-GPU workloads, where throughput matters for performance and ownership cost. Kernelet dynamically slices kernels and schedules slices using a performance model, improving throughput on two GPUs.

1 INTRODUCTION

  • In shared clusters and clouds, throughput matters both to throughput-oriented applications and to GPU efficiency and total ownership cost.The paper also notes that GPUs are expensive devices and that high throughput can improve user performance and productivity.Source: §1 · p. 1
  • Single kernels can severely underutilize GPUs because of irregular memory accesses and execution-pipeline stalls; eight studied kernels averaged 0.52 IPC on C2050.Their memory-bandwidth utilization ranged from 0.02% to 14%.Source: §1 · p. 1
  • Prior concurrent-kernel scheduling work focused mainly on low-occupancy kernels, while optimized kernels with large inputs usually have high occupancy.The paper argues that treating whole kernels as units does not realize GPU resource sharing.Source: §1 · p. 2
  • Slicing creates a trade-off between one-block slices, which risk excessive submission overhead, and whole-kernel slices, which reduce to non-sliced execution.The scheduler must also select slices to co-schedule to maximize GPU utilization.Source: §1 · p. 2
  • Kernelet dynamically slices kernels into tunable-occupancy pieces and uses a Markov-chain performance model to guide scheduling for complementary resource use.A greedy algorithm co-schedules slices from two kernels with the highest modeled performance gain.Source: §1 · p. 2
  • 31.1% and 23.4%: Kernelet improves performance by up to these amounts on the Tesla C2050 and GTX680, respectively.The analytical model captures heterogeneous-workload performance, and the scheduling approach raises GPU throughput.Source: §1 · p. 2

2 BACKGROUND AND PROBLEM DEFINITION

The paper frames GPU sharing as scheduling concurrent kernels on a single GPU, with slicing and co-scheduling aimed at minimizing total execution time. Its setting includes shared and virtualized environments and assumes independent thread blocks.

2.1 GPU Architectures

  • Shared GPUs may receive kernels from different applications, making it feasible to schedule workloads with differing memory and computation characteristics.The paper focuses on CUDA and notes that its design can be extended to OpenCL with little modification.Source: §2.1 · p. 2
  • CUDA groups threads into warps and thread blocks; blocks map to SMs, while occupancy depends on active warps and available registers and shared memory.If a running kernel cannot fully utilize the GPU, blocks from other kernels may be scheduled.Source: §2.1 · pp. 2–3
  • Because shared environments may not provide kernel source code, Kernelet is designed to work with PTX and SASS binaries.CUDA compilation converts PTX to native SASS instructions, which the GPU executes.Source: §2.1 · p. 3

2.2 Problem Definition

  • The considered scenarios are GPU sharing among virtualized tenants and GPU servers receiving local or remote kernel launches through API software.The study focuses on throughput when sharing one GPU; multi-GPU use could be extended with a dispatcher.Source: §2.2 · p. 3
  • Kernelet assumes throughput-oriented kernels with flexible response times, unknown arrival order, and independent thread blocks so slicing is safe.The paper says dependencies between blocks can be identified using static or dynamic program analysis.Source: §2.2 · p. 3
  • A slice is a subset of a kernel’s thread blocks with continuous block IDs, and a slicing plan divides a kernel into an ordered sequence of slices.A co-schedule is the concurrent execution of one or more active slices.Source: §2.2 · p. 3
  • A scheduling plan orders co-schedules so every thread block appears exactly once, and the objective is to minimize total execution time or maximize co-scheduling profit.New kernel arrivals trigger recalculation using residual and newly arrived kernels.Source: §2.2 · pp. 3–4

3 SYSTEM OVERVIEW

Kernelet must make lightweight, real-time scheduling decisions as kernels arrive, despite a large space of slicing and scheduling choices. Its runtime generates plans using a design that limits the search scope and combines preprocessing with model-guided dispatch.

3.1 Design Rationale

  • The space of slicing and scheduling plans grows with slice counts, slice sizes, and possible co-schedules, and new arrivals enlarge it further.Real-time decisions and low overhead rule out exhaustive search and make Monte Carlo simulation too costly for the runtime budget.Source: §3.1 · p. 4
  • Kernelet considers two kernels at a time and keeps their selected slice sizes unchanged until either kernel finishes.The performance model determines suitable slice sizes.Source: §3.1 · p. 4

3.2 System Overview

  • Kernelet generates slicing and scheduling plans at runtime to optimize throughput.Submitted kernels are buffered; preprocessing finds the smallest slice size within an overhead limit, then a probabilistic model guides scheduling and slices are dispatched to the GPU.Source: §3.2 · p. 4

4 KERNELET METHODOLOGY

Kernelet’s methodology divides kernels into schedulable slices and selects, sizes, and prunes kernel pairs for co-scheduling. It uses a probabilistic Markov-chain model, informed by a small set of profiling inputs, to estimate concurrent performance and guide scheduling.

4.1 Kernel Slicing

  • Kernelet slices kernels by thread block, rectifies block indices to launch each slice separately, and targets overhead no greater than 2% of kernel execution time.Thread blocks are used because warps within a block may share data; the slice size is the minimum that meets the overhead target, set to 2% by default.Source: §4.1 · pp. 4–5

4.2 Scheduling

  • Scheduling considers two kernels at a time, tunes their slice sizes for GPU utilization and similar concurrent execution times, then selects the co-schedule with the highest predicted CP.The search prunes candidate co-schedules before applying the performance model; the same co-schedule is reused while pending kernels remain unchanged or both selected kernels have thread blocks.Source: §4.2 · pp. 5–6

4.3 Co-scheduling Space Pruning

  • Kernelet prunes kernel pairs with similar PUR or MUR, since pairs with contrasting instruction-pipeline or memory-bandwidth utilization can better exploit idle cycles and alleviate memory contention.PUR and MUR are derived from single-kernel executions; thresholds αp and αm determine when differences are too small, and are increased if all candidate pairs are pruned.Source: §4.3 · p. 6

4.4 Performance Model

  • A probabilistic Markov-chain model estimates concurrent-kernel performance by representing an SM’s idle warps and deriving IPC and CP from steady-state behavior.For two kernels, it tracks each workload’s idle warps and combines their transition probabilities; it also estimates balanced slice ratios to minimize the execution-time difference between co-scheduled slices. The model extends to coalesced and uncoalesced accesses and multiple warp schedulers, and reduces runtime cost by treating thread blocks as scheduling units.Source: §4.4 · pp. 6–8
  • The performance model relaxes its initial single-scheduler, coalesced-access assumptions by modeling distinct coalesced and uncoalesced stalls and representing multi-scheduler GPUs as a parameter-scaled virtual SM.For multiple schedulers, SMX parameters are divided by the number of schedulers; the paper also describes profiling a small number of thread blocks to obtain model inputs.Source: §4.4 · pp. 7–9
  • The probabilistic model captures inherent nondeterminism in concurrent kernel executions.Source: §4.4 · p. 9
  • The model requires only a small set of profiling inputs on each kernel’s memory and computation characteristics.Source: §4.4 · p. 9
  • Careful probabilistic modeling yields a performance model intended to be sufficiently accurate to guide scheduling decisions.Its effectiveness will be evaluated in the experiments (Section 5).Source: §4.4 · p. 9

5 EVALUATION

Evaluation on C2050 and GTX680 measures slicing overhead, model predictions, and scheduling performance across varied kernel mixes.

5.1 Experimental Setup

  • Experiments used eight benchmarks, four kernel mixes with Poisson arrivals, and BASE, offline OPT, and Monte Carlo scheduling comparisons on C2050 and GTX680.The mixes were CI, MI, MIX, and ALL; the setup assumed at least two kernels were pending at any time.Source: §5.1 · pp. 9–10

5.2 Results on Kernel Slicing

  • Below 2% overhead occurred for almost all GTX680 slice sizes; C2050 overhead reached 66.7% for SAD at small sizes but was ignorable for most kernels at 42 blocks or more.The 42-block threshold corresponds to three thread blocks per SM on C2050; Figure 6 compares overhead across slice sizes on both GPUs.Source: Figure 6 · p. 10, §5.2 · p. 10

5.3 Results on Model Prediction

  • Average absolute single-kernel IPC prediction error was 0.08 on C2050 and 0.21 on GTX680 across eight benchmarks, with most estimates within ±20% of peak IPC.Figure 7 compares measured and estimated IPC; its stated tolerance bands are ±0.2 for C2050 and ±1.6 for GTX680.Source: Figure 7 · p. 10, §5.3 · p. 10
  • Across kernel combinations and slice ratios, the model captured concurrent-execution IPC trends for both model-selected and fixed 1:1 ratios on both GPUs.Figures 8 and 9 show the predicted-versus-measured comparisons for optimal and fixed 1:1 ratios.Source: §5.3 · pp. 10–11, Figure 8 · p. 11, Figure 9 · p. 11
  • Ignoring uncoalesced accesses overpredicted IPC for PC and SPMV, while ignoring GTX680’s multiple warp schedulers severely underpredicted concurrent IPC.The model’s coalesced-only assumption underestimated memory contention; the scheduler omission was evaluated against Figure 8.Source: §5.3 · p. 11, Figure 10 · p. 11, Figure 11 · p. 11
  • Predicted CP was close to measured CP on C2050 and showed similar results on GTX680, supporting its use to guide scheduling decisions.Figure 12 presents the C2050 comparison.Source: Figure 12 · p. 11, §5.3 · p. 11

5.4 Results on Kernel Scheduling

  • Kernelet cut total execution time versus BASE by 5.0–31.1% on C2050 and 6.7–23.4% on GTX680, while staying within 0.7–3.1% and 4.0–15.0% of OPT, respectively.On MIX and ALL, improvement over BASE was more significant because Kernelet had more chances to select kernels with complementary resource usage.Source: §5.4 · pp. 11–12, Figure 13 · p. 12
  • None of the MC(1000) random schedules outperformed Kernelet, and the CDF indicates random co-schedules often hurt performance.Figure 14 shows the execution-time distribution for MC(1000).Source: Figure 14 · p. 12, §5.4 · p. 12

6 RELATED WORK

Prior work covers CPU SMT scheduling and GPU multi-kernel execution, but Kernelet addresses GPU-specific sharing constraints through slicing and concurrent-kernel modeling.

6.1 CPU Scheduling and Performance Modeling

  • CPU SMT schedulers co-schedule threads with complementary resource needs, using mechanisms such as hardware counters, exhaustive pre-execution, and probabilistic models,, –.CPU performance models, including Markov-chain approaches, have also estimated concurrent instruction throughput,.Source: §6.1 · pp. 12–13
  • SMT scheduling does not transfer directly to GPUs because thread parallelism, limited preemption, thousands of launched threads, and dynamic active-warp counts change the scheduling problem,,.Kernelet’s slicing, scheduling, and models are designed for these GPU-specific constraints.Source: §6.1 · p. 13

6.2 GPU Multiple Kernel Execution and Sharing

  • GPU sharing work includes source-level kernel merging,, consolidation, virtualization,, and system-level scheduling,,; Kernelet instead slices kernels and models concurrent execution.Prior GPU performance models generally target single kernels and often require extensive profiling or simulation, unlike Kernelet’s concurrent-kernel model using key per-kernel factors,,.Source: §6.2 · p. 13

7 CONCLUSION

Kernelet improves concurrent kernel throughput in shared GPU environments through kernel slicing and probabilistic performance modeling. Experiments report gains on both evaluated GPUs.

7 CONCLUSION

  • Concurrent kernel executions improve by 5.0–31.1% on C2050 and 6.7–23.4% on GTX680 workloads.The evaluation also demonstrates the accuracy of Kernelet’s performance model.Source: §7 · p. 13
  • Kernelet creates more sharing opportunities by slicing kernels and models the non-deterministic performance of multiple-kernel executions probabilistically.The model guides scheduling decisions.Source: §7 · p. 13
  • Kernelet is evaluated on NVIDIA Tesla C2050 and GTX680 GPUs with Fermi and Kepler architectures, respectively.Source: §7 · p. 13
Loading 1303.5164v1…