基于多核CPU的无锁并行Semi-naive算法  

Lock-free Parallel Semi-naive Algorithm Based on Multi-core CPU

作　　者：喻婷 王立松[1] 秦小麟[1] YU Ting;WANG Lisong;QIN Xiaolin(College of Computer Science and Technology,Nanjing University of Aeronautics and Astronautics,Nanjing 211106,China)

机构地区：[1]南京航空航天大学计算机科学与技术学院,南京211106

出　　处：《计算机科学》2023年第6期29-35,共7页Computer Science

基　　金：国家自然科学基金(61802182)。

摘　　要：Datalog系统被广泛应用于很多领域,如图数据库、网络和静态程序分析等。在处理海量数据时,基于串行的Datalog求解策略无法充分发挥现有多核处理器的计算性能。针对上述问题,提出一种基于多核CPU的无锁并行Semi-naive算法(Parallel Semi-naive, PSN)用于支持Datalog的高效求解。PSN使用B+树索引进行数据划分,将数据分配给不同的线程执行计算,每个分区产生的中间结果元组互不相同,有利于实现计算时无锁的并行。同时提出一种双层哈希表结构来索引中间结果以提高查重的效率,每个线程只在特定的区域执行相关的计算,无需使用锁来防止写冲突。PSN使用任务队列-线程池为空闲线程分配任务,来实现多线程的负载均衡。在KONECT(Koblenz Network Collection)及斯坦福SNAP(Stanford Network Analysis Platform)的公开数据集上的实验结果表明,PSN算法可以优化Datalog规则的查询性能。Datalog system has a wide range of applications in many fields,such as graph databases,networks,and static program analysis.When dealing with massive data,the serial-based Datalog evaluation strategy cannot fully utilize the computational resources of existing multicore processors.To address these problems,a lock-free parallelized semi-naive algorithm,parallel semi-naive(PSN)based on multi-core CPU is proposed to support efficient Datalog evaluation.PSN uses the B+tree index to partition data and allocates data to different threads to perform calculations.The intermediate result tuples generated from each partition are different from each other,which is conducive to the realization of lock-free parallelism during calculation.PSN uses a double-layer hash table structure to index intermediate results to improve the efficiency of duplicate checking.Each thread only performs related calculations in a specific area,without using locks to prevent write conflicts.PSN adopts task queue and thread pool to allocate tasks to idle threads to achieve multi-thread load balancing.Experimental results on the public datasets of Koblenz network collection(KONECT)and Stanford network analysis platform(SNAP)show that the PSN algorithm can optimize the query performance of datalog rules.

关 键 词：DATALOG Semi-naive算法 并行 递归规则 负载均衡 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]