High performance stencil code generation with Lift

ABSTRACT

Stencil computations are widely used from physical simulations to machine-learning. They are embarrassingly parallel and perfectly fit modern hardware such as Graphic Processing Units. Although stencil computations have been extensively studied, optimizing them for increasingly diverse hardware remains challenging. Domain Specific Languages (DSLs) have raised the programming abstraction and offer good performance. However, this places the burden on DSL implementers who have to write almost full-fledged parallelizing compilers and optimizers.

Lift has recently emerged as a promising approach to achieve performance portability and is based on a small set of reusable parallel primitives that DSL or library writers can build upon. Lift’s key novelty is in its encoding of optimizations as a system of extensible rewrite rules which are used to explore the optimization space. However, Lift has mostly focused on linear algebra operations and it remains to be seen whether this approach is applicable for other domains.

This paper demonstrates how complex multidimensional stencil code and optimizations such as tiling are expressible using compositions of simple 1D Lift primitives. By leveraging existing Lift primitives and optimizations, we only require the addition of two primitives and one rewrite rule to do so. Our results show that this approach outperforms existing compiler approaches and hand-tuned codes.

References

1. Jason Ansel, Shoaib Kamil, Kalyan Veeramachaneni, Jonathan RaganKelley, Jeffrey Bosboom, Una-May O’Reilly, and Saman Amarasinghe. 2014. OpenTuner: An Extensible Framework for Program Autotuning. In PACT ’14. ACM, 303–316.
2. Krste Asanovic, Ras Bodik, Bryan Christopher Catanzaro, Joseph James Gebis, Parry Husbands, Kurt Keutzer, David A Patterson, William Lester Plishker, John Shalf, Samuel Webb Williams, et al. 2006. The Landscape Of Parallel Computing Research: A View From Berkeley . Technical Report. UCB/EECS-2006-183, EECS Department, University of California, Berkeley.
3. Olivier Aumage, Denis Barthou, and Alexandre Honorat. 2016. A Stencil DSEL For Single Code Accelerated Computing With SYCL. In SYCL 2016 (Workshop) at ACM SIGPLAN PPoPP .
4. Peter Bastian, Markus Blatt, Christian Engwer, Andreas Dedner, Robert Klöfkorn, S Kuttanikkad, Mario Ohlberger, and Oliver Sander. 2006. The Distributed And Unified Numerics Environment (DUNE). In Proc. Of The 19th Symposium On Simulation Technique In Hannover .
5. Tobias Brandvik and Graham Pullan. 2010. SBLOCK: A Framework For Efficient Stencil-Based PDE Solvers On Multi-Core Platforms. In CIT 2010 . IEEE, 1181–1188.
6. Shuai Che, Michael Boyer, Jiayuan Meng, David Tarjan, Jeremy W Sheaffer, Sang-Ha Lee, and Kevin Skadron. 2009. Rodinia: A Benchmark Suite For Heterogeneous Computing. In IISWC 2009. IEEE, 44–54.
7. Matthias Christen, Olaf Schenk, and Helmar Burkhart. 2011. PATUS: A Code Generation And Autotuning Framework For Parallel Iterative Stencil Computations on Modern Microarchitectures. In IPDPS. IEEE, 676–687.
8. Milosz Ciznicki, Michal Kulczewski, Piotr Kopta, and Krzysztof Kurowski. 2016. Scaling The GCR Solver Using A High-Level Stencil Framework On Multi-And Many-Core Architectures. In Parallel Processing And Applied Mathematics . Springer, 594–606.
9. Murray I Cole. 1988. Algorithmic Skeletons: A Structured Approach To The Management Of Parallel Computation . Ph.D. Dissertation. University of Edinburgh.
10. Anthony Danalis, Gabriel Marin, Collin McCurdy, Jeremy S Meredith, Philip C Roth, Kyle Spafford, Vinod Tipparaju, and Jeffrey S Vetter. 2010. The Scalable Heterogeneous Computing (SHOC) Benchmark Suite. In Proceedings Of The 3rd Workshop On General-Purpose Computation On Graphics Processing Units . ACM, 63–74.
11. Usman Dastgeer and Christoph Kessler. 2012. A Performance-Portable Generic Component For 2D Convolution Computations On GPU-Based Systems. In MULTIPROG Workshop at HiPEAC-2012. 1–12.
12. Fabian Dütsch, Karim Djelassi, Michael Haidl, and Sergei Gorlatch. 2014. HLSF: A High-Level; C++-Based Framework For Stencil Computations On Accelerators. In Proceedings Of The Second Workshop On Optimizing Stencil Computations . ACM, 41–4.
13. Johan Enmyren and Christoph W Kessler. 2010. SkePU: A MultiBackend Skeleton Programming Library For Multi-GPU Systems. In Proceedings Of The Fourth International Workshop On High-Level Parallel Programming And Applications . ACM, 5–14.
14. Thomas L Falch and Anne C Elster. 2016. ImageCL: An Image Processing Language For Performance Portability On Heterogeneous Systems. arXiv preprint arXiv:1605.06399 (2016).
15. Matteo Frigo and Volker Strumpen. 2005. Cache Oblivious Stencil Computations. In ICS 2005. ACM, 361–366.
16. Joseph D Garvey. 2015. Automatic Performance Tuning Of Stencil Computations On Graphics Processing Units . Ph.D. Dissertation. University of Toronto.
17. Tobias Grosser, Albert Cohen, Paul HJ Kelly, J Ramanujam, P Sadayappan, and Sven Verdoolaege. 2013. Split Tiling For GPUs: Automatic Parallelization Using Trapezoidal Tiles. In Proceedings Of The 6th Workshop On General Purpose Processor Using Graphics Processing Units . ACM, 24–31.
18. Tobias Grosser, Sven Verdoolaege, Albert Cohen, and P Sadayappan. 2014. The Relation Between Diamond Tiling And Hexagonal Tiling. Parallel Processing Letters 24, 03 (2014).
19. Jia Guo, Ganesh Bikshandi, Basilio B Fraguela, and David Padua. 2009. Writing Productive Stencil Codes With Overlapped Tiling. Concurrency and Computation: Practice and Experience 21, 1 (2009), 25–39.
20. Tom Henretty, Richard Veras, Franz Franchetti, Louis-Noël Pouchet, Jagannathan Ramanujam, and Ponnuswamy Sadayappan. 2013. A Stencil Compiler For Short-Vector SIMD Architectures. In ICS 2013. ACM, 13–24.
21. Shoaib Kamil, Cy Chan, Leonid Oliker, John Shalf, and Samuel Williams. 2010. An Auto-Tuning Framework For Parallel Multicore Stencil Computations. In IPDPS 2010. IEEE, 1–12.
22. Shoaib Kamil, Derrick Coetzee, Scott Beamer, Henry Cook, Ekaterina Gonina, Jonathan Harper, Jeffrey Morlan, and Armando Fox. 2012. Portable Parallel Performance from Sequential, Productive, Embedded Domain-specific Languages. In PPoPP 2012. ACM, 303–304.
23. DaeGon Kim, Lakshminarayanan Renganarayanan, Dave Rostron, Sanjay Rajopadhye, and Michelle Mills Strout. 2007. Multi-Level Tiling: M For The Price Of One. In SC 2007. ACM, 51.
24. Herbert Kuchen. 2002. A Skeleton Library. In Euro-Par 2002. Springer, 620–629.
25. Michael Lesniak. 2010. PASTHA: Parallelizing Stencil Calculations In Haskell. In Proceedings Of The 5th ACM SIGPLAN Workshop On Declarative Aspects Of Multicore Programming . ACM, 5–14.
26. Tareq Malas, Georg Hager, Hatem Ltaief, and David Keyes. 2015. MultiDimensional Intra-Tile Parallelization For Memory-Starved Stencil Computations. arXiv preprint arXiv:1510.04995 (2015).
27. Azamat Mametjanov, Daniel Lowell, Ching-Chen Ma, and Boyana Norris. 2012. Autotuning Stencil-Based Computations On GPUs. In CLUSTER 2012 . IEEE, 266–274.
28. Naoya Maruyama and Takayuki Aoki. 2014. Optimizing Stencil Computations For NVIDIA Kepler GPUs. In Proceedings Of The 1st International Workshop On High-Performance Stencil Computations, Vienna . 89–95.
29. Trevor L. McDonell, Manuel M.T. Chakravarty, Gabriele Keller, and Ben Lippmeier. 2013. Optimising Purely Functional GPU Programs. In ICFP 2013 . ACM, New York, NY, USA, 49–60.
30. Richard Membarth, Frank Hannig, Jürgen Teich, and Harald Köstler. 2012. Towards Domain-Specific Computing For Stencil Codes In HPC. In SCC 2012. IEEE, 1133–1138.
31. Ravi Teja Mullapudi, Vinay Vasista, and Uday Bondhugula. 2015. PolyMage: Automatic Optimization for Image Processing Pipelines. In ASPLOS 2015 . ACM, New York, NY, USA, 429–443.
32. Anthony Nguyen, Nadathur Satish, Jatin Chhugani, Changkyu Kim, and Pradeep Dubey. 2010. 3.5-D Blocking Optimization For Stencil Computations On Modern CPUs And GPUs. In SC 2010. IEEE Computer Society, 1–13.
33. Jonathan Ragan-Kelley, Connelly Barnes, Andrew Adams, Sylvain Paris, Frédo Durand, and Saman Amarasinghe. 2013. Halide: A Language And Compiler For Optimizing Parallelism, Locality, And Recomputation In Image Processing Pipelines. ACM SIGPLAN Notices 48, 6 (2013), 519–530.
34. Ari Rasch, Michael Haidl, and Sergei Gorlatch. 2017. ATF: A Generic Auto-Tuning Framework. In HPCC. IEEE.
35. Prashant Singh Rawat, Changwan Hong, Mahesh Ravishankar, Vinod Grover, Louis-Noel Pouchet, Atanas Rountev, and P. Sadayappan. 2016. Resource Conscious Reuse-Driven Tiling for GPUs. In PACT 2016. ACM, 99–111.
36. Prashant Singh Rawat, Changwan Hong, Mahesh Ravishankar, Vinod Grover, Louis-Noël Pouchet, and P. Sadayappan. 2016. Effective Resource Management for Enhancing Performance of 2D and 3D Stencils on GPUs. In GPGPU 2016. ACM, New York, NY, USA, 92–102.
37. Lakshminarayanan Renganarayana, Manjukumar Harthikote-Matha, Rinku Dewri, and Sanjay Rajopadhye. 2007. Towards Optimal MultiLevel Tiling For Stencil Computations. In IPDPS 2007. IEEE, 1–10.
38. Michel Steuwer, Christian Fensch, Sam Lindley, and Christophe Dubach. 2015. Generating Performance Portable Code Using Rewrite Rules: From High-Level Functional Expressions To High-Performance OpenCL Code. In ICFP. ACM, 205–217.
39. Michel Steuwer, Michael Haidl, Stefan Breuer, and Sergei Gorlatch. 2014. High-Level Programming Of Stencil Computations On MultiGPU Systems Using The SkelCL Library. Parallel Processing Letters 24, 03 (2014), 1441005.
40. Michel Steuwer, Philipp Kegel, and Sergei Gorlatch. 2011. SkelCL - A Portable Skeleton Library For High-Level Gpu Programming. In Parallel And Distributed Processing Workshops And Phd Forum (IPDPSW), 2011 IEEE International Symposium On . IEEE, 1176–1182.
41. Michel Steuwer, Toomas Remmelg, and Christophe Dubach. 2016. Matrix Multiplication Beyond Auto-Tuning: Rewrite-Based GPU Code generation. In CASES. ACM, 15:1–15:10.
42. Michel Steuwer, Toomas Remmelg, and Christophe Dubach. 2017. Lift: A Functional Data-Parallel IR For High-Performance GPU Code generation. In CGO. ACM, 74–85.
43. Larisa Stoltzfus, Alan Gray, Christophe Dubach, and Stefan Bilbao. 2017. Performance Portability For Room Acoustics Simulations.
44. Robert Strzodka, Mohammed Shaheen, Dawid Pajak, and Hans-Peter Seidel. 2011. Cache Accurate Time Skewing In Iterative Stencil Computations. In ICPP. IEEE, 571–581.
45. Arvind K Sujeeth, Kevin J Brown, Hyoukjoong Lee, Tiark Rompf, Hassan Chafi, Martin Odersky, and Kunle Olukotun. 2014. Delite: A Compiler Architecture For Performance-Oriented Embedded DomainSpecific Languages. TECS (2014), 134.
46. Yuan Tang, Rezaul Alam Chowdhury, Bradley C Kuszmaul, Chi-Keung Luk, and Charles E Leiserson. 2011. The Pochoir Stencil Compiler. In SPAA . ACM, 117–128.
47. Abhishek Udupa, R Govindarajan, and Matthew J Thazhuthaveetil. 2009. Software Pipelined Execution Of Stream Programs On GPUs. In CGO . IEEE, 200–209.
48. Sven Verdoolaege, Juan Carlos Juega, Albert Cohen, José Ignacio Gómez, Christian Tenllado, and Francky Catthoor. 2013. Polyhedral Parallel Code Generation for CUDA. ACM Trans. Archit. Code Optim. 9, 4, Article 54 (Jan. 2013), 23 pages.
49. Craig Jonathan Webb. 2014. PArallel COmputation TEchniques For VIrtual ACoustics And PHysical MOdelling SYnthesis. (2014).
50. Gerhard Wellein, Georg Hager, Thomas Zeiser, Markus Wittmann, and Holger Fehske. 2009. Efficient Temporal Blocking For Stencil Computations By Multicore-Aware Wavefront Parallelization. In COMPSAC, Vol. 1. IEEE, 579–586.
51. Markus Wittmann, Georg Hager, and Gerhard Wellein. 2010. MulticoreAware Parallel Temporal Blocking Of Stencil Codes For Shared And Distributed Memory. In IPDPSW. IEEE, 1–7.
52. Xing Zhou. 2013. Tiling Optimizations For Stencil Computations. Ph.D. Dissertation. University of Illinois at Urbana-Champaign.

Index Terms

• Software and its engineering

  • Software notations and tools

    • Compilers

    • General programming languages

      • Language types

        • Parallel programming languages