Speaker
Andrey Ivanov
(Moscow Institute of Physics and Technology)
Description
We consider well known cache optimization techniques to find the most efficient one when applied to grid-characteristic method. Grid-characteristic method is used to solve elastic wave equation. Elastic wave equation is hyperbolic system of equations inferred from model of linear elastic material, which describes propagation of elastic waves in deformable rigid bodies. The solution to this problem is important in seismic tomography and exploration geophysics. In this work only 2D scenario is studied, but it has an extension to 3D.
Grid-characteristic method consists of a bunch of iterations over the array representing nodes of computational grid. The increase of performance due to change of array traversal order is connected with the spatial and time locality of memory accesses. The following 3 techniques are evaluated: bypassing of memory in rectangular blocks (block tiling), in blocks of diamond shape (diamond tiling), and in recurrently nested tiles of smaller size (hierarchical tiling).
In the case of block tiling we achieved highest performance gain (about 15%). In contrast, performance with diamond tiling is declined by 6% and with hierarchical tiling is dropped by 13%. We assume that last two methods degrade performance because the amount of memory for single grid node is too large. Therefore all the necessary local nodes for block and hierarchical tiling can’t fit simultaneously in L1 cache. We have concluded that block tiling is the most appropriate technique for grid-characteristic method optimization.
The reported study was funded by RFBR according to the research project № 18-07-00914 A.
Primary authors
Andrey Ivanov
(Moscow Institute of Physics and Technology)
Nikolay Khokhlov
(MIPT)
