research-article

Open access

PAGANI: a parallel adaptive GPU algorithm for numerical integration

Authors:

Ioannis Sakiotis,

Kamesh Arumugam,

Balša Terzić,

Mohammad ZubairAuthors Info & Claims

SC '21: Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis

Article No.: 83, Pages 1 - 13

https://doi.org/10.1145/3458817.3476198

Published: 13 November 2021 Publication History

Abstract

We present a new adaptive parallel algorithm for the challenging problem of multi-dimensional numerical integration on massively parallel architectures. Adaptive algorithms have demonstrated the best performance, but efficient many-core utilization is difficult to achieve because the adaptive work-load can vary greatly across the integration space and is impossible to predict a priori. Existing parallel algorithms utilize sequential computations on independent processors, which results in bottlenecks due to the need for data redistribution and processor synchronization. Our algorithm employs a high-throughput approach in which all existing sub-regions are processed and sub-divided in parallel. Repeated sub-region classification and filtering improves upon a brute-force approach and allows the algorithm to make efficient use of computation and memory resources. A CUDA implementation shows orders of magnitude speedup over the fastest open-source CPU method and extends the achievable accuracy for difficult integrands. Our algorithm typically outperforms other existing deterministic parallel methods.

Supplementary Material

MP4 File (PAGANI A Parallel Adaptive GPU Algorithm for Numerical Integration.mp4)

Presentation video

Download
285.47 MB

References

[1]

Pierre L'Ecuyer. Quasi-monte carlo methods with applications in finance. Finance and Stochastics, 13:307--349, 09 2009.

[2]

Wojciech Jarosz. Efficient Monte Carlo Methods for Light Transport in Scattering Media. PhD thesis, UC San Diego, September 2008.

[3]

J. Zuntz, M. Paterno, E. Jennings, D. Rudd, A. Manzotti, S. Dodelson, S. Bridle, S. Sehrish, and J. Kowalkowski. Cosmosis: Modular cosmological parameter estimation. Astronomy and Computing, 12:45--59, 2015.

[4]

Kamesh Arumugam, Desh Ranjan, Mohammad Zubair, Alexander Godunov, and Balša Terzić. High-fidelity simulation of collective effects in electron beams using an innovative parallel method. In Proceedings of the Conference on Summer Computer Simulation, SummerSim '15, page 1--10, San Diego, CA, USA, 2015. Society for Computer Simulation International.

Digital Library

[5]

G. Peter Lepage. VEGAS: AN ADAPTIVE MULTIDIMENSIONAL INTEGRATION PROGRAM. 3 1980.

[6]

Jarle Berntsen, Terje O. Espelid, and Alan Genz. Algorithm 698: Dcuhre: An adaptive multidemensional integration routine for a vector of integrals. ACM Trans. Math. Softw., 17(4):452--456, December 1991.

[7]

T. Hahn. Cuba-a library for multidimensional numerical integration. Computer Physics Communications, 168(2):78--95, 2005.

[8]

Paul van Dooren and Luc de Ridder. An adaptive algorithm for numerical integration over an n-dimensional cube. Journal of Computational and Applied Mathematics, 2(3):207--217, 1976.

[9]

J. Berntsen and T. O. Espelid. An adaptive multidimensional integration routine for a vector of integrals. ACM Transactions on Mathematical Software, 1991.

[10]

R. Piessens, E. de Doncker-Kapenga, C.W. Überhuber, and D.K. Kahaner. Quad-pack: A Subroutine Package for Automatic Integration. Springer Series in Computational Mathematics. Springer Berlin Heidelberg, 2012.

[11]

The NAG Library. The Numerical Algorithms Group (NAG), www.nag.com.

[12]

K. Arumugam, A. Godunov, D. Ranjan, B. Terzic, and M. Zubair. An efficient deterministic parallel algorithm for adaptive multidimensional numerical integration on gpus. In 2013 42nd International Conference on Parallel Processing, pages 486--491, 2013.

Digital Library

[13]

Jarle Berntsen, Terje Espelid, and Alan Genz. An adaptive algorithm for the approximate calculation of multiple integrals. ACM Transactions on Mathematical Software, 17:437--451, 12 1991.

Digital Library

[14]

T. Hahn. Concurrent cuba, 2014.

[15]

