University	  of	  Tsukuba	  	  | Center	  for	  Computational	  Sciences

Numerical	  Computation
Automatic	  Tuning	  of	  Computation-­‐Communication	  Overlap	  for	  Parallel	  1-­‐D	  FFTBackground
The fast Fourier transform (FFT) is widely used in science and engineering. Parallel FFTs on distributed-­‐memory parallel computersrequire intensive all-­‐to-­‐all communication, which affects their performance. How to overlap the computation and the all-­‐to-­‐allcommunication is an issue that needs to be addressed for parallel FFTs.

Overview
We proposed an automatic tuning of computation-­‐communication
overlap for parallel 1-­‐D FFT. We used a computation-­‐communication
overlap method that introduces a communication thread withOpenMP. An automatic tuning facility for selecting the optimal
parameters of the computation-­‐communication overlap, the radices,and the block size was implemented.

Performance
To evaluate the parallel 1-­‐D FFT with automatic tuning, we compared
its performance against that of FFTE 6.1alpha (http://www.ffte.jp/)
and that of FFTE 6.1alpha with automatic tuning (AT). The
performance results demonstrate that the proposed implementationof a parallel 1-­‐D FFT with automatic tuning is efficient for improving
the performance on Fujitsu PRIMEHPC FX100.

Development	  of	  Parallel	  Sparse	  Eigensolver Package:	  z-­‐Pares	  The aim of this research project is to develop numerical software for large-­‐ scale eigenvalue problems for post-­‐petascale computingenvironment. An eigensolver based on contour integral (the SS method) has been proposed by Sakurai and Sugiura [3]. Thismethod has a hierarchical structure and is suitable for massively parallel supercomputers [2]. Moreover, the SS method can beapplicable for nonlinear eigenvalue problem [1]. Block Krylov method [4] improves the performance of the method. Based on thesenewly designed algorithms, we have developed a massively parallel software z-­‐Pares freely-­‐available fromhttp://zpares.cs.tsukuba.ac.jp/. MATLAB version is also available in our webpage. We have also developed CISS eigensolver in SLEPc.

Hierarchical	  Parallel	  Structure

Numerical	  Example	  on	  the	  K	  Computer

Hardware is grouped according to a hierarchical structureof the algorithm.

Application for band calculation with real space density
functional theory (RSDFT) [2].

Algorithm

HardwareTop	  levelΓ1

Γ2

Γ3Middle	  levelz2z1zN

Bottom	  level

T (zj )Xj = VBand	  structure	  of	  silicon	  nanowire	  of	  9,924	  atoms.
(matrix	  size	  =	  8,719,488,	  	  Number	  of	  cores	  =	  6,144)	  *The	  results	  are	  tentative	  since	  they	  are	  obtained	  by	  early	  access	  to	  the	  K	  computer.	  

Reference	  [1]	  J.	  Asakura,	  T.	  Sakurai,	  H.	  Tadano,	  T.	  Ikegami	  and	  K.	  Kimura,	  A	  numerical	  method	  for	  nonlinear	  eigenvalue	  problems	  using	  contour	  integrals, JSIAM	  Letters,	  1	  (2009)	  52-­‐55.	  
[2]	  Y.	  Futamura,	  T.	  Sakurai,	  S.	  Furuya and	  J.-­‐I.	  Iwata,	  Efficient	  algorithm	  for	  linear	  systems	  arising	  in	  solutions	  of	  eigenproblems and	  its	  application	  to	  electronic-­‐structure	  calculations,	  Proc.	  10th	  International	  Meeting	  on	  High-­‐Performance	  Computing	  for	  Computational	  Science	  (VECPAR	  2012),	  7851	  (2013),	  226-­‐235..	  
[3]	  T.	  Sakurai	  and	  H.	  Sugiura,	  A	  projection	  method	  for	  generalized	  eigenvalue	  problems,	  J.	  Comput.	  Appl.	  Math.,	  159	  (2003)	  119-­‐128.	  
[4]	  H.	  Tadano,	  T.	  Sakurai	  and	  Y.	  Kuramashi,	  Block	  BiCGGR:	  A	  new	  block	  Krylov subspace	  method	  for	  computing	  high	  accuracy	  solutions,	  JSIAM	  Letters,	  1	  (2009)	  44-­‐47.	  
Acknowledgment
This	  research	  was	  partially	  supported	  by	  the	  Core	  Research	  for	  Evolutional	  Science	  and	  Technology	  (CREST)	  Project	  of	  JST	  and	  the Grant-­‐in-­‐Aid	  for	  Scientific	  Research	  of	  Ministry	  of	  Education,	  Culture,	  Sports,	  Science	  and	  Technology,	  Japan,	  Grant	  number:	  23105702.	  

contact	  address:	  pr@ccs.tsukuba.ac.jp

http://www.ccs.tsukuba.ac.jp/