GPU-ACCELERATED OPTIMIZATION OF BLOCK LANCZOS SOLVER FOR SPARSE LINEAR SYSTEM

Abstract

Solving large and sparse system of linear equations has been extensively used for several cryptanalytic techniques. Block Lanczos and Block Wiedemann algorithms are well known for solving large sparse systems. However, the time complexity of such popular methods makes it reluctant and hence, the concept of parallelism is made compulsory for such methods. This work introduced an optimization of the Block Lanczos method over the finite field using GPUs. Here we consider GF (2) finite field. The optimization of parallel Block Lanczos solver is performed using NVIDIA Compute Unified Device Architecture (CUDA) and Message Passing Interface (MPI) to take advantage of multilevel parallelism on multi-node and multi-GPU systems. CUDA-aware MPI has been extensively used to leverage GPU-Direct Remote Direct Memory Access (RDMA) and GPU-Direct Point to Point (P2P) for optimized inter and intra node communication. The proposed optimization of Block Lanczos solver explored the memory bandwidth on a single Tesla, multi Tesla K40 and multi Tesla P100 GPU nodes. The parallel efficiency is also achieved on the DGX system with Pascal P100 GPUs respectively.