Scholarlink

Sieving algorithms currently represent the fastest approach of solving the Shortest Vector Problem (SVP). However, current sieving algorithms exclusively utilize either CPUs or GPUs. This paper introduces a novel sieving approach tailored to CPU+GPU heterogeneous computing platforms. We constructed a runtime system capable of concurrently executing both CPU and GPU versions of the sieving algorithm. The GPU version of the sieving algorithm reduces the demand for graphics memory by efficiently transferring data in batches. We used two computing platforms to evaluate our method: Hannibal is equipped with an AMD Ryzen 7 5800H CPU and an NVIDIA RTX 3060 GPU; Zeus is equipped with an Intel Xeon Platinum 8176M CPU and two Integrated Matrox G200eW3 Graphics Controllers. The experimental results show that, compared to the classical sieving algorithm implementation in G6K, the proposed method achieves a minimum speedup of 7.2x (for 30-dimensional SVP) and a maximum of 588x (for 120-dimensional SVP) on Hannibal and a minimum speedup of 4.3x (for 30-dimensional SVP) and a maximum of 1230x (for 120-dimensional SVP) on Zeus.

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Parallel Implementation of Sieving Algorithm on Heterogeneous CPU-GPU Computing Architectures

  • 会议论文

  • 发表日期：

    2025年

查看全文
  • Mengsi Wu,
  • Pei Li,
  • Jiageng Chen,
  • Shixiong Yao

摘要

Sieving algorithms currently represent the fastest approach of solving the Shortest Vector Problem (SVP). However, current sieving algorithms exclusively utilize either CPUs or GPUs. This paper introduces a novel sieving approach tailored to CPU+GPU heterogeneous computing platforms. We constructed a runtime system capable of concurrently executing both CPU and GPU versions of the sieving algorithm. The GPU version of the sieving algorithm reduces the demand for graphics memory by efficiently transferring data in batches. We used two computing platforms to evaluate our method: Hannibal is equipped with an AMD Ryzen 7 5800H CPU and an NVIDIA RTX 3060 GPU; Zeus is equipped with an Intel Xeon Platinum 8176M CPU and two Integrated Matrox G200eW3 Graphics Controllers. The experimental results show that, compared to the classical sieving algorithm implementation in G6K, the proposed method achieves a minimum speedup of 7.2x (for 30-dimensional SVP) and a maximum of 588x (for 120-dimensional SVP) on Hannibal and a minimum speedup of 4.3x (for 30-dimensional SVP) and a maximum of 1230x (for 120-dimensional SVP) on Zeus.