An iteration-based hybrid parallel algorithm for tridiagonal systems of equations on multi-core architectures

摘要

An optimized parallel algorithm is proposed to solve the problem occurred in the process of complicatedrnbackward substitution of cyclic reduction during solving tridiagonal linear systems. Adopting a hybrid parallelrnmodel, this algorithm combines the cyclic reduction method and the partition method. This hybridrnalgorithm has simple backward substitution on parallel computers comparing with the cyclic reductionrnmethod. In this paper, the operation count and execution time are obtained to evaluate and make comparisonrnfor these methods. On the basis of results of these measured parameters, the hybrid algorithm usingrnthe hybrid approach with a multi-threading implementation achieves better efficiency than the other parallelrnmethods, that is, the cyclic reduction and the partition methods. In particular, the approach involved in thisrnpaper has the least scalar operation count and the shortest execution time on a multi-core computer when thernsize of equations meets some dimension threshold. The hybrid parallel algorithm improves the performancernof the cyclic reduction and partition methods by 19.2% and 13.2%, respectively. In addition, by comparingrnthe single-iteration and multi-iteration hybrid parallel algorithms, it is found that increasing iteration stepsrnof the cyclic reduction method does not affect the performance of the hybrid parallel algorithm very much.