Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes a novel algorithm to find a pipeline parallel configuration where each pipeline stage also includes data and tensor model parallelism. The method assumes that the input computational graph consists of multiple “layers” that form a DAG and each layer has a  set of predefined tensor model parallelism configurations. The algorithm is a two-stage dynamic programming algorithm and is mainly evaluated in a simulated environment.
main_review: I lean towards accepting this paper. Although there are limitations with the proposed method and the evaluation method, I believe the proposed two-step problem formulation and dynamic programming algorithm are novel and should be useful for the community. Detailed comments:

Strengths:
- The two-step formulation proposed for pipeline and data/tensor-model parallelism is novel and will greatly reduce the complexity of the overall search space. I believe this is a positive contribution and will be useful for future work working in space.
A two-stage dynamic based on the two-step formulation solves the problem.
- The paper is clear and easy to follow.

Weaknesses:
- The algorithm assumes the knowledge of predefined “layers” and for every layer, there is a list of predefined model-parallel methods. For a more complicated neural network, this is not an easy task. This limits the application of the method on more complicated neural networks.
- There are non-negligible limitations on the experiments in the paper:
  - The paper only evaluates the BERT model. In this case, the DAG formulation actually degenerates to a chain, making the algorithm proposed in the paper overkill. The method should be evaluated on more neural networks with more complex architecture (that actually forms a DAG).
  - Most of the evaluations in the paper are simulated. Although Figure 4 partly proves the simulation is realistic, I’m still not convinced and I would like to see larger-scale experiments.

Minor Issues:
- Some key concepts will be easier to be understood with examples (e.g. Downsets).
Line 26: Maybe also add \emph for “pipelined model parallelism”?

Other questions
- Do you profile the Time-Per-Sample for every downset? How long does this take? Will this be a potential bottleneck when the neural network structure getting more complex?


limitations_and_societal_impact: See weaknesses in the main review section.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper proposes Piper, an efficient dynamic programming algorithm to combine data parallelism, tensor model parallelism, pipeline model parallelism, and activation rematerialization.
The paper evaluates the algorithm on BERT models with real per-layer profiling data and simulated end-to-end results.
It provides insightful analyses of the results.
main_review: Originality and clarity:  
This paper tackles an important problem. The DP algorithm and the idea of using TMPC are novel.
The paper is well written with the necessary background information. It precisely discusses its relations to prior pipeline-parallelism works.

Strength:
1. It is the first work that uses dynamic programming to search in a non-trivial search space that includes data parallelism, tensor model parallelism, pipeline model parallelism, and activation rematerialization.
2. Clear analysis and explanation of the results.

Weakness:
1. The evaluation results in Figure.1 are not measured in real systems. They are obtained by simulation. The y-axis
"throughput" is computed by formulas proposed by authors under various assumptions. It does not reflect the
behavior of real systems. As a paper targeting a system problem, only running evaluation in a simulator is not
enough. The authors show real measured throughput in Figure.4, meaning that the authors have access to the machines.
Could you please use real profiling data in Figure.1, at least for small-scale experiments? The insight drew from these simulation experiments can be misleading if we do not consider some important factors in real systems.
2. In the evaluation, the strategy generated by this paper only provides significant advantages in unrealistic settings. For example, it only shows significant advantages over "equi-no TP" on settings with an extremely low memory budget or an extremely high number of devices.
Training large models under an extremely low memory budget distributedly is not realistic and nobody will do this. When the number of devices becomes large, the simulator model used in the paper is not accurate anymore.
3. The paper does not consider the effect of batch size when measuring the throughput of TMPC. A small batch size typically cannot utilize the full compute power of a modern high-end GPU. Even with the same tensor model parallel configuration, different batch sizes can have different TPS.