K. Arumugam, A. Godunov, D. Ranjan, B. Terzić, and M. Zubair. A memory efficient algorithm for adaptive multidimensional integration with multiple gpus. In 20th Annual International Conference on High Performance Computing, pages 169--175, 2013.

[16]

Michael Griebel Hans-Joachim Bungartz. Sparse grids. Acta Numerica, 13:147--269, 6 2004.

[17]

Michael Griebel and Jens Oettershagen. Dimension-adaptive sparse grid quadrature for integrals with boundary singularities. In Jochen Garcke and Dirk Pflüger, editors, Sparse Grids and Applications - Munich 2012, pages 109--136, Cham, 2014. Springer International Publishing.

[18]

Hans-Joachim Bungartz and Stefan Dirnstorfer. Multivariate quadrature on adaptive sparse grids. Computing, 71(1):89--114, September 2003.

Digital Library

[19]

Thomas Gerstner and Michael Griebel. Numerical integration using sparse grids. Numerical Algorithms, 18(3):209--232, January 1998.

[20]

T. Goda and K. Suzuki. Recent advances in higher order quasi-monte carlo methods. arXiv: Numerical Analysis, 2019.

[21]

Dirk Nuyens and Ronald Cools. Higher order quasi-monte carlo methods: A comparison. AIP Conference Proceedings, 1281(1):553--557, 2010.

[22]

Russel E. Caflisch. Monte carlo and quasi-monte carlo methods. Acta Numerica, 7:1--49, January 1998.

[23]

A. C. Genz and A. A. Malik. An imbedded family of fully symmetric numerical integration rules. SIAM journal on numerical analysis, 20(3):580--588, 1983.

[24]

J. Berntsen. Practical error estimation in adaptive multidimensional quadrature routines. J. Comput. Appl. Math., 25(3):327--340, May 1989.

Digital Library

[25]

Daniel Thuerck, Sven Widmer, Arjan Kuijper, and Michael Goesele. Efficient heuristic adaptive quadrature on gpus: Design and evaluation. In Roman Wyrzykowski, Jack Dongarra, Konrad Karczewski, and Jerzy Waśniewski, editors, Parallel Processing and Applied Mathematics, pages 652--662, Berlin, Heidelberg, 2014. Springer Berlin Heidelberg.

[26]

Giuliano Laccetti, Marco Lapegna, Valeria Mele, and Diego Romano. A study on adaptive algorithms for numerical quadrature on heterogeneous gpu and multicore based systems. In Roman Wyrzykowski, Jack Dongarra, Konrad Karczewski, and Jerzy Waśniewski, editors, Parallel Processing and Applied Mathematics, pages 704--713, Berlin, Heidelberg, 2014. Springer Berlin Heidelberg.

[27]

S. Borowka, G. Heinrich, S. Jahn, S.P. Jones, M. Kerner, and J. Schlenk. A gpu compatible quasi-monte carlo integrator interfaced to pysecdec. Computer Physics Communications, 240:120--137, Jul 2019.

[28]

Alan Genz. Testing multidimensional integration routines. In Proc. of International Conference on Tools, Methods and Languages for Scientific and Engineering Computation, page 81--94, USA, 1984. Elsevier North-Holland, Inc.

Digital Library

[29]

Nathan Bell and Jared Hoberock. Chapter 26 - thrust: A productivity-oriented library for cuda. In Wen mei W. Hwu, editor, GPU Computing Gems Jade Edition, Applications of GPU Computing Series, pages 359--371. Morgan Kaufmann, Boston, 2012.

Cited By

Hu YZhang FXia YYao ZZeng LDing HWei ZZhang XZhai JDu XMa S(2023)Enabling Efficient Random Access to Hierarchically Compressed Text Data on Diverse GPU PlatformsIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2023.329434134:10(2699-2717)Online publication date: 1-Oct-2023
https://dl.acm.org/doi/10.1109/TPDS.2023.3294341
Sakiotis IArumugam KPaterno MRanjan DTerzić BZubair M(2023)Porting Numerical Integration Codes from CUDA to oneAPI: A Case StudyHigh Performance Computing10.1007/978-3-031-32041-5_18(339-358)Online publication date: 21-May-2023
https://dl.acm.org/doi/10.1007/978-3-031-32041-5_18
Zhang FHu YDing HYao ZWei ZZhang XDu X(2022)Optimizing Random Access to Hierarchically-Compressed Data on GPUSC22: International Conference for High Performance Computing, Networking, Storage and Analysis10.1109/SC41404.2022.00023(1-15)Online publication date: Nov-2022
https://doi.org/10.1109/SC41404.2022.00023
Show More Cited By

