Pipeline Parallelism with Controllable Memory

Authors: penghui  qi
xinyi  wan
nyamdavaa  amar
min  lin
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 12:58:19

Abstract: Pipeline parallelism has been widely explored, but most existing schedules lack a systematic methodology. In this paper, we propose a framework to decompose pipeline schedules as repeating a building block, and show that the lifespan of the building block decides the peak activation memory of the pipeline schedule. Guided by the observations, we find that almost all existing pipeline schedules, to the best of our knowledge, are memory inefficient. To address this, we introduce a family of memory efficient building blocks with controllable activation memory, which can reduce the peak activation memory to 1/2 of 1F1B without sacrificing efficiency, and even to 1/3 with comparable throughput. We can also achieve almost zero pipeline bubbles while maintaining the same activation memory as 1F1B. Our evaluations demonstrate that in pure pipeline parallelism settings, our methods outperform 1F1B by from 7\% to 55\% in terms of throughput. When employing a grid search over hybrid parallelism hyperparameters in practical scenarios, our methods demonstrate a 16\% throughput improvement over the 1F1B baseline for large language models. The implementation is open-sourced at https://github.com/sail-sg/zero-bubble-pipeline-parallelism.

Main paper: 
 introduction: 
 Distributed model training has attracted a lot of attention in recent years, especially after the boom of large language models [Brown et al., 2020] . As the model size becomes larger and larger, data parallelism (DP) [Goyal et al., 2017] is no longer capable to hold all the parameters in a single device. Under this background, model parallelism [Harlap et al., 2018 , Huang et al., 2019 , Shoeybi et al., 2019 , Zheng et al., 2022] is proposed to partition parameters into a set of devices to address the memory constraint. Tensor parallelism (TP) [Shoeybi et al., 2019] is a commonly used model parallel strategy, which partitions weight parameters into several devices and performs matrix multiplication separately. A well-known shortcoming of TP is that, it requires a lot of communication volume, which makes it inefficient when bandwidth becomes the bottleneck Narayanan et al. [2021] . In such situations, pipeline parallelism [Harlap et al., 2018 , Huang et al., 2019] , which is another model parallel strategy, shows its advantage in low communication cost. The core idea of pipeline parallelism is to split the entire model into several stages, which can be processed by several devices in a streaming way. In a typical large-scale training scenarios such as Narayanan et al. [2021] , TP is generally used within one compute node, and PP is used to scale up across nodes.Although PP has been widely adopted and developed, it suffers from two prominent disadvantages: pipeline bubbles and large activation memory. To eliminate pipeline bubbles, one line of work focuses on asynchronous PP [Gaunt et al., 2017 , Yang et al., 2021] , which is theoretically bubble free. However, it sacrifices the exact optimization semantics and may result in lower convergence performance [Lian et al., 2018 , Tang et al., 2020] . A parallel line of works revolve around synchronous PP, focusing on reducing pipeline bubbles and/or activation memory. GPipe [Huang et al., 2019 ] is an early work to reduce the bubble rate by increasing the number of microbatches, at the cost of more activation memory. 1F1B [Fan et al., 2021] avoids the activation memory growth with respect to the number of microbatches by staggering forward pass and backward pass, keeping the same bubble rate with GPipe. Another notable work is GEMS [Jain et al., 2020] , which stores activation memory of only one forward pass by scheduling microbatches one after another among two model replicas, thus with a significantly large bubble rate. Chimera [Li and Hoefler, 2021] extends the ideas of GEMS by combining two pipelines in different directions together, which reduces pipeline bubbles when the number of microbatches is small, but with doubled parameter memory. Hanayo [Liu et al., 2023] is introduced to attain the same scheduling efficiency with Chimera without replicated models, but still suffering from scaling to more microbatches. Although its wave-like scheme is kind of similar to our V-shape building blocks, it is not motivated for memory balance, thus resulting in totally different pipeline schedules. In Megatron-LM [Narayanan et al., 2021] , an interleaved strategy is proposed to further reduce the bubble rate, at the cost of more communication cost and a portion of extra activation memory. BPipe [Kim et al., 2023] focuses on reducing the activation memory of 1F1B from another perspective, transferring activations across devices based on the memory imbalance of 1F1B. However, it introduces a lot of extra communication and increases the complexity of the system, which makes it inefficient especially in settings with limited bandwidth. Zero Bubble [Qi et al., 2023] splits the backward into activation gradient computation and weight gradient computation, which can either reduce the pipeline bubbles without changing the maximum peak activation memory, or achieve zero bubble at the cost of doubled activation memory compared to 1F1B.In this paper, we first demonstrate all existing pipelines can be seen as repeating a basic building block in time. We then identify a direct link between the activation memory and the lifespan of each building block, which reveals the core insight of this paper: lifespan decides the activation memory. Based on this insight, we present a family of novel and memory-efficient building blocks and their pipelines. Compared to 1F1B, we reduce the activation memory to 1/2 asymptotically with even higher throughput, and to 1/3 asymptotically with comparable throughput. We can also achieve zero bubble under the same activation memory with 1F1B. Notably, our strategy is almost a pure gain to the existing methods, only at the cost of doubled communication cost between pipeline stages, which is relatively small and can be neglected. 