Additional questions:
1. In Figure.2, the blue line (Piper) is almost a straight line. Does this mean Piper can get perfect **strong** linear scaling? I feel like this is impossible in a real system. For example, even in this paper (https://arxiv.org/pdf/2104.04473.pdf), they can only get good **weak** scaling in a cluster with very high internode bandwidth.

limitations_and_societal_impact: The author adequately addressed the limitation of this paper in Section 6.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper presents a search based method to plan DNN parallelism. The search space includes pipelining, recomputation choices and data partitioning. 

main_review: First of all, this paper studies an important problem of automatic parallelism. Two of the primarily related works are FlexFlow and Pipedream. Piper's search space can be viewed as the combination of the above two, plus the choice of recomputation. The overall contribution over the prior work is slightly incremental.

Given the limited technical contributions, the paper would benefit from stronger empirical evaluations. On that end, it would be beneficial to show a wide variety of model settings and how Piper applies to those models. It would also be useful to bring baselines that reflect the search space used by FlexFlow and PipeDream. Finally, it would be helpful to evaluate Piper's plan on a real end-to-end setting and see the benefit brought by the additional configuration space.

The paper is borderline due to the above considerations.

limitations_and_societal_impact: NA
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: Parallel/distributed training of machine learning models is a big and complex task. This paper proposed a dynamic programming algorithm in searching optimal parallelization configurations for machine learning models, considering tensor parallelization, data parallelization, and pipeline parallelization. Designing such algorithm is important and interesting, and potentially relieve machine learning app writers from manually designing parallelization configurations. To provided an optimal (or close to optimal) parallelization configuration without breaching memory limitation is already good contributions in real-world scenarios.
main_review: Finding parallelization configurations is not a new problem, but the problem is so complex that new contributions are always needed. This paper didn't bring up any new ways to parallelize machine learning models, but tried to provide a better (or optimal) combinations of known parallelization techniques, which is also very interesting. Finding good combinations of parallelization techniques isn't new idea either, but previous publications have missed opportunities. 

Describing such dynamic programming algorithm is not easy. This paper did a good job in clearly presenting the algorithm with formal definitions. The main dynamic programming recursion is deciding where to cut the next pipeline stage from the difference of 2 downsets. This is a clearly good idea. Although the algorithm can probably be optimized to not consider very small pipeline stages or very large pipeline stages, since all the pipeline stages should still probably have similar latencies for optimal performance, this doesn't hurt the correctness of the algorithm.

First question I have is: are the authors only considering PipeDream-style pipelining, and discarding GPipe-style pipelining? It is unclear to me if the algorithm is considering the extra cost of pipeline-filling and pipeline exhausting in GPipe. If the answer is yes, that is probably fine, since PipeDream-style pipelining is probably higher in throughput. If the answer is no, I would like to hear why.

Each pipeline stage is handling a part of the machine learning model, including both its forward computations and backward computations. This is probably a reasonable limitation. Within each pipeline stage, the computation of TPS depends on a heuristics. This is also quite reasonable I think, since solving this problem exactly is almost impossible, not only because the problem is NP-hard, but also because the estimations of memory consumption is very unlikely to be accurate. Each device might reserve memories for other purposes, and some details of memory recycling can be chaotic. Using a heuristics and trying not to use to the memory limit is a wise choice.

However, I think one significant problem of this paper is that the handling of activation recomputation depends on the TMPC. That is to say, recomputation can only happen in a layer. For instance, given a pipeline stage of A -> B -> C -> D -> E, the backward computation of the layers (A', B', C', D', and E') might choose to recompute something in each layer, but you can never recompute multiple layers together, such that the backward computation becomes B -> C -> D -> E' -> D' -> C' -> B' -> A'. In my example, the whole layers of B C and D are recomputed. This limitation might not be so significant in this paper, since the evaluations used models that have huge layers (such as transformer layers). But if the model has many small layers, then it is more likely that consecutive layers need to be recomputed to save memory. How difficult is it for this type of recomputation to be considered?

When modeling the cost of parallelization, the cost of communication is for sure critical. That is why when the authors say that in tensor parallelization, each of the t devices has a full copy of the inputs and outputs, the reviewer is a bit doubtful. One likely reason for this to not be a problem, is that tensor parallelization is not heavily used or optimized at runtime, or most tensor parallelizations likely require full copy of the inputs and outputs to be on all t devices. Based on the supplemental data, it seems that the latter is the reason? This limitation is thus likely reasonable, since the modeling of cost doesn't have to be very very accurate.

In the algorithm, it seems that each pipeline stage has one d (data parallelization) and t (tensor parallelization) value. This is a limitation such that layers in the same pipeline stage must have the same d and t. The reviewer is not very sure how big this limitation is. For instance, if a pipeline stage has layer A -> B -> C -> D, and only layer C has a very efficient tensor parallelization of t = 4, does that mean that the algorithm cannot make use of it, since the other layers (A, B, and D) do not have a TMPC for t = 4? I guess the authors can create a (TMPC of t = 4) by duplicating a (TMPC of t = 1) 4 times (just like data parallelization)? but I am not sure if that works, since it breaks the conceptional separation of data parallelization and tensor parallelization. The authors can certainly argue that, the lack of TMPCs is not the problem for this paper. However, this limitation seems to be quite practical. Can the authors elaborate here?

Of course, in the end, we care about if the new algorithm is providing better throughput than existing methods, and if we learn anything exciting from the dynamic searching algorithm. Evaluation seems to be the main reason of rejection from previous submissions. Indeed, it sticks out that most evaluations are just running the algorithm itself and presenting the estimated throughput. The Figure 1 showed interesting ablation tests, and demonstrated that removing some options in the search space caused worse throughput. It does increase the confidence that the algorithm is considering the right things, but it makes reviewers less confident, since the modeling/estimation itself could be incorrect. The added Figure 4 does boost that confidence.

The take aways are not so exciting but rather expected. The "Power of Piper's search space" is particularly interesting, since it provides a theoretical explanation of why Piper is better. 

In summary, this paper addressed a very relevant problem of high importance. The solution is a small delta to what has been published, but it is nevertheless important. There are 2 significant limitations (about recomputation and fixed d/t for all layers in one stage), which the reviewer hope to get elaborations from the authors. The evaluations are not ideal, but the challenges of running all configurations in real machines is probably too high to request. 
limitations_and_societal_impact: The authors didn't say that their work can potentially solve the climate change problem, but that is totally fine.
review_title: null

Meta-review: After some discussion, there's general consensus toward accepting the work. As Reviewer cpuf notes: "It is the first work that uses dynamic programming to search in a non-trivial search space that includes data parallelism, tensor model parallelism, pipeline model parallelism, and activation rematerialization." There are a number of challenges in finding parallelizable configurations, and while the paper's specific ideas may have overlap with prior works or may be argued as incremental, it makes an important delta in solving this important problem area.

Flaw-wise, there are several experimental limitations that would be worth resolving as Reviewer BM6L and cpuf note. I highly recommend the authors address the rebuttal concerns as they further polish the paper.
Decision: Accept (Poster)