---
abstract: 'Many-Fermion Dynamics—nuclear, or MFDn, is a configuration interaction (CI) code for nuclear structure calculations. It is a platform-independent Fortran 90 code using a hybrid MPI+X programming model. For CPU platforms the application has a robust and optimized OpenMP implementation for shared memory parallelism. As part of the NESAP application readiness program for NERSC's latest Perlmutter system, MFDn has been updated to take advantage of accelerators. The current mainline GPU port is based on OpenACC. In this work we describe some of the key challenges of creating an efficient GPU implementation. Additionally, we compare the support of OpenMP and OpenACC on AMD and NVIDIA GPUs.'
author:
- Brandon Cook
- 'Patrick J. Fasano'
- Pieter Maris
- Chao Yang
- Dossay Oryspayev
bibliography:
- 'refs.bib'
title: 'Accelerating quantum many-body configuration interaction with directives'
---

Introduction
============

Many-Fermion Dynamics—nuclear, or MFDn, is a configuration interaction (CI) code for *ab initio* nuclear physics calculations. It calculates the approximate many-body wave function of self-bound atomic nuclei, starting from two- and three-nucleon interactions. In these calculations, the nuclear many-body Hamiltonian is represented as a large sparse symmetric matrix in configuration space. The lowest eigenvalues of this matrix correspond to the energy levels of the low-lying spectrum, and the eigenvectors represent the corresponding many-body wave function.

MFDn is a platform-independent Fortran 90 code using a hybrid MPI+X programming model. Over the past decade, it has been successfully deployed on multi-core supercomputers such as Jaguar at the Oak Ridge Leadership Class Facility (OLCF), Mira at the Argonne Leadership Class Facility (ALCF), and Edison at the National Energy Research Scientific Computing Center (NERSC) using MPI + OpenMP @Maris:2011as [@Maris:2013poa; @Maris:2014jha; @Binder:2015mbz]. Currently it is in production on many-core systems @10.1007/978-3-319-46079-6_26 [@LENPIC:2018ewt; @Caprio:2021umc] such as Cori at NERSC and Theta at ALCF, as well as other supercomputers worldwide.

As part of the NESAP application readiness program for NERSC's latest Perlmutter system, MFDn is being updated to take advantage of accelerators. The current mainline GPU port uses OpenACC. In this work we consider several kernels that are representative for some of the most time-consuming parts of MFDn @10.5555/1413370.1413386 [@Maris_2013; @10.1007/978-3-319-46079-6_26]. We describe some of the challenges and limitations of running them efficiently on GPUs with OpenMP and/or OpenACC directives, using both the NVIDIA and Cray Fortran compilers. We test their performance on NVIDIA V100 "Volta", NVIDIA A100 "Ampere", and AMD MI100 GPUs, as well as on Intel multi-core CPUs; see Table \[tab:hw\_platformsw\] for more details of the test systems.

                   Cori GPU        Cori DGX      Spock
  ---------------- --------------- ------------- -----------
  GPU              NVIDIA V100     NVIDIA A100   AMD MI100
  CPU              Intel Skylake   AMD Rome      AMD Rome
  GPUs per node    8               8             4
  CPUs per node    2               2             1
  Bus              PCIe 3.0        PCIe 4.0      PCIe 4.0
  per GPU Memory   16GB            40 GB         32 GB

  : Test platforms<span data-label="tab:hw_platformsw"></span>

We performed tests on Cori GPU (NVIDIA V100 GPUs) and Cori DGX (NVIDIA A100) with the NVIDIA compiler only, whereas our tests on Spock (AMD MI100) are performed with the Cray compiler only (see Table \[tab:compilers\]). The Cray compiler version 12.0 was not available for the Cori GPU system at the time of writing and it does not support NVIDIA A100 GPUs. All tests were done on exclusively-allocated nodes. In order to minimize any NUMA effects, tests on GPUs used a single GPU, while tests on CPUs used a single socket.

  Vendor      Version    `_OPENACC`     `_OPENMP`     V100   A100   MI100
  ---------- --------- -------------- -------------- ------ ------ -------
  NVIDIA       21.7     201711 (2.6)   202011 (5.1)                
  HPE/Cray    12.0.1    201306 (2.0)   201511 (4.5)                

  : Compilers. Cray Fortran compiler version 12.0.1 claims full OpenACC 2.0 and partial OpenACC 2.6 support for Fortran.<span data-label="tab:compilers"></span>

In our implementations we have primarily explored three models: OpenACC with `parallel` and `loop` directives, <span>i.e., </span>no `kernels` directives; OpenMP target offload with prescriptive style directives (`teams distribute parallel do`); and OpenMP target with the new `loop` construct introduced in OpenMP 5.0. In all cases maintaining performance on CPUs and code maintainability was also a priority. The NVIDIA compiler claims support for OpenACC 2.6 with "many features" from 2.7 and for a subset of OpenMP 5.1, while the Cray Fortran compiler claims support for OpenACC 2.0 with "partial support" for 2.6 and full support OpenMP 4.5 with partial support for 5.0. We highlight where we encountered missing features or shortcomings throughout and in particular in architectural specialization in Section \[section:fill\_array\] and reductions on arrays in Section \[section:array\_reduction\].

