ParaNUOPT: Parallelization of NUOPT by using UG
on cloud computing platform
June 25, 2019
NTT DATA Mathematical Systems Inc. *Yasumi Ishibashi
Zuse Institute Berlin
Yuji Shinano© 2018 NTT DATA Mathematical Systems Inc.

Contents
1. Overview
2. UG and ParaNUOPT

3. HPC on Cloud
4. Computational Experiment
5. Conclusion© 2018 NTT DATA Mathematical Systems Inc.

1/27

Contents
1. Overview
2. UG and ParaNUOPT

3. HPC on Cloud
4. Computational Experiment
5. Conclusion© 2018 NTT DATA Mathematical Systems Inc.

2/27

1. Overview
 Motivation• Easily get machine resources by cloud computing services• Easily get distributed B&B solver parallelized by UG• Easily run distributed B&B solver on a cloud HPC environment

 Question• Does UG work efficiently on a cloud HPC environment such asAWS ?
• Confirm the speedup of ParaNUOPT on AWS• Confirm the impact of network performance on speedup Answer• Under investigation. But,
• 4 times speedup with 8 compute nodes in some problems on AWS• Super-linear speedup on AWS, not a supercomputer© 2018 NTT DATA Mathematical Systems Inc.

3/27

Contents
1. Overview
2. UG and ParaNUOPT

3. HPC on Cloud
4. Computational Experiment
5. Conclusion© 2018 NTT DATA Mathematical Systems Inc.

4/27

