Skip to content

Numerical Experiments in Papers

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

Table of Contents

CMAP-LAP [Tat+21a]

VI.B. Information sharing

Setting files

This experiment is for evaluation the effect of information-sharing scheme of CMAP-TEST.

Common settings for this experiment are follows.

  • 1 supervisor process
  • 143 solver processes
  • all solvers execute DeepBKZ lattice basis reduction algorithm

These CMAP-LAP parameter setting enable us to realize "all solvers execute DeepBKZ".

NumOfInitialDeepBkzSolvers = -1  # assign DeepBKZ algorithm to all remaining solvers
NumOfInitialEnumSolvers    = 0  # do not assign ENUM algorithm
NumOfInitialSieveSolvers   = 0  # do not assign Sieve algorithm

We executed CMAP-TEST following three patterns.

  1. size of share-data pool = 100,000
  2. size of share-data pool = 1
  3. size of share-data pool = 0

We can change the size of share-data pool by setting ShareDataPoolSize value.

ShareDataPoolSize = 100000

We show the full setting file for size of share-data pool = 100,000, for example.

# -------------------------------------------
#     Logging
# -------------------------------------------
Quiet = FALSE
LogSolvingStatus = TRUE
LogSolvingStatusFilePath  = "./logs/all_deepbkz.poolsize100000__"
CheckpointFilePath        = "./logs/all_deepbkz.poolsize100000__"
SolutionFilePath          = "./logs/all_deepbkz.poolsize100000__"

# ------------------------------------------
#     Checkpoint
# ------------------------------------------
Checkpoint = TRUE
CheckpointInterval = 600

# ------------------------------------------
#     Base ( Communication )
# ------------------------------------------
TimeLimit = 3600
NotificationInterval = 60
IReceiveInterval     = 1
ShareVectorsInterval = 10
CMapLapParamFilePath = "./settings/cmaplap.ug.param"

# ------------------------------------------
#     Base ( LC )
# ------------------------------------------
NumOfInitialDeepBkzSolvers = -1
NumOfInitialEnumSolvers    = 0
NumOfInitialSieveSolvers   = 0
ShareDataPoolSize = 100000

# ------------------------------------------
#     DeepBkz
# ------------------------------------------
# ReductionType; 1 no-communication, 2 parallel
DeepBkzReductionType = 2
DeepBkzStartBlockSize = 30
DeepBkzEndBlockSize = 30
DeepBkzBlockSizeInterval = 5
RandomizeRows = -1
DeepBkzNumOfSendVectorsToPool = 5
DeepBkzNumOfReceiveVectorsFromPool = 1

Commands

1. size of share-data pool = 100,000

mpiexec.hydra -n 4 ./bin/paracmaptest ./settings/cmaplap.paper/all_deepbkz.poolsize0.set ./storage/svpmatrix/dim100/LLL/dim100seed0LLL.txt -ntpr 1

2. size of share-data pool = 1

mpiexec.hydra -n 4 ./bin/paracmaptest ./settings/cmaplap.paper/all_deepbkz.poolsize1.set ./storage/svpmatrix/dim100/LLL/dim100seed0LLL.txt -ntpr 1

3. size of share-data pool = 0

mpiexec.hydra -n 4 ./bin/paracmaptest ./settings/cmaplap.paper/all_deepbkz.poolsize100000.set ./storage/svpmatrix/dim100/LLL/dim100seed0LLL.txt -ntpr 1

VI.C. Coordination of heterogeneous algorithms

Setting files

This experiment is for evaluation the effect of heterogeneous algorithm execution scheme of CMAP-TEST.

  • 1 supervisor process
  • 143 solver processes
  • size of share-data pool = 100,000

We executed CMAP-TEST following four patterns.

1. (DeepBKZ, sub-ENUM, GaussSieve) = (143, 0, 0)
2. (DeepBKZ, sub-ENUM, GaussSieve) = (126, 16, 1)
3. (DeepBKZ, sub-ENUM, GaussSieve) = (110, 32, 1)
4. (DeepBKZ, sub-ENUM, GaussSieve) = (78, 64, 1)

We can change the number of algorithms by setting NumOfInitialDeepBkzSolvers, NumOfInitialEnumSolvers and NumOfInitialSieveSolvers.

For example, when we want to execut (DeepBKZ, sub-ENUM, GaussSieve) = (78, 64, 1) configure, we set the parameters as follows.

NumOfInitialDeepBkzSolvers = 78
NumOfInitialEnumSolvers = 64
NumOfInitialSieveSolvers = 1

We show the full setting file for (DeepBKZ, sub-ENUM, GaussSieve) = (78, 64, 1) configure.

# -------------------------------------------
#     Logging
# -------------------------------------------
Quiet = FALSE
LogSolvingStatus = TRUE
LogSolvingStatusFilePath  = "./logs/deepbkz78.enum64.sieve1__"
CheckpointFilePath        = "./logs/deepbkz78.enum64.sieve1__"
SolutionFilePath          = "./logs/deepbkz78.enum64.sieve1__"

# ------------------------------------------
#     Checkpoint
# ------------------------------------------
Checkpoint = TRUE
CheckpointInterval = 600

# ------------------------------------------
#     Base ( Communication )
# ------------------------------------------
TimeLimit = 3600
NotificationInterval = 60
IReceiveInterval     = 1
ShareVectorsInterval = 10
CMapLapParamFilePath = "./settings/cmaplap.ug.param"

