---
title: "TASO — paper by Jia et al. (2019) · SOSP 2019"
description: "Deep learning frameworks such as TensorFlow, PyTorch, TensorRT and TVM speed up computation… 40 references, cited by 72 papers here."
authors: ["Zhihao Jia", "Oded Padon", "James Thomas", "Todd Warszawski", "Matei Zaharia", "Alex Aiken"]
year: 2019
venue: "SOSP 2019"
source: "https://cs.stanford.edu/~padon/taso-sosp19.pdf"
licence: "author's copy — read only"
summary_licence: "Elamur Cosmic License"
canonical: "https://research.elamur.ai/free/en/papers/jia-2019-taso-optimizing-deep-learning-computation/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/jia-2019-taso-optimizing-deep-learning-computation/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2019](https://md.research.elamur.ai/free/en/papers/2019/page/6/) / TASO: Optimizing Deep Learning Computation with Automatic Generation of Graph Substitutions

# TASO: Optimizing Deep Learning Computation with Automatic Generation of Graph Substitutions

**Authors:** [Zhihao Jia](https://md.research.elamur.ai/free/en/authors/zhihao-jia/), [Oded Padon](https://md.research.elamur.ai/free/en/authors/oded-padon/), James Thomas, Todd Warszawski, [Matei Zaharia](https://md.research.elamur.ai/free/en/authors/matei-zaharia/) and [Alex Aiken](https://md.research.elamur.ai/free/en/authors/alex-aiken/) · **Year:** 2019 · **Venue:** SOSP 2019 · **Licence:** author's copy — read only

**Links:** [Publisher's page](https://cs.stanford.edu/~padon/taso-sosp19.pdf) · [PDF](https://cs.stanford.edu/~padon/taso-sosp19.pdf)

**Citations:** [72](https://md.research.elamur.ai/free/en/papers/jia-2019-taso-optimizing-deep-learning-computation/cited-by/) in our library, of the 149,439 papers whose bibliographies we read

## Summary
Deep learning frameworks such as TensorFlow, PyTorch, TensorRT and TVM speed up computation graphs by rewriting subgraphs into faster equivalent forms. These rewrite rules are written by hand, which is costly to maintain as new operators appear, can introduce bugs, and misses optimizations. TASO (Tensor Algebra SuperOptimizer) generates these rewrites automatically.

Developers supply only operator definitions and mathematical properties. TASO enumerates every small graph built from these operators and runs each one on random tensors. Graphs that produce the same output fingerprint become candidate substitutions. An automated theorem prover then checks each candidate against the operator properties, using a first-order logic encoding that does not depend on tensor size. Finally, a cost-based backtracking search, adapted from MetaFlow, applies the verified rewrites and chooses data layouts at the same time.

On five real networks, TASO matches heavily hand-tuned frameworks on familiar models and runs up to 2.8× faster on newer ones. This makes graph-level optimization cheaper to build, easier to extend, and provably correct.

## Key points
- TensorFlow r1.14 has 155 hand-written substitutions in about 53K lines of C++. TASO needs only about 1,400 lines of operator definitions and specifications.
- The verifier relies on 43 operator properties, such as linearity of convolution. Validating these specifications exposed bugs both in the specs and in the generator.
- The evaluation covered ResNet-50, ResNeXt-50, Nas-RNN, NasNet-A and BERT:
  - TASO matched existing frameworks on ResNet-50.
  - It was up to 2.8× faster on the other models.
- Optimizing graph substitutions and data layout together gave a further 1.2× speedup over handling them one after the other. Every optimized graph was found in under ten minutes.
- The approach has two main limits:
  - Enumeration does not currently scale beyond graphs of size 4.
  - Users must still write the operator properties by hand.

*Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.*

📚 Shelves (1): [🖥️ Computer Science](https://md.research.elamur.ai/free/en/shelves/computer-science/) · 18,614 works

## Cite

Cite as: Zhihao Jia, Oded Padon, James Thomas, Todd Warszawski, Matei Zaharia and Alex Aiken. 2019. TASO: Optimizing Deep Learning Computation with Automatic Generation of Graph Substitutions. SOSP 2019.

The paper itself, not this page. BibTeX from the library's record of the work.

```bibtex
@inproceedings{jia2019taso,
  title = {{TASO: Optimizing Deep Learning Computation with Automatic Generation of Graph Substitutions}},
  author = {Zhihao Jia, Oded Padon, James Thomas, Todd Warszawski, Matei Zaharia and Alex Aiken},
  booktitle = {SOSP 2019},
  year = {2019},
  url = {https://cs.stanford.edu/~padon/taso-sosp19.pdf}
}
```

- [← previous Evaluating BERT for natural language inference: A case study on the CommitmentBank](https://md.research.elamur.ai/free/en/papers/jiang-2019-evaluating-bert-natural-language-inference/)
- [next → Arabic Text Diacritization Using Deep Neural Networks](https://md.research.elamur.ai/free/en/papers/fadel-2019-arabic-text-diacritization-using-deep/)
- [↑ back to papers of 2019](https://md.research.elamur.ai/free/en/papers/2019/page/6/)

## References

40 references, 11 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

1. 2017. Amazon EC2 P3 Instances. [https://aws.amazon.com/ec2/instance-types/p3/](https://aws.amazon.com/ec2/instance-types/p3/). [↗](https://aws.amazon.com/ec2/instance-types/p3/)
2. 2017. Tensorflow graph transform creates corrupted graph. [https://github.com/tensorflow/tensorflow/issues/7523](https://github.com/tensorflow/tensorflow/issues/7523). [↗](https://github.com/tensorflow/tensorflow/issues/7523)
3. 2017. XLA: Optimizing Compiler for TensorFlow. [https://www.tensorflow.org/xla](https://www.tensorflow.org/xla). [↗](https://www.tensorflow.org/xla)
4. 2018. Graph transform: fold constant with invalid graph. [https://github.com/tensorflow/tensorflow/issues/16545](https://github.com/tensorflow/tensorflow/issues/16545). [↗](https://github.com/tensorflow/tensorflow/issues/16545)
5. 2018. Tensor Cores in NVIDIA Volta Architecture. [https://www.nvidia.com/en-us/data-center/tensorcore/](https://www.nvidia.com/en-us/data-center/tensorcore/). [↗](https://www.nvidia.com/en-us/data-center/tensorcore/)
6. Martín Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Geoffrey Irving, Michael Isard, Manjunath Kudlur, Josh Levenberg, Rajat Monga, Sherry Moore, Derek G. Murray, Benoit Steiner, Paul Tucker, Vijay Vasudevan, Pete Warden, Martin Wicke, Yua… — [TensorFlow: A system for large-scale machine learning](https://md.research.elamur.ai/free/en/papers/abadi-2016-tensorflow-system-large-scale-machine/)
7. Sorav Bansal and Alex Aiken. 2006. Automatic Generation of Peephole Superoptimizers. In Proceedings of the 12th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS XII). [find](https://scholar.google.com/scholar?q=Sorav+Bansal+and+Alex+Aiken%2E+2006%2E+Automatic+Generation+of+Peephole+Superoptimizers%2E+In+Proceedings+of+the+12th+International+Conference+on+Architectural+Support+for+Programming+Languages+and+Operatin)
8. Tianqi Chen, Thierry Moreau, Ziheng Jiang, Haichen Shen, Eddie Q. Yan, Leyuan Wang, Yuwei Hu, Luis Ceze, Carlos Guestrin, and Arvind Krishnamurthy. 2018. [TVM: End-to-End Optimization Stack for Deep Learning](https://md.research.elamur.ai/free/en/papers/chen-2018-tvm-automated-end-end-optimizing/). CoRR abs/1802.04799 (2018). http://arxiv.org/abs/1802.04799 [↗](http://arxiv.org/abs/1802.04799)
9. Tianqi Chen, Lianmin Zheng, Eddie Yan, Ziheng Jiang, Thierry Moreau, Luis Ceze, Carlos Guestrin, and Arvind Krishnamurthy. 2018. [Learning to Optimize Tensor Programs](https://md.research.elamur.ai/free/en/papers/chen-2019-learning-optimize-tensor-programs/). In Advances in Neural Information Processing Systems 31.
10. Sharan Chetlur, Cliff Woolley, Philippe Vandermersch, Jonathan Cohen, John Tran, Bryan Catanzaro, and Evan Shelhamer. 2014. [cuDNN: Efficient Primitives for Deep Learning](https://md.research.elamur.ai/free/en/papers/chetlur-2014-cudnn-efficient-primitives-deep-learning/). CoRR abs/1410.0759 (2014). http://arxiv.org/abs/1410.0759 [↗](http://arxiv.org/abs/1410.0759)
11. Berkeley R. Churchill, Oded Padon, Rahul Sharma, and Alex Aiken. 2019. Semantic Program Alignment for Equivalence Checking. In Proceedings of the 2019 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), Phoenix, AZ, USA, June 22-26, 2019. https://doi.org/10.1145/3314221.… — [doi:10.1145/3314221.3314596](https://doi.org/10.1145/3314221.3314596) [↗](https://doi.org/10.1145/3314221.…)
12. cuBLAS 2016. Dense Linear Algebra on GPUs. [https://developer.nvidia.com/cublas](https://developer.nvidia.com/cublas). [↗](https://developer.nvidia.com/cublas)
13. Manjeet Dahiya and Sorav Bansal. 2017. Black-Box Equivalence Checking Across Compiler Optimizations. In Programming Languages and Systems, Bor-Yuh Evan Chang (Ed.). Springer International Publishing, Cham. [find](https://scholar.google.com/scholar?q=Manjeet+Dahiya+and+Sorav+Bansal%2E+2017%2E+Black%2DBox+Equivalence+Checking+Across+Compiler+Optimizations%2E+In+Programming+Languages+and+Systems%2C+Bor%2DYuh+Evan+Chang+%28Ed%2E%29%2E+Springer+International+Publishing%2C+)
14. Leonardo De Moura and Nikolaj Bjørner. 2008. Z3: An Efficient SMT Solver. In Proceedings of the Theory and Practice of Software, 14th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS’08/ETAPS’08). [find](https://scholar.google.com/scholar?q=Leonardo+De+Moura+and+Nikolaj+Bj%C3%B8rner%2E+2008%2E+Z3%3A+An+Efficient+SMT+Solver%2E+In+Proceedings+of+the+Theory+and+Practice+of+Software%2C+14th+International+Conference+on+Tools+and+Algorithms+for+the+Construct)
15. Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2018. [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://md.research.elamur.ai/free/en/papers/devlin-2019-bert-pre-training-deep-bidirectional/). CoRR abs/1810.04805 (2018).
16. Vincent Dumoulin and Francesco Visin. 2016. A guide to convolution arithmetic for deep learning. CoRR (2016). [find](https://scholar.google.com/scholar?q=Vincent+Dumoulin+and+Francesco+Visin%2E+2016%2E+A+guide+to+convolution+arithmetic+for+deep+learning%2E+CoRR+%282016%29%2E)
17. Sumit Gulwani and George C. Necula. 2003. Discovering Affine Equalities Using Random Interpretation. In Proceedings of the 30th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL ’03). ACM. [find](https://scholar.google.com/scholar?q=Sumit+Gulwani+and+George+C%2E+Necula%2E+2003%2E+Discovering+Affine+Equalities+Using+Random+Interpretation%2E+In+Proceedings+of+the+30th+ACM+SIGPLAN%2DSIGACT+Symposium+on+Principles+of+Programming+Languages+%28POP)
18. Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. 2016. [Deep residual learning for image recognition](https://md.research.elamur.ai/free/en/papers/he-2015-deep-residual-learning-image-recognition/). In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR).
19. Andrew G. Howard, Menglong Zhu, Bo Chen, Dmitry Kalenichenko, Weijun Wang, Tobias Weyand, Marco Andreetto, and Hartwig Adam. 2017. [MobileNets: Efficient Convolutional Neural Networks for Mobile Vision Applications](https://md.research.elamur.ai/free/en/papers/howard-2017-mobilenets-efficient-convolutional-neural-networks/). CoRR abs/1704.04861 (2017).
20. Zhihao Jia, Sina Lin, Charles R. Qi, and Alex Aiken. 2018. Exploring Hidden Dimensions in Accelerating Convolutional Neural Networks. In Proceedings of the 35th International Conference on Machine Learning (Proceedings of Machine Learning Research), Vol. 80. PMLR. [find](https://scholar.google.com/scholar?q=Zhihao+Jia%2C+Sina+Lin%2C+Charles+R%2E+Qi%2C+and+Alex+Aiken%2E+2018%2E+Exploring+Hidden+Dimensions+in+Accelerating+Convolutional+Neural+Networks%2E+In+Proceedings+of+the+35th+International+Conference+on+Machine+Lea)
21. Zhihao Jia, James Thomas, Todd Warzawski, Mingyu Gao, Matei Zaharia, and Alex Aiken. 2019. Optimizing DNN Computation with Relaxed Graph Substitutions. In Proceedings of the 2nd Conference on Systems and Machine Learning (SysML’19). [find](https://scholar.google.com/scholar?q=Zhihao+Jia%2C+James+Thomas%2C+Todd+Warzawski%2C+Mingyu+Gao%2C+Matei+Zaharia%2C+and+Alex+Aiken%2E+2019%2E+Optimizing+DNN+Computation+with+Relaxed+Graph+Substitutions%2E+In+Proceedings+of+the+2nd+Conference+on+Systems+)
22. Zhihao Jia, Matei Zaharia, and Alex Aiken. 2019. [Beyond Data and Model Parallelism for Deep Neural Networks](https://md.research.elamur.ai/free/en/papers/jia-2018-beyond-data-model-parallelism-deep/). In Proceedings of the 2nd Conference on Systems and Machine Learning (SysML’19).
23. Vu Le, Mehrdad Afshari, and Zhendong Su. 2014. Compiler validation via equivalence modulo inputs. In ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI ’14, Edinburgh, United Kingdom - June 09 - 11, 2014. 216–226. https://doi.org/10.1145/2594291.2594334 — [doi:10.1145/2594291.2594334](https://doi.org/10.1145/2594291.2594334) [↗](https://doi.org/10.1145/2594291.2594334)
24. Chao Li, Yi Yang, Min Feng, Srimat Chakradhar, and Huiyang Zhou. 2016. Optimizing memory efficiency for deep convolutional neural networks on GPUs. In SC’16: Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis. IEEE. [find](https://scholar.google.com/scholar?q=Chao+Li%2C+Yi+Yang%2C+Min+Feng%2C+Srimat+Chakradhar%2C+and+Huiyang+Zhou%2E+2016%2E+Optimizing+memory+efficiency+for+deep+convolutional+neural+networks+on+GPUs%2E+In+SC%E2%80%9916%3A+Proceedings+of+the+International+Conferenc)
25. Henry Massalin. 1987. Superoptimizer: a look at the smallest program. In ACM SIGARCH Computer Architecture News, Vol. 15. [find](https://scholar.google.com/scholar?q=Henry+Massalin%2E+1987%2E+Superoptimizer%3A+a+look+at+the+smallest+program%2E+In+ACM+SIGARCH+Computer+Architecture+News%2C+Vol%2E+15%2E)
26. Azalia Mirhoseini, Hieu Pham, Quoc V Le, Benoit Steiner, Rasmus Larsen, Yuefeng Zhou, Naveen Kumar, Mohammad Norouzi, Samy Bengio, and Jeff Dean. 2017. Device Placement Optimization with Reinforcement Learning. (2017). [find](https://scholar.google.com/scholar?q=Azalia+Mirhoseini%2C+Hieu+Pham%2C+Quoc+V+Le%2C+Benoit+Steiner%2C+Rasmus+Larsen%2C+Yuefeng+Zhou%2C+Naveen+Kumar%2C+Mohammad+Norouzi%2C+Samy+Bengio%2C+and+Jeff+Dean%2E+2017%2E+Device+Placement+Optimization+with+Reinforcement)
27. MKLDNN 2016. Intel Math Kernel Library for Deep Neural Networks. [https://01.org/mkl-dnn](https://01.org/mkl-dnn). [↗](https://01.org/mkl-dnn)
28. Vinod Nair and Geoffrey E. Hinton. 2010. Rectified Linear Units Improve Restricted Boltzmann Machines. In Proceedings of the 27th International Conference on International Conference on Machine Learning (ICML’10). Omnipress, USA, 807–814. [http://dl.acm.org/citation.cfm?id=3104322.3104425](http://dl.acm.org/citation.cfm?id=3104322.3104425) [↗](http://dl.acm.org/citation.cfm?id=3104322.3104425)
29. George C. Necula. 2000. Translation validation for an optimizing compiler. In Proceedings of the 2000 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), Vancouver, Britith Columbia, Canada, June 18-21, 2000. 83–94. https://doi.org/10.1145/349299.349314 [↗](https://doi.org/10.1145/349299.349314)
30. Amir Pnueli, Michael Siegel, and Eli Singerman. 1998. Translation Validation. In Tools and Algorithms for Construction and Analysis of Systems, 4th International Conference, TACAS ’98, Held as Part of the European Joint Conferences on the Theory and Practice of Software, ETAPS’98, Lisbon, Portugal,… — [doi:10.1007/bfb0054170](https://doi.org/10.1007/bfb0054170) [find](https://scholar.google.com/scholar?q=Amir+Pnueli%2C+Michael+Siegel%2C+and+Eli+Singerman%2E+1998%2E+Translation+Validation%2E+In+Tools+and+Algorithms+for+Construction+and+Analysis+of+Systems%2C+4th+International+Conference%2C+TACAS+%E2%80%9998%2C+Held+as+Part+of)
31. PyTorch 2017. Tensors and Dynamic neural networks in Python with strong GPU acceleration. [https://pytorch.org](https://pytorch.org). [↗](https://pytorch.org)
32. Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, Alexander C. Berg, and Li Fei-Fei. 2015. [ImageNet Large Scale Visual Recognition Challenge](https://md.research.elamur.ai/free/en/papers/russakovsky-2014-imagenet-large-scale-visual-recognition/). International Journal of Computer Vision (IJCV) 115, 3 (2015),…
33. Rahul Sharma, Eric Schkufza, Berkeley R. Churchill, and Alex Aiken. 2013. Data-driven equivalence checking. In Proceedings of the 2013 ACM SIGPLAN International Conference on Object Oriented Programming Systems Languages & Applications, OOPSLA 2013, part of SPLASH 2013, Indianapolis, IN, USA, Octobe… [find](https://scholar.google.com/scholar?q=Rahul+Sharma%2C+Eric+Schkufza%2C+Berkeley+R%2E+Churchill%2C+and+Alex+Aiken%2E+2013%2E+Data%2Ddriven+equivalence+checking%2E+In+Proceedings+of+the+2013+ACM+SIGPLAN+International+Conference+on+Object+Oriented+Programmi)
34. Muthian Sivathanu, Tapan Chugh, Sanjay S. Singapuram, and Lidong Zhou. 2019. Astra: Exploiting Predictability to Optimize Deep Learning. In Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS ’19). ACM, New York,… [find](https://scholar.google.com/scholar?q=Muthian+Sivathanu%2C+Tapan+Chugh%2C+Sanjay+S%2E+Singapuram%2C+and+Lidong+Zhou%2E+2019%2E+Astra%3A+Exploiting+Predictability+to+Optimize+Deep+Learning%2E+In+Proceedings+of+the+Twenty%2DFourth+International+Conference+on)
35. Ross Tate, Michael Stepp, Zachary Tatlock, and Sorin Lerner. 2011. Equality Saturation: A New Approach to Optimization. Logical Methods in Computer Science 7, 1 (2011). https://doi.org/10.2168/LMCS-7(1: 10)2011 [↗](https://doi.org/10.2168/LMCS-7(1:)
36. TensorRT 2017. NVIDIA TensorRT: Programmable Inference Accelerator. [https://developer.nvidia.com/tensorrt](https://developer.nvidia.com/tensorrt). [↗](https://developer.nvidia.com/tensorrt)
37. Shuang Wu, Guoqi Li, Feng Chen, and Luping Shi. 2018. Training and Inference with Integers in Deep Neural Networks. In International Conference on Learning Representations. [find](https://scholar.google.com/scholar?q=Shuang+Wu%2C+Guoqi+Li%2C+Feng+Chen%2C+and+Luping+Shi%2E+2018%2E+Training+and+Inference+with+Integers+in+Deep+Neural+Networks%2E+In+International+Conference+on+Learning+Representations%2E)
38. Saining Xie, Ross B. Girshick, Piotr Dollár, Zhuowen Tu, and Kaiming He. 2016. Aggregated Residual Transformations for Deep Neural Networks. CoRR abs/1611.05431 (2016). [find](https://scholar.google.com/scholar?q=Saining+Xie%2C+Ross+B%2E+Girshick%2C+Piotr+Doll%C3%A1r%2C+Zhuowen+Tu%2C+and+Kaiming+He%2E+2016%2E+Aggregated+Residual+Transformations+for+Deep+Neural+Networks%2E+CoRR+abs%2F1611%2E05431+%282016%29%2E)
39. Barret Zoph and Quoc V. Le. 2016. [Neural Architecture Search with Reinforcement Learning](https://md.research.elamur.ai/free/en/papers/zoph-2016-neural-architecture-search-reinforcement-learning/). CoRR abs/1611.01578 (2016).
40. Barret Zoph, Vijay Vasudevan, Jonathon Shlens, and Quoc V Le. 2018. [Learning transferable architectures for scalable image recognition](https://md.research.elamur.ai/free/en/papers/zoph-2017-learning-transferable-architectures-scalable-image/). In Proceedings of the IEEE conference on computer vision and pattern recognition.

*Updated 2 November 2026*