how to build a pipeline: 
 We propose a four-step framework to design pipeline schedules.Building Block: It starts by laying out the passes for a single microbatch, which we call a building block. For example, the building block of 1F1B is made of a sequence of forward passes followed by backward passes in the reverse order. We highlight the building block of 1F1B in color in Figure 1a .Repeating: More microbatches are then introduced. The building blocks are repeated and woven together to form a pipeline. In Figure 1 (top), the repeating building blocks are shown in different shades of gray. Notably, legit building blocks are required to repeat without a collision, namely, the passes from two building blocks should not overlap with each other.Squeezing: Depending on the building block, there may be redundant bubbles in the pipeline, which can be simply removed by squeezing without changing the order of the passes. For example, Figure 1b shows a case where squeezing produces a more efficient pipeline.We can reorder the passes in the warm-up and cool-down phase to further improve the computation throughput. Intuitively, the peak of memory happens in the stable phase of the pipeline, while in the warm-up and cool-down phases the RAM is under utilized, leaving some space for improving the computation throughput without changing peak memory. We leave the details in Appendix C.Most of existing pipeline schedules can be explained under this framework. Besides the 1F1B and eager 1F1B shown in Figure 1 , we show the interleaved 1F1B [Shoeybi et al., 2019] , ZB-H1 [Qi et al., 2023] and a series of well-known pipelines in a more extensive gallery (see Appendix I).The computation and memory efficiency of various pipelines can be attributed to their building blocks. The diversity of the building blocks primarily comes from three factors, model partitioning, device placement, and offsets between passes. We follow the idea and notations in zero bubble PP [Qi et al., 2023] , using F to denote forward pass, B to denote "backward for the activations", and W to denote "backward for the weights". Note that such finer granularity can be generalized to previous methods like 1F1B, by always grouping B and W together.Model partitioning deals with how the model is divided into pipeline stages. The most common pattern is to equally divide the model to match the number of devices. A prominent example is the 1F1B schedule (Figure 1a ). This is extended in interleaved 1F1B where the number of stages can be an integer multiple of the number of devices.Device placement is another key factor in the design of building blocks. While conventionally each pipeline stage is sequentially placed on a different device, it is not uncommon to place multiple stages on the same device like in interleaved 1F1B (Figure 18h ). Another example of unconventional device placement is Chimera, where two pipelines are placed in reversed device order.Last but not least, the offsets between F,B,W passes play a major role in the computation and memory efficiencies of the pipeline. By simply enlarging the offsets between subsequent F passes in the building block of 1F1B, we obtain the eager 1F1B [Zhuang et al., 2023] (Figure 1b ) where more F passes are eagerly scheduled, resulting in higher memory consumption (but better communication overlapping). GPipe can be seen as adding a large offset between the last F and the first B in the 1F1B building block. One more example on the effect of the offset is the comparison of ZB-H1 (Figure 18c ) and ZB-H2 (Figure 18d ) schedules, one can see that properly chosen offsets result in zero bubble schedules like ZB-H2. In this work, we assume that every F, B or W pass takes equally one unit of computation time, and only consider integer unit of offsets. Although this may limit the number of feasible building blocks, it greatly improves the simplicity of analysis.Not every pipeline is born equal, researchers are constantly looking for pipelines that are more efficient in computation and/or memory. While efficient pipelines could be discovered by enumerating every possible building block, it is nonetheless prohibitively expensive. We discover that the peak memory consumption of a pipeline can be calculated from its building block via a simple formula. This enables us to design pipelines with a controllable peak memory.Two quantities are crucial for the calculation of peak memory, the lifespan of a stage, and the repeating interval of the building blocks, both of which are illustrated in Figure 1 . The lifespan of a stage is defined as the amount of time between the starting of the F pass and the ending of B or W pass. A piece of activation memory is allocated at the starting of F, and retained in the RAM throughout the lifespan until it is consumed by both B and W. The peak memory consumption can be calculated by finding the maximum number of microbatches whose lifespans overlap with that of every other microbatch. Using l to denote lifespan, T to denote the repeating interval and m the size of activation memory for a single microbatch, we have the relation.peak memory ≤ ⌈ l T ⌉mWhen there are multiple stages on one device, e.g. interleaved 1F1B, their contributions to the peak memory are independent, using S i to denote all the stages allocated to device i, we sum the contributions from every stage.peak memory of device i≤ s∈Si ⌈ l s T ⌉m s (1)Another key insight is that the repeating interval T is readily determined from the building block.In an efficient pipeline, T should be equal to the number of units of computation in each stage of the building block. Any T larger than that would cause pipeline bubbles in the stable phase, and T smaller than that would lead to collisions. A subtle exception is the interleaved 1F1B whose repeating interval is not uniform. We leave the discussion to Appendix G.One constraint to keep in mind when designing the building blocks is that a legit building block is required to repeat without any collision. It may seem unintuitive how to design building blocks with this constraint. In practice, we design the building block first and perform a post-hoc verification.Another useful observation is that a legit building block usually produces a stable phase in the middle of the pipeline, which contains a repeating d × T rectangle, where d is the number of devices and T is the repeating interval. This offers an alternative to constrain the building blocks. We can start by ordering passes within this rectangle and convert it back to a building block.Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes] Justification: The major limitation of our work is that the performance V-Min method degrades when F B and W times are different. We discussed the limitation in Section 3.2 and also reflected them in the evaluation Section 4 Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 3. Theory Assumptions and Proofs some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. 