Computational Motifs in Configuration Interaction code MFDn
===========================================================

The key computational challenges for MFDn are (1) efficient localization of the nonzero Hamiltonian matrix elements and evaluation of the corresponding matrix elements, and (2) efficient sparse matrix–vector and matrix–matrix products used in the solution of the eigenvalue problem, both while effectively using the available aggregate memory @10.5555/1413370.1413386 [@Maris_2013; @10.1007/978-3-319-46079-6_26]. Figure \[fig:MFDn\_structure\] shows the overall structure of MFDn. The GPU port of the LOBPCG eigensolver @SHAO20181 using OpenACC is described in @Maris:2021mug. In this work we concentrate on the matrix construction phase and the evaluation of observables, which each take up about one-quarter to one-third of the total runtime, while iterative eigensolving takes about one-third to one-half of the total runtime.

<span>0.95</span>

1.  Enumerate and distribute many-body basis orbitals ($\Psi_j$)

2.  \[tile\_cnt\] Loop over column orbitals ($\Psi_m$)\
    Loop over row orbitals ($\Psi_l$)

3.  Compare the single-particle orbitals of $\Psi_l$ and $\Psi_m$\
    increment $tile\_cnt$ if up to $2d$ differences\
    End Loop\
    End Loop

4.  Allocate arrays of length $tile\_cnt$ to store nonzero tiles ($T_k$)

5.  Repeat \[tile\_cnt\] and store nonzero tiles ($T_k = (\Psi_l,\Psi_m)$):\
    pairs of orbitals with up to $2d$ differences

6.  Loop over tiles ($(\Psi_l,\Psi_m) = T_k$)

7.  Loop over column states ($\Phi_j \in \Psi_m$)\
    Loop over row states ($\Phi_i \in \Psi_l$)

8.  Compare the single-particle states of $\Phi_i$ and $\Phi_j$\
    increment $cnt_k$ if up to $2d$ differences\
    End Loop\
    End Loop\
    End Loop

9.  Convert $cnt_k$'s to <span>*offset*</span>$_k$'s

10. Allocate arrays of length $\sum cnt_k$ to store $H_{ij}$

11. Loop over tiles ($(\Psi_l,\Psi_m) = T_k$)

12. Loop over column states ($\Phi_j \in \Psi_m$)\
    Loop over row states ($\Phi_i \in \Psi_l$)

13. Compare the single-particle states of $\Phi_i$ and $\Phi_j$\
    cycle if more than $2d$ differences

14. Compute the nonzero matrix entry $H_{ij}$ and store\
    End Loop\
    End Loop\
    End Loop

15. Obtain lowest $n$ eigenvalues $E$ and eigenvectors $\vec{c}$ of $H_{ij}$\
    using distributed LOBPCG or Lanczos algorithm

16. Loop over tiles ($(\Psi_l,\Psi_m) = T_k$)

17. Loop over column states ($\Phi_j \in \Psi_m$)\
    Loop over row states ($\Phi_i \in \Psi_l$)

18. Compare the single-particle states of $\Phi_i$ and $\Phi_j$\
    cycle if more than $2d$ differences

19. Compute $m$ nonzero matrix elements $O_{ij}(1:m)$

20. Update $a(1:n*m) = a(1:n*m) + c_i(1:n) * O_{ij}(1:m) * c_j(1:n)$\
    End Loop\
    End Loop\
    End Loop

In CI calculations, the many-body wave functions are approximated by an expansion in <span>*many-body basis states*</span>; in MFDn we use antisymmetrized products of single-particle states with quantum numbers $(n, \ell, j, m)$ (see, e.g., Ref. @Suhonen:2007vjh for the meaning of these quantum numbers). The many-body basis states can then be characterized by the set of single-particle quantum numbers for each nucleon. It is convenient to group together many-body states with the same sets of values for the quantum numbers $(n, \ell, j)$, but different sets of values for the magnetic projection quantum numbers $m$. This grouping leads to a natural hierarchy in the sparsity structure of the Hamiltonian matrix, which in turn allows for efficient localization and evaluation of nonzero matrix elements. In addition, this grouping also facilitates an efficient block-diagonal preconditioner for the LOBPCG algorithm @SHAO20181. We refer to these groups of many-body states as <span>*many-body basis orbitals*</span>. To describe the sparsity structure, we furthermore define tiles as pairs of row and column many-body basis orbitals.

In order to efficiently locate the nonzero matrix elements we exploit this hierarchical structure, by first determining which tiles can contain nonzero matrix elements (lines 2 through 5 of Fig. \[fig:MFDn\_structure\]) and next counting how many nonzero matrix elements there are (lines 6 through 8) in each tile. The actual construction of the sparse matrix starts in line 11, with the nonzero matrix elements and their location evaluated and stored in line 14 of Fig. \[fig:MFDn\_structure\]. Note that the structure of the double loops starting in lines 2 and in line 7 is essentially the same; the corresponding motif is discussed in Section \[section:sparsity\] below. Also the double loops starting in line 12 have a similar structure, except that in this case, the obtained results in the innermost loop are stored in an array; this motif is discussed in Section \[section:fill\_array\] below. (Note that this motif is also used implicitly in line 5 of Fig. \[fig:MFDn\_structure\].)

