一种有效的多Transputer系统的并行算法——ABC法

An Efficient parallel Algorithm for Multitransputer Systems—ABC Method

本文讨论了多Transputer系统的一种有效的并行算法——ABC法。这种算法有三种基本相组成:聚集数据相(A相)、通讯相(B相)和计算相(C相)。在这三相中,B相最为关键,因为它直接关系到算法的成功和效率。本文通过对ABC法的计算复杂度、通讯复杂度、加速比和效率的分析,发现ABC法的效率与通讯复杂度和计算复杂度的比直接相关;该比值越小,则效率越高。因此对于通讯复杂度/计算复杂度较小的问题,ABC法是一种有效的方法。研究ABC法,就是要研究降低通讯复杂度与计算复杂度的比值的措施。为此本文专门讨论了ABC法的实施策略。 ABC法及本文提出的实施策略已被成功地用来并行处理线性方程组的直接解法问题。实例表明,本文得出的结论是正确的,对于满阵线性方程组,阶越高,ABC法的效率越高。这是因为阶越高,通讯复杂度/计算复杂度越小的缘故。

An efficient parallel algorithm——ABC for multitransputer systems is discussed.The algorithm consists of three basic phases: phase A(Aggregate data to be transmitted), phase B( Breadcast between transputers )and phase C ( Compute in parallel), of which phase B is the most crucial, because it is related directly with the success and efficiency of the algorithm ABC. Through the analysis of arithmetic complexity (AC), Communication complexity(CC), speed up and efficiency of the algorithm, it is found that the efficiency of the algorithm is related closely with the ratio of CC to AC, the less the ratio, the higher the efficiency. For the problem with small ratio of CC to AC, therefore, algorithm ABC is an efficient parallel process. To study the algorithm ABC is to research the measure of reducing the ratio of CC to AC, so the implementation strategy of the algorithm ABC is discussed in this paper too,Algorithm ABC and the strategy for it proposed in this paper have been used successfully to process in parallel the problem of solving linear systems of algebraic equations[1,2]. The example in this paper shows that for the linear algebraic systems with full matrix, the higher the order, the higher the parallel efficiency, because of the small ratio of CC to AC.