关键词: 三对角, 申威众核处理器, 循环消去（CR）算法

Abstract: Tridiagonal solver is an important numeric kernel that is widely used in scientific and engineering applications. Many highly optimized parallel algorithms on mainstream hardware platforms, such as CPU and GPU, have been proposed. However, on the Chinese domestically-made Sunway 26010 many-core processor, there is no such an algorithm that utilizes its unique hardware characteristics to maximize the performance. A Sunway-oriented distributive cyclic reduction algorithm (swDCR) is proposed in this paper, to solve a large number of small tridia-gonal equations. swDCR uses multiple CPEs (computation processing element) to solve each equation in parallel, combines the caches of multiple CPEs to store all the intermediate data in caches, and transmits data among CPEs using register communication. By well-designed thread-level data partition, the optimization effect of vectorization is maximized. swDCR outperforms MPE (management processing element) Thomas algorithm by 43.9 times in single precision and 36.7 times in double precision, and outperforms CPE Thomas algorithm by 2.07 times in both single and double precision. It achieves an effective bandwidth of 24 GB/s on one core group of Sunway 26010 processor.

Key words: tridiagonal, Sunway many-core processor, cyclic reduction (CR) algorithm