Once the nonzero matrix elements are evaluated and stored, we can obtain the lowest $n$ eigenvalues and eigenvectors $\vec{c}$ using an iterative eigensolver. In MFDn we use either LOBPCG or a Lanczos algorithm with reorthogonalization, as indicated in line 15 of Fig. \[fig:MFDn\_structure\]. Details of the GPU port of our LOBPCG eigensolver using OpenACC are described in Ref. @Maris:2021mug.

Finally, in lines 16 through 20 of Fig. \[fig:MFDn\_structure\] we calculate $m$ different physical observables using the coefficients $c_i$ of the lowest $n$ eigenvectors and $m$ two-body operators. Typically, we use $8$ or $16$ eigenvectors, and up to $m \sim 16$ different operators corresponding to different observables. Note that lines 16 to 18 have the same structure as lines 11 to 13, but instead of storing the nonzero matrix elements of the operators, we contract them with the $n$ eigenvectors. The corresponding motif for these loops is discussed in Section \[section:array\_reduction\] below.

Matrix Sparsity Determination {#section:sparsity}
-----------------------------

A typical loop structure in the matrix construction phase, as well as in the evaluation of observables, is shown in Fig. \[fig:loop\]. The $(i,j)$th entry of the many-body Hamiltonian with a $d$-body interaction, $H_{ij} = \langle
\Phi_i \vert H \vert \Phi_j \rangle$, can only be nonzero if the many-body states $\Phi_i$ and $\Phi_j$ differ by at most $2d$ single-particle states. Thus, the first step in the matrix construction (and in the evaluation of observables given by the expectation value of a $d$-body operator) is to determine which matrix elements can be nonzero. This is done in line 3 of the loop; subsequently, lines 4 and 5 indicate the actual evaluation of the nonzero matrix entry, which can be stored in memory (see line 14 of Fig. \[fig:MFDn\_structure\]) , or directly used in a matrix–vector multiply or vector–matrix–vector contraction for the calculation of expectation values (see line 20 of Fig. \[fig:MFDn\_structure\]). These are more complicated operations which are accomplished by separate (sequential) subroutine calls, the details of which are beyond the scope of this work.

<span>0.95</span>

1.  Loop over column states ($\Phi_j$)

2.  Loop over row states ($\Phi_i$)

3.  Compare the single-particle states of $\Phi_i$ and $\Phi_j$\
    cycle if more than $2d$ differences

4.  (optional) Compute the nonzero matrix entry $H_{ij}$ and store

5.  (optional) FMA of $H_{ij}$ with $i$th row (and $j$th column) vector element

6.  End Loop

7.  End Loop

The localization of nonzero matrix elements involves determining which many-body basis states may be connected by the given particle rank (<span>e.g., </span>two-body) Hamiltonian. Given a single-particle basis with $n_\mathrm{s.p.}$ single-particle states, a many-body basis state $\Phi_i$ for fermionic systems can be represented by a binary string of length $n_\mathrm{s.p.}$, denoted by $\operatorname{\mathtt{BIN}}(\Phi_i)$, where each binary bit of $\operatorname{\mathtt{BIN}}(\Phi_i)$ indicates whether the corresponding single-particle state is occupied. The total number of particles in the many-body state $\Phi_i$ is the number of 1's in $\operatorname{\mathtt{BIN}}(\Phi_i)$, <span>i.e., </span>the population count $\mathtt{popcount}(\operatorname{\mathtt{BIN}}(\Phi_i))$. Information regarding all differently-occupied single-particle states between two bit-representations $\operatorname{\mathtt{BIN}}(\Phi_i)$ and $\operatorname{\mathtt{BIN}}(\Phi_j)$ is encoded by $\operatorname{\mathtt{BIN}}(\Phi_i)\operatorname{\oplus}\operatorname{\mathtt{BIN}}(\Phi_j)$, where $\operatorname{\oplus}$ denotes the bit-wise exclusive-or operation. The number of differently-occupied single-particle states is then $\mathtt{popcount}(\operatorname{\mathtt{BIN}}(\Phi_i)\operatorname{\oplus}\operatorname{\mathtt{BIN}}(\Phi_j))$. If both bit-representations describe states with the same number of particles, then the number of differently-occupied single-particle states is always even; with a two-body potential, only many-body matrix elements with 0, 2, or 4 differently-occupied single-particle states can be nonzero. If there are more than four differently-occupied single-particle states the matrix element must be zero.

The storage requirements of such a bit representation is proportional to the number of single-particle states, but independent of the number of particles in the system. Alternatively, one can represent an $N$-body basis state $\Phi_i$ by an array or tuple of $N$ short integers $\operatorname{\mathtt{MBS}}(a_1{:}a_N)$ with $a_1 < a_2 <
\cdots < a_N$, where each element $a_i$ indicates which single-particle state is occupied. The storage requirement of this method is proportional to $N$, the number of particles, but independent of the number of single-particle states $n_\mathrm{s.p.}$. For a relatively small number of particles ($N\sim 10-20$ in MFDn), but a large ($n_\mathrm{s.p.} \gtrsim 1,000$) number of single-particle states, the $\operatorname{\mathtt{MBS}}$ representation is more advantageous in terms of memory than storing the states as a bit representation. However, determining the differently-occupied single-particle states is significantly more complex when $\Phi_i$ and $\Phi_j$ are in the $\operatorname{\mathtt{MBS}}$ representation (see Listing \[listing:cnt\_difference\]). Note the factor of two to ensure consistent counts with the population count on the bit representation.

``` {.fortran}
integer function count_difference(s1, n1, s2, n2)
  integer, intent(in) 8b7c:f320:99b9:690f:4595:cd17:293a:c069 n1, n2, s1(n1), s2(n2)
  integer 8b7c:f320:99b9:690f:4595:cd17:293a:c069 i1, i2, d, diffs1, diffs2
  !$acc routine seq
  i1 = 1
  i2 = 1
  diffs1 = 0
  diffs2 = 0
  do
     if ( (i1 > n1) .or. (i2 > n2) ) exit
     d = s1(i1) - s2(i2)
     if (d < 0) then
        diffs1 = diffs1 + 1
        i1 = i1 + 1
     else if (d > 0) then
        diffs2 = diffs2 + 1
        i2 = i2 + 1
     else
        i1 = i1 + 1
        i2 = i2 + 1
     end if
  end do
  count_difference = 2*max(diffs1, diffs2)
end function count_difference
```

In MFDn the low-lying single-particle states are most likely to be occupied. For this reason we use a bit representation for the 64 lowest single-particle states, in combination with an array of $N$ 16-bit integers $\operatorname{\mathtt{MBS}}(a_1{:}a_N)$ to store the full many-body state. This allows for efficient filtering of pairs of states with bit arithmetic on the most likely to be occupied states while incurring minimal additional storage overhead. Our OpenACC implementation of the algorithm used to count the number of different single-particle states by first performing a population count on the 64 lowest single-particle states, followed by a detailed comparison of the $\operatorname{\mathtt{MBS}}$ representation if the population count is at most $2d$, is given in code Listings \[listing:cnt\_difference\] and \[listing:count\_nonzero\].

\[highlightlines=<span>1,4</span>\]<span>fortran</span> !$acc parallel loop
do i = 1, n
   c = 0
   !$acc loop reduction(+:c) do j = 1, n d = popcnt(ieor(bitrep1(i), bitrep2(j))) if (d &gt; 4) cycle d = count\_difference(mbstate1(:,i), np, mbstate2(:,j), np) if (d &lt;= 4) c = c + 1 end do !$acc end loop
   counts(i) = c
end do
!$acc end parallel loop numnnz = sum(counts)

OpenMP prescriptive, OpenMP loop and OpenMP loop with bind hints directives for the first and second level of parallelism in Listing \[listing:count\_nonzero\] are shown in Listings \[listing:count\_level1\] and \[listing:count\_level2\] respectively. The first level is typically mapped to cores on CPUs, thread blocks on NVIDIA GPUs and workgroups on AMD GPUs while the second level is typically mapped to SIMD lane(s) on CPUs, threads on NVIDIA GPUs and work items on AMD GPUs. Note that the comparison of the two complete many-body states is performed in a function (see Listing \[listing:cnt\_difference\]), which needs a `!$acc routine seq` directive so that the OpenACC loops in Listing \[listing:count\_nonzero\] do indeed get parallelized; with OpenMP there is no need for a similar directive when the routine is defined in the same compilation unit, though `!$omp declare target` may be used when this is not the case.

``` {.fortran}
!$acc parallel loop
!$omp target teams distribute private(d)
!$omp target teams loop private(d)
!$omp target teams loop bind(teams) private(d)
```

``` {.fortran}
!$acc loop reduction(+:c)
!$omp parallel do reduction(+:c) private(d)
!$omp loop reduction(+:c) private(d)
!$omp loop bind(parallel) reduction(+:c) private(d)
```

For our performance tests we used many-body states with 4, 8, 12, 16 and 20 particles, 128 single-particle states, and a bit representation based on only the lowest 64 single-particle states. We randomly generated many-body states biased towards the lowest states, and counted the number of nonzero matrix elements for a two-body interaction. We present in Figs. \[fig:count\_a100\] and \[fig:count\_arch\] results with 8 particles as the density of nonzeros (median density was $6\times 10^{-6}$) most closely represents the regime of interest for MFDn. Note that fewer particles with the state generation scheme correspond to more nonzero elements and more particles result in fewer nonzero elements. For comparison and correctness, we also ran two additional versions: a version without the `popcount` on the bit representation, as well as a version with a complete bit representation of all 128 single-particle states and using exclusively the `popcount` on this extended bit representation.

![Performance of interacting state counting routines on A100 with 8 particles (median density of nonzero elements is $\sim 6\times 10^{-6}$). The vertical axis shows the number of state comparisons made per second, $\textrm{rate} = n^2 / \textrm{time}$ (higher is better).<span data-label="fig:count_a100"></span>](fig3.pdf){width="\textwidth"}

![Performance of bit representation only and combined interacting state counting routines on A100 and MI100 with 8 particles (median density of nonzero elements is $0.000006$). The vertical axis shows the number of state comparisons made per second, $\textrm{rate} = n^2 / \textrm{time}$ (higher is better).<span data-label="fig:count_arch"></span>](fig4.pdf){width="\textwidth"}

Figure \[fig:count\_arch\] shows the performance of the bit representation and combined versions of the counting routines on MI100 and A100 GPUs implemented with OpenACC and OpenMP. On NVIDIA and AMD GPUs the OpenACC directives provide the best performance in most cases. In several instances there were performance issues when a function or subroutine call was introduced: particularly with OpenMP, usually manifest as a failure to generate parallel code for the second level of parallelism. In the case of `!$omp loop` directives we found that it was necessary to include bind annotations to recover the performance obtained by the OpenACC implementations on NVIDIA GPUs. The performance difference between all versions and implementations is shown in Fig. \[fig:count\_a100\]. On NVIDIA platforms we found there is overhead associated with OpenMP with prescriptive `!$omp target teams distribute` and `!$omp parallel do` directives compared to the `!$omp loop` directives. The compiler parallelizes on both teams and threads, but shows reduced performance. This is likely due to the additional semantic constraints for the `!$omp parallel` directive introducing some overhead in code generated by the compiler.

Parallel prefix sum {#section:prefix_sum}
-------------------

On multi-core CPUs, it is often convenient to use private arrays – and as long as there is sufficient memory, there is no intrinsic limitation on the private array size. In practice, it is limited by the `OMP_STACKSIZE` which the user can increase from its default value if necessary. Further, the use of thread-private arrays can often result in good performance as it helps ensure cache locality on CPUs. However, the situation on GPUs is different. Although private arrays can be used in both OpenACC and with OpenMP offload, there are more limitations on the size of such private arrays and/or on the number of gangs/teams or vector length one can use, due to the order of magnitude more parallelism available in GPUs. In particular in inner loops, private arrays should be avoided or limited to small arrays with only a handful of array elements; and even at the gang/team level, large arrays with (tens of) thousands of array elements severely limits the number of gangs/teams one can use.

In order to reduce (or better, completely avoid) the need for private arrays, it can be useful to convert counts, such as the counts of nonzero matrix elements discussed in Section \[section:sparsity\], into offsets, so that one can use a single large shared array with appropriate offsets, instead of many allocatable private arrays. Specifically, converting counts $x_i$ into offsets $y_i$ can be implemented as $$y_{i+1} = \sum_{j=0}^{i} x_j = y_i + x_i$$ with $y_1=0$, and is often referred to as a prefix sum or cumulative sum or scan. Here we focus on addition of integers, but in general only a binary associative operator is required.

\[b\]

``` {.fortran}
!$acc serial present(x,y)
y(1) = 0
do i = 1, n-1
   y(i+1) = y(i) + x(i)
end do
!$acc end serial
```

On CPUs this operation is fast, and furthermore OpenMP 5.0 introduced a `scan` directive that extends reductions. However, this feature is not currently supported for GPUs by the compilers tested in this work. OpenACC provides no equivalent directive. We note that production quality implementations of this operation may be available in C++ libraries such as Thrust @CarterEdwards20143202 or Kokkos @bell2012thrust, but that including C++ or vendor specific frameworks in a Fortran code with a goal of portability introduces significant maintenance costs. In many cases it is preferable to avoid data transfers between the host and accelerator, even at the cost of inefficient use of the device. With OpenACC's `!$acc serial` directive a potentially expensive data transfer can be avoided as shown in Listing \[listing:scan\_serial\_acc\]. Generally one should consider a performance model that includes bandwidth between host and device, performance on either host and device and the potential for any latency/ blocking effects introduced by the data motion when considering an implementation.

For prefix sums over large sequences, a parallel implementation can realize significant speedups. We note that in MFDn the offsets can be reused many times so that the overall impact for the application run time is small, but this common primitive can be found in many applications @BlellochTR90. A work-efficient algorithm for a parallel scan is shown in Algorithm \[algo:parallel\_prefix\] - the work-efficient algorithm consists of an up and down sweep @harris2007parallel [@BlellochTR90]. The main idea is to sweep up and down a binary tree of the input data. The "up" or "reduce" sweep proceeds from the leaves to the root, computing partial sums in place. In the "down" sweep phase the binary tree is traversed from the last element down (root) to the leaves.

\[t\]

\[1\] $y\left(j+2^{p+1}\right) \gets y\left(j+2^{p}\right) + y\left(j+2^{p+1}\right)$ $x(n) \gets 0$ $tmp \gets y\left(j+2^p\right)$ $y\left(j+2^p\right) \gets y\left(j+2^{p+1}\right)$ $y\left(j+2^{p+1}\right) \gets tmp + y\left(j+2^{p+1}\right)$

``` {.fortran}
!$acc data present(x,y)
!$acc parallel loop async
do j = 1, n
   y(j) = x(j)
end do
!$acc end parallel
offset = 1
! sweep up, reduction in place
do while (offset < n)
   !$acc parallel loop firstprivate(offset) present(y) async
   do concurrent (j=0:n-1:2*offset)
      y(j + 2*offset) = y(j + offset) + y(j + 2*offset)
   end do
   !$acc end parallel
   offset = 2*offset
end do
! sweep down, complete the scan
!$acc serial async
y(n) = 0
!$acc end serial
offset = rshift(offset, 1)
do while(offset > 0)
   !$acc parallel loop firstprivate(offset, tmp) present(y) async
   do concurrent(j=0:n-1:2*offset) local(tmp)
      tmp = y(j + offset)
      y(j + offset) = y(j + 2*offset)
      y(j + 2*offset) = tmp + y(j + 2*offset)
   end do
   !$acc end parallel
   offset = rshift(offset, 1)
end do
!$acc wait
!$acc end data
```

An implementation of Algorithm \[algo:parallel\_prefix\] in OpenACC is shown in Listing \[listing:scan\_acc\]. As written it assumes power of two arrays; non-power of two arrays can be padded with zeros. We note that there are many possible further optimizations and refer interested readers to Refs. @harris2007parallel [@BlellochTR90]. In OpenACC, each `parallel` region will result in a new kernel launch, but with the `async` clause we can queue them all in non-blocking manner and rely that they will be executed in order. A similar approach can be implemented in OpenMP with `nowait` and `depend` clauses. Figure \[fig:scan\_arch\_perf\] shows the performance of serial and parallel prefix sum with OpenACC on A100, V100, and Skylake. Unfortunately the Cray compiler's partial support for OpenACC 2.6 does not include the `serial` directive so we do not include MI100 results for these implementations. For large arrays on A100 GPUs the parallel implementation can be over 500x faster than a serial implementation. This demonstrates the importance of support for serial work on accelerators (and corresponding constructs) for productivity, support for asynchronous work for performance and the desirability of a good language/ library support for parallel primitives such as prefix sums.

![Performance of prefix sum implemented with OpenACC on different architectures in parallel and serial (lower is better).<span data-label="fig:scan_arch_perf"></span>](fig5.pdf){width="90.00000%"}

Filling shared arrays {#section:fill_array}
---------------------

After an initial pass to obtain the nonzero counts and offsets as described in Sections \[section:sparsity\] and \[section:prefix\_sum\] a second pass is often performed to store relevant information such as a row or column index, or the nonzero value, into a global (shared) array, see e.g. line 14 of Fig. \[fig:MFDn\_structure\]. Since we are using a multilevel hierarchical structure for the sparse matrix, this motif appears in several situations, not only for the matrix elements themselves. Generally there are two levels of parallelism: an outer loop, with no data dependencies, and an inner loop, where order does not matter but there is a dependency. The outer loop alone typically has enough parallelism to saturate a CPU but not a GPU.

On GPUs, OpenACC directives can be used to efficiently implement such a motif as shown in Listing \[listing:filling\]. Equivalent directives are available in OpenMP. The `!$acc atomic capture` directive ensures that the value of the shared array element gets incremented by one and assigned to the local (private) variable , which can then be used as an index for filling the desired array with the appropriate value. On GPUs the performance penalty attributed to atomic operation in the inner loop is rather modest, and the exposed parallelism of the inner loop overwhelms this penalty, resulting in significant speedup over CPUs as shown in Fig. \[fig:fill-array-by-arch\].

``` {.fortran}
!$acc parallel loop
do i = 1, n
   indx(i) = offset(i)
   !$acc loop device_type(host) seq
   do j = 1, m
      if (mod(j,p) == 0) then
         !$acc atomic capture
         indx(i) = indx(i) + 1
         k = indx(i)
         !$acc end atomic
         arr(k) = j
      end if
   end do
end do
!$acc end parallel
```

![Performance of filling a shared array with OpenACC (Listing \[listing:filling\]) with $m=512$ and $p=1$ on MI100, A100, V100 and Skylake (lower is better).<span data-label="fig:fill-array-by-arch"></span>](fig6.pdf){width="90.00000%"}

The same source code can also be compiled for and run on CPUs. On CPUs, when the parallelism available in the outermost level is sufficient, we can indicate that the inner loop should be sequential with the addition of the `!$acc device_type(host) seq` clauses. Unfortunately, the OpenACC specification does not support the `!$acc device_type` clause on `!$acc atomic` constructs. The performance of Listing \[listing:filling\] on multiple architectures is shown in Figure \[fig:fill-array-by-arch\]. With the atomic operation explicitly in the inner loop, this implementation performs worse on CPUs than necessary despite there being no contention between threads on the atomic operations due to the overhead of atomic semantics. In OpenMP 5.0 `metadirective` was introduced to support this use case, but compiler support is not available at the time of writing. In principle, `declare variant` in OpenMP or runtime calls in OpenACC to selectively choose between multiple subroutine versions could be used to enable performance on CPUs and GPUs with a single source at the expense of code duplication. Otherwise use of the preprocessor would be required.

Array Reductions {#section:array_reduction}
----------------

Finally, to compute physical observables one needs to calculate the expectation values of the corresponding operators $O_k$ (see line 20 of Fig. \[fig:MFDn\_structure\]): $$a_k = \sum_{ij} x_i\, (O_k)_{ij} \; y_j \;.$$ In practice this requires a reduction of an array with a small number of elements. In the context of the MFDn application the array is typically of dimension $m \in [8,256]$. Here we consider a simplified version of the motif (shown in Listing \[listing:array\_reduction\_array\]) that omits the check if two many-body states interact and any computation of additional physical matrix elements in order to explore programming model support for the motif. In this application trading memory for performance as in @kim2021gpu is undesirable since it will limit scaling to large problems on full systems. We consider 3 implementations for "small" array reductions:

-   reduction clauses with array arguments;

-   atomic updates to individual array elements;

-   generating a scalar reduction for each element of the array with `fypp`.

``` {.fortran}
!$acc parallel loop collapse(2) reduction(+:a)
do i = 1, n
   do j = 1, n
      do k = 1, m
         a(k) = a(k) + x(k,i) * y(k,j)
      end do
   end do
end do
!$acc end parallel
```

### direct array reduction support

Both the OpenACC 2.7+ and OpenMP 4.5+ specifications support arrays as arguments to reduction clauses in directives. However, compiler support for these features varies. With OpenACC, the Cray compiler only provides partial OpenACC 2.6 support and array reductions were not introduced until 2.7. The NVIDIA compiler also does not support arrays in reduction clauses with OpenACC. With OpenMP both Cray and NVIDIA compilers support array reductions. However, this feature was only introduced in NVIDIA's 21.7 release. With Cray the compiler warns, "An OpenMP teams construct with an array reduction is limited to a single team." With OpenMP, the NVIDIA compiler encounters a run time error as the array size is increased, or fails to compile when managed memory is used. Figure \[fig:array-reduction\] shows the performance of array reduction on A100, MI100 and Skylake CPUs respectively where supported. Performance of array reductions was only competitive with other solutions on Skylake.

``` {.fortran}
!$acc parallel loop collapse(3)
do i = 1, n
   do j = 1, n
      do k = 1, m
         !$acc atomic
         a(k) = a(k) + x(k,i) * y(k,j)
         !$acc end atomic
      end do
   end do
end do
!$acc end parallel
```

![Performance of array reduction with array size of 64 (higher is better).\
*Top:* On Skylake CPUs; *Middle:* On A100, where we encountered run time errors for $n>2^5$ with OpenMP array reduction and a compile error with OpenMP with loops; *Bottom:* On MI100, where for $mn^2 \geq 2^{32}$ there appears to be a correctness error due to integer overflow on the collapsed loops with the Cray compiler.<span data-label="fig:array-reduction"></span>](fig7-1.pdf "fig:"){width="70.00000%"} ![Performance of array reduction with array size of 64 (higher is better).\
*Top:* On Skylake CPUs; *Middle:* On A100, where we encountered run time errors for $n>2^5$ with OpenMP array reduction and a compile error with OpenMP with loops; *Bottom:* On MI100, where for $mn^2 \geq 2^{32}$ there appears to be a correctness error due to integer overflow on the collapsed loops with the Cray compiler.<span data-label="fig:array-reduction"></span>](fig7-2.pdf "fig:"){width="70.00000%"} ![Performance of array reduction with array size of 64 (higher is better).\
*Top:* On Skylake CPUs; *Middle:* On A100, where we encountered run time errors for $n>2^5$ with OpenMP array reduction and a compile error with OpenMP with loops; *Bottom:* On MI100, where for $mn^2 \geq 2^{32}$ there appears to be a correctness error due to integer overflow on the collapsed loops with the Cray compiler.<span data-label="fig:array-reduction"></span>](fig7-3.pdf "fig:"){width="70.00000%"}

### array reduction with atomics

With atomic constructs we are able to compile a single version for all architectures. Compared to the case in Section \[section:fill\_array\] where there is no contention, when $n \gg m$, the contention is quite high which results in a significant performance penalty compared to an optimized reduction algorithm on the Skylake CPU as seen in the top panel of Fig. \[fig:array-reduction\]. Our results indicate that the implementation shown in Listing \[listing:array\_reduction\_atomic\] can achieve reasonable performance on GPUs but not CPUs. We also note that there is an additional danger with the use of `collapse` with many loops, the combined iteration space may manifest a integer overflow for realistic array sizes if 32 bit integers are used as loop indices even though no individual loop overflows in a serial implementation.

### generated scalar reductions

In the case of small arrays another approach is to use a preprocessor that enables templating and metaprogramming such as `fypp` to generate routines that implement a scalar reduction for each element of the array as in Listings \[listing:fypp\_array\] and \[listing:fypp\]. As shown in Fig. \[fig:array-reduction\] this approach achieves good performance on all architectures. However, this approach works for small arrays, but as array size is increased runs into several issues either with directive line length (NVIDIA) or compiler register allocation routines (HPE/Cray). Further it can result in significant undesirable cognitive and compilation time overhead. In summary no one method for array reductions is best in all situations, but in this case the manually generated reductions on scalars with OpenACC give the best overall cross-platform performance.

``` {.fortran}
#:def CSV(x,n)
${",".join(f"{x}{i}" for i in range(1, n+1))}$
#:enddef CSV
#:for num_elements in range(2, max_elements+1)
  subroutine reduction${num_elements}$(x, y, a, n, dt)
    integer, parameter 8b7c:f320:99b9:690f:4595:cd17:293a:c069 m = ${num_elements}$
    integer, intent(in) 8b7c:f320:99b9:690f:4595:cd17:293a:c069 n
    real(sp), dimension(m, n), intent(in) 8b7c:f320:99b9:690f:4595:cd17:293a:c069 x, y
    real(sp), intent(out) 8b7c:f320:99b9:690f:4595:cd17:293a:c069 a(m)
    integer 8b7c:f320:99b9:690f:4595:cd17:293a:c069 i,j
    real(dp) 8b7c:f320:99b9:690f:4595:cd17:293a:c069 t0
    real(dp), intent(out) 8b7c:f320:99b9:690f:4595:cd17:293a:c069 dt
#:for i in range(1, num_elements+1)
    real(sp) 8b7c:f320:99b9:690f:4595:cd17:293a:c069 a${i}$
#:endfor
    !$acc data present(x,y)
    t0 = wtime()
#:for i in range(1, num_elements+1)
    a${i}$ = a(${i}$)
#:endfor
    !$acc parallel loop collapse(2) &
    !$acc reduction(+:${CSV("a",num_elements}$)
    do i = 1, n
       do j = 1, n
#:for i in range(1, num_elements+1)
          a${i}$ = a${i}$ + x(${i}$,i) * y(${i}$,j)
#:endfor
       end do
    end do
    !$acc end parallel
#:for i in range(1, num_elements+1)
    a(${i}$) = a${i}$
#:endfor
    dt = wtime() - t0
    !$acc end data
  end subroutine reduction${num_elements}$

#:endfor
```

``` {.fortran}
  subroutine reduction3(x, y, a, n, dt)
    integer, parameter 8b7c:f320:99b9:690f:4595:cd17:293a:c069 m = 3
    integer, intent(in) 8b7c:f320:99b9:690f:4595:cd17:293a:c069 n
    real(sp), dimension(m, n), intent(in) 8b7c:f320:99b9:690f:4595:cd17:293a:c069 x, y
    real(sp), intent(out) 8b7c:f320:99b9:690f:4595:cd17:293a:c069 a(m)
    integer 8b7c:f320:99b9:690f:4595:cd17:293a:c069 i,j
    real(dp) 8b7c:f320:99b9:690f:4595:cd17:293a:c069 t0
    real(dp), intent(out) 8b7c:f320:99b9:690f:4595:cd17:293a:c069 dt
    real(sp) 8b7c:f320:99b9:690f:4595:cd17:293a:c069 a1
    real(sp) 8b7c:f320:99b9:690f:4595:cd17:293a:c069 a2
    real(sp) 8b7c:f320:99b9:690f:4595:cd17:293a:c069 a3
    !$acc data present(x,y)
    t0 = wtime()
    a1 = a(1)
    a2 = a(2)
    a3 = a(3)
    !$acc parallel loop collapse(2) &
    !$acc reduction(+:a1,a2,a3)
    do i = 1, n
       do j = 1, n
          a1 = a1 + x(1,i) * y(1,j)
          a2 = a2 + x(2,i) * y(2,j)
          a3 = a3 + x(3,i) * y(3,j)
       end do
    end do
    !$acc end parallel
    a(1) = a1
    a(2) = a2
    a(3) = a3
    dt = wtime() - t0
    !$acc end data
  end subroutine reduction3
```

Conclusion and Outlook
======================

We highlighted several important features of programming for accelerators with directives that were key for an efficient GPU accelerated port of MFDn. Further we explored the performance implications of these modifications with CPUs and with multiple GPU and compiler vendors.

Avoiding use of private arrays in a production application that has undergone several years of optimization for multicore CPU platforms was a key challenge. The conversion of counts to offsets followed by indexing of shared array in a way that preserves CPU performance while enabling GPU offload was a key pattern that involved restructuring of many key data structures and routines in the application.

Our key points for application developers can be summarized as: avoid private arrays; check compiler diagnostic output to ensure parallel code is in fact generated; carefully check correctness along with performance; and be mindful of atomic operations when developing single source code for CPU and GPU architectures.

Our findings have shown several shortcomings of both the OpenACC and OpenMP specification/implementation with respect to specialization of code for different architectures that can hopefully be addressed in future editions of those specifications and compilers. Finally, we have identified several areas and motifs that compiler vendors may use to improve their products.

Acknowledgements {#acknowledgements .unnumbered}
----------------

This work is supported by the U.S. Department of Energy (DOE) under Award Nos. DE-FG02-95ER40934 and DE-SC0018223 (SciDAC/NUCLEI), and by the DOE Office of Science, Office of Workforce Development for Teachers and Scientists, Office of Science Graduate Student Research (SCGSR) program (administered by the Oak Ridge Institute for Science and Education (ORISE), managed by ORAU under contract number DE‐SC0014664). This research used resources of the National Energy Research Scientific Computing Center (NERSC), a DOE Office of Science User Facility located at Lawrence Berkeley National Laboratory, operated under Contract No. DE-AC02-05CH11231, as well as resources of the Oak Ridge Leadership Computing Facility at the Oak Ridge National Laboratory, which is supported by the DOE Office of Science under Contract No. DE-AC05-00OR22725.

{'source': 'arXiv_out/2110'}