摘要
首先简要地介绍了用于图像处理的一维和二维Ｗａｌｓｈ变换的一种截断方法，然后根据图像操作的特点，着重介绍了用分块的方法在大规模分布存储并行机曙光－１０００上的并行实现．用Ｐ个节点计算，在最坏情况下，ＮＮ的二维Ｗａｌｓｈ变换截断方法复杂度为Ｏ（Ｎ２ｌｏｇＮ／Ｐ），最好情况为Ｏ（Ｎ２／Ｐ）．实验结果表明该方法十分快速、实用，易于并行处理，并有良好的可扩放性．
This article first gives a brief introduction to a truncation method for computing one dimension and two dimension transforms with applications to image processing, then emphasizes the parallel implementation on MPP dawn1000 using the blocked method according to the characteristic of image operation. By computing the Walsh transforms of two dimension matrix of N*N with P nodes based on truncation methods, the complexity of O(N2logN2/P) under the worst circumstances, and the complexity of O(N2/P) under the best circumstances can be obtained. Experiment results show that this algorithm is very fast, practical, easily parallelprocessed, and has a good scalability.
基金
863计划
国家教委博士基金
中国合肥高性能计算中心支持
