Practical Parallel Band Triangular System Solvers
Practical Parallel Band Triangular System Solvers
复制标题
实用平行带三角系统求解器
DOI：
10.1145/355791.355797
复制
发表时间：
1978
期刊：
影响因子：
--
通讯作者：
A. Sameh
中科院分区：
文献类型：
--
作者：
Shyh;D. Kuck;A. Sameh
我们提出了一种用于HNEAR复发系统快速解决方案的新算法，我们以带状三角线性系统的形式讨论了该算法。几位作者，例如[2-7、11、12]。此处介绍的算法非常适合低阶复发。当在有限数量的处理器上求解此类系统时，提出的方法可在以前的算法中获得2至4的速度提高。在整个论文中，我们假设可以随时使用任何数量的处理器，但是我们对此数字进行了界限。假定所有处理器都可以在每个时间步骤执行相同的操作，并且每个算术操作都可以在一个步骤中执行。如果P是使用的处理器数量，我们用TP表示计算时间。我们还通过SP = ti/tp来定义并行算法的加速，其中T〜是仅使用一个处理器所需的算法所需的最小时间，我们用EP = S J P表示效率。在第2节中，我们介绍了我们的算法，并给出了某些特殊案例的实际案例。其中包括仅计算解决方案的最后几个元素和toeplitz的情况
We present a new algorithm for the fast solution of hnear recurrence systems, which we discuss in the form of band triangular linear systems. Parallel linear recurrence system solvers have also been discussed by several authors, e.g. [2-7, 11, 12]. The algorithm presented here is well suited to recurrences of low order. When solving such systems on a limited number of processors, the method presented obtains speed improvements of the order of 2 to 4 over previous algorithms. Throughout the paper we assume that any number of processors can be used at any time, but we give bounds on this number. All processors are assumed to perform the same operation on each time step, and each arithmetic operation can be performed in one step. If p is the number of processors used, we denote the computation time by Tp. We also define the speedup of the parallel algorithm by Sp = TI/Tp, where T~ is the minimum time required by the algorithm using only one processor, and we denote the efficiency by Ep = S J p . In Section 2 we present our algorithm and give variations on it which hold for certain special cases of practical interest. These include the computation of only the last few elements of the solution to a recurrence and the case of Toeplitz