Solving Banded Triangular Linear Systems on 3-D Torus Networks

摘要

In this paper, we examine the problem of designing banded triangular solvers on 3-dimensional tori. In order to determine how to design an optimal solver, we begin by deriving a lower bound on execution time. In particular, we derive two lower bounds: (a) a general lower bound and (b) one that makes realistic assumptions on how data can be initially assigned across processors. Furthermore, an efficient algorithm is designed and comparred to the lower bounds proven.