A concurrent van Emde Boas array as a fast and simple concurrent dynamic set alternative. (25th January 2013)

• Record Type: Journal Article
• Authors: Kułakowski, Konrad
• Is Part Of: Concurrency and computation. Volume 26:Number 2(2014:Feb.)
• Page Start: 360
• Page End: 379
• Publication Date: 2013-01-25
• Subjects: Parallel processing (Electronic computers) -- Periodicals; Parallel computers -- Periodicals; 004.35
• DOI: 10.1002/cpe.2995
• Languages: English
• ISSNs: 1532-0626

Abstract

<abstract abstract-type="main" id="cpe2995-abs-0001"> <title>SUMMARY</title> <p>Increasing demand for computationally efficient algorithms and processors has turned the attention of researchers toward parallel and concurrent solutions. Because the frequency of contemporary processors cannot be tweaked infinitely, the only hopes for squeezing more performance from computers are parallel processing and parallel computation. The important part of every parallel solution is concurrent data structures, which allow multithread programming environments to be taken advantage of. In this article, a new concurrent dynamic set structure is proposed. It is based on the van Emde Boas trees concept, where on every node of a tree, an array of the node's children is stored. The structure is equipped with a simple but effective locking algorithm, which allows it to be used concurrently by any number of threads. The presented algorithm idea is accompanied by an experimental implementation written in JAVA 6. Preliminary tests prove that, especially for moderately larger data sets with a predominance of read operations, the concurrent van Emde Boas array proposed in this article may be a viable alternative for other structures providing a similar functionality. Copyright © 2013 John Wiley &amp; Sons, Ltd.</p> </abstract>