Warning
I've stopped maintaining this project !
Benchmarking Finite Field Arithmetics on Accelerators, using SYCL
I've been exploring finite field arithmetics libraries which I can use for offloading computation to accelerator devices i.e. CPU, GPU. Most of the arbitrary precision modular arithmetic libraries I came across, makes use of dynamic memory allocation, which is prohibited when running field arithmetics inside kernels, which are offloaded to CPU/ GPU, using backends like OpenCL, CUDA. Recently I discovered ctbignum
, written by Niek J. Bouman, which is wholely based on modern C++ features i.e. std::array
, std::integer_sequence
etc., fully avoiding any need of dynamic allocation. All field elements ( read limbs if field element can't be stored in single machine word ) are kept in stack/ registers.
With this setup, I write benchmark code for two prime fields, while offloading parallel computation to CPU/ GPU. I'm using SYCL as frontend framework, while OpenCL/ CUDA/ HIP can be used as backend, given that SYCL implementation can produce code for such backend.
These are two prime fields, I'm benchmarking on. These two prime fields are particularly of my interest, which is why I choose them.
- F(18446744069414584321) --- 64-bit Prime Field
- F(21888242871839275222246405745257275088548364400416034343698204186575808495617) --- 254-bit Prime Field
Note: For compiling
ctbignum
down to GPU digestable SPIRV-64 code, I had to make small modification inctbignum
. If interested, read more.
- I'm on
$ lsb_release -d
Description: Ubuntu 20.04.3 LTS
-
I've compiled Intel DPC++ compiler from source, with CUDA support, while following guide here
-
Compiler version is
$ clang++ --version
clang version 14.0.0 (https://github.com/intel/llvm c690ac8d771e8bb1a1be651872b782f4044d936c)
Target: x86_64-unknown-linux-gnu
Thread model: posix
InstalledDir: /home/ubuntu/sycl_workspace/llvm/build/bin
- I've
libstdc++-10
installed so that I can use C++20 features
sudo apt-get install libstdc++-10-dev
- Clone
ctbignum
& include headers in include path
cd ~
git clone https://github.com/itzmeanjan/ctbignum.git
pushd ctbignum
git checkout e8fdb0d6f7d304fb1eed2029078d3f653c4f67db # **important**
sudo cp -r include/ctbignum /usr/local/include
popd
- Also you'll need
make
and standard system development tools.
- Run benchmark
# either
# Prime field elements are pre-calculated &
# those operands are used inside kernel body ( i.e. loop )
ON_THE_FLY=0 make
# or
# Prime field elements are computed on-the-fly ( runtime )
# and what they are is dictated by work-item index, iteration
# round index etc.
ON_THE_FLY=1 make
- Clean up
make clean
- If you make any changes in soource, reformat
# given that you've clang-format installed
make format
- It's possible to target some specific accelerator device, if you have multiple
DEVICE=cpu make # target first CPU available
DEVICE=gpu make # target first GPU available
DEVICE=host make # target host, *always* available
DEVICE=default make # no need to mention device here, it's default case
All above kernels are JIT compiled, for AOT try taking a look here.
- I've added build recipe for AOT compiling all benchmark kernels, targeting CPU, using
avx*
/sse4.2
instructions
DEVICE=cpu ON_THE_FLY={0,1} make aot_cpu
- If you've access to Nvidia GPU, you can compile kernels using experimental CUDA backend of DPC++
DEVICE=gpu ON_THE_FLY={0,1} make cuda
I suggest checking Makefile living in root of repository.
For running benchmark in data parallel environment, I make use of 2D compute grid, where each cell of square matrix of dimension N x N, is one work-item. Each work-item computes some specific field arithmetic operation on given operands, M-many times. So in each round of benchmarking, when some specific arithmetic operator is chosen, for prime field F_p; that operation is concurrently run on chosen accelerator device N x N x M
times. These benchmarks don't include any (host-to-device and vice-versa) data transfer. As suggested/ corrected by @niekbauman, I've modified kernels to make use of global memory and ensure that each work-item writes some accumulated data back to designated location in global memory at end of work-item's compute cycle, so that compiler doesn't end up optimizing too much that kernel actually doesn't do its desired job and I collect wrong metrics.
ON_THE_FLY |
Prime Field | Results |
---|---|---|
0 | 64 -bit | benchmarks/64-bit-on-gpu-no-otf.md |
1 | 64 -bit | benchmarks/64-bit-on-gpu-otf.md |
0 | 254 -bit | benchmarks/254-bit-on-gpu-no-otf.md |
1 | 254 -bit | benchmarks/254-bit-on-gpu-otf.md |