CMAP-LAP: Configurable Massively Parallel Solver for Lattice Problems

Nariaki Tateiwa, Yuji Shinano, Keiichiro Yamamura, Akihiro Yoshida, Shizuo Kaji, Masaya Yasuda, Katsuki Fujisawa

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Citation (Scopus)

Abstract

Lattice problems are a class of optimization problems that are notably hard. There are no classical or quantum algorithms known to solve these problems efficiently. Their hardness has made lattices a major cryptographic primitive for post-quantum cryptography. Several different approaches have been used for lattice problems with different computational profiles; some suffer from super-exponential time, and others require exponential space. This motivated us to develop a novel lattice problem solver, CMAP-LAP, based on the clever coordination of different algorithms that run massively in parallel. With our flexible framework, heterogeneous modules run asynchronously in parallel on a large-scale distributed system while exchanging information, which drastically boosts the overall performance. We also implement full checkpoint-and-restart functionality, which is vital to high-dimensional lattice problems. CMAP-LAP facilitates the implementation of large-scale parallel strategies for lattice problems since all the functions are designed to be customizable and abstract. Through numerical experiments with up to 103, 680 cores, we evaluated the performance and stability of our system and demonstrated its high capability for future massive-scale experiments.

Original languageEnglish
Title of host publicationProceedings - 2021 IEEE 28th International Conference on High Performance Computing, Data, and Analytics, HiPC 2021
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages42-52
Number of pages11
ISBN (Electronic)9781665410168
DOIs
Publication statusPublished - 2021
Event28th IEEE International Conference on High Performance Computing, Data, and Analytics, HiPC 2021 - Virtual, Bangalore, India
Duration: Dec 17 2021Dec 18 2021

Publication series

NameProceedings - 2021 IEEE 28th International Conference on High Performance Computing, Data, and Analytics, HiPC 2021

Conference

Conference28th IEEE International Conference on High Performance Computing, Data, and Analytics, HiPC 2021
Country/TerritoryIndia
CityVirtual, Bangalore
Period12/17/2112/18/21

All Science Journal Classification (ASJC) codes

  • Artificial Intelligence
  • Computer Networks and Communications
  • Computer Science Applications
  • Hardware and Architecture
  • Information Systems

Fingerprint

Dive into the research topics of 'CMAP-LAP: Configurable Massively Parallel Solver for Lattice Problems'. Together they form a unique fingerprint.

Cite this