Calculating the Fibonacci numbers on GPU

Summary

Calculating the fibonacci numbers on GPU 21 Jun, 2025 In this blogpost we will show how to perform very fast calculation of the Fibonacci sequence using GPU programming. In this blogpost we will employ Thrust an NVIDIA library which uses concepts from modern C++ to make GPU programming easy. IntroductionScan is one of the fundamental examples for parallelizable algorithms. If you are interested in the foundations of the algorithm I refer you to a previous blogpost where I implemented scan in CUDA. The scan is the operation which transforms x=[x1,...,xN]to y=[y1,...,yN]We call the inclusive iff yi=x0⊕...⊕xiand exclusive iff yi=x0⊕...⊕xi−1where ⊕ is an associative binary operator. Simple exlusive scan in thrustThis is how to perform an exlusive scan using thrust. thrust::device_vector<int> in{1,2,3}; thrust::device_vector<int> out(3); By default we apply the plus operator. Here we use 0 as the initial element x0. thrust::exclusive_scan(thrust::device, in.begin(), in.end(), out.begin(), 0 ); This will output We can similary apply the multiply operator: thrust::exclusive_scan(thrust::device, in.begin(), in.end(), out.begin(), 1, [=]__host__ __device__(int cur, int prev) { return cur * prev; } ); where we use a simple lambda function to define the binary operation. This will output Matrix scan operationThrust is very flexible and the matrix multiplication is associative. This allows us to perform a scan using matrices! // 2 x 2 Matrix // a00, a01, a10, a11 using Matrix = thrust::tuple<int, int, int, int>; ... Matrix scale_two{thrust::make_tuple(2, 0, 0, 2)}; Matrix identity_matrix{thrust::make_tuple(1, 0, 0, 1)}; ... thrust::exclusive_scan(thrust::device, in.begin(), in.end(), out.begin(), identity_matrix, matmul_lambda ); ... This will output out: [1, 0, 0, 1] [2, 0, 0, 2] [4, 0, 0, 4] [8, 0, 0, 8] [16, 0, 0, 16] At each step our scan operation is simply a multiplication by the diagonal matrix with 2 on the diagonal. The result at step n simply contains the correspondin...