Scheduling parallel iterative methods on multiprocessor systems |
| |
Authors: | Nikolaos M Missirlis |
| |
Affiliation: | Department of Mathematics, University of Athens, Athens, Greece |
| |
Abstract: | 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. |
| |
Keywords: | Parallel numerical algorithms parallel iterative methods parallel SOR method large sparse linear systems |
本文献已被 ScienceDirect 等数据库收录! |
|