基于MPI的二维经验模分解并行算法
Parallel Algorithm of Bi-Dimensional Empirical Mode Decomposition Based on MPI
-
摘要: 针对二维经验模分解(BEMD)处理大尺寸图像耗时较长的问题,提出了一种基于MPI技术的BEMD并行算法.对BEMD串行程序中极值点选取、平面三角剖分、三角域内数值插值等几个主要部分的运行时间进行了统计,结果表明三角域内数值插值是耗时的主要部分,也是并行化的重点处理部分;随后在高性能计算平台上构建并行环境,基于MPI技术对BEMD算法的包络面生成部分实现了并行化,具体方法是先将剖分后的三角形序列按照进程数均匀划分,使整个图像分割为若干子区域并分配给相应进程,然后各进程拟合出对应子区域的上下Bezier曲面并由0进程进行合并,进而生成上下包络面;最后通过加速比等指标对该算法进行测评.结果表明,算法在30核并行执行时加速比可达20.1396,利用率为64.97%,运行效率的提升较为明显.在数据量达到原始数据的25倍时可扩展性指标为1.3975,表明该算法对大数据量的任务有很好的适应性.Abstract: This paper investigates a parallel algorithm of bi-dimensional empirical mode decomposition(BEMD) based on MPI technique to solve the problem that it will take a long time using BEMD to decompose large-size images. At first, the running time of extreme points selecting, plane triangulation and numerical interpolation in serial program was collected, the result showed that numerical interpolation was the main part of time-comsuming as well as the key part of parallelization. Then the parallel environment was constructed in high-performance computing platform, and the envelope surface was parallelized based on MPI technique. The specific method was that triangular series were evenly divided according to the number of processes, so the entire image was divided into many sub-areas assigned to the corresponding process, then each process fitted Bezier surface and was merged by 0 process to generate the up and down envelope surface. At last, this algorithm was evaluated by some indicators such as speedup. The results show that the speedup is 20.1396 when algorithm iss executed in 30 core parallelization, and the utilization is 64.97%, the efficiency is enhanced. The scalability indicators is 1.3975 when the data amount has been 25 times of original data, showing that the algorithm has good adaptability for large amount of data.
下载: