并行计算机系统中的计数算法研究  

Counting algorithm for parallel computing systems

作　　者：王俊昌[1,2] 高亮[1,2] 李涛 

机构地区：[1]南京邮电大学计算机学院,江苏南京210023 [2]南京邮电大学江苏省大数据安全与智能处理重点实验室,江苏南京210023

出　　处：《南京邮电大学学报（自然科学版）》2017年第6期81-89,共9页Journal of Nanjing University of Posts and Telecommunications：Natural Science Edition

基　　金：国家自然科学基金(61602264);国家博士后自然科学基金(2017M611882);南京邮电大学引进人才科研启动基金(NY215044)资助项目

摘　　要：计数算法是计算机程序设计中的基础算法。然而,传统计数算法在新兴的多核并行计算机系统中存在计数效率低下以及计数不准确的问题。文中首先对这些问题进行深入量化分析,之后提出了一种适用于并行计算机系统的确定性高速计数算法。该算法采用对计数器数据先进行快照再进行统计计数的方法,有效避免了计数算法中读者线程与写者线程之间的相互干扰,保证了计数数据的准确性;同时,通过采用无锁链表队列存储计数数据快照,实现了并发读取情况下的无阻塞计数统计,保证了计数算法的效率。实验论证和性能分析结果表明:在新一代的多核并行计算机中,本计数算法计数效率高且计数准确,综合性能优于现有算法。The counting algorithm is one of the fundamental data structures in software design. Two classes of solutions, lock-based counting algorithm and statistical counting algorithm, are either inefficient or inaccurate in counting results. To tackle the problem, this paper firstly systematically analyzes the inefficiency and the inaccuracy issues in existing solutions, and then presents a novel counting algorithm. The new algorithm is efficient and accurate, by first taking snapshot of counting array and then calculating counting results to avoid interruptions between the reader thread and the writer thread of the counting algorithm, thus ensuring the accuracy of counting results. Besides, the new algorithm utilizes lock-free linked list to manage snapshots, which providing an efficient approach for reader threads to calculating counting results. Experiments show that the new algorithm is efficient and accurate, serving as a good candidate for parallel computers.

关 键 词：无锁数据结构 计数算法 最终一致性 

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