Enabling Bitwise Reproducibility for the Unstructured Computational Motif
Source abstract
Abstract
In this paper we identify the causes of numerical non-reproducibility in the unstructured mesh computational motif, a class of algorithms commonly used for the solution of PDEs. We introduce a number of parallel and distributed algorithms to address nondeterminism in the order of floating-point computations, in particular, a new graph coloring scheme that produces identical coloring results regardless of how many parts the graph is partitioned to. We implement these in the OP2 domain specific language (DSL) and show how it can be automatically deployed to any application that uses OP2 without user intervention. We contrast differences in results without reproducibility and then demonstrate how bitwise reproducibility can be gained using our methods on a variety of applications including a production CFD application used at Rolls-Royce. We evaluate the performance and overheads of enforcing bitwise reproducibility on a cluster of CPUs and GPUs.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Parallel Computing and Optimization Techniques · Numerical Methods and Algorithms · Advanced Data Storage Technologies
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
Faculty of Information Technology and Bionics, Pázmány Péter Catholic University, 1088 Budapest, Hungary
Department of Computer Science, University of Warwick, Coventry CV4 7AL, UK
Funding
National Research, Development and Innovation Fund of Hungary · Engineering and Physical Sciences Research Council
References (58)
Show source-provided references
1. What Every Computer Scientist Should Know about Floating-Point Arithmetic10.1145/103162.103163 ↗
2. The white rat of numerical reproducibility10.1063/5.0057176 ↗
3. Langlois, P., Nheili, R., and Denis, C. (2015, January 27–29). Numerical reproducibility: Feasibility issues. Proceedings of the 2015 7th International Conference on New Technologies, Mobility and Security (NTMS), Paris, France.10.1109/NTMS.2015.7266509 ↗
4. Using Accurate Arithmetics to Improve Numerical Reproducibility and Stability in Parallel Applications10.1023/A:1008153532043 ↗
5. Taufer, M., Padron, O., Saponaro, P., and Patel, S. (2010, January 19–23). Improving numerical reproducibility and stability in large-scale numerical simulations on GPUs. Proceedings of the 2010 IEEE International Symposium on Parallel Distributed Processing (IPDPS), Atlanta, GA, USA.10.1109/IPDPS.2010.5470481 ↗
6. Full-neighbor-list based numerical reproducibility method for parallel molecular dynamics simulations10.1016/j.parco.2019.04.002 ↗
7. In Search of Numerical Consistency in Parallel Programming10.1016/j.parco.2011.02.009 ↗
8. Chandrasekaran, S., and Juckeland, G. (2018). Accelerator Programming Using Directives: Proceedings of the Fourth Workshop on Accelerator Programming Using Directives (WACCPD 2017), Newark, DE, USA, 13 November 2017, Springer. Lecture Notes in Computer Science.10.1007/978-3-319-74896-2 ↗
9. Salgado-Estrada, R., Galván, A., Moreno-Martínez, J.Y., Elvira-Hernández, E.A., Carpio, F., Herrera-May, A.L., Zamora Castro, S.A., and Herrera-Díaz, I.E. (2023). Wind Vulnerability of Flexible Outdoor Single-Post Billboards. Appl. Sci., 13.10.3390/app13106197 ↗
10. An, X., Li, S., and Wu, T. (2023). Modeling Nonlinear Aeroelastic Forces for Bridge Decks with Various Leading Edges Using LSTM Networks. Appl. Sci., 13.10.3390/app13106005 ↗
11. Pracniques: Further Remarks on Reducing Truncation Errors10.1145/363707.363723 ↗
12. Demmel, J., and Nguyen, H.D. (2013, January 7–10). Fast Reproducible Floating-Point Summation. Proceedings of the 2013 IEEE 21st Symposium on Computer Arithmetic, Austin, TX, USA.10.1109/ARITH.2013.9 ↗
13. Chohra, C., Langlois, P., and Parello, D. (2016, January 24–26). Reproducible, Accurately Rounded and Efficient BLAS. Proceedings of the Euro-Par 2016 Parallel Processing Workshops, Grenoble, France.10.1007/978-3-319-58943-5_49 ↗
14. (2023, October 16). Open TELEMAC-MASCARET. v.7.0, Release Notes. Available online: www.opentelemac.org.
15. Colella, P. (2004, January 1). Defining software requirements for scientific computing. Proceedings of the DARPA HPCS Presentation, Arlington, VA, USA.
16. Demmel, J., Ahrens, P., and Nguyen, H.D. (2016). Efficient Reproducible Floating Point Summation and BLAS, EECS Department, University of California. Technical Report UCB/EECS-2016-121.
17. Jalal Apostal, S.F., Apostal, D., and Marsh, R. (August, January 31). Improving Numerical Reproducibility of Scientific Software in Parallel Systems. Proceedings of the 2020 IEEE International Conference on Electro Information Technology (EIT), Chicago, IL, USA.10.1109/EIT48999.2020.9208338 ↗
18. Siklósi, B., Reguly, I.Z., and Mudalige, G.R. (2020, January 11–14). Bitwise Reproducible task execution on unstructured mesh applications. Proceedings of the 2020 20th IEEE/ACM International Symposium on Cluster, Cloud and Internet Computing (CCGRID), Melbourne, VIC, Australia.10.1109/CCGrid49817.2020.00015 ↗
19. Using Automatic Difierentiation for Adjoint CFD Code Development
20. Zienkiewicz, O., Taylor, R., and Zhu, J. (2013). The Finite Element Method: Its Basis and Fundamentals, Butterworth-Heinemann. [7th ed.].
21. (2021, May 20). MG-CFD-OP2 GitHub Repository. Available online: https://github.com/warwick-hpsc/MG-CFD-app-OP2.
22. Acceleration of a Full-Scale Industrial CFD Application with OP210.1109/TPDS.2015.2453972 ↗
23. LAMMPS—A flexible simulation tool for particle-based materials modeling at the atomic, meso, and continuum scales10.1016/j.cpc.2021.108171 ↗
24. Hida, Y., Li, S., and Bailey, D. (2008). Library for Double-Double and Quad-Double Arithmetic, Massachusetts Institute of Technology (MIT).
25. A summation algorithm with error correction for parallel computers10.1002/scj.4690240706 ↗
26. Knuth, D.E. (1997). The Art of Computer Programming, Addison Wesley Longman Publishing Co., Inc.. [3rd ed.].
27. Reproducible execution of SR programs10.1002/(SICI)1096-9128(19990810)11:9<479::AID-CPE441>3.0.CO;2-S ↗
28. Zhang, J., Dai, Z., Li, R., Deng, L., Liu, J., and Zhou, N. (2023). Acceleration of a Production-Level Unstructured Grid Finite Volume CFD Code on GPU. Appl. Sci., 13.10.3390/app13106193 ↗
29. (1985). IEEE Standard for Binary Floating-Point Arithmetic (Standard No. ANSI/IEEE 754-1985).
30. Reengineering for Parallelism: An entry point into PLPP for legacy applications10.1002/cpe.1147 ↗
31. The Collaboratory for the Study of Earthquake Predictability perspective on computational earthquake science10.1002/cpe.1519 ↗
32. Teodosio, L., Marchitto, L., Tornatore, C., Bozza, F., and Valentino, G. (2021). Effect of Cylinder-by-Cylinder Variation on Performance and Gaseous Emissions of a PFI Spark Ignition Engine: Experimental and 1D Numerical Study. Appl. Sci., 11.10.3390/app11136035 ↗
33. Ren, J., Zeng, Y., Zhou, S., and Zhang, Y. (2021). An Experimental Study on State Representation Extraction for Vision-Based Deep Reinforcement Learning. Appl. Sci., 11.10.3390/app112110337 ↗
34. Sergi, P.N., De la Oliva, N., del Valle, J., Navarro, X., and Micera, S. (2021). Physically Consistent Scar Tissue Dynamics from Scattered Set of Data: A Novel Computational Approach to Avoid the Onset of the Runge Phenomenon. Appl. Sci., 11.10.3390/app11188568 ↗
35. Elster, L., Staab, J.P., and Peters, S. (2023). Making Automotive Radar Sensor Validation Measurements Comparable. Appl. Sci., 13.10.20944/preprints202308.2045.v1 ↗
36. NIC-based Reduction Algorithms for Large-scale Clusters
37. A long accumulator like a carry-save adder10.1007/s00607-011-0164-x ↗
38. Atmanspacher, H., and Maasen, S. (2016). Reproducibility: Principles, Problems, Practices, and Prospects, John Wiley & Sons.10.1002/9781118865064 ↗
39. Arteaga, A., Fuhrer, O., and Hoefler, T. (2014, January 19–23). Designing Bit-Reproducible Portable High-Performance Applications. Proceedings of the 2014 IEEE 28th International Parallel and Distributed Processing Symposium, Phoenix, AZ, USA.10.1109/IPDPS.2014.127 ↗
40. (2019). IEEE Standard for Floating-Point Arithmetic (Standard No. IEEE Std 754-2019 (Revision of IEEE 754-2008)).
41. Ahrens, P., Nguyen, H.D., and Demmel, J. (2015). Efficient Reproducible Floating Point Summation and BLAS, EECS Department, University of California. Technical Report UCB/EECS-2015-229.
42. Firedrake: Automating the Finite Element Method by Composing Abstractions
43. Logg, A., Mardal, K.-A., and Wells, G. (2012). Automated Solution of Differential Equations by the Finite Element Method, Springer.10.1007/978-3-642-23099-8 ↗
44. NASA (2024, January 03). FUN3D Manual: 13.6, Available online: https://ntrs.nasa.gov/citations/20190033239.
45. Mudalige, G., Giles, M., Reguly, I., Bertolli, C., and Kelly, P. (2012, January 13–14). OP2: An active library framework for solving unstructured mesh-based applications on multi-core and many-core architectures. Proceedings of the 2012 Innovative Parallel Computing Conference (InPar), San Jose, CA, USA.10.1109/InPar.2012.6339594 ↗
46. PT-Scotch: A tool for efficient parallel graph ordering10.1016/j.parco.2007.12.001 ↗
47. Karypis, G. (2011). Encyclopedia of Parallel Computing, Springer.
48. Zhang, X., Sun, X., Guo, X., Du, Y., Lu, Y., and Liu, Y. (2020, January 9–11). Re-evaluation of Atomic Operations and Graph Coloring for Unstructured Finite Volume GPU Simulations. Proceedings of the 2020 IEEE 32nd International Symposium on Computer Architecture and High Performance Computing (SBAC-PAD), Porto, Portugal.10.1109/SBAC-PAD49847.2020.00048 ↗
49. Locality optimized unstructured mesh algorithms on GPUs10.1016/j.jpdc.2019.07.011 ↗
50. Bertolli, C., Betts, A., Mudalige, G., Giles, M., and Kelly, P. (September, January 29). Design and Performance of the OP2 Library for Unstructured Mesh Applications. Proceedings of the Euro-Par 2011: Parallel Processing Workshops, Bordeaux, France.10.1007/978-3-642-29737-3_22 ↗
51. Corrigan, A., Camelli, F., Löhner, R., and Wallin, J. (2009;, January 22–25). Running Unstructured Grid CFD Solvers on Modern Graphics Hardware. Proceedings of the 19th AIAA Computational Fluid Dynamics Conference, Palm Springs, CA, USA.10.2514/6.2009-4001 ↗
52. (2019, November 08). Rodinia: Accelerating Compute-Intensive Applications with Accelerators. Available online: https://rodinia.cs.virginia.edu/.
53. An Unstructured CFD Mini-Application for the Performance Prediction of a Production CFD Code10.1002/cpe.5443 ↗
54. Lapworth, L. (July, January 30). Hydra-CFD: A framework for collaborative CFD development. Proceedings of the International Conference on Scientific and Engineering Computation (IC-SEC), Singapore.
55. Edge-Based Multigrid and Preconditioning for Hybrid Grids10.2514/2.1556 ↗
56. Algorithm Developments for Discrete Adjoint Methods10.2514/2.1961 ↗
57. Osama, M., Truong, M., Yang, C., Buluç, A., and Owens, J. (2019, January 20–24). Graph Coloring on the GPU. Proceedings of the 2019 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW), Rio de Janeiro, Brazil.10.1109/IPDPSW.2019.00046 ↗
58. Algorithm Alley: Hash Functions