Peta-scale General Solver for Semidefinite Programming– Extremely Large-scale Parallel Cholesky Solver –Kyushu University & JST CREST
Tokyo Institute of Technology & JST CREST

1.

∗ FUJISAWA Katsuki

ENDO Toshio

Introduction

In the last two decades, semidefinite programming (SDP) problems have been intensively studied
both in theoretical and practical aspects in a wide range of fields such as combinatorial optimization,
structural optimization, control theory, economics, quantum chemistry, sensor network location, datamining, and machine learning. The SDPA algorithm (SDPA) is one of the most famous software
packages of the primal-dual interior-point method (PDIPM) for solving the standard-form SDP problem (formulation (1)). software packages including the SDPA to be solvable on a single node. Thereexist two well-known major bottleneck parts in the algorithmic framework of PDIPM. The first partis the generation of the so-called Schur complement matrix (SCM). The second part is the Cholesky
factorization of SCM. These two parts are called ELEMENTS and CHOLESKY, respectively.
The standard-form SDP has the following primal-dual form.
P: minimize
subject toD: maximize
subject to∑mck xkk=1∑m
X = k=1 F k xk − F 0 ,X ⪰ O.
F0 • YF k • Y = ck (k = 1, . . . , m),Y ⪰ O.

(1)

We denote by Sn the space of n × n symmetric matrices. The notation X ⪰ O (X ≻ O) indicatesthat X ∈ Sn is a positive semidefinite(positivedefinite) matrix. The inner-product between U ∈ Sn∑∑nnand V ∈ Sn is defined by U • V = i=1 j=1 Uij Vij .
The size of a given SDP problem can be roughly measured in terms of five metrics:
1. m: the number of equality constraints in the dual form D (which equals the size of the SCM)
2. n: the size of the variable matrices X and Y
We denote the time complexities of ELEMENTS and CHOLESKY by O(mn3 + m2 n2 ) and O(m3 ),respectively.
We developed a new version of semidefinite programming algorithm parallel version (SDPARA)
7.6.0-G, which is a parallel implementation on multiples CPUs and GPUs for solving extremely largescale SDP problems. SDPARA is designed to execute PDIPM on parallel computers with distributed
memory space. The speed-up achieved by SDPARA is essentially attributable to its use of parallel
computation to overcome the computational bottlenecks of ELEMENTS and CHOLESKY. Eachprocess reads the input data and stores them and all variables in the process memory space, while theSCM data are divided between processes. We previously reported that SDPARA can compute eachrow of the SCM in parallel, and applied the parallel Cholesky factorization provided by ScaLAPACKto the SCM. In our previous work [1], we developed SDPARA 7.5.0-G on TSUBAME 2.0 1 , which
is a high-performance GPU-accelerated supercomputer at the Tokyo Institute of Technology. We
solved the largest SDP problem (which has over 1.48 million constraints), and created a new world
record in 2012. In the same year, our implementation also achieved 533 TFlops in double precision
for large-scale Cholesky factorization using 4,080 GPUs.
1

http://www.gsic.titech.ac.jp/en/tsubame

2.

Extremely Large-scale Parallel Cholesky Solver

As mentioned in the previous Section, SDP has many applications that involve SDP problems
with special structures. We initiated the SDPA project 2 , which aims to develop high-performance
software packages for SDP, and we have solved a large number of SDP problems since 1995; therefore,
we can classify the various types of SDP problems into the following three cases:
1. Case 1: SDP problems are sparse and satisfy the property of correlative sparsity; therefore,
SCM tends to become sparse (e.g., the sensor network location problem and the polynomial
optimization problem). In this case, CHOLESKY is the bottleneck part of PDIPM.
2. Case 2: m is less or not considerably greater than n and SCM is fully dense (e.g., the quantum
chemistry problem and the truss topology problem). In this case, ELEMENTS is the bottleneck
part of PDIPM, so we can decrease the time complexity of ELEMENTS O(mn3 + m2 n2 ) toO(m2 ) by exploiting the sparsity of the data matrix.
3. Case 3: m is considerably greater than n and SCM is fully dense (e.g., the combinatorial
optimization problem and quadratic assignment problem(QAP) [1]). In this case, CHOLESKY
is the bottleneck part of PDIPM.
Table 1: Performance (teraflops) of GPU CHOLESKY obtained by using up to 1360 nodes (4080GPUs) on TSUBAME 2.0 [1] and 2.5 [2].
(a) 400 nodes (1200 GPUs)