memory efficient building blocks: 
 With the above framework, we can conveniently analyze the memory consumption pattern of existing pipelines. To our knowledge, all existing pipelines are memory inefficient due to two primary reasons: redundant dependency chain, and imbalanced memory usage. Before Zero Bubble [Qi et al., 2023] , the backward is often regarded as a single pass, resulting in unnecessarily longer lifespan thus more memory footprint. In this paper, we leverage the backward splitting strategy to remove these redundant lifespan. The imbalanced memory comes from the innate heterogeneity of the lifespans across stages. From Figure 1a , we can easily see that the lifespan of the stages differs greatly from each other, with the first stage having the longest lifespan. Consequently, it causes a memory bottleneck on the first device and under utilization of memory on all other devices. To resolve this problem, we introduce a family of novel building blocks, which we refer to as V-Shape building blocks. The core insight comes from Equation 1 which says that the peak memory depends on the sum of the lifespans. Therefore, when we place multiple stages on the same device, we should always collocate stages of long lifespans with those of short lifespans. When the total sum of lifespans is fixed, balanced placement always means higher memory efficiency. This can be demonstrated by Figure 2 , the parallel schedule (used in interleaved 1F1B) is imbalanced and has a memory bottleneck proportional to l 1 + l 4 , while in the V-Shape schedule it is l 1 + l 6 .The V-Shape schedule requests the model to be partitioned into stages twice the number of devices and the device placement of the second half of stages to be in reverse order as the first half. As the offsets directly determine the lifespan of each stage and therefore the peak memory by Equation 1, we can then further control the offsets between passes to generate building blocks with diverse memory.Figure 2 : The V-Shape building block ensures balanced peak memory across all devices, whereas the parallel building block has a memory bottleneck in the first device.We assume the model is uniformly partitioned, namely, both the computation and memory of each stage are identical. For a single microbatch, we denote the activation memory of each stage as m, and (a) 1F1BF B F B F B F B 2d 4d (a) 1F1B F F B W B W F F B W B F F B W B W F F B B W W 2d-1 d 2d-1 d (b) V-Half F F B W B W F F B W B W F F B W B W F F B B W W d d d d (c) V-Min F F B W B W F F B W B W F F B W B W F F B B W W 4d-3 2d-1 4d-3 2d-1 (d) V-ZB Figure 3: V-1 2 3 1 1 1 2 2 1 2 1 4 3 3 2 3 2 5 4 4 3 4 3 6 5 5 4 5 4 7 6 6 5 6 5 8 7 7 6 7 6 8 8 7 8 7 8 81 2 1 2 1 1 3 1 2 1 2 3 4 2 3 2 3 4 5 3 4 3 4 5 6 4 5 4 5 6 7 5 6 5 6 7 8 6 7 6 7 8 7 8 7 8 8 81 2 1 2 1 1 1 3 1 2 3 2 2 4 2 3 4 3 3 5 3 4 5 4 4 6 4 5 6 5 5 7 5 6 7 6 6 8 6 7 8 7 7 7 8 8 8 81 1 2 2 1 1 1 1 3 3 2 2 2 2 4 4 3 3 3 3 5 5 4 4 4 4 6 6 5 5 5 5 7 7 6 6 6 6 8 8 7 7 7 7 8 8 8 8(b) V-Min 1 2 3 4 5 1 1 1 2 2 2 3 1 1 3 3 4 6 2 2 4 4 5 7 3 3 5 5 6 8 4 4 6 6 7 7 5 7 5 8 8 8 6 6 7 7 8 81 2 3 4 1 2 1 1 3 2 1 2 5 1 4 3 2 3 6 2 5 4 3 4 7 3 6 5 4 5 8 4 7 6 5 6 5 7 8 7 6 8 6 7 8 7 8 81 2 3 1 2 3 1 1 4 1 1 2 2 4 5 2 2 3 3 5 6 3 3 4 4 6 7 4 4 5 5 7 8 5 5 6 6 8 7 6 7 7 8 6 7 8 8 8 1 1 2 2 3 3 1 1 1 4 1 4 2 2 2 5 2 5 3 3 3 6 3 6 4 4 4 7 4 7 5 5 5 8 5 8 6 6 7 7 6 6 8 8 7 7 8 8(c) V-Half 1 2 3 4 5 6 7 1 1 1 2 2 2 3 3 3 4 4 1 4 1 8 5 5 2 5 2 6 6 3 6 3 7 7 4 7 4 8 8 5 8 6 5 7 6 8 7 8 1 2 3 4 5 1 6 2 1 1 3 2 2 4 3 1 3 1 7 5 4 2 4 2 8 6 5 3 5 3 7 6 4 6 4 8 7 5 8 6 7 7 5 8 8 6 7 81 2 3 1 4 2 5 3 1 1 4 2 1 2 1 6 5 3 2 3 2 7 6 4 3 4 3 8 7 5 4 5 4 8 6 5 7 6 8 7 6 8 5 7 6 8 7 8 1 1 2 2 3 3 4 4 1 1 1 1 5 5 2 2 2 2 6 6 3 3 3 3 7 7 4 4 4 4 8 8 5 5 6 6 7 7 8 8 5 5 6 6 7 7 8 8 The stable phases adhere to the pattern of their building blocks.(d) V-ZBthe total activation memory of the entire model as M . Note that M = 2dm, where d is the number of devices. To make it simple and tractable, we use uniform offsets within each half of F and B passes to control the peak memory. Specifically, we apply the same offset δ 0 F between two adjacent F passes within the first d stages (e.g., δ 0 F = 2 in Figure 3b , δ 0 F = 1 in Figure 3c and δ 0 F = 4 in Figure 3d ). Similar constraints are applied to the other half of the F passes and both halves of the B passes, denoted as δ 1 F , δ 0 B , δ 1 B , respectively. To guarantee balanced peak memory across devices, we add another two constraints, δ 0 F = δ 1 B = δ 0 and δ 1 F = δ 0 B = δ 1 , where we use notations δ 0 and δ 1 for simplicity. For example, in Figure 3d , we set δ 0 = 4 and δ 1 = 2. Note that we only control the offsets across different devices. For those adjacent passes within the same device (e.g., F and B of the last stage, two F and two B in the last device), we use brute force to find optimal solutions, ensuring their offsets are small (less than the repeating interval). Note that W can always be placed greedily after settling all F and B passes, so we don't need to search their offsets during brute force.According to Equation 1, we can analyze the asymptotic peak memory with respect to d,peak memory of device i ≤ 2d(δ 0 + δ 1 ) + O(1) 6 m ≈ δ 0 + δ 1 6 M (2)By ignoring the small constant, we can directly control the peak memory by the value of δ 0 and δ 1 .Table 1 : Small constant values are ignored for bubbles and peak memory of V-Min and V-Half . For 1F1B, δ 0 /δ 1 are redefined as the offsets between adjacent forward/backward passes. M represents the total activation memory of the entire model, and d is the number of devices.Building Blockδ 0 δ 1 Peak Memory Bubbles 1F1B 2 4 M ≈ 6d V-Min 1 1 ≈ M/3 ≈ 4d V-Half 2 1 ≈ M/2 ≈ 3d V-ZB 4 2 M 0 3.2 V-Shape Pipeline SchedulesBy varying the values of δ 0 and δ 1 , we come up with 3 novel V-Shape building blocks (Figure 3 ), and present their final schedules based on our framework in Figure 4 . The building block of V-Min (Figure 3c ) has the minimum offsets, namely δ 0 = δ 1 = 1, thus the minimum memory consumption. With δ 0 = 4 and δ 1 = 2 as in Figure 3d , V-ZB eliminates the bubble to almost 0 (Figure 4d ), pushing to extreme throughput. The building block of V-Half (Figure 3b ), which uses δ 0 = 2 and δ 1 = 1, sits between the two extremes and consumes about half of the activation memory required by 1F1B.Although both V-Min and V-Half have lower memory footprint than 1F1B, V-Min contains about 2/3 and V-Half contains about 1/2 of 1F1B's bubbles, assuming F, B, W have equal run time. We show the comparison between our proposed V-Shape schedules and 1F1B in Table 1 . Notably, the exact peak memory is ⌈ d+2 3 ⌉ M d for V-Min, and ⌈ d+1 2 ⌉ M d for V-Half . To avoid collisions in the building blocks of V-Min and V-Half , the offsets (within the same device) are slightly different for different values of d. The details are in Appendix F.In real-world scenarios where F, B and W have different run times, V-Min suffers from a repeating bubble. As shown in Figure 5 , there exists bubbles for every repeating interval T . Consequently, the bubble grows as the number of microbatches increases. Although V-Half may encounter the same issue (when the times of F, B and W differ significantly), it generates patterns that tessellate well in most empirical cases due to its loose dependencies. As illustrated in Figure 5b , the throughput of V-Half is robust to the variation of run times. Additionally, the bubbles of V-ZB will never grow when increasing the number of microbatches. We leave the related discussions in Appendix E. 1 4 3 3 2 3 2 5 4 4 3 4 3 6 5 5 4 5 4   1 2  1  2 1 1 3  1 2 1 2 3 4 2 3 2 3 4 5 3 4 3 4 5 6 4 5 4 5 ... 1 2 3 2 2 4 2 3 4 3 3 5 3 4 5 4 4 6 4 5 6   1 1 2 2  1 1 1 1 3 3 2 2 2 2 4 4 3 3 3 3 5 5 4 4 4 4 6 6 5   2 3 2 5 4 4   3 2 3 4 5 3 F=3,B=4,W=2 1 2 3 4 5  1 1 1 2 2 2 3  1 1 3 3 4 6 2 2 4 4 5 7 3 3 5 5 6 8 4 4 6   1 2 3 4  1  2 1 1 3 2  1 2 5 1 4 3 2 3 6 2 5 4 3 4 7 3 6 5 4 5 8 4 ... 1 2 3 1  2  3 1 1 4 1 1 2 2 4 5 2 2 3 3 5 6 3 3 4 4 6 7 4 4 5 5 7   1 1 2 2 3 3  1 1 1 4 1 4 2 2 2 5 2 5 3 3 3 6 3 6 4 4 4 7 4 7 5   4 4 5 7 3 1 2 3 1 1 1 2 2 1 21 2 1 2 1 1 1 3Besides V-Shape building blocks, we also propose some other interesting building blocks in Appendix H, to show the generalization ability of our framework. Some useful examples include a) 1F1B-V achieving 2/3 of 1F1B's activation memory without doing B-W split; b) a schedule consumes less memory than interleaved 1F1B but with the same bubble rate (Figure 17c ). Additionally, we design an adaptive scheduler to control the memory at a finer granularity in Appendix A. 
