More Web Proxy on the site http://driver.im/

research-article

Devito: automated fast finite difference computation

Authors:

Navjot Kukreja,

Mathias Louboutin,

Felippe Vieira,

Fabio Luporini,

Gerard GormanAuthors Info & Claims

WOLFHPC '16: Proceedings of the Sixth International Workshop on Domain-Specific Languages and High-Level Frameworks for HPC

Pages 11 - 19

Published: 13 November 2016 Publication History

Abstract

Domain specific languages have successfully been used in a variety of fields to cleanly express scientific problems as well as to simplify implementation and performance optimization on different computer architectures. Although a large number of stencil languages are available, finite difference domain specific languages have proved challenging to design because most practical use cases require additional features that fall outside the finite difference abstraction. Inspired by the complexity of real-world seismic imaging problems, we introduce Devito, a domain specific language in which high level equations are expressed using symbolic expressions from the SymPy package. Complex equations are automatically manipulated, optimized, and translated into highly optimized C code that aims to perform comparably or better than hand-tuned code. All this is transparent to users, who only see concise symbolic mathematical expressions.

References

[1]

A. Arbona, A. Artigues, C. Bona-Casas, J. Massó, B. Miñano, A. Rigo, M. Trias, and C. Bona. Simflowny: A general-purpose platform for the management of physical models and simulation problems. Computer Physics Communications, 184(10):2321--2331, 2013.

[2]

A. J. Bik, M. Girkar, P. M. Grey, and X. Tian. Automatic intra-register vectorization for the intel® architecture. International Journal of Parallel Programming, 30(2):65--98, 2002.

Digital Library

[3]

U. Bondhugula, A. Hartono, J. Ramanujam, and P. Sadayappan. A practical automatic polyhedral parallelizer and locality optimizer. In Proceedings of the 2008 ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI '08, pages 101--113, New York, NY, USA, 2008. ACM.

Digital Library

[4]

T. Brandvik and G. Pullan. Sblock: A framework for efficient stencil-based pde solvers on multi-core platforms. In Proceedings of the 2010 10th IEEE International Conference on Computer and Information Technology, CIT '10, pages 1181--1188, Washington, DC, USA, 2010. IEEE Computer Society.

Digital Library

[5]

A. F. Cárdenas and W. J. Karplus. Pdel---a language for partial differential equations. Communications of the ACM, 13(3):184--191, 1970.

Digital Library

[6]

M. Christen, O. Schenk, and H. Burkhart. Patus: A code generation and autotuning framework for parallel iterative stencil computations on modern microarchitectures. In Proceedings of the 2011 IEEE International Parallel & Distributed Processing Symposium, IPDPS '11, pages 676--687, Washington, DC, USA, 2011. IEEE Computer Society.

Digital Library

[7]

G. O. Cook Jr. Alpal: A tool for the development of large-scale simulation codes. Technical report, Lawrence Livermore National Lab., CA (USA), 1988.

[8]

K. Datta, M. Murphy, V. Volkov, S. Williams, J. Carter, L. Oliker, D. Patterson, J. Shalf, and K. Yelick. Stencil computation optimization and auto-tuning on state-of-the-art multicore architectures. In Proceedings of the 2008 ACM/IEEE Conference on Supercomputing, SC '08, pages 4:1--4:12, Piscataway, NJ, USA, 2008. IEEE Press.

Digital Library

[9]

E. Haber, M. Chung, and F. J. Herrmann. An effective method for parameter estimation with PDE constraints with multiple right hand sides. SIAM Journal on Optimization, 22(3), 7 2012.

[10]

