``HYPHA: a framework based on separation of parallelism to accelerate 
persistent homology matrix reduction" 

Simon Zhang, Mengbai Xiao, Chengxin Guo, Liang Geng, Hao Wang, and Xiaodong Zhang

Proceedings of 33rd ACM International Conference on Supercomputing (ICS 2019) 
Phoenix, Arizona, June 26-28, 2019.    


Abstract

Persistent homology (PH) matrix reduction is an important tool for
data analytics in many application areas. Due to its highly irregular
execution patterns in computation, it is challenging to gain high
efficiency in parallel processing for increasingly large data sets.

In this paper, we introduce HYPHA, a HYbrid Persistent Homology
matrix reduction Accelerator, to make parallel processing
highly efficient on both GPU and multicore. The essential foundation
of our algorithm design and implementation is the separation
of SIMT and MIMD parallelisms in PH matrix reduction computation.
With such a separation, we are able to perform massive
parallel scanning operations on GPU in a super-fast manner, which
also collects rich information from an input boundary matrix for
further parallel reduction operations on multicore with high efficiency.
The HYPHA framework may provide a general purpose
guidance to high performance computing on multiple hardware
accelerators.

To our best knowledge, HYPHA achieves the highest performance
in PH matrix reduction execution. Our experiments show
speedups of up to 116x against the standard PH algorithm. Compared
to the state-of-the-art parallel PH software packages, such
as PHAT and DIPHA, HYPHA outperforms their fastest PH matrix
reduction algorithms by factor up to 2.3x.