TensorTonic
Study Plans
Study Plan
Measure Pipeline Bubble Utilization
Distributed Computing
Medium

Construct a deterministic GPipe schedule with equal-duration stage operations and no overlap between the forward and backward waves. Let ppp be num_stages and mmm be num_microbatches. Each wave lasts TTT time slots:

T=m+p−1.T=m+p-1.T=m+p−1.

In forward time slot ttt, stage sss processes microbatch iforwardi_{\mathrm{forward}}iforward​:

iforward=t−s.i_{\mathrm{forward}}=t-s.iforward​=t−s.

When include_backward is true, the backward wave follows the completed forward wave. At backward offset uuu, stage sss processes microbatch ibackwardi_{\mathrm{backward}}ibackward​:

ibackward=m−1−(u−(p−1−s)).i_{\mathrm{backward}}=m-1-\left(u-(p-1-s)\right).ibackward​=m−1−(u−(p−1−s)).

All indices start at zero: sss ranges from 0 through p−1p-1p−1, while ttt and uuu range from 0 through T−1T-1T−1. A microbatch index outside 0 through m−1m-1m−1 means that stage is idle. Label work F0, F1, and so on for forward, or B0, B1, and so on for backward; use None for idle cells. With q=2q=2q=2 when backward is included and q=1q=1q=1 otherwise, useful and total stage-slot counts are:

Cuseful=qpm.C_{\mathrm{useful}}=qpm.Cuseful​=qpm. Ctotal=qTp.C_{\mathrm{total}}=qTp.Ctotal​=qTp.

Return a Python dictionary with schedule, a time-ordered list of stage-ordered lists containing strings or None; bubble_slots and total_slots, Python integer cell counts; and utilization, a Python float equal to useful cells divided by total cells.

Loading visualization...

Examples

Input: num_stages = 2, num_microbatches = 3, include_backward = false

Output: {"schedule":[["F0",null],["F1","F0"],["F2","F1"],[null,"F2"]],"bubble_slots":2,"total_slots":8,"utilization":0.75}

Explanation: Six forward computations occupy eight stage-slot cells, leaving two bubbles.

Input: num_stages = 2, num_microbatches = 2, include_backward = true

Output: {"schedule":[["F0",null],["F1","F0"],[null,"F1"],[null,"B1"],["B1","B0"],["B0",null]],"bubble_slots":4,"total_slots":12,"utilization":0.666667}

Input: num_stages = 1, num_microbatches = 3, include_backward = false

Output: {"schedule":[["F0"],["F1"],["F2"]],"bubble_slots":0,"total_slots":3,"utilization":1}

Hint 1

range supplies zero-based slot and stage indices.

Hint 2

An f-string can combine a phase letter with a microbatch index.

Hint 3

sum can count Boolean conditions across nested lists.

Requirements

  • Preserve chronological slot order and increasing stage order within each slot.
  • Include the backward wave only when requested.
  • Count stage-slot cells, not time slots, in the two integer metrics.

Constraints

  • num_stages and num_microbatches are positive Python integers.
  • include_backward is a Python Boolean.
  • Stage and microbatch indices start at zero.
  • Each stage operation takes one time slot.
Try Similar Problems
Account for ZeRO Memory by StageEasyChoose a Topology-Aware Parallel PlanHardSynchronize Data-Parallel GradientsMediumSimulate Distributed CollectivesMediumReconstruct a Column-Parallel MLP LayerMediumCalculate Collective Effective BandwidthEasyTrain a BPE Tokenizer From Scratch in PythonMediumCanonicalize Pairwise Preference DataMediumCalculate Tensor Parallel Communication CostHardSimulate Disaggregated Prefill and Decode ServingHardEstimate Model Memory and Minimum GPU CountEasyImplement Expert Parallel Routing Across GPUsHard

Accepts: number

Accepts: number

You must run your code first.

Measure Pipeline Bubble Utilization

Distributed Computing
Medium

Construct a deterministic GPipe schedule with equal-duration stage operations and no overlap between the forward and backward waves. Let ppp be num_stages and mmm be num_microbatches. Each wave lasts TTT time slots:

T=m+p−1.T=m+p-1.T=m+p−1.

In forward time slot ttt, stage sss processes microbatch iforwardi_{\mathrm{forward}}iforward​:

iforward=t−s.i_{\mathrm{forward}}=t-s.iforward​=t−s.

When include_backward is true, the backward wave follows the completed forward wave. At backward offset uuu, stage sss processes microbatch ibackwardi_{\mathrm{backward}}ibackward​:

ibackward=m−1−(u−(p−1−s)).i_{\mathrm{backward}}=m-1-\left(u-(p-1-s)\right).ibackward​=m−1−(u−(p−1−s)).

All indices start at zero: sss ranges from 0 through p−1p-1p−1, while ttt and uuu range from 0 through T−1T-1T−1. A microbatch index outside 0 through m−1m-1m−1 means that stage is idle. Label work F0, F1, and so on for forward, or B0, B1, and so on for backward; use None for idle cells. With q=2q=2q=2 when backward is included and q=1q=1q=1 otherwise, useful and total stage-slot counts are:

Cuseful=qpm.C_{\mathrm{useful}}=qpm.Cuseful​=qpm. Ctotal=qTp.C_{\mathrm{total}}=qTp.Ctotal​=qTp.

Return a Python dictionary with schedule, a time-ordered list of stage-ordered lists containing strings or None; bubble_slots and total_slots, Python integer cell counts; and utilization, a Python float equal to useful cells divided by total cells.

Loading visualization...

Examples

Input: num_stages = 2, num_microbatches = 3, include_backward = false

Output: {"schedule":[["F0",null],["F1","F0"],["F2","F1"],[null,"F2"]],"bubble_slots":2,"total_slots":8,"utilization":0.75}

Explanation: Six forward computations occupy eight stage-slot cells, leaving two bubbles.

Input: num_stages = 2, num_microbatches = 2, include_backward = true

Output: {"schedule":[["F0",null],["F1","F0"],[null,"F1"],[null,"B1"],["B1","B0"],["B0",null]],"bubble_slots":4,"total_slots":12,"utilization":0.666667}

Input: num_stages = 1, num_microbatches = 3, include_backward = false

Output: {"schedule":[["F0"],["F1"],["F2"]],"bubble_slots":0,"total_slots":3,"utilization":1}

Hint 1

range supplies zero-based slot and stage indices.

Hint 2

An f-string can combine a phase letter with a microbatch index.

Hint 3

sum can count Boolean conditions across nested lists.

Requirements

  • Preserve chronological slot order and increasing stage order within each slot.
  • Include the backward wave only when requested.
  • Count stage-slot cells, not time slots, in the two integer metrics.

Constraints

  • num_stages and num_microbatches are positive Python integers.
  • include_backward is a Python Boolean.
  • Stage and microbatch indices start at zero.
  • Each stage operation takes one time slot.
Try Similar Problems
Account for ZeRO Memory by StageEasyChoose a Topology-Aware Parallel PlanHardSynchronize Data-Parallel GradientsMediumSimulate Distributed CollectivesMediumReconstruct a Column-Parallel MLP LayerMediumCalculate Collective Effective BandwidthEasyTrain a BPE Tokenizer From Scratch in PythonMediumCanonicalize Pairwise Preference DataMediumCalculate Tensor Parallel Communication CostHardSimulate Disaggregated Prefill and Decode ServingHardEstimate Model Memory and Minimum GPU CountEasyImplement Expert Parallel Routing Across GPUsHard

Accepts: number

Accepts: number

You must run your code first.