多重网格区域分裂分布式计算

基金项目:

国家高性能计算技术基金 984057

DISTRIBUTED MULTIGRID COMPUTATION WITH DOMAIN DECOMPOSITION

Department of Computer Science, South-Central College for Nationalities, Wuhan 430074, China

摘要: 对分布式多重网格计算进行了研究.其顺序算法描述的是非递归形式, 算法并行化是基于区域分裂实现的.网状拓扑结构组织在多处理机上, 并行算法映射到多进程上, 在一定程度上显著提高并行化速度和并行化效率
- 分布式 /
- 多重网格计算 /
- 网状拓扑结构 /
- 并行化
Abstract: This paper presents the distributed multigrid computation. The sequential algorithm is expressed in a non recursive form. The parallel algorithm is achieved based on domain decomposition. Mesh topology architectures are organized with multiple transputers. Parallel algorithms are mapped onto processes, increasing markedly, to some extent, the speed and efficiency of parallelization.
- distribution /
- multigrid computation /
- mesh topology architectures /
- parallelization

图 1 等距网格

Fig. 1. Uniformly meshed domain

下载: 全尺寸图片幻灯片

图 2 粗网格校正

Fig. 2. Coarse grid correction

下载: 全尺寸图片幻灯片

图 3 周期性精网格校正

图中o.表示平滑; 。表示压缩(细-粗网格映射); /.表示扩充(粗-细网格映射); □.表示求准确解.

Fig. 3. Periodic fine grid correction

下载: 全尺寸图片幻灯片

图 4 多重网格迭代

Fig. 4. Multigrid cyclic iteration

下载: 全尺寸图片幻灯片

图 5 单并行处理单元

Fig. 5. Single transputer processing element

下载: 全尺寸图片幻灯片

图 6 2×2处理机网状拓扑

Fig. 6. 2×2 processor mesh topology

下载: 全尺寸图片幻灯片

图 7 区域分裂

Fig. 7. Domain decomposition

下载: 全尺寸图片幻灯片

图 8 并行平滑与边界数据交换

Fig. 8. Parallel smoothing and boundary data exchange

下载: 全尺寸图片幻灯片

图 9 网格间映射

Fig. 9. Intergrid mapping

下载: 全尺寸图片幻灯片

表 1 执行时间

Table 1. Executive time

[1]	McCormick S F. Mult-igrid methods[M]. SIAM: Philadelphia, 1987.
[2]	Hackbusch W. Multigrid algorithms. Introduction, survey and convergence analysis[A]. In: Spedicato E, ed. Computer algorithms for solving linear algebraic equations[C]. The State of the Art: Springer-Verlag, 1990.133160.
[3]	Xu Z Q. Distributing mult-igrid computation on a message passing system[D]. Wuhan: Huazhong University of Science and Technology, 1993.
[4]	Xu Z Q, Libert G. Non-recursive multigrid computation on transputers[A]. In: Veronis A M, Paker Y, eds. Transputer research and applications 5[C]. Amsterdam: IOS Press, 1992.302309.