Gradient Bucket Overlap Fraction

Problem

Simulate bucket-overlapped all-reduce during backward. Bucket i (0-indexed) becomes ready at (i + 1) / num_buckets * backward_ms; communications run in order on one link, each starting at max(ready_time, link_free) and lasting comm_ms_per_bucket. Return [hidden_fraction, exposed_ms], where exposed_ms is how far the final communication extends past backward_ms and hidden_fraction = 1 - exposed_ms / total_comm_ms.

The signature is bucket_overlap_fraction(backward_ms, num_buckets, comm_ms_per_bucket). If comm_ms_per_bucket is 0 return [1.0, 0.0].

Hint

The last bucket becomes ready exactly when backward ends, so its communication can never hide.

Test cases

case 1

in: [100,10,5]

expected: [0.9,5]

case 2

in: [100,5,40]

expected: [0.4,120]

case 3

in: [100,1,20]

expected: [0,20]

case 4

in: [50,4,10]

expected: [0.75,10]

case 5

in: [80,8,0]

expected: [1,0]

Starter codePython

def bucket_overlap_fraction(backward_ms, num_buckets, comm_ms_per_bucket):
    # Your code here
    pass

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