Parallel algorithms have been designed for the past 20 years initially by parallelising existing sequential algorithms for many different parallel architectures. More recently parallel strategies have been identified ...Parallel algorithms have been designed for the past 20 years initially by parallelising existing sequential algorithms for many different parallel architectures. More recently parallel strategies have been identified and utilized 'resulting in many new parallel algorithms. However the analysis of such algorithms reveals that further strategies can be applied to increase the parallelism. One of these, i.e., increasing the computational capacity in each processing node can reduce the congestion/communicgtion for shared memory/distributed memory multiprocessor systems and dramahcally improve the Performance of the algorithm. Two algorithms are identified and studied, i.e., the Cyclic reduction method for solving large tridiagonal linear systems in which the odd/even sequence is increased to a 'stride of 3' or more resulting in an improved algorithm. Similarly the Gaussian Elimination method for solving linear systems in which one element is eliminated at a time can be adapted to parallel form in which two elements are simultaneously eliminated resulting in the Parallel Implicit Elimination (P.I.E.) method. Numerical results are presented to support the analyses.展开更多
文摘Parallel algorithms have been designed for the past 20 years initially by parallelising existing sequential algorithms for many different parallel architectures. More recently parallel strategies have been identified and utilized 'resulting in many new parallel algorithms. However the analysis of such algorithms reveals that further strategies can be applied to increase the parallelism. One of these, i.e., increasing the computational capacity in each processing node can reduce the congestion/communicgtion for shared memory/distributed memory multiprocessor systems and dramahcally improve the Performance of the algorithm. Two algorithms are identified and studied, i.e., the Cyclic reduction method for solving large tridiagonal linear systems in which the odd/even sequence is increased to a 'stride of 3' or more resulting in an improved algorithm. Similarly the Gaussian Elimination method for solving linear systems in which one element is eliminated at a time can be adapted to parallel form in which two elements are simultaneously eliminated resulting in the Parallel Implicit Elimination (P.I.E.) method. Numerical results are presented to support the analyses.
