科研之友
微信
新浪微博
Facebook
分享链接
摘要
Datalog系统被广泛应用于很多领域，如图数据库、网络和静态程序分析等。在处理海量数据时，基于串行的Datalog求解策略无法充分发挥现有多核处理器的计算性能。针对上述问题，提出一种基于多核CPU的无锁并行Semi-naive算法(Parallel Semi-naive, PSN)用于支持Datalog的高效求解。PSN使用B+树索引进行数据划分，将数据分配给不同的线程执行计算，每个分区产生的中间结果元组互不相同，有利于实现计算时无锁的并行。同时提出一种双层哈希表结构来索引中间结果以提高查重的效率，每个线程只在特定的区域执行相关的计算，无需使用锁来防止写冲突。PSN使用任务队列-线程池为空闲线程分配任务，来实现多线程的负载均衡。在KONECT(Koblenz Network Collection)及斯坦福SNAP(Stanford Network Analysis Platform)的公开数据集上的实验结果表明，PSN算法可以优化Datalog规则的查询性能。
- 单位
