Study Plan

Measure Kernel Timeline Utilization

GPU ProgrammingInference

Medium

Implement utilization analysis for separate and fused kernel timelines. Merge touching or overlapping busy intervals independently per streaming multiprocessor. For $N$ processors, makespan $T$ , and merged busy time $T_{\mathrm{busy},s}$ :

U=\frac{\sum_s T_{\mathrm{busy},s}}{NT}.

For each processor, idle tail is makespan minus its final positive-work end, or the full makespan when it did no work. Return a dictionary with separate metrics, fused metrics, and relative_makespan_speedup. Two empty timelines have speedup one.

Loading visualization...

Examples

Input: separate_intervals = [[0,0,4],[0,2,6],[1,1,3]], fused_intervals = [[0,0,3],[1,0,3]], separate_sm_count = 2, fused_sm_count = 2

Output: {"separate":{"makespan":6,"busy_time":8,"utilization":0.666667,"idle_tails":[0,3]},"fused":{"makespan":3,"busy_time":6,"utilization":1,"idle_tails":[0,0]},"relative_makespan_speedup":2}

Explanation: The two overlapping intervals on processor zero merge into one six-unit busy interval.

Input: separate_intervals = [[0,1,3]], fused_intervals = [[0,1,3]], separate_sm_count = 3, fused_sm_count = 3

Output: {"separate":{"makespan":3,"busy_time":2,"utilization":0.222222,"idle_tails":[0,3,3]},"fused":{"makespan":3,"busy_time":2,"utilization":0.222222,"idle_tails":[0,3,3]},"relative_makespan_speedup":1}

Input: separate_intervals = [], fused_intervals = [], separate_sm_count = 2, fused_sm_count = 3

Output: {"separate":{"makespan":0,"busy_time":0,"utilization":0,"idle_tails":[0,0]},"fused":{"makespan":0,"busy_time":0,"utilization":0,"idle_tails":[0,0,0]},"relative_makespan_speedup":1}

Hint 1

Sort and merge intervals independently for each processor.

Hint 2

Derive utilization and idle tails from merged ranges.

Requirements

Group intervals by processor and merge touching or overlapping ranges.
Ignore zero-length intervals when computing busy time and makespan.
Return makespan, busy_time, utilization, and idle_tails for both timelines.
Compute separate makespan divided by fused makespan, with speedup one for two empty timelines.
Do not modify interval lists.

Constraints

Processor counts are positive Python integers.
Every interval is [processor_id, start, end] with a valid ID and finite 0 <= start <= end.
A nonempty separate timeline has a nonempty fused timeline.
Empty timelines are valid.

Try Similar Problems

Find Reusable Prefixes in a KV TrieMedium Route Cache-Aware Prefill RequestsHard Simulate Continuous Decode BatchingHard GPU Occupancy CalculatorMedium Plan KV-Cache CapacityMedium Decode Attention with a KV CacheHard Shared-Memory Bank Conflict AnalyzerEasy Global-Memory Coalescing CounterEasy Implement Per-Channel Weight QuantizationMedium Analyze Prefill and Decode with the Roofline ModelMedium Implement Group-Wise INT4 QuantizationHard Implement Block-Wise FP8 QuantizationHard