SCHEDULING PARALLEL ITERATIVE METHODS ON MULTIPROCESSOR SYSTEMS

作     者：MISSIRLIS, NM 

作者机构：Department of Mathematics University of Athens Athens Greece 

出 版 物：《PARALLEL COMPUTING》 (并行计算)

年 卷 期：1987年第5卷第3期

页      面：295-302页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Greek Ministry of Industry  Research and Technology 

主　　题：Parallel numerical algorithms parallel iterative methods parallel SOR method large sparse linear systems 

摘      要：The paper describes the implementation of the Successive Overrelaxation (SOR) method on an asynchronous multiprocessor computer for solving large, linear systems. The parallel algorithm is derived by dividing the serial SOR method into noninterfering tasks which are then combined with an optimal schedule of a feasible number of processors. The important features of the algorithm are: (i) achieves a speedup Sp ? O(N/3) and an efficiency Ep ? 2/3 using p = [N/2] processors, where N is the number of the equations, (ii) contains a high level of inherent parallelism, whereas on the other hand, the convergence theory of the parallel SOR method is the same as its sequential counterpart and (iii) may be modified to use block methods in order to minimise the overhead due to communication and synchronisation of the processors.