超立方机上一阶线性递推问题的并行求解

本文考察解一阶线性递推问题的三个并行算法在超立方机上的实现方案.通过给出原始数据与超立方机之间的适当的映射以及算法执行过程中数据的通讯方式,奇偶消元法、奇偶约简法和变间距二分法都可以在起立方机上有效地执行.文中给出了这些算法的复杂性结论.最后,为进一步减少通讯费用,我们提供了一种复杂性更小的新算法,其通讯时间是与问题规模无关的常数.

Parallel Solution of First-Order Linear Recurrence Problem on the Hypercube Multiprocessor

In this paper, the authot examines the implementing schemes of several parallel algorithms for solving first-order linear recurrence problem on the hypercube multiprocessor. In order to decrease the communication cost as far as possible, the author presents the efficient implementing schemes of three algorithms OEE, OER and GIB, and analyzes their complexities. Finally, a new algorithm to reduce communication cost further is proposed, the complexity of the algorithm is the least among those of the algorithms discussed in the paper, and the communication cost of the new algorithm is a constant which does not depend on the size of the recurrence problem.