Interleaved Pipeline Bubble

Problem

Compute the bubble fraction for interleaved pipeline parallelism: each stage processes chunks_per_stage non-contiguous chunks of the micro-batch stream, so the schedule has num_microbatches * chunks_per_stage work slots and the bubble fraction is (num_stages - 1) / (num_microbatches * chunks_per_stage + num_stages - 1).

The signature is interleaved_bubble_fraction(num_stages, num_microbatches, chunks_per_stage=1).

Hint

More chunks per stage multiplies the effective number of slots and shrinks the bubble.

Test cases

case 1

in: [4,8]

expected: 0.2727272727

case 2

in: [4,8,2]

expected: 0.1578947368

case 3

in: [4,1,4]

expected: 0.4285714286

case 4

in: [1,10,3]

expected: 0

case 5

in: [8,32,2]

expected: 0.0985915493

Starter codePython

def interleaved_bubble_fraction(num_stages, num_microbatches, chunks_per_stage=1):
    # Your code here
    pass

5 test cases · run your code against them in the editor