K. A. Hawick and D. P. Playne. Simulation software generation using a domain-specific language for partial differential field equations. In 11th International Conference on Software Engineering Research and Practice (SERP'13), number CSTN-187, page SER3829, Las Vegas, USA, 22--25 July 2013. WorldComp.

[11]

T. Henretty, R. Veras, F. Franchetti, L.-N. Pouchet, J. Ramanujam, and P. Sadayappan. A stencil compiler for short-vector simd architectures. In Proceedings of the 27th International ACM Conference on International Conference on Supercomputing, ICS '13, pages 13--24, New York, NY, USA, 2013. ACM.

Digital Library

[12]

J. Jeffers and J. Reinders. Intel Xeon Phi coprocessor high-performance programming. Newnes, 2013.

Digital Library

[13]

M. D. Lam, E. E. Rothberg, and M. E. Wolf. The cache performance and optimizations of blocked algorithms. In ACM SIGARCH Computer Architecture News, volume 19, pages 63--74. ACM, 1991.

Digital Library

[14]

A. Logg, K.-A. Mardal, G. N. Wells, et al. Automated Solution of Differential Equations by the Finite Element Method. Springer, 2012.

Digital Library

[15]

F. Luporini, D. A. Ham, and P. H. J. Kelly. An algorithm for the optimization of finite element integration loops. Submitted to ACM Transactions on Mathematical Software (TOMS)., 2016.

[16]

G. R. Markall, F. Rathgeber, L. Mitchell, N. Loriant, C. Bertolli, D. A. Ham, and P. H. J. Kelly. Performance portable finite element assembly using PyOP2 and FEn-iCS. In Proceedings of the International Supercomputing Conference (ISC) '13, volume 7905 of Lecture Notes in Computer Science, June 2013. In press.

[17]

R. Membarth, F. Hannig, J. Teich, and H. Koöstler. Towards domain-specific computing for stencil codes in hpc. In High Performance Computing, Networking, Storage and Analysis (SCC), 2012 SC Companion:, pages 1133--1138. IEEE, 2012.

Digital Library

[18]

R.-E. Plessix. A review of the adjoint-state method for computing the gradient of a functional with geophysical applications. Geophysical Journal International, 167(2):495--503, 2006.

[19]

J. Ragan-Kelley, C. Barnes, A. Adams, S. Paris, F. Du-rand, and S. Amarasinghe. Halide: A language and compiler for optimizing parallelism, locality, and recomputation in image processing pipelines. In Proceedings of the 34th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI '13, pages 519--530, New York, NY, USA, 2013. ACM.

Digital Library

[20]

F. Rathgeber, D. A. Ham, L. Mitchell, M. Lange, F. Luporini, A. T. T. McRae, G. Bercea, G. R. Markall, and P. H. J. Kelly. Firedrake: automating the finite element method by composing abstractions. CoRR, abs/1501.01809, 2015.

[21]

I. Z. Reguly, G. R. Mudalige, M. B. Giles, D. Curran, and S. McIntosh-Smith. The ops domain specific abstraction for multi-block structured grid computations. In Proceedings of the Fourth International Workshop on Domain-Specific Languages and High-Level Frameworks for High Performance Computing, WOLFHPC '14, pages 58--67, Piscataway, NJ, USA, 2014. IEEE Press.

Digital Library

[22]

Symes. Reverse time migration with optimal checkpointing. GEOPHYSICS, 72(5):SM213--SM221, 2007.

[23]

C. Terboven, D. Schmidl, H. Jin, T. Reichstein, et al. Data and thread affinity in openmp programs. In Proceedings of the 2008 workshop on Memory access on future processors: a solved problem?, pages 377--384. ACM, 2008.

Digital Library

[24]

Y. Umetani. Deqsol a numerical simulation language for vector/parallel processors. Proc. IFIP TC2/WG22, 1985, 5:147--164, 1985.

[25]

D. Unat, J. Zhou, Y. Cui, S. B. Baden, and X. Cai. Accelerating a 3d finite-difference earthquake simulation with a c-to-cuda translator. Computing in Science and Engg., 14(3):48--59, May 2012.

Digital Library

[26]

R. Van Engelen, L. Wolters, and G. Cats. Ctadel: A generator of multi-platform high performance codes for pde-based scientific applications. In Proceedings of the 10th international conference on Supercomputing, pages 86--93. ACM, 1996.

Digital Library

[27]

J. Virieux and S. Operto. An overview of full-waveform inversion in exploration geophysics. GEOPHYSICS, 74(5):WCC1--WCC26, 2009.

[28]

W. H. Wen-mei. GPU Computing Gems Jade Edition. Elsevier, 2011.

Digital Library

[29]

Y. Zhang and F. Mueller. Auto-generation and autotuning of 3d stencil codes on gpu clusters. In Proceedings of the Tenth International Symposium on Code Generation and Optimization, CGO '12, pages 155--164, New York, NY, USA, 2012. ACM.

Digital Library

Cited By

Burrows EFriis HHaveraaen MScholz SShivers O(2018)An array API for finite difference methodsProceedings of the 5th ACM SIGPLAN International Workshop on Libraries, Languages, and Compilers for Array Programming10.1145/3219753.3219761(59-66)Online publication date: 19-Jun-2018
https://dl.acm.org/doi/10.1145/3219753.3219761

Recommendations

Devito: towards a generic finite difference DSL using symbolic Python
PyHPC '16: Proceedings of the 6th Workshop on Python for High-Performance and Scientific Computing

Domain specific languages (DSL) have been used in a variety of fields to express complex scientific problems in a concise manner and provide automated performance optimization for a range of computational architectures. As such DSLs provide a powerful ...
Architecture and Performance of Devito, a System for Automated Stencil Computation

Stencil computations are a key part of many high-performance computing applications, such as image processing, convolutional neural networks, and finite-difference solvers for partial differential equations. Devito is a framework capable of generating ...
Layout-sensitive language extensibility with SugarHaskell
Haskell '12: Proceedings of the 2012 Haskell Symposium

Programmers need convenient syntax to write elegant and concise programs. Consequently, the Haskell standard provides syntactic sugar for some scenarios (e.g., do notation for monadic code), authors of Haskell compilers provide syntactic sugar for more ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

WOLFHPC '16: Proceedings of the Sixth International Workshop on Domain-Specific Languages and High-Level Frameworks for HPC

November 2016

44 pages

ISBN:9781509061563

Sponsors

SIGHPC: ACM Special Interest Group on High Performance Computing, Special Interest Group on High Performance Computing
IEEE-CS\DATC: IEEE Computer Society

In-Cooperation

SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

IEEE Press

Publication History

Published: 13 November 2016

Check for updates

Qualifiers

Research-article

Conference

SC16

Sponsor:

SIGHPC
IEEE-CS\DATC

SC16: The International Conference for High Performance Computing, Networking, Storage and Analysis

November 13 - 18, 2016

Utah, Salt Lake City

Acceptance Rates

WOLFHPC '16 Paper Acceptance Rate 4 of 6 submissions, 67%;

Overall Acceptance Rate 13 of 19 submissions, 68%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 16 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Burrows EFriis HHaveraaen MScholz SShivers O(2018)An array API for finite difference methodsProceedings of the 5th ACM SIGPLAN International Workshop on Libraries, Languages, and Compilers for Array Programming10.1145/3219753.3219761(59-66)Online publication date: 19-Jun-2018
https://dl.acm.org/doi/10.1145/3219753.3219761

View Options

View options

Media

Figures

Other

Tables

View Table of Contents