Configurable Massively Parallel Solver
for Lattice Problems
Nariaki Tateiwa(speaker)1, Yuji Shinano2, Keiichiro Yamamura1
Akihiro Yoshida1, Shizuo Kaji1, Masaya Yasuda3, Katsuki Fujisawa1
1 Kyushu University, Fukuoka, Japan

2 Zuse Institute Berlin, Berlin, German
3 Rikkyo University, Tokyo, Japan

1/October/2021
Second International UG Workshop 2021
Workshop on Parallel Algorithms in Tree Search and Mathematical Optimization@onlineContribution and topics
We developed Shortest Vector Problem (SVP) solver using UG
CMAP-LAP: the Configurable Massive Parallel
Solver for Lattice Problem
ü First Generalized UG application
ü SVP, the combinational problem,
supports security of a post-quantum cryptography

Topics of this presentation
ü How to use the Generalized UG to parallelize our solver?
ü Unique new features for solving SVP
ü Show performances of our solver via numerical experiments2Outline
1. Contribution & Introduction
2. What is SVP?
3. Key components of parallelization
4. System of our developed solver based on UG
5. Numerical experiments
6. Summary3

Outline

4

1. Contribution & Introduction
2. What is SVP?
3. Key components of parallelization
4. System of our developed solver
5. Numerical experiments
6. Summary

Topics
1. Definition of Lattice & SVP
2. Features of SVP
3. Benchmark

What is SVP ?

5

Lattice
Definition
An 𝑛-dimensional lattice is$ℒ 𝐁 ≔ ' 𝑥! 𝐛! ; 𝑥! ∈ ℤ!"#

O