Name
QAP6
QAP7

m
709,275
1,218,400org(2.0)
223.0
248.8

new(2.0)
233.0
306.2

new(2.5)
314.5
505.8

(b) 700 nodes (2100 GPUs)

Name
QAP6
QAP7
QAP8

m
709,275
1,218,400
1,484,406

org(2.0)
309.5
440.0
463.8

new(2.0)
329.0
470.0
512.9

new(2.5)
387.5
707.1
825.1

(c) 1360 nodes (4080 GPUs)

Name
QAP6
QAP7
QAP8
QAP9
QAP10

m
709,2751,218,400
1,484,406
1,962,225
2,339,331

org(2.0)
439.6
695.2
779.3
––

new(2.0)
437.8
718.8
825.6
964.4
1018.5new(2.5)
508.7
952.0
1186.41526.51713.0We previously reported that SDPARA can certainly determine whether the SCM of an input SDP
problem becomes sparse (Case 1) or not (Cases 2 and 3). In the present study, we mainly focusedon parallel computation of ELEMENTS and CHOLESKY in Cases 2 and 3, respectively. We also
demonstrated that SDPARA is a high-performance general solver for SDPs in various application
fields through numerical experiments on the TSUBAME 2.5 supercomputer and solved the largest
SDP problem (QAP10), which has over 2.33 million constraints [2]; and we created a new world
record. Fig 1 and Table 1 show the speed of the CHOLESKY component in teraflops.
New
corresponds to the latest algorithm [2], while org denotes the original algorithm in our previous
paper [1]. Our implementation also achieved 1.713 PFlops in double precision for large-scale Cholesky
factorization using 2,720 CPUs and 4,080 GPUs. Table 2 shows that the speed of the CHOLESKY
2

http://sdpa.sourceforge.net/

Table 2: Performance (teraflops) of GPU CHOLESKY obtained by using up to 384 nodes (384 GPUs)
on CX400(a) 128 nodes (128 GPUs)

Name
QAP6
QAP7

m
709,275
1,218,400

Name
QAP8
QAP8-1m
1,484,406
1,495,602

org(2.0)––

new(2.0)––

new(2.5)
90.1
98.7(b) 384 nodes (384 GPUs)org(2.0)––

new(2.0)––

new(2.5)
288.0
294.2

component in teraflops on the CX400 supercomputer at Kyushu University. We have achieved 294.2TFlops when using 384 GPUs.
1713
1526

Speed of CHOLESKY (TFlops)

1186
952 1019
964

1024

512

506

825

826

707

719

509

513
470

438

388
329

314
306

256

233

400

512

700

1024

1360

Number of nodes
QAP6/org(2.0)
QAP7/org(2.0)
QAP8/org(2.0)
QAP9/org(2.0)
QAP10/org(2.0)

QAP6/new(2.0)
QAP7/new(2.0)
QAP8/new(2.0)
QAP9/new(2.0)
QAP10/new(2.0)

QAP6/new(2.5)
QAP7/new(2.5)
QAP8/new(2.5)
QAP9/new(2.5)
QAP10/new(2.5)

Figure 1: Performance of GPU CHOLESKY obtained by using up to 1360 nodes (4080 GPUs) onTSUBAME 2.0 and 2.5.

Acknowledgment
This research was supported by Advanced Computational Scientific Program of ResearchInstitute for Information Technology, Kyushu University, the Japan Science and Technology Agency(JST), the Core Research of Evolutionary Science, and Technology(CREST) research project, andthe TSUBAME 2.5 Supercomputer Grand Challenge Program at the Tokyo Institute of Technology.

REFERENCES[1] K. Fujisawa et al. : High-Performance General Solver for Extremely Large-scale Semidefinite
Programming Problems, The 2012 ACM/IEEE Conference on Supercomputing, SC’12, (2012)[2] K. Fujisawa et al. : Peta-scale General Solver for Semidefinite Programming Problems with overTwo Million Constraints, The 28th IEEE International Parallel & Distributed Processing Symposium (IPDPS2014), (2014)