experiments: 
 We construct our experiments to show three conclusions: a) The throughput and memory of V-Min, V-Half and V-ZB aligns with the theoretical analysis in Section 3.2; b) Memory-saving methods including V-Min and V-Half can bring accelerations; c) Our methods still perform best when combining with other state-of-the-art techniques.We evaluate our methods using a series of models detailed in Table 2 analogous to GPT-3 [Brown et al., 2020] . Our implementation is based on the open-source Megatron-LM project [Narayanan et al., 2021] and is experimented on up to 40 NVIDIA A100 SXM 80G GPUs distributed across 5 nodes interconnected by a RoCE RDMA network. The running time of each iteration is recorded after several warm-up iterations. Similar to the settings in [Qi et al., 2023] , we deduct one transformer layer from both the initial and final pipeline stage to compensate for the embedding and output layer in LM, which can otherwise become the bottleneck of the pipeline and interfere to the efficiency. Our experiments majorly focuses on the following pipeline parallel schedules: a) V-Min, V-Half and V-ZB: schedules introduced in Section 3.2; b) 1F1B and Interleaved 1F1B: methods implemented in Megatron-LM; c) 1F1B-R: 1F1B with full activation rematerialization [Chen et al., 2016] ; d) ZB-1P and ZB-2P: the adaptive zero-bubble methods introduced in [Qi et al., 2023] with activation memory limit set to the 1x/2x times of 1F1B. V-ZB ZB-1P V-Half 1F1B V-Min 1F1B-RIn Figure 6 , we present comparisons of the throughput measured in FLOPS utilization (MFU) and activation memory consumption across different pipeline schedules under various settings. From the results, V-ZB outperforms all other methods in terms of throughput, which aligns with Figure 4 . When comparing the activation memory consumption, V-Min and V-Half stand out by significantly reducing activation memory to approximately 1/3 and 1/2, while other methods' memory is similar except for 1F1B-R. More details of our experiments and definition of metrics can be found in Appendix D.1. Notably V-Min has a comparable throughput against 1F1B, but its throughput falls behind 1F1B at a larger number of microbatches due to the aforementioned repeating bubble in Figure 5a , as discussed in Section 3.3. However, it still outperforms 1F1B with full activation rematerialization, providing a strong alternative for saving memory. We also plot both memory and MFU for the various methods in Figure 7 in a typical, but slightly different setting in which we reduced the microbatch size of 9.6B and 21B model to allow ZB-2P and Interleaved 1F1B to run which would otherwise run out of memory (OOM). It shows that the V-Shape pipeline schedules lie at the Pareto frontier.While V-ZB provides optimal throughput, V-Half and V-Min methods are mainly used when memory budget is tight. Conventionally, rematerialization is used when it runs out of memory (OOM). However, rematerialization leads to repeated computation and consequently decrease the throughput.V-Half and V-Min significantly outperforms rematerialization (1F1B-R) as we show in Table 7 . Another benefit of saving memory is that we can potentially use the extra memory for an increased microbatch size, which leads to a higher arithmetic intensity. We present the results in Figure 8 . On bigger models, where memory pressure is higher and hence microbatch size is smaller, V-Half schedule can surpass V-ZB and other baselines because of its arithmetic intensity gain. This observation does not apply for V-Min, implying its arithmetic intensity gain can not compensate for the increased bubble. Doubling/Tripling the microbatch size for V-Half /V-Min results in a slightly higher activation memory than the other methods. This reflects the constant factors we ignored in Section 3.2. The increase is less significant as the number of devices grows.We present our methods in the context of LLM training together with various other techniques. The following techniques are considered: a) Flash Attention [Dao et al., 2022 , Dao, 2023] ; b) Tensor Parallelism [Narayanan et al., 2021] and Sequence Parallelism [Korthikanti et al., 2023] ; c) Distributed Optimizer provided in Megatron-LM. The implementations are all from Megatron-LM [Narayanan et al., 2021] . Both our methods and the baseline methods are combined with the above techniques. Similar to the evaluation method in Kim et al. [2023] , we perform a grid search on the following parameters: the size of PP; the size of TP; the size of DP; the microbatch size (mbs). We use 40 GPUs in this experiment. For each method, the best result from the grid search is reported.We present the best result for each pipeline parallel schedule in Table 3 and the corresponding parameters. We find that when sequence length is smaller and hence the memory budget is more abundant, V-ZB performs the best due to the elimination of bubbles. When we increase the memory pressure by increasing the sequence length, V-Half performs the best because of its memory efficiency. The detailed data and analysis of grid search can be found in the Appendix D.3 D.4.  
