Model guided algorithm optimization for tridiagonal solver on many-core architectures

Tridiagonal solver is an important kernel used in a wide range of applications and has been well supported in mainstream numerical libraries. Quite a few parallel algorithms have been developed, but the best-performing algorithm may vary across architectures as well as input sizes. Targeting this algorithm choice challenge, we present a model guided approach to determine the best batched tridiagonal algorithm for various many-core architectures and input sizes efficiently and effectively, managing to achieve the accuracy of algorithm choice over 92% for important architectures. Following the approach, we propose a hybrid CR-PCR-pThomas algorithm to well leverage computation and memory access. The hybrid algorithm outperforms the current state-of-the-art alternatives by up to 32% and 21% on Pascal P100 and Knights Landing respectively. On SW26010 that powers the No.6 supercomputer Sunway TaihuLight, we present an improved cyclic reduction algorithm Dist-CR. The proposed Dist-CR outperforms Thomas algorithm by speedups up to 2.14x.