一种基于优化存储格式的 DLB_GaBP 算法-《计算机技术与发展》

文章信息/Info

作者:: 陈振武¹; 2 ; 黄婧1 ; 兰添才¹; 2 ; 郑汉垣³; 1. 龙岩学院数学与信息工程学院,福建龙岩 364012;2. 龙岩学院大数据挖掘与应用福建省重点实验室,福建龙岩 364012;3. 龙岩学院传播与设计学院,福建龙岩 364012

Author(s):: CHEN Zhen-wu¹; 2 ; HUANG Jing¹; LAN Tian-cai¹; 2 ; ZHENG Han-yuan³; 1. School of Mathematics and Information Engineering,Longyan University,Longyan 364012,China;2. Key Laboratory of Big Data Mining and Application of Fujian Province,Longyan University,Longyan 364012,China;3. School of Communication and Design,Longyan Univ

Keywords:: arge-scale parallel operation; sparse matrix storage format; dynamic load balancing; GaBP algorithm; DLB_GaBP algorithm

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

Abstract:: 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 parall-? elism 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 experi-ment 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.