Accurate counting algorithm for high‐speed parallel applications. (23rd November 2018)

• Record Type: Journal Article
• Authors: Wang, Junchang; Li, Tao; Fu, Xiong
• Is Part Of: Concurrency and computation. Volume 31:Number 13(2019)
• Page Start: n/a
• Page End: n/a
• Publication Date: 2018-11-23
• Subjects: counting algorithm -- lock‐free data structure -- multi‐core -- strong consistency; Parallel processing (Electronic computers) -- Periodicals; Parallel computers -- Periodicals; 004.35
• DOI: 10.1002/cpe.5090
• Languages: English
• ISSNs: 1532-0626

Abstract

Summary: Statistical counter offers the appeal of an efficient and scalable counting mechanism on multi‐core architectures where parallelism has been increasing sharply. Statistical counter has been widely used in practice (eg, in high‐end network devices to count the number of packets received) despite the truth that it can only provide weak consistency guarantee on the counting results it returns, that is, statistical counter could miscount and the returned results may be inaccurate. As hardware and its parallelism advances, the miscount issue has raised concerns in both industry and academy. This paper is motivated by this real‐world miscount issue that we were facing when building a high‐speed intrusion detection system on a commercial multi‐core server with 40Gbps NICs. To tackle the problem, we first systematically analyze the miscount issue and quantify the miscounts in counting results. Then, we present a novel counting algorithm that (1) is competitive to statistical counter in performance on multi‐core architectures and (2) provides strong consistency guarantee on counting results returned. Experiments show that it takes the new counting algorithm 10ns and 1, 500ns to perform an update and a read operation, respectively. Moreover, the counting results returned are accurate.