Malik Silva, Richard Wait
Data reuse is widely used to improve the memory hierarchy performance of compute intensive scientific applications. Many large-scale computational problems result from 3d grid based models. Typically the major part of the computation is in solving systems of equations based on the grid. We focus on a typical iterative scheme known as Red-Black Gauss-Seidel. In the standard version of this problem, all the red nodes are updated before any of the black nodes. In a better version, once red nodes in a particular plane are updated the black nodes in the previous plane are updated immediately.
Furthermore, we can fuse multiple iterations to further increase data reuse: as the red nodes in each new plane are updated, we update as many previously updated black and red planes as possible. The idea is to maximize the reuse of data that have recently visited the memory system. In our tests, this technique gives computation time improvements of around 98%, especially for out-of-memory grid sizes.