conclusion and future work: 
 In this work, we present a framework that constructs pipeline schedules by focusing on their repeating building blocks. This framework enables direct computation of peak memory from the lifespan of the building block. Based on this capability, we design a family of memory-efficient building blocks. We discuss three representative methods from this family, namely V-Min, V-Half and V-ZB, and demonstrate with experiments that our methods advance the Pareto frontier of throughput and memory in large model training. Furthermore, our methodology of designing pipeline schedules through building blocks may inspire the research community to explore more novel pipeline schedules. Notice that repeating a building block is not the only way of building a pipeline, other methods like greedy search could generate a pipeline that has no repeating patterns.In the future, we plan to further explore more memory efficient pipeline schedules based on our framework. A major limitation of V-Min is that, it suffers from growing bubbles when increasing the number of microbatches. Although V-Half mitigates this issue, there is still a space to further reduce the memory consumption. Using continuous offsets or finer-granularity discretization is a possible way to solve it. We leave it in our future work.Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material? Answer: [Yes] Justification: We'll opensource the implementation code on camera-ready version.Guidelines:• The answer NA means that paper does not include experiments requiring code. Justification: As mentioned in Section 4, we need at most 40 GPUs to run our experiments.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Answer: [Yes] Justification: We conforms to the NeurIPS code of ethics.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [NA] Justification: Our methods are focusing on the training systems only, not on the algorithms. They should not have any societal impacts.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: Our methods has no risk of being misused.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [Yes] Justification: Our implementation is based on Megatron-LM which has a lisence that allow other works to freely work on them.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.• If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 13. New Assets Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets? Answer: [Yes] Justification: We'll opensource our code with documentation on usage on camera-ready version.Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix: Now we consider more general scenarios, where we want to minimize the bubbles given an activation memory limit. A straightforward approach should be simply searching over all possible offsets and picking the one with minimal bubbles. However, this naive method cannot work well due to there are exponentially many possible offsets, which makes it intractable to iterate thoroughly. In this section, we propose a more practical searching method to solve this general problem.We use superscript c ∈ {0, 1} to denote which stage in a device, and use subscript i ∈ {1, 2, ..., d} to denote the index of the device. For example, F c i represent the forward pass of stage cd + i in the i-th device. We define the offset from u to v as δ(u, v) = t(v) -t(u), where t(v) represent the cell index along time horizon of pass v. To simplify the notations, we defineδF 0 i = δ(F 0 i , F 0 i+1 ), δF 1 i = δ(F 1 i , F 1 i-1 ), δB 1 i = δ(B 1 i , B 1 i+1 ) and δB 0 i = δ(B 0 i , B 0 i-1), to denote the offset from a pass to its next pass.Instead of all possible offsets, we limit our search space to uniform offsets across devices. We also try to ensure each device has a balanced peak memory. Note that for the uniform offsets introduced in Section 3.1, the peak memory only falls into a small discrete set ({ k 6 M }, where k is an integer). To make it work for a finer granularity of memory controlling, we split the repeating module into two parts, containing the first K rows and the last d -K rows respectively. More formally, we use the constraint as follows.EQUATIONNote that the above constraints have good properties that the peak memory is balanced across devices. As we can always greedily fill W 0 i and W 1 i when repeating, we only need to search over the permutation of the first device, the values of δ 0 <K , δ 1 ≤K , δ 0 ≥K , δ 1 >K and K. The computational complexity is O(d) if we regard repeating interval as a constant.For each building block searched, we repeat the building block, check collision, do squeezing and reordering as mentioned in 2.1. After searching over all possible building blocks, we pick the schedule with minimal bubbles. Note that we can use the true run times of F, B and W to calculate the bubbles, which will lead to more efficient schedule in real cases.In Figure 9 we plot the bubble rate of adaptive V-Shape schedulers introduced in A under various settings and different memory limit. The run times of F, B and W are from profiled real cases, as in Table 5 . We observe that the bubble rate drops as memory limit increases. Notably, there's a sudden drop in bubble rate when the memory limit just goes above approximately 1/2 of 1F1B, at which point the repeating bubble mentioned in Figure 5a We also compare V scheduler with the adaptive zero bubble scheduler proposed in [Qi et al., 2023] in Figure 10 . We find that V scheduler has a boarder range of memory configurations and a smaller bubble rate compared to zero bubble scheduler. We also draw the bubble rate of 1F1B as a reference, though 1F1B does not support a configurable memory. In our framework, we may need to reorder the warm-up and cool-down phase after squeezing. Basically, we employ simple greedy approaches to handle the reordering for warm-up and cool-down, and illustrate how zero bubble schedule is reordered in Figure 11 .1 2 3 4 1 1 1 5 2 2 2 6 3 3 3 7 4 4 1 4 1 8 5 5 2 5 2 6 6 3 6 3 7 7 4 7 4 8 8 5 8 5 6 6 7 7 8 81 2 3 1 4 2 1 1 5 3 2 2 6 4 3 1 3 1 7 5 4 2 4 2 8 6 5 3 5 3 7 6 4 6 4 8 7 5 7 5 8 6 8 6 7 7 8 81 2 1 3 2 4 3 1 1 5 4 2 1 2 1 6 5 3 2 3 2 7 6 4 3 4 3 8 7 5 4 5 4 8 6 5 6 5 7 6 7 6 8 7 8 7 8 81 1 2 2 3 3 4 4 1 1 1 1 5 5 2 2 2 2 6 6 3 3 3 3 7 7 4 4 4 4 8 8 5 5 5 5 6 6 6 6 7 7 7 7 8 8 8 8Reordering 1 2 3 4 5 6 7 1 1 1 2 2 2 3 3 3 4 4 1 4 1 8 5 5 2 5 2 6 6 3 6 3 7 7 4 7 4 8 8 5 8 6 5 7 6 8 7 8 1 2 3 4 5 1 6 2 1 1 3 2 2 4 3 1 3 1 7 5 4 2 4 2 8 6 5 3 5 3 7 6 4 6 4 8 7 5 8 6 7 7 5 8 8 6 7 81 2 3 1 4 2 5 3 1 1 4 2 1 2 1 6 5 3 2 3 2 7 6 4 3 4 3 8 7 5 4 5 4 8 6 5 7 6 8 7 6 8 5 7 6 8 7 8 1 1 2 2 3 3 4 4 1 1 1 1 5 5 2 2 2 2 6 6 3 3 3 3 7 7 4 4 4 4 8 8 5 5 6 6 7 7 8 8 5 5 6 6 7 7 8 8 Warm-up In warm-up phase, bubbles mainly happen before the first B. We iterate all the cells from left to right. If a vacant cell (which means a bubble) is encountered, we try to find a computation pass to fill this bubble. We iterate all the following computation passes in the same device, and check whether it is possible to move if we keep all other passes unchanged. If the check succeeds, we move it to the vacant cell, and the bubble is filled.Cool-down In cool-down phase, W can be scheduled at any time after its corresponding B. So we utilize a heuristic way to handle the bubbles. Firstly, we delete all the W passes in cool-down phase. Next, we squeeze the schedule to remove the bubbles caused by deleting W. After that, we use W to fill the remaining bubbles, ensuring each W is after its corresponding B. Finally, we schedule all the remaining W passes at the end.Despite its simplicity, the above heuristics is general and effective. However, it may not achieve the best performance in some cases. We also design other greedy or constructive methods as a complement for some building blocks. We will release all the related code in our repository. For Section 4.2, we present our detailed experiment data in Table 4 . Specifically, the metrics are defined as:• MFU: The FLOPS utilization of the training system. The calculation of FLOPS of a model is following [Narayanan et al., 2021] . • Peak Memory: The maximum peak memory cross all devices.• Activation Memory: Estimated as deducting the iteration-start memory from peak memory on each device. The number presented is the maximum activation memory cross all devices.• Bubble Rate: The theoretical bubble rate reported by scheduler, using profiled run times of F, B and W at starting iterations.To evaluate how increasing microbatch size increases the arithmetic intensity, we profile the run time of each single F/B/W pass and calculate their single-pass MFU. We list the results in Table 5 . It shows that whether there are significant MFU gain depends on both the model and the microbatch size. For the first experiment group, the best setup is V-ZB under pure PP because of its bubble elimination.For the second setup, the best setup is V-Half because its memory efficiency enables a lower TP The throughput of PP also decreases as PP degree increases for two major reasons: a) for PP schedules with a fixed global batch size, a higher PP degree usually results in higher pipeline bubbles. For example, 1F1B has a bubble rate of p-1 p+n-1 , which would increase if p grows and n keeps unchanged; b) the first and last pipeline stage for a language model usually have an embedding or output layer which has innegligible additional computations, making the pipeline unbalanced and hurting the efficiency. With higher PP degree, the unbalance would be aggravated. However, theses two issues can be mitigated. For the first issue, a larger number of microbatches or using V-ZB can significantly reduce the pipeline bubble. For the second issue, we can use another standalone stage to handle the embedding or output layer instead to avoid bottleneck. In our experiments, we simply deduct 1 layer from both the first and last pipeline stage to mitigate this problem. As a result, our methods essentially push the preference from TP to PP.Although we mainly focus on the memory efficiency in this paper, we also need to take care of the bubbles in pipeline parallelism. Typically, there is a trade-off between memory and bubble, where allowing more memory usage can reduce the bubble of a pipeline schedule. In this section, we will discuss how to identify whether the bubble of a schedule will grow with respect to the number of microbatches. Additionally, we illustrate an empirical lower bound of bubble in our methods. We follow the notation in Section 3.1 and Appendix A in this section.In pipeline parallelism, we usually expect there is no repeating bubbles introduced in Section 3.3, namely, the bubble is only related to the number of pipeline devices (d), and won't grow when increasing the number of microbatches (n). This property guarantees a good scalability with respect to n. We say a pipeline schedule is with O(d) bubble if it satisfies this property, otherwise with O(n) bubble. Note that the conclusion is based on the values of T F , T B and T W , which are the run times of F, B and W respectively. For example, the schedule of V-Min (Figure 4b ) is with O(d) bubble when T F = T B = T W , but is with O(n) bubble when T W is significantly smaller than T F and T B .If there are no repeating bubbles in a schedule for any values of T F , T B , T W , the minimal memory is 2dm. In a pipeline schedule, there are two types of dependencies, streaming dependency within the same device and computational dependency across devices. We define a dependency path as a sequence of passes τ = (v 1 , v 2 , ..., v |τ | ) where for any 1 < i ≤ |τ |, v i is dependent on v i-1 (either streaming dependency or computational dependency). We define the time cost of a dependency path as T τ = 1≤i≤|τ | T vi where T vi is the time cost of v i . Then the runtime of the whole pipeline should be T = max τ T τ .Obviously, there is a trivial dependency path τ 1 that all the passes are from the same device, and T τ1 = 2n(T F + T B + T W ). Note that it is the lower bound of runtime, and any extra runtime would be considered as bubbles.Let's consider another dependency path τ 2 containing only forward passes. To be simple, we denote Fj as the forward sequence for the j-th microbatch. Then τ 2 = concatenate( F0 , Fk , ..., F⌊ n-1 k ⌋k ) thus T τ2 = 2d⌊ n+k-1 k ⌋T F , where 6k > δ(F 0 1 , F 1 1 ) > 6(k -1) (greedily include as many forward passes as possible). Note that if we want to guarantee O(d) bubble for any values of T F , T B , T W , we should choose k ≥ d to make2d⌊ n+k-1 k ⌋ ≤ 2n, otherwise 2d⌊ n+k-1 k ⌋T F -2n(T F + T B + T W ) ∈ O(n) if we set T B = T W = 0.Then we can get δ(F 0 1 , F 1 1 ) > 6d -6. Then we consider a similar dependency path τ 3 containing only backward passes, and we can get δ(B 1 1 , B 0 1 ) > 6d -6. According to Equation 1, we can get the peak memory in the first device is at least (⌈δ(F 0 1 ,F 1 1 ) 6 ⌉ + ⌈ δ(B 1 1 ,B 0 1 ) 6 ⌉)m ≥ 2dm.For most real cases, V-Half is enough to guarantee there are no repeating bubbles. Although the above proof shows that 2dm memory is required to guarantee O(d) bubble for any values of T F , T B , T W , we don't need that much memory in practice because the values of T F , T B and T W are well constrained. As in Qi et al. [2023] , F, B and W have similar total FLOPS, and T F , T B , T W don't differ too much in real cases. Based on this insight, we can check the conditions where our methods are with O(d) bubble.Because both warm-up phase and cool-down phase have O(d) passes, we only need to consider the stable phase to identify whether a schedule is with O(d) bubble or with O(n) bubble. Obviously, streaming dependency won't block the device from executing the next pass. So bubble is caused only by the computational dependency. Formally, a schedule is with O(n) bubble if and only if there exist two passes u and v (within the same device) and there are two dependency paths τ and τ ′ between them, where τ only contains streaming dependencies, τ ′ contains at least two computational dependencies, and T τ < T τ ′ . Based on our V-shape building blocks, we only need to check u and v with a small distance (< 6) and τ ′ within two adjacent devices. In this way, we can conclude that the schedule in Figure 4c is with O(d) bubble whenT W + 2T B ≥ 2T F & T W + 2T F ≥ 2T B ,which is satisfied in most real cases.Device 1 1 1 1 8 8 8 8Device 2 1 1 1 8 8 8Device 3 1 1 1 8 8 8Device 4 1 1 1 1 1 1 5 5 2 2 2 2 6 6 3 3 3 3 7 7 4 4 4 4 8 8 8 8 Time →Figure 13 : A dependency path of pipeline schedule.The runtime of a schedule can be bounded by any dependency path. In Figure 13 , we present a dependency path which is a non-trivial lower bound for most schedules after squeezing and reordering.Assuming the actual peak memory is km (k ≤ 2d) and T F = T B = T W = 1, then the runtime of this dependency path is at least 6n + 6d -3k -1. Empirically, we find that we can always get close to this lower bound in our adaptive scheduler.To avoid collisions when repeating building blocks, we need a slightly different offsets for different number of devices d. We list the details in Table 9 and 10 while continue using the notation defined in A. We do not list the offsets related to W passes because they always fill in the empty grids left by F and B. Some samples can also be found at Figure 14 . Table 9 : Offsets for V-MinF F B W B W F F B W B W F F B W B W F F B W B W F F B W B W F F B W B W V-Min F F B W B W F F B W B W F F B B W W F F B B W W F F B B W W F F B B W W d mod 3 = 0 d mod 3 = 1 d mod 3 = 2 F F B W B W F F B W B W F F B W B W V-Half F F B W B W F F B W B W F F B W B W F F B W B W F F B B W W F F B B W W d mod 2 = 0 d mod 2 = 11 ≤ i < d, 1 < j ≤ d δF 0 i δF 1 j δB 0 i δB 1 j δ(F 0 d , F 1 d ) δ(F 1 1 , B 1 1 ) δ(B 0 d , B 1 d ) d ≡ 0 mod 3 1 1 1 1 1 3 1 d ̸ ≡ 0 mod 3 1 1 1 1 1 1 1 Table 10: Offsets for V-Half 1 ≤ i < d, 1 < j ≤ d δF 0 i δF 1 j δB 0 i δB 1 j δ(F 0 d , F 1 d ) δ(F 1 1 , B 1 1 ) δ(B 0 d , B 1 d ) d ≡ 0 mod 2 2 1 2 1 2 4 1 d ≡ 1 mod 2 2 1 2 1 2 1 1G Non-uniform Repeating Interval of Interleaved 1F1BWhile most existing schedules (Figure 18 ) are repeated with uniform interval, interleaved 1F1B [Narayanan et al., 2021] is slightly different in the repeating pattern. The official interleaved 1F1B has a repeating pattern as shown in Figure 15a . If we also employ uniform repeating interval as in Figure 15b , we can obtain another schedule with the same memory footprint and bubble rate as the official interleaved 1F1B, shown in the gallery (Figure 18i ). (a) The non-uniform repeating interval of interleaved 1F1B. The number in highlighted grids shows the microbatch with that index starts at this cell. Under the guidance of lifespan defined in Section 2.2, we also find some other building blocks besides the V-Shape building block family. We show the building blocks in Figure 16 and their full schedulesF F B B F F B B F F B B F F B B F F B B (a) 1F1B-V F F B W B W F F B B W W F F B B W W F F B W B W F B F B W W (b) Zero bubble schedule with 2/3 1F1B memory F F B B F F B B F F B B F F B B F F B B(c) A variation of interleaved 1F1B with the same bubble rate but lower memory Figure 16 : Other memory-efficient building blocks. (a) 1F1B-V 1 2 3 4 1 1 2 5 2 6 3 3 4 7 4 8 5 5 6 6 7 7 8 8 1 2 3 1 4 2 1 2 5 3 6 4 3 4 7 5 8 6 5 6 7 7 8 8 1 2 1 3 2 4 1 2 3 5 4 6 3 4 5 7 6 8 5 6 7 7 8 81 2 1 1 2 3 2 4 3 3 4 5 4 6 5 5 6 7 6 8 7 7 8 8 1 1 2 2 1 2 3 3 4 4 3 4 5 5 6 6 5 6 7 7 8 8 7 8(b) Zero bubble schedule with 2/3 1F1B memory 1 2 3 4 5 1 2 3 4 5 1 6 2 7 3 6 4 8 1 7 2 8 5 3 6 7 8 4 5 6 7 81 2 3 4 5 1 2 3 4 1 5 2 6 3 7 4 6 1 8 2 7 5 8 3 6 7 8 4 5 6 7 81 2 3 4 5 1 2 3 1 4 2 5 3 6 4 7 1 6 2 8 5 7 3 8 6 7 8 4 5 6 7 81 2 3 4 5 1 2 1 3 2 4 3 5 4 6 1 7 2 6 5 8 3 7 6 8 7 8 4 5 6 7 81 2 3 4 5 1 1 2 2 3 3 4 4 5 1 6 2 7 5 6 3 8 6 7 7 8 8 4 5 6 7 8(c) A variation of interleaved 1F1B with the same bubble rate but lower memory in Figure 17 . All these schedules have lower bubble rate than 1F1B. Specifically, 1F1B-V applies V-Shape to the building block of 1F1B but without B-W split, which can reduce the peak memory to asymptotically 2/3 of 1F1B. We also find that utilizing B-W split, the zero bubble pipeline schedules proposed in [Qi et al., 2023] with configurable memory limit can support a minimum of 2/3 activation memory of 1F1B, using the building block shown in Figure 16b . Note that two microbatches are included in a single building block to avoid collision. Using the building block defined in Figure 16c , we can make a schedule with the same bubble rate as interleaved 1F1B but lower memory, shown in Figure 17c .We show the building blocks and full schedules of some well-known existing methods in Figure 18 . (f) GEMSF F B B F F B B F F B B F F B B 1 3 2 2 4 4 1 3 1 2 3 4 2 1 4 3 2 1 4 3 1 2 3 4 2 4 1 1 3 3 2 4 (g) Chimera F F B B F F B B F F B B1 2 3 1 2 3 4 5 1 6 2 4 3 5 1 6 2 3 4 5 6 4 5 61 2 3 1 2 3 1 4 2 5 3 6 1 4 2 5 3 6 4 5 6 4 5 61 2 3 1 1 2 2 3 3 4 1 5 2 6 3 4 4 5 5 6 6 4 5 6(h) Interleaved 1F1B F F B B F F B B F F B B1 2 3 1 2 4 3 5 1 4 2 6 1 5 3 2 6 4 3 5 6 4 5 6 1 2 3 1 2 4 1 3 2 5 1 4 3 6 2 5 4 3 6 5 6 4 5 61 2 3 1 1 2 2 4 1 3 3 5 2 4 4 6 3 5 5 6 6 4 5 6(i) Interleaved 1F1B with uniform interval (with reordering)Figure 18 : A gallery of pipeline schedules and their building blocks. The upper row of each schedule shows the building block and how it repeats. The lower row shows the final schedule after squeezing.1. Claims Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? Answer: [Yes] Justification: Our paper focus on the memory efficiency of pipeline parallelism. Our major contribution contains a framework to design pipeline schedules, which can control the activation memory by adjusting the lifespan, and a family of memory-efficient schedules. These are highlighted in the abstract and introduction. Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 


