Skip to content

Contents of this repository

Jump to bottom
Nariaki Tateiwa edited this page Mar 30, 2022 · 1 revision

Table of Contents

laptools

Tools for lattice problems and algorithms.

Contents of laptools

  • Lattice manager
  • Some lattice algorithms
    • Reduction: DeepLLL, DeepBKZ
    • Enumeration:
    • Sieving: GaussSieve

UG framework (version 1.0)

[link]

UG is a generic framework to parallelize branch-and-bound based solvers (e.g., MIP, MINLP, ExactIP) in a distributed or shared memory computing environment.

  • Exploits powerful performance of state-of-the-art "base solvers", such as SCIP, CPLEX, etc.
  • Without the need for base solver parallelization

CMAP-LAP

Configurable massively parallel framework for lattice problem

Features

  • Load Coordinator (process in rank = 0)
    • creates and assigns task to solvers
    • collects lattice vectors and basis from solvers and distributes them
  • Solvers (process in rank > 0)
    • execute lattice algorithms
    • send lattice vectors and basis to Load Coordinator
    • receive lattice vectors and basis from Load Coordinator

Created libraries

  • synchronous_cmapdeepbkz : for synchronous shared memory parallelization
  • fcmaplaplib : for shared memory parallelization
  • paracmaplaplib : for distributed memory parallelization

CMAP-TEST

Test configure for cmaplap framework

Customized part of CMAP-LAP

  • Add CMapTestParaSolver by inheriting CMapLapParaSolver
  • Add lattice algorithms with data sharing through CMapTestParaSolver's API
    • CMapTestDeepBkz
    • CMapTestDeepLll
    • CMapTestEnumeration
    • CMapTestSieve

CMAP-DeepBKZ

Solver of Massively parallel reduction algorithm

Features

  • All solvers executes reduction algorithm
  • Solvers share the top-k lattice vectors in their basis
  • LoadCoordinator maintains and destributes the global lattice basis

Customized part of CMAP-LAP

  • Add CMapDeepBkzLoadCoordinator by inheriting CMapLapParaLoadCoordinator
  • Add CMapDeepBkzParaSolver by inheriting CMapLapParaParaSolver
  • Add DeepBKZ reduction algorithms with basis sharing through CMapDeepBkzParaSolver's API
Clone this wiki locally