PARCEL SYCL v1.2 / User Guide User Guide API Reference Search Download 日本語

2 Basic Structure

2.1 Data Structures

In general, programs for sparse iterative methods adopt data structures that store only information on the nonzero elements (value, row position, column position) to save memory. This chapter describes the sparse matrix storage format used in this library.


2.1.1 Compressed Row Storage (CRS) Format

The CRS format (compressed row storage) packs the nonzero elements row by row and stores their values and column indices in one-dimensional arrays. For this purpose, a row pointer (rowptr) recording the starting position of each row in the one-dimensional arrays is used. All indices are 0-based (the C and Fortran APIs can also use 1-based indices; Usage). In parallel processing, the matrix is partitioned by rows, and each process stores a contiguous block of rows (see “MPI Decomposition” in “Usage” for details). In this case, rowptr is given in local numbering, with the first owned row of each process as 0, and the column indices (crsCol) are given as global indices of the whole matrix. The column indices within each row are assumed to be in ascending order.


A=(a00a01a0200a1100a200a22a230a31a32a33) A = \left( \begin{array}{cccc} a_{00} & a_{01} & a_{02} & 0\\ 0 & a_{11} & 0 & 0\\ a_{20} & 0 & a_{22} & a_{23}\\ 0 & a_{31} & a_{32} & a_{33} \end{array} \right)


One Process

Nonzero values of the matrix :: val={a00,a01,a02,a11,a20,a22,a23,a31,a32,a33}val=\{a_{00},a_{01},a_{02},a_{11},a_{20},a_{22},a_{23},a_{31},a_{32},a_{33}\}

Row pointer :: rowptr={0,3,4,7,10}rowptr=\{0,3,4,7,10\}

Column indices of nonzero values :: crsCol={0,1,2,1,0,2,3,1,2,3}crsCol=\{0,1,2,1,0,2,3,1,2,3\}


Two Processes

Nonzero values of the matrix :: val={a00,a01,a02,a11}val=\{a_{00},a_{01},a_{02},a_{11}\}

Row pointer :: rowptr={0,3,4}rowptr=\{0,3,4\}

Column indices of nonzero values :: crsCol={0,1,2,1}crsCol=\{0,1,2,1\}

Nonzero values of the matrix :: val={a20,a22,a23,a31,a32,a33}val=\{a_{20},a_{22},a_{23},a_{31},a_{32},a_{33}\}

Row pointer :: rowptr={0,3,6}rowptr=\{0,3,6\}

Column indices of nonzero values :: crsCol={0,2,3,1,2,3}crsCol=\{0,2,3,1,2,3\}




2.2 GPUs, MPI Ranks and Data

PARCEL assigns one MPI rank to one computing resource, partitions the coefficient matrix and the vectors by rows, and gives each rank its part. MPI handles the communication between ranks, and SYCL handles the parallelism within a rank (kernels on the device for GPUs, threads of the OpenMP backend for CPUs). A build with MPI (the default for C++, C and Fortran) uses this structure even when it runs as a single process. A single-process version without MPI can also be built (“Build without MPI”).

The computing resource assigned to one rank (hereafter the device) is one of the following. See the glossary for the names of the hardware and environments.

Global matrix A (n_global rows) own columns ● columns of other ranks (received by halo exchange) rank 0rows nstart₀–nend₀ rank 1rows nstart₁–nend₁ rank 2rows nstart₂–nend₂ device 0local rows and vectors device 1local rows and vectors device 2local rows and vectors internal vector of rank 1 local n_local entries halo 0 – n_local−1 n_local – halo exchange (MPI) halo exchange (MPI) 1 rank = 1 device (one GPU, one MIG partition, the GPU part of an APU, or a group of CPU cores). set_crsMat() builds the halo table from the column indices.
Figure: Row-block partitioning with 3 ranks. Each rank keeps on its device only a contiguous set of rows and the corresponding parts of the vectors.

2.2.1 Row-Block Partitioning

Let nglobaln_{global} be the global number of rows. Rank pp is responsible for the contiguous rows nstartpnstart_p to nendpnend_p (0-based, both ends inclusive), and its local number of rows is nlocal=nendp−nstartp+1n_{local} = nend_p - nstart_p + 1. Each rank holds the following.

