A concurrent van Emde Boas array as a fast and simple concurrent dynamic set alternative
| Autor: | Konrad Kułakowski |
|---|---|
| Rok vydání: | 2013 |
| Předmět: |
Java
Computer Networks and Communications Concurrent data structure Computer science Parallel computing Thread (computing) Computer Science Applications Theoretical Computer Science Set (abstract data type) Tree (data structure) Computational Theory and Mathematics Parallel processing (DSP implementation) Van Emde Boas tree Concurrent computing Node (circuits) computer Software computer.programming_language |
| Zdroj: | Concurrency and Computation: Practice and Experience. 26:360-379 |
| ISSN: | 1532-0626 |
| DOI: | 10.1002/cpe.2995 |
| Popis: | SUMMARY 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 & Sons, Ltd. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Plný text