一种基于优化存储格式的DLB_GaBP算法

A DLB_GaBP Algorithm Based on Optimized Storage Format

基于动态运行的多线程或多进程环境中的多核并行处理机,常存在数据存储格式及数据读取方法不合理,并行运行任务的不均衡性状态,直接影响到系统工作的整体效率,因此,优化数据存储格式、均衡优化任务调度算法是保证整个系统运行效率的关键。利用高斯置信传播算法(GaBP)在求解对称对角占优线性方程组中具有高并行度、低复杂度的特性,结合对数据存储格式进行优化的基础上,设计实现一种具有动态负载均衡特性的多核并行GaBP算法(DLB_GaBP算法)。利用该算法并通过对稀疏矩阵集(UFget)的求解实验,在千万量级别以上的大规模计算环境中,DLB_GaBP算法具有更好的计算效率和更高的加速比,这为充分发挥多核并行处理机的运算能力及大规模计算问题的快速求解提供了一种新算法思路。

The multi-core parallel processor based on dynamic multi-thread or multi-process environment often has unreasonable data storage format and data reading method,and the unbalanced state of parallel running task directly affects the overall efficiency of the system.Optimizing data storage format and balancing and optimizing task scheduling algorithm are the key to ensure the efficiency of the whole system.Based on the high parallelism and low complexity of Gaussian confidence propagation algorithm(GaBP)in solving symmetric diagonal dominant linear equations,a multi-core parallel GaBP algorithm(DLB_GaBP algorithm)with dynamic load balancing characteristics is designed and implemented on the basis of optimizing the data storage format.In a large-scale computing environment with more than 10 million levels,the algorithm is used and the experiment of solving sparse matrix set(UFget)is carried out.DLB_GaBP algorithm has better computational efficiency and higher acceleration ratio,which provides a new algorithm idea for giving full play to the computing power of multi-core parallel processors and fast solving large-scale computing problems.