Data Part held by each rank Length
Coefficient matrix AA CRS of the owned rows (rowptr, column indices, values). Column indices are passed as global indices rowptr is nlocal+1n_{local} + 1; column indices and values are the number of nonzeros in the owned rows
Solution xx, right-hand side bb, eigenvectors The part corresponding to the owned rows nlocaln_{local} (EigenVec of ks_arnoldi is at least nlocal×nevn_{local} \times nev; min⁡(kkeep,number of elements/nlocal)\min(k_{keep}, \text{number of elements}/n_{local}) vectors are written)
Preconditioner matrix The part for the owned rows (built by the solver from the local rows of AA) —

The number of rows may differ between ranks (non-uniform partitioning). The row blocks of all ranks together must cover [0,nglobal)[0, n_{global}) without overlaps or gaps. They need not be in the order of the rank numbers. Each rank must have at least one row (a rank with 0 rows is not supported). set_crsMat() in C++ and the C and Fortran APIs check this (“MPI Decomposition” in “Usage”). The local number of rows can be obtained with parcel::matrix::n_local().

2.2.2 Mapping One Rank to One Device

Each rank creates its own SYCL queue (an in-order queue) and places the matrix and the vectors on the device of that queue. The bundled samples select the default device with sycl::queue q{sycl::default_selector_v, sycl::property::queue::in_order{}};. On a node with several GPUs, all ranks may select the same GPU by default, so restrict the GPUs visible to each rank to one before starting. For example, place the following wrapper between mpirun and the program.

#!/bin/bash
# gpu_bind.sh: assign GPU R to the rank R within the node
R=${OMPI_COMM_WORLD_LOCAL_RANK:-${PMIX_RANK:-0}}
export CUDA_VISIBLE_DEVICES=$R      # NVIDIA
export HIP_VISIBLE_DEVICES=$R       # AMD (MI300A)
unset ROCR_VISIBLE_DEVICES
exec "$@"
mpirun -n 4 ./gpu_bind.sh ./run

On AMD GPUs, do not set HIP_VISIBLE_DEVICES and ROCR_VISIBLE_DEVICES at the same time. The two act in sequence: after ROCR_VISIBLE_DEVICES restricts the GPUs to one, HIP_VISIBLE_DEVICES tries to select the R-th of them and fails, and that rank gets no GPU and runs on the CPU OpenMP backend.

Check that each rank uses the intended device by its device name (the verification sample parcel_krylov_sample_verify.cpp prints one line with the device name for each rank at the start). If even one rank falls back to the CPU OpenMP backend, the numbers stay correct, but all ranks wait for that rank in the MPI_Allreduce of the dot products and the whole run becomes slower by orders of magnitude. For example, on an environment with one GPU per node (Miyabi-G), placing two ranks on one node makes the second rank fall back to the CPU. This mistake cannot be noticed from the numerical results alone.

2.2.2.1 MIG (NVIDIA Multi-Instance GPU)

MIG divides one GPU into partitions (instances) by SM and memory, and presents each partition as an independent GPU. From PARCEL’s point of view, one partition is one device, and as with a whole GPU, one partition is assigned to one rank. The device name of a partition includes its size (profile), such as NVIDIA GH200 120GB MIG 2g.24gb.

When several partitions are used, assign each rank to a partition with gpu_bind.sh above. Depending on the allocation, partitions of different sizes (profiles) may be mixed in the same job (2g.24gb and 1g.24gb on Miyabi-G). Partitions of different sizes run at different speeds, and the other ranks wait for the rank on the slower partition in the reduction of the dot products, so for performance measurements use partitions of the same size or whole GPUs.

2.2.2.2 APU (AMD Instinct MI300A)

The MI300A is an APU that places CPU cores and a GPU in one package and shares HBM between them. On PS-B, 1 NUMA node = 1 vnode = 1 APU (24 cores, one GPU, 124 GB), so assign one APU to one rank and request one chunk per rank in PBS with select=<number of ranks>:ncpus=24:mpiprocs=1:ngpus=1. With select=1:ngpus=4, only one vnode is allocated and only one GPU is available.

From SYCL, the GPU part of an APU appears as one device. As with other GPUs, PARCEL places the matrix and the vectors on the device in SYCL buffers and copies them to and from host buffers for the halo exchange (there is no separate path for APUs). Since the host and device memory is physically the same HBM, the host-side arrays held by the user’s program (such as the CRS arrays) and the device-side copies are taken from the same capacity of each APU.

On CPUs, one rank is responsible for a group of OpenMP threads. Place the threads of a rank within one NUMA node (or socket). The number of partitions of the blocked kernels and the default number of blocks of the block Jacobi preconditioner are determined by the number of threads per rank (“Blocking” in the “Optimization” chapter).

The recommended mapping for each environment is shown below.

Environment Assigned to one rank Threads per rank
s86 GPU (V100 ×4 / node) One GPU 12
Aquarius (A100) One GPU 9
Miyabi-G (GH200; one GPU / node) One GPU (= one node). With MIG, one partition (2g.24gb or 1g.24gb) and 18 cores 72 (18 with MIG)
PS-B (MI300A ×4 / node) One APU (one GPU part and 24 cores) 6
s86 CPU (Xeon Gold 6242R 20 cores ×2) 5 cores 5
Miyabi-C (Xeon Max 9480) 14 cores 14
PS-A (Xeon 6980P) 14 cores (pinned to a NUMA node with I_MPI_PIN_DOMAIN of Intel MPI) 14
Odyssey (A64FX) One CMG (12 cores) 12

2.2.3 What set_crsMat() Does

parcel::matrix::set_crsMat() (the MPI version) receives the CRS of the owned rows and performs the following (set_crsMat() in the API Reference). Both steps are collective operations called on all ranks. Before that, it checks the input (“Setting the Matrix” in “Usage”), and if the input is broken, all ranks throw the same std::invalid_argument.

  1. Renumbers the column indices to local indices. The nonzeros of each row are reordered so that the columns of the own rank (index c−nstartc - nstart, 0 to nlocal−1n_{local} - 1) come first and the columns of other ranks come after them. A column of another rank is renumbered to nlocal+kn_{local} + k, where kk is its position in the list of column indices of other ranks referenced by the owned rows, sorted in ascending order with duplicates removed. The caller’s arrays of column indices and values are overwritten at this point (“Setting the Matrix” in “Usage”).
  2. Exchanges the ranges owned by all ranks (nstartnstart, nendnend) with MPI_Alltoall, compares them with the list from step 1, and builds the table of which rows’ values are sent to which rank and received from which rank (the halo exchange table).

After this, the values and column indices are transferred to the device.

2.2.4 Sparse Matrix-Vector Product and Halo Exchange

A vector that is multiplied by AA inside a solver has, after its nlocaln_{local} local entries, an area for the values received from other ranks (the halo). The number of halo entries is the length of the list in step 1 above (pcg and power print it as nadd = at the start). Before every sparse matrix-vector product, the following halo exchange is performed.

  1. The values to send are packed into a send buffer on the device and copied to the host.
  2. MPI_Isend and MPI_Irecv are performed on the host buffers, and their completion is waited for.
  3. The received values are copied to the device and written into the halo of the vector (entries from nlocaln_{local} on).

Since communication goes through host buffers, a GPU-aware (CUDA-aware, etc.) MPI is not required. When run with one rank, the halo is empty and no communication occurs. The Jacobi preconditioner performs the same halo exchange in every Jacobi iteration, while the point Jacobi and block Jacobi preconditioners do not communicate (Preconditioners chapter). Dot products and norms reduce the partial sums of the ranks with MPI_Allreduce.


2.3 Precision Configurations

PARCEL lets you specify the precision in which data are held (data precision) separately from the precision of arithmetic (computation precision), and further separately for the preconditioner and for the rest. There are four types: parcel_fp16 (half precision), parcel_float (single precision), parcel_double (double precision) and parcel_doubledouble (double-double [12,13], equivalent to quadruple precision). The precision template arguments can be omitted, and the default precision is parcel_double (what can be omitted: the types of parcel::matrix<> and parcel::vector<>, the four computation-precision arguments of the classes, and the data-precision arguments of solver() that cannot be deduced from the actual arguments; the defaults of Todd_basis and Teven_basis of pcagmres are the same type as Tbasis). The syntax is shown in “Specifying Precision” in “Usage”, and the meaning of each template argument in “Class Template Arguments (Computation Precision)” and “Template Arguments of solver() (Data Precision)” in the API Reference. This section summarizes the overall picture of the specification and the representative configurations.

2.3.1 Where Precision Is Specified