# ------------------------------------------
#     Base ( LC )
# ------------------------------------------
NumOfInitialDeepBkzSolvers = 78
NumOfInitialEnumSolvers    = 64
NumOfInitialSieveSolvers   = 1
ShareDataPoolSize = 100000

# ------------------------------------------
#     DeepBkz
# ------------------------------------------
# ReductionType; 1 no-communication, 2 parallel
DeepBkzReductionType = 2
DeepBkzStartBlockSize = 30
DeepBkzEndBlockSize = 30
DeepBkzBlockSizeInterval = 5
RandomizeRows = -1
DeepBkzNumOfSendVectorsToPool = 10
DeepBkzNumOfReceiveVectorsFromPool = 1

# ------------------------------------------
#     Enum
# ------------------------------------------
EnumPruningParameter = 1e-10
EnumSamplingDepth = 3
EnumNumOfSendVectorsToPool = 10

# ------------------------------------------
#     Sieve
# ------------------------------------------
SieveMaxCollision = -1
SieveMaxListSize  = -1
SieveMaxStackSize = -1
SieveNumOfSendVectorsToPool = 5
SieveNumOfReceiveVectorsFromPool = 100

Commands

1. (DeepBKZ, sub-ENUM, GaussSieve) = (143, 0, 0)

mpirun -n 144 ./bin/paracmaptest ./settings/cmaplap.paper/deepbkz143.enum0.sieve0.set ./storage/svpmatrix/dim100/LLL/dim100seed0LLL.txt -ntpr 1

2. (DeepBKZ, sub-ENUM, GaussSieve) = (126, 16, 1)

mpirun -n 144 ./bin/paracmaptest ./settings/cmaplap.paper/deepbkz126.enum16.sieve1.set ./storage/svpmatrix/dim100/LLL/dim100seed0LLL.txt -ntpr 1

3. (DeepBKZ, sub-ENUM, GaussSieve) = (110, 32, 1)

mpirun -n 144 ./bin/paracmaptest ./settings/cmaplap.paper/deepbkz110.enum32.sieve1.set ./storage/svpmatrix/dim100/LLL/dim100seed0LLL.txt -ntpr 1

4. (DeepBKZ, sub-ENUM, GaussSieve) = (78, 64, 1)

mpirun -n 144 ./bin/paracmaptest ./settings/cmaplap.paper/deepbkz78.enum64.sieve1.set ./storage/svpmatrix/dim100/LLL/dim100seed0LLL.txt -ntpr 1



CMAP-DeepBKZ [Tat+21b]

4.3 Effect of sharing short vectors on the diversity of bases

This experiment is for quantify the diversity of bases while lattice basis reduction.

We use synchronous_cmapdeepbkz binary.

Common settings for this experiment are follows.

  • Syncronous experimtents
  • number of solvers = 100 (--num_solvers option)
  • all solvers execute DeepBKZ with blocksize = 30 (-b option)
  • number of tours = 200 (--total_tour option)

We experiments while changine number of shared vectors (--num_shares option). Experiment command is follows.

./bin/synchronous_cmapdeepbkz -i ./storage/svpmatrix/dim90/LLL/dim90seed0LLL.txt -b 30 --num_solvers 100 --num_threads 4 --num_shares 1 --total_tour 200

4.4 Distribution of reduced bases

This experiment is to investigate the heuristic of [22, Heuristic 3].

  • Generate 100 random basis copies
  • Run DeepBKZ 100 tour independently
  • Visualize (i,Divi(C,dg)− Divi(B, dg))

Experiment command is follows.

./bin/synchronous_cmapdeepbkz -i ./storage/svpmatrix/dim90/LLL/dim90seed0LLL.txt -b 30 --num_solvers 100 --num_threads 4 --num_shares 0 --total_tour 100

5.1.2 Analysis of MPI parallelization using CMAP-DeepBKZ

Setting files

This experiment is to evaluate the efficiency for sharing a part of lattice basis of each lattice reduction solvers.

  • Number of solvers is 2303
  • All solvers run DeepBKZ with blocksize 30

We experiments while chaning number of lattice vectors shared by setting DimensionOfSharedLattice parameter, e.g,

DimensionOfSharedLattice = 32

Commands

mpirun -n 2304 ./bin/paracmapdeepbkz ./settings/cmapdeepbkz.paper/share0.set ./storage/sample_mats/dim100.txt -ntpr 1

Reference

[Tat+21a] Nariaki Tateiwa, Yuji Shinano, Keiichiro Yamamura, Akihiro Yoshida, Shizuo Kaji, Masaya Yasuda, and Katsuki Fujisawa. “CMAP-LAP: Configurable massively parallel solver for lattice problems”. In: 2021 IEEE 28th International Conference on High Performance Computing, Data, and Analytics (HiPC). IEEE. 2021, pp. 42–52.

[Tat+21b] Nariaki Tateiwa, Yuji Shinano, Masaya Yasuda, Shizuo Kaji, Keiichiro Yamamura, and Katsuki Fujisawa. Massively parallel sharing lattice basis reduction. eng. Tech. rep. 21-38. Takustr. 7, 14195 Berlin: ZIB, 2021.

Clone this wiki locally