Decision: All reviewers have given favorable ratings for this paper, ranging from 5 to 7.
Average Rating: 6.33 (Min: 5, Max: 7)
The following strengths of the paper have been highlighted. However, as there are few strong recommendations for this paper, an acceptance as a poster presentation is considered appropriate.

1: This paper proposes a novel framework that decomposes pipeline parallelism schedules into memory-efficient building blocks. This approach addresses inefficiencies in existing schedules, designing new schedules that reduce memory usage while improving throughput.

2: The proposed method demonstrates a 7% to 55% improvement in throughput in pure pipeline parallelism settings compared to 1F1B. Additionally, it achieves a 16% throughput improvement over the 1F1B baseline for large language models.

3: The paper presents a systematic methodology focused on balancing memory usage and reducing pipeline bubbles. The evaluations confirm the effectiveness of the proposed method through both theoretical and experimental validation.

4: The paper introduces new V-Shape building blocks, such as V-Min, V-Half, and V-ZB, which reduce memory usage by more than half compared to traditional methods while maintaining comparable throughput.

Reviews: review: paper_summary: paper_summary: Authors propose a way to identify the repeated building block a pipeline schedule is built from. By relating the peak activation memory of the schedule to the lifespan of the building block the authors show that existing schedules do not optimally use memory, and design higher-throughput schedules that use the same activation memory as the baseline. The methods demonstrate up to 55% improvement in throughput for pure pipeline parallelism settings and 16% improvement for large language models over the 1F1B baseline. The paper also provides a systematic methodology for designing pipeline schedules, emphasizing memory usage balance and reduced pipeline bubbles.
strength_weakness: strength_weakness: The paper suffers from quite a few clarity issues and could use some copyediting (there are lots of small grammatical errors, etc.). Main clarity issues in the paper are, for example, a lack of useful captions in figures, a lack of substantive discussion in some of the appendices (i.e., “we leave the discussion to appendix X” but there is not much discussion in appendix X).