Category Where to specify Macro in the samples
Computation precision (SpMV, vector operations, dot products) Class template arguments Tspmv, Taxpy, Tdot parcel_solver_calc_type (the same type is given to all three)
Computation precision of the preconditioner Class template argument Tprecon parcel_solver_calc_precon_type
Data precision (matrix, vectors) T of parcel::matrix<T> and parcel::vector<T>, and the template arguments Tmat, Tvecx, Tvecb, Tvec of solver() (Teigen_val, Teigen_vec for the eigenvalue solvers) parcel_solver_data_type
Data precision of the preconditioner Template arguments Tprecon_mat (preconditioner matrix) and Tprecon_vec (preconditioner vectors) of solver() parcel_solver_data_precon_mat_type, parcel_solver_data_precon_vec_type

The macros are used by the bundled verification sample (tests/verify/parcel_default.hpp, where all defaults are parcel_double) and by the C and Fortran wrapper (capi/wrapper_parcel_sycl.cpp; defaults in capi/parcel_capi_default.hpp); the library itself looks only at the template arguments. When using C++ directly, different types may be given to the template arguments for each operation. pgmres and pcagmres have additional arguments for the precision of orthogonalization, the basis and the Hessenberg matrix. These are explained in “Precision of Orthogonalization and of the Basis” in the Linear Solvers chapter.

2.3.2 13 Representative Configurations

The 13 configurations used in the regression tests and their convergence tolerances in the regression tests are shown below. “Lower” and “raise” in the table are relative to double precision (double). Blank cells are parcel_double.

Configuration Computation precision Computation precision of the preconditioner Data precision Data precision of the preconditioner What is lowered / raised Tolerance in the regression tests
double (reference) 1e-9
calcF16 FP16 Lowers arithmetic to FP16 1e-3
dataF16 FP16 FP16 Lowers arithmetic and the storage of the matrix and vectors to FP16 1e-2
precon_calcF16 FP16 Lowers only the arithmetic of the preconditioner to FP16 1e-9 (relaxed for some solvers)
precon_dataF16 FP16 Lowers only the storage of the preconditioner matrix and vectors to FP16 1e-9
precon_allF16 FP16 FP16 Lowers the arithmetic and storage of the preconditioner to FP16 1e-9 (relaxed for some solvers)
calcF FP32 Lowers arithmetic to FP32 1e-6
dataF FP32 FP32 Lowers arithmetic and storage to FP32 1e-6
precon_calcF FP32 Lowers only the arithmetic of the preconditioner to FP32 1e-9 (1e-6 for ks_arnoldi)
precon_dataF FP32 Lowers only the storage of the preconditioner to FP32 1e-9
precon_allF FP32 FP32 Lowers the arithmetic and storage of the preconditioner to FP32 1e-9 (1e-6 for ks_arnoldi)
calcDD dd Raises arithmetic to double-double 1e-9
dataDD dd dd Raises arithmetic and storage to double-double 1e-9

The properties of the configurations are as follows. The achievable accuracy and the restrictions are detailed in “Known Limits at Low Precision” and “double-double”.

When the verification sample is built with -DPARCEL_RUNTIME_PRECISION, 9 of the above configurations (double, calcF16, dataF16, precon_calcF16, calcF, dataF, precon_calcF, calcDD, dataDD) are put into one executable and selected with the environment variable PARCEL_PRECISION (run-time options of the verification sample). The four configurations that change the data precision of the preconditioner are specified with compile-time macros.


2.3.3 Precisions Available in Each Language

How precision is specified, and which configurations are available, depend on the language.

Language How to specify Available precisions
C++ Template arguments of the classes and solver() (“Specifying Precision” in “Usage”) All combinations, including the 13 configurations. Can differ per solver and per call
C / Fortran Compile-time macros of the wrapper capi/wrapper_parcel_sycl.cpp (parcel_solver_data_type, etc.) One configuration per built wrapper; cannot be changed at run time. Input and output arrays are double (double / real(c_double))
Python None Double only (data and arithmetic are parcel_double). Input and output arrays are float64

The Python package is double only because precision is decided at build time by C++ template arguments, and only instantiated combinations can be used. The native layer of Python (python/src/parcel_py.cpp) instantiates only the double combination. Making all 13 configurations selectable from Python would require instantiating each of them, increasing the build time and the library size accordingly. In addition, NumPy has no type corresponding to double-double. To use mixed precision from Python, write the solver call in C++, or call the C API built with precision macros through ctypes or the like.

2.3.4 Integer Type

