Abstract
Algorithms with space-time tiling increase the performance of numerical simulations by increasing data reuse and arithmetic intensity; they also improve parallel scaling by making process synchronization less frequent. The theory of Locally Recursive non-Locally Asynchronous (LRnLA) algorithms provides the performance model with account for data localization at all levels of the memory hierarchy. However, effective implementation is difficult since modern optimizing compilers do not support the required traversal methods and data structures by default. The data exchange is typically implemented by writing the updated values to the main data array. Here, we suggest a new data structure that contains the partially updated state of the simulation domain. Data is arranged within this structure for coalesced access and seamless exchange between subtasks. We demonstrate the preliminary results of its superiority over previously used methods by localizing the processed data in the L2 GPU cache for the Lattice Boltzmann Method (LBM) simulation so that the performance is not limited by the GDDR throughput but is determined by the L2 cache access rate. If we estimate the ideal stepwise code performance to be memory-bound with a read/write ratio equal to 1 and assume it is localized in the GPU memory and performs at 100% of the theoretical memory bandwidth, then the results of our benchmarks exceed that peak by a factor of the order of 1.2.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Akbudak, K., Ltaief, H., Etienne, V., Abdelkhalak, R., Tonellot, T., Keyes, D.: Asynchronous computations for solving the acoustic wave propagation equation. Int. J. High Perf. Comput. Appl. 1094342020923027 (2020)
Korneev, B., Levchenko, V.: Detailed numerical simulation of shock-body interaction in 3D multicomponent flow using the RKDG numerical method and “DiamondTorre” GPU algorithm of implementation. J. Phys. Conf. Ser. 681, 012046 (2016)
Krüger, T., Kusumaatmaja, H., Kuzmin, A., Shardt, O., Silva, G., Viggen, E.M.: The Lattice Boltzmann Method. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-44649-3
Levchenko, V., Perepelkina, A.: Locally recursive non-locally asynchronous algorithms for stencil computation. Lobachevskii J. Math. 39(4), 552–561 (2018). https://doi.org/10.1134/S1995080218040108
Perepelkina, A., Levchenko, V., Zakirov, A.: New compact streaming in LBM with ConeFold LRnLA algorithms. In: Voevodin, V., Sobolev, S. (eds.) RuSCDays 2020. CCIS, vol. 1331, pp. 50–62. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-64616-5_5
Levchenko, V., Zakirov, A., Perepelkina, A.: GPU implementation of ConeTorre algorithm for fluid dynamics simulation. In: Malyshkin, V. (ed.) PaCT 2019. LNCS, vol. 11657, pp. 199–213. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-25636-4_16
Malas, T.M., Hager, G., Ltaief, H., Keyes, D.E.: Multidimensional intratile parallelization for memory-starved stencil computations. ACM Trans. Parallel Comput. (TOPC) 4(3), 1–32 (2017)
Muraoka, Y.: Parallelism exposure and exploitation in programs. Ph.D. thesis, USA (1971). AAI7121189
Perepelkina, A., Levchenko, V.: Synchronous and asynchronous parallelism in the LRnLA algorithms. In: Sokolinsky, L., Zymbler, M. (eds.) PCT 2020. CCIS, vol. 1263, pp. 146–161. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-55326-5_11
Perepelkina, A., Levchenko, V., Zakirov, A.: Extending the problem data size for GPU simulation beyond the GPU memory storage with LRnLA algorithms. J. Phys. Conf. Ser. 1740, 012,054 (2021). https://doi.org/10.1088/1742-6596/1740/1/012054
Perepelkina, A.Y., Goryachev, I.A., Levchenko, V.D.: CFHall code validation with 3D3V Weibel instability simulation. J. Phys. Conf. Ser. 441, 012,014 (2013). https://doi.org/10.1088/1742-6596/441/1/012014
Strzodka, R., Shaheen, M., Pajak, D., Seidel, H.P.: Cache accurate time skewing in iterative stencil computations. In: 2011 International Conference on Parallel Processing, pp. 571–581. IEEE (2011)
Vardhan, M., Gounley, J., Hegele, L., Draeger, E.W., Randles, A.: Moment representation in the lattice Boltzmann method on massively parallel hardware. In: Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, pp. 1–21 (2019)
Wellein, G., Hager, G., Zeiser, T., Wittmann, M., Fehske, H.: Efficient temporal blocking for stencil computations by multicore-aware wavefront parallelization. In: 2009 33rd Annual IEEE International Computer Software and Applications Conference, vol. 1, pp. 579–586. IEEE (2009)
Williams, S., Waterman, A., Patterson, D.: Roofline: an insightful visual performance model for multicore architectures. Commun. ACM 52(4), 65–76 (2009)
Wolfe, M.: Loops skewing: the wavefront method revisited. Int. J. Parallel Prog. 15(4), 279–293 (1986)
Wonnacott, D.: Time skewing for parallel computers. In: Carter, L., Ferrante, J. (eds.) LCPC 1999. LNCS, vol. 1863, pp. 477–480. Springer, Heidelberg (2000). https://doi.org/10.1007/3-540-44905-1_35
Yount, C., Duran, A.: Effective use of large high-bandwidth memory caches in HPC stencil computation via temporal wave-front tiling. In: 2016 7th International Workshop on Performance Modeling, Benchmarking and Simulation of High Performance Computer Systems (PMBS), pp. 65–75. IEEE, Salt Lake (2016). https://doi.org/10.1109/PMBS.2016.012. http://ieeexplore.ieee.org/document/7836415/
Zakirov, A., Levchenko, V., Ivanov, A., Perepelkina, A., Levchenko, T., Rok, V.: High-performance 3D modeling of a full-wave seismic field for seismic survey tasks. Geoinformatika 3, 34–45 (2017)
Zakirov, A., Levchenko, V., Perepelkina, A., Zempo, Y.: High performance FDTD algorithm for GPGPU supercomputers. J. Phys. Conf. Ser. 759, 012100 (2016). https://doi.org/10.1088/1742-6596/759/1/012100
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Appendix
Appendix
In the compact scheme for LBM [5] (see Fig. 9) in a group of \(2\times 2\times 2\) cells, the \(f_q\) value for the collision in a cell is taken from the cell with the other \(x_\alpha \) if the projection of \(\mathbf{o}_q\) on the \(\alpha \) axis is negative. Otherwise, the value is taken from the cell with the same \(x_\alpha \) as the collision cell. After the collision in the cell, \(f_q\) is written to the cell with different \(x_\alpha \) only if the projection of \(\mathbf{o}_q\) on the \(\alpha \) axis is positive. The collision in \(\mathbf{x}_i\) is mirrored in the \(\alpha \) direction if \(x_{i\alpha }=1\). The connection between \(\mathbf{o}\) and \(\mathbf{c}_q\) is defined in the collision state, namely \(o_{q\alpha }=c_{q\alpha }\) if \(x_{i\alpha }=0\), and \(o_{q\alpha }=-c_{q\alpha }\) otherwise. With \(f_q\) mirroring, the code is especially simple, without the need to find the q index correspondence between DDF values (see Fig. 10). Thus, the three steps of the compact streaming scheme for LBM (see Fig. 9) are:
-
1.
de-compact (put into the collision state);
-
2.
collision;
-
3.
compact (put into the compacted state).
In the present paper, they are restated in the order (2)-(3)-(1) (see Fig. 10), so that the values are stored in tiles in the pre-collision state, and each cell contains its own DDFs. However, the DDFs in cells with an odd coordinate are still mirrored in the direction of that coordinate.
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Perepelkina, A., Levchenko, V.D. (2021). Functionally Arranged Data for Algorithms with Space-Time Wavefront. In: Sokolinsky, L., Zymbler, M. (eds) Parallel Computational Technologies. PCT 2021. Communications in Computer and Information Science, vol 1437. Springer, Cham. https://doi.org/10.1007/978-3-030-81691-9_10
Download citation
DOI: https://doi.org/10.1007/978-3-030-81691-9_10
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-81690-2
Online ISBN: 978-3-030-81691-9
eBook Packages: Computer ScienceComputer Science (R0)