# Efficient GPU Implementation of the McMurchie-Davidson Method for Shell-Based ERI Computations
## 5 Implementations in Graphics Processing Unit (GPU)
### Triple-Buffering of Shared Memory  
With the goal of reducing the overall memory usage required in the _batch_-based algorithm, this section proposes the concept of triple-buffering of the _shared memory_, which is inspired by the notion of avoiding the storage of unnecessary values from the computed recurrences. In the _batch_-based algorithm (Section 4.2), the values of the recurrence \(R^{n}_{t,u,v}\) for _batch_\(k\) are computed sequentially starting from _batch_\(0\) to _batch_\(K\). By observing the features of Equation (22) and Figure 4, one can note that only the values for _batch_\(k-1\) and _batch_\(k-2\) are needed to calculate the recurrence \(R^{n}_{t,u,v}\) for _batch_\(k\). Therefore, it becomes unnecessary to store all the values of the recurrence \(R^{n}_{t,u,v}\) for the entire _batch_ algorithm. Concretely speaking, for implementations, three buffers are prepared on the _shared memory_, in which each buffer stores the values computed from the recurrence \(R^{n}_{t,u,v}\) for one _batch_. To show the basic idea behind the triple-buffering of the shared memory, Figure 5 shows the dependencies behind computing the corresponding recurrences \(R\) for each _batch_ under the triple-buffering scheme. By observing the dependency paths in Figure 5, computations switch between buffers. For instance, during the computation of _batch_\(k\), the values from the recurrence \(R\) from _batch_\(k-1\) and _batch_\(k-2\), stored in two buffers, are used to calculate the \(R\) value for _batch_\(k\), whose result is then stored in the remaining buffer. In the subsequent computation of _batch_\(k+1\), the \(R\) values from _batch_\(k\) and _batch_\(k-1\), stored in the two buffers, are used to compute the \(R\) value for _batch_\(k+1\), which is then stored in the buffer that previously held the \(R\) value for _batch_\(k-2\). By repeating the above-mentioned process, all \(R\) values can be calculated efficiently using only three buffers. The triple-buffering technique is a well-known approach for optimizing memory usage. However, in the context of the MD method, its effectiveness depends on the specific recurrence dependencies unique to this method, which are observed in Equation (22). Our work leverages these dependencies to minimize memory requirements while preserving computational efficiency. By carefully managing buffer usage in accordance with the recurrence properties, we achieve a significant reduction in shared memory consumption, as demonstrated in our analysis. The above-mentioned implementation requires significantly less _shared memory_ compared to the approach that would preserve the computed values of \(R^{n}_{t,u,v}\). In particular, an algorithm that would preserve computed values would require the following size of _shared memory_:\[\sum_{k=0}^{K}\frac{(k+2)(k+1)(K-k+1)}{2}=\frac{(K+1)(K+2)(K+3)(K+4)}{24}.\]  
In contrast, the buffer size used in the triple-buffering method is:  
\[\max_{0\leq k\leq K}\frac{(k+1)(k+2)(K-k+1)}{2}.\]  
Since three buffers become necessary, the required memory is three times a constant size. Additionally, the values computed from the recurrence \(R_{t,u,v}^{0}\) in Algorithm 2 are retained separately, implying  
\[\sum_{k=0}^{K}\frac{(k+2)(k+1)}{2}=\frac{(K+1)(K+2)(K+3)}{6}\]  
elements of memory. It is possible to estimate the required size of the _shared memory_ needed to compute all the _batches_. First, we consider a straightforward approach that would store all the values rendered from the recurrences \(R\) into the _shared memory_. From Section 4.2, the number of \(R\) values computed in _batch_\(k\) is given by  
\[\frac{(k+2)(k+1)(K-k+1)}{2}.\]  
Therefore, the total number of \(R\) values for all batches from \(k=0\) to \(k=K\) is:  
\[\sum_{k=0}^{K}\frac{(k+2)(k+1)(K-k+1)}{2}=\frac{(K+1)(K+2)(K+3)(K+4)}{24}.\]  
Figure 5: Basic idea of the computation of \(R\) values for each batch using triple-buffering of the shared memory.