> 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/ios-inter-operator-scheduler-for-cnn-acceleration.md).

# IOS: Inter-Operator Scheduler for CNN Acceleration

* Executive summary 
  * Motivation: sequential execution --> under-utilization problem 
* Inter-Operator Scheduler 
  * Inter-operator parallelism 
  * Dynamic programming --> optimal schedule 
  * 1.1-1.5x speedup 
* Efficient deployment of CNNs is important 
  * Is CNN inference in current DL libraries well utilizing underlying hardware? 
* Motivation for Inter-Operator Parallelization 
  * More small convs in CNN design
  * GPU peak performance increased 
  * Intra- and inter-operator parallelization 
    * Sequential execution: Intra-operator Parallelization: Device under-utilization (small op & opwerful GPU)
    * Inter-Op Parallel Execution: better device utilization 
* Background: wavefront schedule policy 
  * Execute all available operators stage by stage 
  * A better schedule 
    * Put op to saturated stage: marginal benefit 
    * Under-utilization problem 
    * Wavefront schedule policy is sub-optimal 
* Inter-operator scheduler (IOS)
  * General idea: explore the schedule space exhausitvely 
  * Challenge: the number of schedules is exp in the number of operators 
    * Prohibitive to enumerate 
  * Observation 1: optimal schedule for a subgraph can be reused 
    * Key idea: dynamic programming 
  * Observation 2: the width of the computation graph is usually small (max number of parallelizable operators) 
    * Key result: time complexity is only exponential in the width 
  * ![](/files/UIocBRnacCsbwYyHuIHx)
  * Parallelization strategy selection 
    * Concurrent execution --> multi-GPU kernel at the same time 
    * Operator merge --> merged convolution, usually better performance 
    * Profile & select 
  * Last stage candidates 
    * S' can be the last stage of S <--> there is no edge from S' to S - S'&#x20;
  * Transition graph and time complexity&#x20;
  * Methodology&#x20;
    * Benchmarks&#x20;
      * Inception V3, SqueezeNet, Randwire, NasNet
    * Baselines: state-of-the-art frameworks, different schedules on IOS Runtime&#x20;
    * Environment: NVIDIA V100, Cuda, cuDNN
  * More active warps improve utilization