GPU Kernel Scheduler
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.
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:
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:
T, and the next available kernel only arrives at time T', the GPU will remain idle until T', then start processing.Examples
Example 1
Input:
kernels = [[1,2], [2,4], [3,1]]
Output:
[0,2,1]
Note:
Example 2
Input:
kernels = [[0,2], [0,1], [1,3]]
Output:
[1,0,2]
Note:
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].
Constraints
1 <= kernels.length <= 10^51 <= arrivalTime_i, processingTime_i <= 10^9arrivalTime_i are non-negative.processingTime_i are positive.kernels array will not be empty.10^5 kernels within typical time limits (e.g., O(N log N)).Loading editor...