A lot could be done to improve clarity of the discussion in section 3. For example, although the paper explicitly details asymptotic behavior (d -> infinity?) this is really only mentioned in lines 166-167, which somewhat confuses the issue. Some brief discussion of what the effect is in low-d situations would be nice (not new experiments – just a qualitative idea). Fig. 3 and Table 1 contradict each other due to the presence/absence of the asymptotic limit, which is mentioned in the title of Table 1 and briefly in the text but is not very clear, especially since Fig. 3 and Table 1 are supposed to be read together (?).

The figure captions should at minimum restate what is shown in the figures and what relevant terms (d, l, etc.) mean – this makes it much easier to refer to the figure without searching through the text for definitions and explanations. This should be doable in 1 or 2 sentences per caption at most and should not take a lot of space.

Some plots are hard to read. For example, Figure 4 and Figure 5 shows detailed pipelines using various colors of blocks and fonts without proper definition or explanation. It is also not clear the shown pipeline is the actual setting or a high-level demonstration of the design. 

V-Half seems to be a heuristic method based on V-Min and V-ZB. It may not be an optimal solution for the pipeline. Other configurations regarding the trade-off of memory and throughput are not evaluated.

Section 4.4 is confusing. Table 3 is not referenced anywhere and not explained in this section.  The results mentioned in this section (Table 6) do not clearly show the combined performance of the proposed approach and existing techniques.
questions: questions: Why is 1F1B the baseline used for the paper? It feels like there could be some more discussion here that is missing.