Index Terms

PAGANI: a parallel adaptive GPU algorithm for numerical integration
1. Computing methodologies

Recommendations

A Comparison of 12 Parallel FORTRAN Dialects

A simple program that approximates pi by numerical quadrature is rewritten to run on nine commercially available processors to illustrate the compilations that arise in parallel programming in FORTRAN. The machines used are the Alliant FX/8, BBN ...
Adaptive Optimization for Petascale Heterogeneous CPU/GPU Computing
CLUSTER '10: Proceedings of the 2010 IEEE International Conference on Cluster Computing

In this paper, we describe our experiment developing an implementation of the Linpack benchmark for TianHe-1, a petascale CPU/GPU supercomputer system, the largest GPU-accelerated system ever attempted before. An adaptive optimization framework is ...
Preliminary experiences with the uintah framework on Intel Xeon Phi and stampede
XSEDE '13: Proceedings of the Conference on Extreme Science and Engineering Discovery Environment: Gateway to Discovery

In this work, we describe our preliminary experiences on the Stampede system in the context of the Uintah Computational Framework. Uintah was developed to provide an environment for solving a broad class of fluid-structure interaction problems on ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SC '21: Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis

November 2021

1493 pages

ISBN:9781450384421

DOI:10.1145/3458817

General Chair:
Bronis R. de Supinski,
Program Chairs:
Mary Hall,
Todd Gamblin

Copyright © 2021 ACM.

© 2021 Association for Computing Machinery. ACM acknowledges that this contribution was authored or co-authored by an employee, contractor or affiliate of the United States government. As such, the United States Government retains a nonexclusive, royalty-free right to publish or reproduce this article, or to allow others to do so, for Government purposes only.

Sponsors

SIGHPC: ACM Special Interest Group on High Performance Computing, Special Interest Group on High Performance Computing

In-Cooperation

IEEE CS

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 November 2021

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Badges

Author Tags

Qualifiers

Research-article

Conference

SC '21

Sponsor:

SIGHPC

SC '21: The International Conference for High Performance Computing, Networking, Storage and Analysis

November 14 - 19, 2021

Missouri, St. Louis

Acceptance Rates

Overall Acceptance Rate 1,516 of 6,373 submissions, 24%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
477
Total Downloads

Downloads (Last 12 months)129
Downloads (Last 6 weeks)25

Reflects downloads up to 16 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Hu YZhang FXia YYao ZZeng LDing HWei ZZhang XZhai JDu XMa S(2023)Enabling Efficient Random Access to Hierarchically Compressed Text Data on Diverse GPU PlatformsIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2023.329434134:10(2699-2717)Online publication date: 1-Oct-2023
https://dl.acm.org/doi/10.1109/TPDS.2023.3294341
Sakiotis IArumugam KPaterno MRanjan DTerzić BZubair M(2023)Porting Numerical Integration Codes from CUDA to oneAPI: A Case StudyHigh Performance Computing10.1007/978-3-031-32041-5_18(339-358)Online publication date: 21-May-2023
https://dl.acm.org/doi/10.1007/978-3-031-32041-5_18
Zhang FHu YDing HYao ZWei ZZhang XDu X(2022)Optimizing Random Access to Hierarchically-Compressed Data on GPUSC22: International Conference for High Performance Computing, Networking, Storage and Analysis10.1109/SC41404.2022.00023(1-15)Online publication date: Nov-2022
https://doi.org/10.1109/SC41404.2022.00023
Sakiotis IArumugam KPaterno MRanjan DTerzić BZubair M(2022)m-Cubes: An Efficient and Portable Implementation of Multi-dimensional Integration for GPUsHigh Performance Computing10.1007/978-3-031-07312-0_10(192-209)Online publication date: 29-May-2022
https://dl.acm.org/doi/10.1007/978-3-031-07312-0_10

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Figures

Tables

Media

View Table of Conten