# Beyond Data and Model Parallelism for Deep Neural Networks

* Parallelizing DNN training is hard 
  * Complex DNN models --> complex machine architectures 
* Existing approaches: data and model parallelism 
  * Data parallelism is the default strategy in existing DNN framework
  * Manually-designed strategies 
    * Combine data and model parallelism to accelerate DNNs 
  * Automatic generated strategies 
    * ColocRL uses RL to find device placement for model paralellism 
  * Exploring dimensions beyond data and model parallelism can further accelerate DNN training (by  up to 3.3x) 
* A search-based approach 
  * Define the SOAP search space of possible parallelization approach 
  * A cost model and a search algorithm 
  * Combining them: optimized strategies 
* The SOSP search space 
  * Samples, operators, attributes, parameters
    * Samples: partitioning training samples (data parallelism)
    * Operators: partitioning DNN operators (model parallelism)
    * Attributes: partitioning attributes in a sample (e.g., different pixels) 
    * Parameters: partitioning parameters in an operator 
  * Hybrid parallelism: different strategies perform the same computation (same accuracy, and focus on runtime performance) 
* This work: by considering a large search space, able to find better solution 
  * Example: data parallelism, model parallelism, hybrid 
* A cost model and a search algorithm 
  * Optimized solution in this search space 
  * FlexFlow
    * Input: operator graph (computation in DNN model), device topology (set of available devices, and their inter-connections)
    * Execution optimizer 
      * MCMC: search algorithm 
        * Iterative generate candidate strategies 
      * Execution simulator: cost model
        * Simulate the execution of the strategies and send the simulated performance back to the search algorithm 
        * Challenge: measuring distributed executions on real hardware is slow 
        * Two observations 
          * The performance of DNN operators is highly predictable 
          * DNN models only use a small number of distinct operators (redundancy) 
        * Execution simulator
          * Measure each distinct operator once 
          * Use the measurements to estimate different parallelization strategies 
          * Delta simulation algorithm 
            * Idea: do nothave to build task graph from scratch
            * Observation 
              * The MCMC search proposes a new strategy by updating the previous strategy 
              * Most of the task graph does not change 
            * Solution: simulate a new strategy using incremental updates to previous simulations 
      * Best found strategy will be sent to distributed runtime to parallelize training 
  * Evaluation 
    * Simulation reduces the search by 2-7x 
    * The search only takes a few minutes 
    * Two clusters, six DNN benchmarks 


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://sliu583.gitbook.io/blog/specific-work/seminar-and-talk/fall-21-reading-list/beyond-data-and-model-parallelism-for-deep-neural-networks.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.