Frontend School

GPU Kernel Scheduler

DSA
medium

GPU Kernel Scheduler

Medium
Heap
Priority Queue
Arrays
Greedy
Scheduling

Overview

In high-performance computing, efficient scheduling of GPU kernels is crucial for maximizing throughput and minimizing latency. Consider a scenario where multiple compute kernels are submitted to a single GPU. Each kernel has a specific arrival time and requires a certain processing time. To optimize resource utilization and responsiveness, the GPU scheduler needs to intelligently decide which kernel to execute next when multiple are pending.

What you need to do / Task

You are tasked with implementing a GPU kernel scheduler that determines the execution order of kernels based on a specific priority rule. Your solution should:

  1. Process kernels in chronological order of their arrival times.
  2. When the GPU becomes idle, or when multiple kernels are available for execution (i.e., their arrival time is less than or equal to the current GPU time), it must select the kernel with the shortest processing time.
  3. If there's a tie in processing times among available kernels, prioritize the one that arrived earliest.
  4. If there's still a tie (same processing time and arrival time), prioritize the kernel with the smallest original index (0-indexed).
  5. Return an array of integers representing the original indices of the kernels in the order they are processed by the GPU.

Input & output

Input:

  • kernels: An array of arrays, where kernels[i] = [arrivalTime_i, processingTime_i] represents the i-th kernel.
    • arrivalTime_i: A non-negative integer representing the time at which the i-th kernel arrives and becomes available.
    • processingTime_i: A positive integer representing the time required to execute the i-th kernel.

Output:

  • An array of integers representing the original 0-indexed order of kernels as they are processed by the GPU.

Clarifications

  • Arrival Order: Kernels are given in an arbitrary order. You should consider sorting them by arrival time initially to process them chronologically.
  • GPU Idle Time: If the GPU finishes a kernel at time T, and the next available kernel only arrives at time T', the GPU will remain idle until T', then start processing.
  • Simultaneous Arrival/Completion: If multiple kernels arrive at the same time, or if a kernel completes and multiple kernels are waiting, the priority rules (shortest processing time, then earliest arrival, then smallest index) apply.

Examples

1

Example 1

Input:

kernels = [[1,2], [2,4], [3,1]]

Output:

[0,2,1]

Note:

  1. At time t=1, kernel 0 ([1,2]) arrives. GPU starts processing kernel 0.
  2. At time t=2, kernel 1 ([2,4]) arrives. Kernel 0 is still processing.
  3. At time t=3, kernel 2 ([3,1]) arrives. Kernel 0 finishes at t=1+2=3. Now, at t=3, kernels 1 and 2 are available.
    • Kernel 1: processingTime=4, arrivalTime=2, index=1
    • Kernel 2: processingTime=1, arrivalTime=3, index=2 The shortest processing time is 1 (for kernel 2). GPU starts processing kernel 2.
  4. At time t=3+1=4, kernel 2 finishes. Only kernel 1 is available. GPU starts processing kernel 1.
  5. At time t=4+4=8, kernel 1 finishes. All kernels processed. Execution order: 0, 2, 1.
2

Example 2

Input:

kernels = [[0,2], [0,1], [1,3]]

Output:

[1,0,2]

Note:

  1. At time t=0, kernel 0 ([0,2]) and kernel 1 ([0,1]) arrive.
    • Kernel 0: processingTime=2, arrivalTime=0, index=0
    • Kernel 1: processingTime=1, arrivalTime=0, index=1 Shortest processing time is 1 (for kernel 1). GPU starts processing kernel 1.
  2. At time t=1, kernel 2 ([1,3]) arrives. Kernel 1 finishes at t=0+1=1. Now, at t=1, kernels 0 and 2 are available.
    • Kernel 0: processingTime=2, arrivalTime=0, index=0
    • Kernel 2: processingTime=3, arrivalTime=1, index=2 Shortest processing time is 2 (for kernel 0). GPU starts processing kernel 0.
  3. At time t=1+2=3, kernel 0 finishes. Only kernel 2 is available. GPU starts processing kernel 2.
  4. At time t=3+3=6, kernel 2 finishes. All kernels processed. Execution order: 1, 0, 2.
3

Example 3

Input:

kernels = [[5,10], [1,1], [10,5], [2,2]]

Output:

[1,3,0,2]

Note:

Initial kernels (with original index): K0:[5,10], K1:[1,1], K2:[10,5], K3:[2,2].

  1. At t=0, GPU idle. Next arrival at t=1 (K1).
  2. At t=1, K1 ([1,1]) arrives. GPU starts K1.
  3. At t=1+1=2, K1 finishes. K3 ([2,2]) arrives. GPU starts K3.
  4. At t=2+2=4, K3 finishes. GPU idle. Next arrival at t=5 (K0).
  5. At t=5, K0 ([5,10]) arrives. GPU starts K0.
  6. At t=5+10=15, K0 finishes. K2 ([10,5]) arrived at t=10. GPU starts K2.
  7. At t=15+5=20, K2 finishes. All kernels processed. Execution order: 1, 3, 0, 2.

Constraints

Constraints & assumptions

  • 1 <= kernels.length <= 10^5
  • 1 <= arrivalTime_i, processingTime_i <= 10^9
  • All arrivalTime_i are non-negative.
  • All processingTime_i are positive.
  • The input kernels array will not be empty.
  • The solution should be efficient enough to handle 10^5 kernels within typical time limits (e.g., O(N log N)).

What interviewers evaluate

  • Correctness: The solution must correctly implement the scheduling logic and priority rules to produce the exact execution order.
  • Efficiency: The algorithm should be optimized for time and space complexity, particularly for large inputs.
  • Data Structures: Appropriate use of data structures (e.g., priority queues, sorting) to manage available and pending kernels.
  • Edge Cases: Handling of edge cases such as simultaneous arrivals, very short/long processing times, and periods of GPU idle time.

Loading editor...