2-1. What is UG ?
 UG (http://ug.zib.de)• Framework to parallelize branch and bound solver (Shinano 2010)
 Already parallelize many solvers• SCIP (Shinano 2010) -> ParaSCIP• Xpress (Shinano 2016) -> ParaXpress• PIPS-SBB (Munguía 2017)• and so on
 Computational results on a supercomputer are reported
 ParaSCIP and ParaXpress solved open instances from MIPLIB2017
 Details of UG will be given in the following talkTuesday, 14:30-16:00 - L249
Software for large-scale optimization IIConfiguring ParaXpress to Enhance its Heuristic Performance
Yuji Shinano, Timo Berthold, Lluis-Miquel Munguia© 2018 NTT DATA Mathematical Systems Inc.

5/27

2-2. Mechanism of UG (1/2)
 Supervisor-Worker coordination mechanism with subtree parallelism(Ralphs+ 2016)• Worker solves unexplored nodes of search tree
• Supervisor coordinates workload, communicates with each workers
 Communication is basically one to one
Supervisor (LoadCoordinator)

Worker (BaseSolver)© 2018 NTT DATA Mathematical Systems Inc.

6/27

2-2. Mechanism of UG (2/2)
 Supervisor-Worker coordination mechanism with subtree parallelism(Ralphs+ 2016)• Worker solves unexplored nodes of search tree
• Supervisor coordinates workload, communicates with each workers
 Communication is basically one to one

MessageFrequency

Size

Worker status

regularly

small (60 bytes)

Primal boundwhen needed double (8 bytes)

Incumbent solution

when needed depend on the number of vars.

Unexplored node (task)

when needed depend on the number of vars.

 Worker status is the only message communicated regularly• Expect that network performance does not affect the speedup of UG© 2018 NTT DATA Mathematical Systems Inc.

7/27

2-3. What is NUOPT and ParaNUOPT ?
 NUOPT• Commercial mathematical optimization solver ParaNUOPT• NUOPT parallelized by UG for research ParaNUOPT first solved the following open instances from MIPLIB2017• gen-ip016 (in 71498 seconds, on PC cluster with 19 cores)• rococoC11-010100 (in 32368 seconds, on PC cluster with 9 cores) Does UG work also efficiently on a cloud HPC cluster ?
• If this answer is “Yes”,
anyone who does not have a supercomputer can use it© 2018 NTT DATA Mathematical Systems Inc.

8/27

Contents
1. Overview
2. UG and ParaNUOPT

3. HPC on Cloud
4. Computational Experiment
5. Conclusion© 2018 NTT DATA Mathematical Systems Inc.

9/27

3-1. What is Cloud Computing Service?
 Cloud computing service• Provide computing resources/services via the internet
 Major cloud venders• Amazon (AWS : https://aws.amazon.com ) market leader• Microsoft (Azure : https://azure.microsoft.com )• Google (GCP : https://cloud.google.com ) Cloud venders provide various virtual machines• Let's see the virtual machines of AWS for HPC© 2018 NTT DATA Mathematical Systems Inc.

10/27

3-2. Virtual Machines for HPC (AWS) Purpose：Computing
 CPU：Intel Xeon Platinum 3.0 GHz
 Network Bandwidth：10 Gbps
 Price (Tokyo)： Spot price gives about 70% discount

VM(EC2 Instance)

CPU

Memory(GiB)

NetworkBandwidth(Gbps)

On-demand
Spot Price
Price ($/hour) ($/hour)c5.xlarge

28100.214

0.0736c5.2xlarge

416100.428

0.1364c5.4xlarge

832100.856

0.2661c5.9xlarge

1872101.926 -70% 0.5998

c5.18xlarge

36144

103.852© 2018 NTT DATA Mathematical Systems Inc.

11/27

1.1976

3-3. How to create HPC on AWS
 ParallelCluster (http://aws-parallelcluster.readthedocs.io)• Create flexible HPC cluster with a single command When there are no jobs, compute nodes will be shutdown
 save money

 Other cloud vendors also provide tools to create HPC cluster• What cloud vendors provide the best HPC cluster ?

© 2018 NTT DATA Mathematical Systems Inc.

12/27

3-4. HPC comparison on the cloud Mohammad and Timur compared cloud HPC cluster
by using High Performance LINPACK (2018); Microsoft AzureVendor

VMCoresFreq. (GHz) RAM (Gb) Network.

AzureH16r

18

3.2

112

Infiniband 54Gbps

AWSc4.8xlarge 18

2.960

Ethernet 10Gbps

Azure vs AWS

2030

15
20
1015
10

5
50

0
1(18)

2(36)

4(72)

8(144)

16(288)

Number of compute nodes (Cores)© 2018 NTT DATA Mathematical Systems Inc.

13/27

32(576)

Speedup

The higher
Rmax isbetter

RMax (TFLOPS)

25

Azure H16r

AWS c4.8xlarge
Azure H16r
AWS c4.8xlarge

3-5. Question (1/2)
 Communication-intensive application will not be accelerated on AWS
 Because AWS does not provide Infiniband.
 HPC cluster on Azure is the best for High Performance LINPACK

 Question• Does UG work efficiently on a cloud HPC environment such asAWS ?

• When we use UG, what cloud vendors is the best in terms ofcost and performance ?

© 2018 NTT DATA Mathematical Systems Inc.

14/27

3-5. Question (2/2)
 Communication-intensive application will not be accelerated on AWS
 Because AWS does not provide Infiniband.
 HPC cluster on Azure is the best for High Performance LINPACK

 Question• Does UG work efficiently on a cloud HPC environment such asAWS ?
• Confirm the speedup of ParaNUOPT on AWS• Confirm the impact of network performance on speedup• When we use UG, what cloud vendors is the best in terms ofcost and performance ?

© 2018 NTT DATA Mathematical Systems Inc.

15/27

3-6. Performance of Virtual Machine on AWS
VM (EC2)

Freq. Cores(GHz)

NB = Network Bandwidth
Memory NB
NB
Network(GiB)(Single) (Total)
Latency

c4.8xlarge

2.960?

10 Gbps ?

limit to 18 144?

25 Gbps ?

c5.18xlarge 3.018MemoryBandwidth

Copy(GB/s)

Scale
Add(GB/s) (GB/s)

Triad(GB/s)

c4.8xlarge

58.16

56.02

61.04

62.94

c5.18xlarge

129.45120.94 135.66

132.75Total

by STREAM (version 5.10)© 2018 NTT DATA Mathematical Systems Inc.

Single16/27

3-7. Measure Network Bandwidth/Latency (1/2)
Single 1-to-1

 OpenMPI 4.0.1
 OSU MICRO BENCHMARKS 5.6.1
 Logarithmic scale
16384
8192
4096
2048
1024
512
256
12864
32
1684214096

c4.8xlarge

2048

c4.8xlargec5.18xlarge

1024c5.18xlarge

512

Latency (μs)

Bandwidth (Mbps)

max 10 Gbps

256128643216842
1
Size (Byte)© 2018 NTT DATA Mathematical Systems Inc.

Size (Byte)

17/27

3-7. Measure Network Bandwidth/Latency (2/2)
 Latency of c4.8xlarge is 1.7 times slower than c5.18xlarge Bandwidth of c4.8xlarge is about 0.6 times smaller than c5.18xlarge formessages of 8192 bytes or lessc4.8xlarge vs c5.18xlarge
3.5

bandwidth

Ratio (c4 / c5)

3latency

2.5
2

1.7

1.5
10.6

0.5© 2018 NTT DATA Mathematical Systems Inc.

18/27

4194304

20971521048576524288262144

65536

32768

131072Size (byte)

16384

8192

4096

2048

1024

512

256128643216842103-8. Performance of Virtual Machine on AWS
VM (EC2)

Freq. Cores(GHz)

NB = Network Bandwidth
Memory NB
NB
Ratio of(GiB)(Single) (Total)
Network
Latency

c4.8xlarge

2.9

60

c5.18xlarge 3.0

18max
10 Gbps slower 1.7x10 Gbps

limit to 18 144max
25 Gbps 1.010 Gbps
SingleMemoryBandwidthCopy(GB/s)

ScaleAdd(GB/s) (GB/s)

Triad(GB/s)

c4.8xlarge

58.16

56.02

61.04

62.94

c5.18xlarge

129.45120.94 135.66

132.75by STREAM (version 5.10)© 2018 NTT DATA Mathematical Systems Inc.

19/27

Total

Contents
1. Overview
2. UG and ParaNUOPT

3. HPC on Cloud
4. Computational Experiment
5. Conclusion© 2018 NTT DATA Mathematical Systems Inc.

20/27

4-1. Configuration of Computational Experiment Use c4.8xlarge and c5.18xlarge• Confirm the speedup of ParaNUOPT on AWS• Confirm the impact of network performance on the speedup Use three problems as MIPProblem

LIBVariables

Constraints

Nonzeroschr20a (*)

QAPLIB

800

441

16,440fastxgemm-n2r6s0t2 MIPLIB2017 784

5,998

19,376

nu25-pr12

2,313

17,712MIPLIB2017 5,868(*) QAP is linearized by Kauffmann and Broeckx formulation (1978)

 Run ParaNUOPT 10 times to give an average value Because ParaNUOPT is nondeterministic
 Turn off racing of UG so that parameters will not change dynamically© 2018 NTT DATA Mathematical Systems Inc.

21/27

4-2. Result (chr20a)
 800 variables, 441 constraints, 16,440 nonzeros
3000

c5.18xlargec4.8xlargec5.18xlarge

c4.8xlarge

6.00

2500

4.00
1500
3.00
1000

Speedup

5.00

2000

Time (s)

7.00

2.00

500

1.00

00.00
1(18)

2(36)

4(72)

8(144)

16(288)

Number of compute nodes (Cores) The slight difference in speedup with 16 compute nodes,
but the speedup with up to 8 compute nodes is the same chr20a is so easy that the speedup may saturate with 16 compute nodes© 2018 NTT DATA Mathematical Systems Inc.

22/27

4-3. Result (fastxgemm-n2r6s0t2)
 784 variables, 5,998 constraints, 19,376 nonzeros2500

c5.18xlarge

c4.8xlargec5.18xlarge

c4.8xlarge

8.00
7.00

2000
6.00

Time (s)

4.00
1000

3.00
2.00

500
1.00
00.00
1(18)

2(36)

4(72)

8(144)

Number of compute nodes (Cores) Can not confirm the difference in speedup© 2018 NTT DATA Mathematical Systems Inc.

23/27

16(288)Speedup

5.00

1500

4-4. Result (nu25-pr12)
 5,868 variables, 2,313 constraints, 17,712 nonzeros
3000

c5.18xlarge

c4.8xlargec5.18xlarge

c4.8xlarge

45.00
40.00

2500
35.00
30.00
25.00
1500
20.00
1000

SpeedupTime (s)2000

15.00
10.00

500
5.00

00.00
1(18)

2(36)

4(72)

8(144)

Number of compute nodes (Cores)

16(288)

 Super-linear speedup
 The difference in speedup at more than 4 compute nodes© 2018 NTT DATA Mathematical Systems Inc.

24/27

4-5. Number of Explored Nodes (nu25-pr12)
Number of explored nodes

35000000

c5.18xlarge

30000000

c4.8xlarge

25000000
20000000
15000000
10000000

reversed

5000000
0

1(18)

2(36)

4(72)

8(144)

16(288)

Number of compute nodes (Cores) The number of explored nodes on c5 with 1 comp. node is larger than c4• Base of the speedup on c5 is worse than c4
 The number of explored nodes is reversed at 4 compute nodes• C5 gets the larger speedup than c4© 2018 NTT DATA Mathematical Systems Inc.

25/27

Contents
1. Overview
2. UG and ParaNUOPT

3. HPC on Cloud
4. Computational Experiment
5. Conclusion© 2018 NTT DATA Mathematical Systems Inc.

26/27

5. Conclusion
 Question• Does UG work efficiently on a cloud HPC environment such as
AWS ?
 Answer• Under investigation. But,
• 4 times speedup with 8 compute nodes in some problems on AWS• Super-linear speedup on AWS, not a supercomputer Future work
• Problems used for this experiment may be too easy
 Try large and hard problems• Confirm clearly the impact of network performance on the speedup
 Compare the performance of ParaNUOPT between Ethernet andInfiniband© 2018 NTT DATA Mathematical Systems Inc.

27/27

References
1.

L. Kaufman, et al. “An algorithm for the quadratic assignment problem using Bender'sdecomposition". European Journal of Operational Research 2.3, 1978, pp. 207-211.

2.

Y. Shinano, et al. “ParaSCIP: a parallel extension of SCIP". In Competence in High
Performance Computing 2010. Springer, 2011, pp. 135-148.

3.

Y. Shinano, et al. “A first implementation of ParaXpress: Combining internal and external
parallelization to solve MIPs on supercomputers". In International Congress on
Mathematical Software. Springer, 2016, pp. 308-316.

4.

L. M. Munguía, et al. “Parallel PIPS-SBB: Multi-level parallelism for stochastic mixedinteger programs". Computational Optimization and Applications, 2017, pp. 1-27.

5.

T. Ralphs, et al. “Parallel solvers for mixed integer linear optimization". In Handbook ofparallel constraint reasoning, Springer, 2018, pp. 283-336.

6.

M. Mohammadi, et al. “Comparative benchmarking of cloud computing vendors with highperformance linpack". In Proceedings of the 2nd International Conference on High
Performance Compilation, Computing and Communications, 2018, pp. 1-5.

© 2018 NTT DATA Mathematical Systems Inc.

28/27

© 2018 NTT DATA Mathematical Systems Inc.