对称区域分裂与循环约化:MIMD计算机上的一种快速并行算法

Symmetric Domain Decomposition and Cyclic Reduction:A Fast Parallel Algorithm on MIMD Computer

介绍一种适合于 MIMD计算机解对称区域上偏微分方程的快速并行算法。其基本思想是 :先利用对称区域分裂原理 ,将一个定义在Ω Rn 上的原问题分裂成Ω上某子区域Ω1 ( Ω)上的 2 P( 1≤ P≤ n)个子问题 ,并映射到 MIMD计算机的多处理单元上 ,如此极易组织作业级与任务级并行 ;然后用循环约化——快速 Fourier变换或循环约化——预条件迭代解各子问题 ,两种过程都有很高的向量化率。称这种算法为对称区域分裂与循环约化方法 ,它能有效地实现作业、任务。

A fast parallel algorithm is given,it would be used to solve the partial differential equations in a symmetric domain with MIMD computer The basic idea includes: first by using symmetric domain decomposition concept, the original problem defined in ΩR n is decomposed 2 p(1≤P≤n) subproblems defined in Ω 1(Ω) and mapped into multiprocess unit of MIMD computer,for which the parallel operation is easily realized on assignment level and task level;and then the cyclic reduction--fast speed Fourier transform (FFT) or cyclic reduction--precondition iteration would be used to solve each of the sburbles These two processes have very high ratio of vectors The method used is called SDD CR method, with which the overall parallel of operation, task, command and data could be effectively implemented at all levels