> For the complete documentation index, see [llms.txt](https://sliu583.gitbook.io/blog/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://sliu583.gitbook.io/blog/specific-work/seminar-and-talk/fall-21-reading-list/beyond-data-and-model-parallelism-for-deep-neural-networks.md).

# 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