𝐁 = 𝐛# , … , 𝐛$ are linearly independent vectors.
(𝐁 is called a “lattice basis”.)𝐛"𝐛!
fig: 2-dimensional lattice
All intersection 𝐯 in lattice are represented as𝐯 = 𝑥! 𝐛! + 𝑥" 𝐛" (x! , x" ∈ ℤ )What is SVP ?

6

Lattice
Definition
An 𝑛-dimensional lattice is$ℒ 𝐁 ≔ ' 𝑥! 𝐛! ; 𝑥! ∈ ℤ

𝐛′!

!"#

𝐁 = 𝐛# , … , 𝐛$ are linearly independent vectors.
(𝐁 is called a “lattice basis”.)

O

𝐛′"

𝐛"

Randomization of lattice basisℒ 𝐁 = ℒ 𝐔𝐁

∀𝐔: Unimodular matrix(𝑈 ∈ ℤ$×$ , det(𝑈) = ±1)

The lattice does not changeby transformation with unimodular matrix𝐛!
fig: 2-dimensional lattice
All intersection 𝐯 in lattice are represented as𝐯 = 𝑥! 𝐛! + 𝑥" 𝐛" (x! , x" ∈ ℤ )What is SVP ?

7

Shortest Vector Problem
Definition
The Shortest Vector Problem (SVP) asks to findthe shortest non-zero vector in the lattice

the shortest vectorO

minimize 𝐯
subject to 𝐯 ∈ ℒ(𝐁) ∖ {𝟎}

=

𝐛"

&

minimize𝒙 = 𝑥!, … , 𝑥"

subject to

∈ ℤ"

𝐛!

' 𝑥! 𝐛!
!"#𝒙 ≠ 𝟎fig: 2-dimensional latticeWhat is SVP ?

8

Shortest Vector Problem
Definition
The Shortest Vector Problem (SVP) asks to findthe shortest non-zero vector in the lattice

the shortest vectorO

minimize 𝐯
subject to 𝐯 ∈ ℒ(𝐁) ∖ {𝟎}

=

𝐛"

&

minimize𝒙 = 𝑥!, … , 𝑥"

subject to

∈ ℤ"

𝐛!

' 𝑥! 𝐛!
!"#𝒙 ≠ 𝟎fig: 2-dimensional latticeWhat is SVP ?

9

Why we try to solve Shortest Vector Problem?
Features

Lattice-based cryptography• no single definite algorithm• SVP supports the security of somelattice-based cryptographies• Common cryptographies have risk to bebroken by quantum computers• Lattice-based cryptography is the candidate of
new standard post-quantum cryptographies• urgent to investigate• security levelIC, credit card ..

If the size of the public key is large,
some of the current cryptosystems
cannot be replaced new cryptosystem
due to memory limitation.

Benchmark
SVP Challenge• contest of solving approximate SVP
of 40 – 200 dimension
𝟏. 𝟎𝟓-approximate SVP
Kinding𝐯 ∈ ℒ 𝐁 ∖ {𝟎}subject to 𝐯 ≤ 1.05 𝜆# ℒ 𝐁
the estimated optimal value•

Sieve-algorithm solver (G6K) is major,
recently10

Outline11

1. Contribution & Introduction
2. What is SVP?
3. Key components of parallelization

Topics▷ Algorithms for SVP
4. System of our developed solver based on1. UG

5. Numerical experiments
6. Summary

2. Features of algorithms
for parallelization

Lattice Problem Algorithms
Enumeration(Exactive)

d!

•
•
•

O

12

Reduction(Approximate)
O

c!

d"

d!

Sieve
(Probabilistic)O

sampledlattice vector

d"

𝑜

c"

Depth-first search
Nodes of the tree correspondto lattice vectors
Tree contains all lattice vectors
with norm ≤ 𝑅 ( parameter)ü pros: Low memory usage
ü cons: Huge searching timeü dim 100 --> 10^06 yearsü dim 130 --> 10^25 years(dim = dimension)••

Matrix transformation
make the lattice basis as close
to orthogonal as possible•••

ü pros: Low memory usage
ü cons: No guarantee for finding
the shortest vector

short lattice vector
generated fromtwo-samples

Sampling and Reduce
Generate shorter vectors byaddition(+) and subtraction(-)
sampled lattice vectors
Based on birthday paradox

ü pros: High performance
ü cons: Huge memory usage

Lattice Problem Algorithms
Enumeration(Exactive)

d!

•
•
•

O

13

Reduction(Approximate)
O

c!

d"

d!

Sieve
(Probabilistic)O

sampledlattice vector

d"

𝑜

c"

Depth-first search
Nodes of the tree correspondto lattice vectors
Tree contains all lattice vectors
with norm ≤ 𝑅 ( parameter)ü pros: Low memory usage
ü cons: Huge searching timeü dim 100 --> 10^06 yearsü dim 130 --> 10^25 years(dim = dimension)••

Matrix transformation
make the lattice basis as close
to orthogonal as possible•••

ü pros: Low memory usage
ü cons: No guarantee for finding
the shortest vector

short lattice vector
generated fromtwo-samples

Sampling and Reduce
Generate shorter vectors byaddition(+) and subtraction(-)
sampled lattice vectors
Based on birthday paradox

ü pros: High performance
ü cons: Huge memory usage

Lattice Problem Algorithms
Enumeration(Exactive)

d!

•
•
•

O

14

Reduction(Approximate)
O

c!

d"

d!

Sieve
(Probabilistic)O

sampledlattice vector

d"

𝑜

c"

Depth-first search
Nodes of the tree correspondto lattice vectors
Tree contains all lattice vectors
with norm ≤ 𝑅 ( parameter)ü pros: Low memory usage
ü cons: Huge searching timeü dim 100 --> 10^06 yearsü dim 130 --> 10^25 years(dim = dimension)••

Matrix transformation
make the lattice basis as close
to orthogonal as possible•••

ü pros: Low memory usage
ü cons: No guarantee for finding
the shortest vector

short lattice vector
generated fromtwo-samples

Sampling and Reduce
Generate shorter vectors byaddition(+) and subtraction(-)
sampled lattice vectors
Based on birthday paradox

ü pros: High performance
ü cons: Huge memory usage

Lattice Problem Algorithms
Enumeration(Exactive)

d!

•
•
•

O

15

Reduction(Approximate)
O

c!

d"

d!

Sieve
(Probabilistic)O

sampledlattice vector

d"

𝑜

c"

Depth-first search
Nodes of the tree correspondto lattice vectors
Tree contains all lattice vectors
with norm ≤ 𝑅 ( parameter)ü pros: Low memory usage
ü cons: Huge searching timeü dim 100 --> 10^06 yearsü dim 130 --> 10^25 years(dim = dimension)••

Matrix transformation
make the lattice basis as close
to orthogonal as possible•••

ü pros: Low memory usage
ü cons: No guarantee for finding
the shortest vector

short lattice vector
generated fromtwo-samples

Sampling and Reduce
Generate shorter vectors byaddition(+) and subtraction(-)
sampled lattice vectors
Based on birthday paradox

ü pros: High performance
ü cons: Huge memory usage

Key components of parallelization
Enumeration(Exactive)

d!

O

d"

16

Reduction(Approximate)
O

c!

d!

Sieve
(Probabilistic)
O

d"

c"

common features of algorithms
ü Behavior changes depending on input basis
ü Algorithms can also find short vectors (not only the shortest one)
ü Interactions of different algorithms

sampledlattice vector𝑜short lattice vector
generated fromtwo-samples

Key components of parallelization
Enumeration(Exactive)

d!

O

d"

17

Reduction(Approximate)
O

c!
c"

d!

Sieve
(Probabilistic)Od"sampledlattice vector𝑜short lattice vector
generated fromtwo-samples

common features of algorithms
Randomization of lattice basis

ü Behavior changes depending on input basis
ü Algorithms can also find short vectors (not only the ℒshortestone)∀$: Unimodular matrix" = ℒ $"(( ∈ ℤ!×! , det(() = ±1)
ü Interactions of different algorithms
The lattice does not changeby transformation with unimodular matrix

Parallel Strategy Idea
ü Task parallel strategy
ü basis is randomized
ü LoadCoordinator (master) distribute basis
ü Solver (worker) run algorithm independently
LoadCoordinator
Basis

b!

18

Solver A
O

c!

Reduction
Algorithmc"Solver B
Enumeration
Algorithm

Ob"
Solver C!

Sieve
Algorithm

Parallel Strategy Idea
ü Task parallel strategy
ü basis is randomized
ü LoadCoordinator (master) distribute basis
ü Solver (worker) run algorithm independently
LoadCoordinator
Basis

b!

19

Solver A
O

c!

Reduction
Algorithmc"Solver B
Enumeration
Algorithm

Ob"
Solver C

Can we improve the performanceby taking advantage of lattice properties?

!

Sieve
Algorithm

Key components of parallelization
Enumeration(Exactive)

d!

O

d"

20

Reduction(Approximate)
O

c!

d!

Sieve
(Probabilistic)
O

d"

c"

common features of algorithms
ü Behavior changes depending on input basis
ü Algorithms can also find short vectors (not only the shortest one)
ü Interactions of different algorithms

sampledlattice vector𝑜short lattice vector
generated fromtwo-samples

Key components of parallelization
Enumeration(Exactive)

d!

O

d"

21

Reduction(Approximate)
O

c!

d!

Sieve
(Probabilistic)
O

d"

c"

common features of algorithms
ü Behavior changes depending on input basis
ü Algorithms can also find short vectors (not only the shortest one)
ü Interactions of different algorithms

sampledlattice vector𝑜short lattice vector
generated fromtwo-samples

Key components of parallelization

22

Interactions of algorithms
ü lattice algorithms find• short lattice vectors,
not only shortest one• reduced basis

Case of Enumeration
Enumeration
Basis

d!

ü These can be used as
input and booster
for other algorithms

O

c!

d!

O

c"

make matrix
as close to orthogonald"Enumeration

Reduction
Basis

O

d"

Basis

d!

reduced basis

Od"Cost is small↓Key components of parallelization

23

Interactions of algorithms

Sieve-sampling

Case of Sieveü lattice algorithms find• short lattice vectors,
not only shortest one• reduced basis

𝑜

Basis

ü These can be used as
input and booster
for other algorithms

Reduction
Basis

O

c!

d!

O

d"

Basis

c"

make matrix
as close to orthogonal

reduced basis𝑜sampling
performance up↑

Key components of parallelization

24

Interactions of algorithms
Case of Sieveü lattice algorithms find• short lattice vectors,
not only shortest one• reduced basis

Enumerationd!

O

vectorsd"ü These can be used as
input and booster
for other algorithms

Reduction
Basis

O

c!

d!

O

c"

make matrix
as close to orthogonal𝑜d"sampling
performance up↑

Key components of parallelization

25

Interactions of algorithms
ü lattice algorithms findCase of Reduction• short lattice vectors,
not only shortest one• reduced basis

ü These can be used as
input and booster
for other algorithms

Enumerationd!

O

vectorsd"

Sieve

Reduction

sampledlattice vector!

short lattice vector
generated fromtwo-samples

O

c!

d!

O

d"

c"

output more
orthogonality basis ↑Key components of parallelization

26

By-products of the lattice algorithm
ü lattice algorithms find• short lattice vectors,
not only shortest one• reduced basis

ü These can be used as
input and booster
for other algorithms

ü However, there is no SVP solver which
effectively utilizes these interactions

Reduction(§4.4)

Enumeration(§4.1, 4.3)

reduced basis

Sieve(§4.2, 4.3)

short vectors

current shortest
vector foundOutline27

1. Contribution & Introduction
2. What is SVP?
3. Key components of parallelization

Topics

4. System of our solver based on UG

1. ▷ Overview

5. Numerical experiments

2. Communication of Task

6. Summary

3. Checkpointing
4. Asynchronously
Communication

CMAP-LAP: Our new solver
ü Supervisor-Worker parallelization type
ü Heterogeneous algorithm execution
ü Acceleration by asynchronously
sharing lattice vectors via data pool in LC

b"

O

c!

Reduction
Algorithm

Solver B

Basis PoolO

Solver A

c"

LoadCoordinatorb!

28

Enumeration
Algorithm

O

c!
c"

Solver C
Vector Pool!

Sieve
Algorithm

CMAP-LAP: Our new solver
Flow of execution• Create MPI processes• Start LoadCoordinator process in Rank 0,
and Solver processes in other Rank

29

Solver A (Rank = 1)

LoadCoordinator (Rank = 0)Basis Pool

Solver B (Rank = 2)

Solver C (Rank = 3)
Vector Pool

CMAP-LAP: Our new solver

30

Flow of execution
Solver A

Give Instance
LoadCoordinator
Basis Poolb!

Solver B

Ob"Solver C
Vector Pool

CMAP-LAP: Our new solver

31

Flow of execution
Solver A

createLoadCoordinator
Basis Pool
b!

O

b"

Task
Task
• instance
Short Vector• algorithm
Pool• parameters

Solver B

Solver C
Vector Pool

CMAP-LAP: Our new solver

32

Flow of execution
Solver A

createLoadCoordinator
Basis Pool
b!

O

b"

Task
Task
• instance
Short Vector• algorithm
Pool• parameters

O

c!
c"

Solver B

Solver C
Vector Pool

Reduction
Algorithm

CMAP-LAP: Our new solver

33

Flow of execution
Solver A
O

c!

LoadCoordinator
Basis Pool
b!

O

b"

Vector PoolcreateTask
Task• instance
Short Vector• algorithm
Pool• parameters

Reduction
Algorithmc"Solver B
Enumeration
Algorithm

Solver C

CMAP-LAP: Our new solver

34

Flow of execution
Solver A
O

c!

LoadCoordinator
Basis Pool
b!

O

b"

Vector Pool

Reduction
Algorithm

c"createTask
Task• instance
Short Vector• algorithm
Pool• parameters

Solver B
Enumeration
Algorithm
Solver C!

Sieve
Algorithm

CMAP-LAP: Our new solver

35

Flow of execution
Send Basis
Send/Receive Vectorb"c!

Reduction
Algorithm

Solver B

Basis Pool
O

O

c"

LoadCoordinatorb!

Solver A

Enumeration
Algorithm

O

c!
c"

Solver C
Vector Pool!

Sieve
Algorithm

CMAP-LAP: Our new solver

36

Flow of execution
Send Basis
Send/Receive Vectorb"c!

Reduction
Algorithm

Solver B

Basis Pool
O

O

c"

LoadCoordinatorb!

Solver A

Enumeration
Algorithm

O

c!
c"

Solver C
Vector Pool!

Sieve
Algorithm

CMAP-LAP: Our new solver

37

Flow of execution
Solver A

finishLoadCoordinator
Solver B

Basis Pool
b!

O

b"

Enumeration
Algorithm

O

c!
c"

Solver C
Vector Pool!

Sieve
Algorithm

CMAP-LAP: Our new solver

38

Flow of execution
Solver A

createLoadCoordinator
Basis Pool
O

c!
c"

Task
Task
• instance
Short Vector• algorithm
Pool• parameters

b!

O

b"

Reduction
Algorithm

Solver B
Enumeration
Algorithm
Solver C

Vector Pool!

Sieve
Algorithm

Implementation of Our new solver

39

~2020

2021

UG
( for only B&B solver )Generalized UG

refactoring almost
from scratch

UG_BB
inheritance

B&B
based
solvers…

MAP-SVP(our previous
SVP solver)

B&B
based
solvers…

CMAP-LAP(our new SVP
solver)Implementation of Our new solver

40

~2020

2021

UG
( for only B&B solver )Generalized UG

refactoring almost
from scratch

UG_BB
inheritance

B&B
based
solvers…

MAP-SVP(our previous
SVP solver)

inheritance

B&B
based
solvers…

CMAP-LAP(our new SVP
solver)Implementation of Our new solver

41

2021

Generalized UG provides• Customable and asynchronous
communication API for Task andother information• Checkpointing and restart
functionality• Both MPI and Pthreadcommunicators can be selected,
and hybrid parallelization ispossible by combining them

Generalized UG

UG_BB
inheritance

B&B
based
solvers…

CMAP-LAP(our new SVP
solver)Implementation of Our new solver

42

LoadCoordinator (LC)Basis

Solver Pool
SolverSolver

Task
⋯
Task

Task

⋯

Basis

Vector Pool
Vec Vec
Vec Vec⋯

Basis Pool⋯• Some data pool created in
LoadCoordinator for
sharing lattice basis andvector, and checkpointing

Message Handler

SolverParaSolver
Algorithm

Receive
Task

basis

StatusMessage Handler

Vec
Vec

Task

Basis

・Parameters+ ・Initial Status

Outline

43

1. Contribution & Introduction
2. What is SVP?
3. Key components of parallelization

Topics

4. System of our solver based on UG

1. Overview

5. Numerical experiments

2. ▷ Communication of Task

6. Summary

3. Asynchronously
Communication
4. CheckpointingTask
Create Send Receive Task

44

LoadCoordinator (LC)Basis Pool

Task is Triple of

pop

Basis
Basis

Task
Task

SolverSolver

Task
Task

⋯

⋯

• Instance

Solver Pool

• Basis 𝐁 ∈ ℤ$×$

• Algorithm• type of algorithm• Parameters• Parameters change duringexecution of the algorithm

SolverParaSolver

Message Handler

Task
Create Send Receive Task

45

LoadCoordinator (LC)Basis Pool

Task is Triple of

Basis
Basis

Task
Task

SolverSolver

Task
Task

⋯

⋯

• Instance

Solver Pool

• Basis 𝐁 ∈ ℤ$×$

send

• Algorithm• type of algorithm• Parameters• Parameters change duringexecution of the algorithm

SolverParaSolver

Message Handler

Asynchronously Communication

46

LoadCoordinator (LC)Create Send Receive Task

Basis PoolParaSolver class object executes

Solver Pool

Basis

Task

Basis

Solver

Task
Task

⋯

⋯

runAlgorithm(
basis, parameters, this)Solver=ParaSolver object pointerSolverParaSolver
Algorithm function
Reduction
O

c!
c"

d!

O

d"

Message Handler

Task

Basis

・Parameters+ ・Initial Status

Asynchronously Communication

47

⋯

⋯

LoadCoordinator (LC)function runAlgorithm(basis, Basisparams,*paraSolver){
Pool
Solver Pool
while( algorithm is not finished){
Solver
Basis
Task
Task
runSubroutine(basis,params, paraSolver);Basis
Solver Task
communicateToLC(paraSolver);// send or receive lattice vectors and basis// asynchronously}}
SolverParaSolver
Algorithm function
Reduction
O

c!
c"

d!

O

d"

Message Handler

Outline48

1. Contribution & Introduction
2. What is SVP?
3. Key components of parallelization

Topics

4. System of our solver based on UG

1. Overview

5. Numerical experiments

2. Communication of Task

6. Summary

3. ▷ Asynchronously
Communication
4. CheckpointingAsynchronously Communication – non-blocking version –run communicate
subroutine to LC

communicate runrun
to LC subroutine
subroutine

Algorithm
IProbeSolverCommunicator

IProbeVectors

want to need the shortvectors
ISend
LoadCoordinator

Vectors

Vectors49

Asynchronously Communication – non-blocking version –run communicate
subroutine to LC

communicate runrun
to LC subroutine
subroutine

Algorithm
IProbeSolverCommunicator

vectorrequest

Vectors

vectorrequest

Vectors

ISend

ISend

LoadCoordinator

IProbeVectors• communicator send “vector request” to LC by Isend (MPI_Isend),
which is non-blocking function50

Asynchronously Communication – non-blocking version –run communicate
subroutine to LC

communicate runrun
to LC subroutine
subroutine

Algorithm
IProbeSolverCommunicator

vectorrequest

Vectors

vectorrequest

Vectors

ISend

ISend

LoadCoordinator

IProbeVectors• Solver return to running algorithm• In subroutine, iProbe (MPI_Iprobe) is called to check the message

51

Asynchronously Communication – non-blocking version –run communicate
subroutine to LC

communicate runrun
to LC subroutine
subroutine

Algorithm
IProbeSolverCommunicator

vectorrequest

Vectors

ISend

LoadCoordinator

IProbevectorrequestISendvectors• LC prepare vectors according to the vector request• LC send vectors by Isend (MPI_Isend)

Vectors52

Asynchronously Communication – non-blocking version –run communicate
subroutine to LC

communicate runrun
to LC subroutine
subroutine

Algorithm
IProbeSolverCommunicator

vectorrequestvectors
ISend

LoadCoordinatorvectorrequestISendvectors• communicator receives vectors and keep them

Vectors

53

Asynchronously Communication – non-blocking version –run communicate
subroutine to LC

communicate runrun
to LC subroutine
subroutine

Algorithm
IProbeSolverCommunicator

vectorrequestvectors
ISend

LoadCoordinator

IProbevectorrequestvectors

ISendvectors• In the following communication part,the algorithm can use the vector received by the communicator54

Asynchronously Communication – non-blocking version –run communicate
subroutine to LC

communicate runrun
to LC subroutine
subroutine

Algorithm
IProbeSolverCommunicator

vectorrequestvectors
ISend

LoadCoordinator

IProbevectorrequest• Then, Solver run subroutine again …

ISendvectors

vectors55

Asynchronously Communication – non-blocking version –communicate
run
to LC
subroutine

communicate
communicate
run
run
to LC
to LC
subroutine
subroutine

Algorithm

SolverCommunicator

vectorrequestvectors
ISend

LoadCoordinatorvectorrequestISendvectors
Delay replay to request• Even if LC delays in replying to a vector request,
algorithm can receive vectors more next communication part
• SVP algorithm can incorporate vectors at any time

vectors56

Outline57

1. Contribution & Introduction
2. What is SVP?
3. Key components of parallelization

Topics

4. System of our solver based on UG

1. Overview

5. Numerical experiments

2. Communication of Task

6. Summary

3. Asynchronously
Communication
4. ▷ CheckpointingCheckpointing

58

LoadCoordinator (LC)Basis Pool

• Solver update task
according to the progressof algorithm

Basis

Task

Basis

SolverSolver

Task
Task

⋯

⋯

• Solver send update Task to
LC, and LC replaces it fromold task in solver pool

Solver Pool

Task

Basis

・Parameters+ ・Initial Status

SolverParaSolver
Algorithm function
Reduction
O

c!
c"

d!

O

d"

Message Handler

send &
updateCheckpointing

59

LoadCoordinator (LC)SolverSolver

Task
Task

⋯

• Write compressed data in Solver
Pool into checkpointing files, anddata in other pools write to files, too

Solver Poolwrite checkpoint files(Instance, Algorithm, Parameters)
for all solvers

Checkpointing
RestartLoad checkpoint file and store data intosolver pool

60

LoadCoordinator (LC)Solver Pool
SolverSolver

Task
Task

⋯

load checkpoint files(Instance, Algorithm, Parameters)
for all solvers

Checkpointing
Restart61

LoadCoordinator (LC)Basis Pool

Load checkpoint file andstore data into solver pool

Solver Pool

Basis

Task

Basis

SolverSolver

Task

⋯

⋯

Task

SolverParaSolver
Algorithm
Reduction
O

c!
c"

d!

O

Message Handler

Task
d"

Basis

・Parameters+ ・Initial Status

Outline
1. Contribution & Introduction
2. What is SVP?
3. Key components of parallelization
4. System of our solver
5. Numerical experiments
6. Summary

62

Numerical Experiments

63

New solution for SVP Challenge
CMAP-LAP• CMAP-LAP had succeeded in finding
shorter lattice vectors in
104, 111, 121, and 127
dimensions of the SVP Challenge.
• CMAP-LAP finds a sufficiently shortvector in a reasonably short time.
• The G6K, a famous SVP solver,
reported taking
14 days = 336 hours
to find a sufficiently short vector fora 127-dimensional lattice

CMAP-LAP

App. factor := approximation factor of the incumbent lattice vector

Numerical Experiments

64

New solution for SVP Challenge
CMAP-LAP• CMAP-LAP had succeeded in finding
shorter lattice vectors in
104, 111, 121, and 127
dimensions of the SVP Challenge.
• CMAP-LAP finds a sufficiently shortvector in a reasonably short time.
• The G6K, a famous SVP solver,
reported taking
14 days = 336 hours
to find a sufficiently short vector fora 127-dimensional lattice

CMAP-LAP

Numerical Experiments

65

New solution for SVP Challenge
CMAP-LAP• CMAP-LAP had succeeded in finding
shorter lattice vectors in
104, 111, 121, and 127
dimensions of the SVP Challenge.
• CMAP-LAP finds a sufficiently shortvector in a reasonably short time.
• The G6K, a famous SVP solver,
reported taking
14 days = 336 hours
to find a sufficiently short vector fora 127-dimensional lattice

CMAP-LAP

max #process is 91,200 in HLRN

Numerical Experiments

66

New solution for SVP Challenge
CMAP-LAP• CMAP-LAP had succeeded in finding
shorter lattice vectors in
104, 111, 121, and 127
dimensions of the SVP Challenge.
• CMAP-LAP finds a sufficiently shortvector in a reasonably short time.
• The G6K, a famous SVP solver,
reported taking
14 days = 336 hours
to find a sufficiently short vector fora 127-dimensional lattice

CMAP-LAP

App. factor := estimatedapproximation factor of theincumbent solution

Numerical Experiments
Scalability•

Scalability keeps even in the larger-scale, e.g.,
100,032 processes•

Metric is Root Hermite Factor 𝜸𝟏⁄𝒏 ,which is an index to measure
the output quality of a reduction algorithm
#/$

𝐛
⁄$
#
𝛾
≔
vol 𝐿 #⁄$
where 𝐛 is the shortest basis vector
output by reduction algorithm.
•

Smaller 𝛾 #⁄$ means that output quality is goodand find shorter vector•

All solver run Reduction ( DeepBKZ ) algorithm

67

Numerical Experiments
Sharing efficiency• Execute with different vector pool size•••

Size of pool = 0 ( blue )⇔ no sharing
Size of pool = 1 ( orange )⇔ sharing only incumbent vector
Size of pool = 100,000 ( green )⇔ sharing almost all short vectors•

All solver run Reduction ( DeepBKZ )algorithm•

With the effect of sharing vectors,
the Root Hermite Factor could get smaller

68

Numerical Experiments

69

Heterogeneously efficiency• Execute with different algorithm
configuration• #(Reduction, Enumeration, Sieve)
•
•
•
•

•
•

= (143,= (126,= (110,= (78,

0,
16,
32,
64,

0) ( blue )1) ( orange )1) ( green )1) ( red )There was difference in results
depending on the configuration
For further improvement,
it is necessary• tuning parameters• dynamic modification of theconfiguration

Future work

Numerical Experiments

70

Heterogeneously efficiency• Execute with different algorithm
configuration• #(Reduction, Enumeration, Sieve)
•
•
•
•

•
•

= (143,= (126,= (110,= (78,

0,
16,
32,
64,

0) ( blue )1) ( orange )1) ( green )1) ( red )There was difference in results
depending on the configuration
For further improvement,
it is necessary• tuning parameters• dynamic modification of theconfiguration

Future work

Numerical Experiments: communication overhead

71

Parallelization performance of UG
start LdOe tLme oI each soOver

7Lme [s]102• Definition of idle times

101
100
10−1
10−2
16

start

Solverstart idle time

7Lme [s]send / receive
vectors

64

84

104

124

144

180 1024 2048
I72 I72

10−3
10−5
10−7

108

wait idle time

16

32

48

64

84

104

124

144

180 1024 2048
I72 I72

7otaO number oI communLcatLons between LC and 6oOvers

106
Count

distributes
instance48

waLt LdOe tLme oI each soOver

10−1

LC
start

32

104
send

102

receLve

16

32

48

64

84

104

124

144

1umber oI Srocesses

180 1024 2048
I72 I72

Numerical Experiments: communication overhead

72

Parallelization performance of UG
start LdOe tLme oI each soOver• Although the LC's load increases, idle
time is much less than the total
running time per hour.

100
10−1
10−2
16

32

48

64

84

104

124

144

180 1024 2048
I72 I72

waLt LdOe tLme oI each soOver

10−1
7Lme [s]• As the number of processes increases,
the LC’s load increases

101

10−3
10−5
10−7

108

16

32

48

64

84

104

124

144

180 1024 2048
I72 I72

7otaO number oI communLcatLons between LC and 6oOvers

106
Count

• CMAP-LAP ran for two hours with
100-dimensional SVP as input

7Lme [s]

102

104
send

102

receLve

16

32

48

64

84

104

124

144

1umber oI Srocesses

180 1024 2048
I72 I72

Summary73

ü We developed a parallel solver for SVP based on Generalized UG
ü Supervisor-Worker parallelization type
ü Heterogeneous algorithm execution
ü Acceleration by asynchronously
sharing lattice vectorsb"Reduction
Algorithm

Solver B

Basis Pool
O

O

c!
c"

LoadCoordinatorb!

Solver A

Enumeration
Algorithm

O

c!
c"

Solver C
Vector Pool!

ü Update some SVP Challenge records
ü Show scalability and low communication overhead
sharing and heterogeneously efficiency of our solver

Sieve
Algorithm