Is the lack of bubble in V-Half (figure 5) purely empirical or is there some reason it should be expected? There doesn’t seem to be anything special about V-Half from the point of view of the discussion in the paper (only the activation memory is relevant to V-half; it’s not clear why this specifically should not have bubbles). Also, V-ZB has no bubbles in the case of differing runtimes, if I understand correctly; so maybe it is more accurate to say that the number of bubbles decreases to 0 as activation memory budget increases?

How is the number of stages in the pipeline determined? While the authors mentioned that it depends on the number of devices, what is the number of stages used in this work? How does the number of stages influence performance?

Given the constraints of memory or throughput, do the authors use grid search to find an optimal schedule? Is it possible to use a theoretical or approximation method to quickly find a good pipeline schedule?
limitations: limitations: Yes
paper_summary: paper_summary: This work proposes systematic methodology for designing pipeline parallelism schedules and analyzing their performance (e.g. peak memory and pipeline bubbles).
The major observation is that a pipeline schedule can be viewed as repeating a building block, and the peak memory critically depends on the lifespan of a block.
Based on these insights, the authors design a family of novel V-shape building blocks and pipeline schedules that are memory efficient and achieve higher throughput than strong baselines like 1F1B (though at the cost of more communication), which is validated both theoretically and empirically.
strength_weakness: strength_weakness: There is still room for improvement in writing. For example:
- There are quite some typos, some of which are listed here: Line 22 "tensor" -> "Tensor"; Line 189, "V-Min" -> "V-ZB" (?); Line 193, "serious" -> "series".
- Line 210, "while other methods' memory is similar": one exception is 1F1B-R, whose activation memory is much smaller.
questions: questions: A high-level question that might be worth a brief discussion in the manuscript is: 
is it true that a pipeline schedule *must be* repetition of a building block? 
Actually the answer is no.
A naive example I can think of is a variant of GPipe, where the order of backward passes can be arbitrary, and thus the building block for one microbatch can be different from that of another microbatch.
This extension of GPipe is designed just out of theoretical curiosity though.

So the next question is whether there could be any real advantage (in terms of peak memory, throughput, etc.) in a pipeline schedule that cannot be expressed as repetition of a building block.
It would be great if there is a clear answer with a formal proof.
But even if the authors do not know the answer yet (and neither do I), it might be worth mentioning, so that anyone who has read this work will keep this in mind, rather than blindly constrain themselves to repeating a building block when designing new schedules.
limitations: limitations: Limitations are discussed throughout the manuscript.
paper_summary: paper_summary: The paper addresses the inefficiencies in current pipeline parallelism schedules used for training large-scale models, particularly focusing on high activation memory and pipeline bubbles. The paper proposes a new framework to decompose pipeline schedules into repeating building blocks and introduces V-shape building blocks (V-Min, V-Half, V-ZB) with controllable activation memory. Such building blocks reduce peak activation memory compared to the traditional 1F1B approach and even achieve higher throughput with reduced pipeline bubbles. The evaluations demonstrate substantial improvements in throughput and memory efficiency over 1F1B and 1F1B-I methods.
strength_weakness: strength_weakness: - It would be helpful to have experimental results for long sequence lengths. 1024 and 3072 sequence lengths are too short compared to what SOTA LLMs can handle.
questions: questions: - One of the problems with pipeline parallelism is that it increases implementation complexity because of its multi-program-multi-data (MPMD) nature. Do V-shaped abstractions bring any convenience in terms of implementation perspective?
limitations: limitations: No societal impact exists.

Comments: comment: Thank you for the rebuttal and certain rewrites. I will keep my score.
Thank you for the rebuttal. I have no further question, and will keep my score.