Integers such as row indices, column indices, numbers of rows and numbers of nonzeros are held, separately from the floating-point precisions, in two types: global quantities in PARCEL_INT, and indices within one rank in PARCEL_LINT. There is one width of each per build; it cannot be chosen per solver or per matrix (see “Integer Type” in the Installation chapter).

Type Default Used for
PARCEL_INT (global indices) int64_t The number of global rows, the row range of each rank (nstart, nend), the row-pointer and column-index arrays passed to set_crsMat() (global column indices), allocation of vectors, the global column indices used to build the halo-exchange tables, and the C and Fortran APIs
PARCEL_LINT (rank-local indices) int32_t The CRS on the device (row pointers and column indices renumbered within the rank), the indices of the elements packed for the halo exchange, and the SpMV and preconditioner kernels

User programs deal only with PARCEL_INT. set_crsMat() receives PARCEL_INT arrays, renumbers the column indices within the rank (the own rows as 0 to local rows - 1, the halo after them), copies them into PARCEL_LINT arrays and sends them to the device. During the copy, 4 (n + nnz) extra bytes are used temporarily on the host (n is the number of local rows, nnz the number of nonzeros of the rank). If the row-pointer and column-index arrays of the CRS in the user program are declared with the type PARCEL_INT, the build can be switched without changing the source.

In the default configuration, the column indices and row pointers of the CRS on the device take 4 bytes per element; one nonzero of a double-precision matrix takes 12 bytes (8 bytes for the value and 4 bytes for the column index), and one grid point of a 3D 7-point stencil matrix takes 88 bytes. Holding the global quantities in 64 bits does not increase the memory traffic of SpMV or of the preconditioners.

The ranges of matrices that can be handled are as follows.

If even one rank exceeds the range of PARCEL_LINT, set_crsMat() throws the same std::overflow_error on all ranks and stops. The message asks to rebuild with -DPARCEL_LOCAL_INT64 or to use more MPI ranks. Normally, use more ranks to reduce the nonzeros per rank. If that is not possible, build with -DPARCEL_LOCAL_INT64 to make PARCEL_LINT 64-bit. The CRS on the device then takes 8 bytes per index element: 16 bytes per nonzero of a double-precision matrix and 120 bytes per grid point of a 3D 7-point stencil matrix. The memory traffic of SpMV grows, and bandwidth-bound SpMV and the Jacobi preconditioner become slower. std::overflow_error is also thrown when a CRS built by a preconditioner (such as the L and U factors of block Jacobi) has more nonzeros than the original matrix and exceeds the range (in this case only the ranks that exceed it throw).

With -DPARCEL_INT32, both PARCEL_INT and PARCEL_LINT are 32-bit. The arrays passed to set_crsMat() on the host are halved and no copy is made. The CRS on the device and the performance are the same as in the default configuration. The number of global rows (the largest column index) must be at most 231−12^{31} - 1; if a larger matrix is passed, set_crsMat() and others throw std::overflow_error (asking to remove -DPARCEL_INT32) and stop.

The C and Fortran APIs receive these integers as 64-bit integers (parcel_int = int64_t in C, integer(parcel_int_kind) in Fortran) regardless of PARCEL_INT (“Setting the Matrix” for C in “Usage”). If the wrapper is built with -DPARCEL_INT32 and a value does not fit in 32 bits, the call returns PARCEL_ERR_ARG.

For large problems, watch out for integer overflow. A 32-bit signed integer holds values up to 231−12^{31} - 1 (about 2.15 billion). For a 3D 7-point stencil matrix the number of nonzeros is about 7 times the number of rows, so the global number of nonzeros exceeds the 32-bit range at about 310 million rows (NX of about 675), and the global number of rows at about 2.15 billion rows (NX of about 1290). Row pointer values are serial numbers of nonzeros, so they overflow before the row count does. Computed in 32 bits, such values wrap to negative or small numbers, and the program reads or writes out of bounds or silently returns wrong results. For this reason the default of the global index PARCEL_INT is 64 bits in v1.2, and set_crsMat() and others detect out-of-range values with std::overflow_error. In user programs too, keep the global numbers of rows and nonzeros, the row pointers, and index computations using them (nstart + i, grid point numbers i+NX(j+NXk)i + NX\,(j + NX\,k), etc.) in PARCEL_INT (64 bits). A product of two 32-bit int values overflows at the multiplication even if it is assigned to a 64-bit variable.

The index within a rank, PARCEL_LINT, on the other hand stays 32 bits by default, for the speed of the local kernels (SpMV, preconditioners).