Sökning: id:"swepub:oai:research.chalmers.se:1f9ed76f-3323-45f8-b815-09ad2060b36c" >
Concurrent lock-fre...
Concurrent lock-free unbounded priority queue with mutable priorities
-
- Walulya, Ivan, 1985 (författare)
- Chalmers tekniska högskola,Chalmers University of Technology
-
Chatterjee, Bapi, 1982 (författare)
-
- Datta, Ajoy K. (författare)
- University of Nevada, Las Vegas (UNLV)
-
visa fler...
-
- Niyolia, Rashmi (författare)
- University of Nevada, Las Vegas (UNLV)
-
- Tsigas, Philippas, 1967 (författare)
- Chalmers tekniska högskola,Chalmers University of Technology
-
visa färre...
-
(creator_code:org_t)
- 2018-10-20
- 2018
- Engelska.
-
Ingår i: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). - Cham : Springer International Publishing. - 1611-3349 .- 0302-9743. ; 11201 LNCS, s. 365-380
- Relaterad länk:
-
https://doi.org/10.1...
-
visa fler...
-
https://research.cha...
-
visa färre...
Abstract
Ämnesord
Stäng
- The priority queue with DeleteMin and Insert operations is a classical interface for ordering items associated with priorities. Some important algorithms, such as Dijkstra’s single-source-shortest-path, Adaptive Huffman Trees, etc. also require changing the priorities of items in the runtime. Existing lock-free priority queues do not directly support the dynamic mutation of the priorities. This paper presents the first concurrent lock-free unbounded binary heap that implements a priority queue with mutable priorities. The operations are provably linearizable. We also designed an optimized version of the algorithm by combining the concurrent operations that substantially improves the performance. For experimental evaluation, we implemented the algorithm in both C/C++ and Java. A number of micro-benchmarks show that our algorithm performs well in comparison to existing implementations.
Ämnesord
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datorteknik (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Engineering (hsv//eng)
- TEKNIK OCH TEKNOLOGIER -- Elektroteknik och elektronik -- Signalbehandling (hsv//swe)
- ENGINEERING AND TECHNOLOGY -- Electrical Engineering, Electronic Engineering, Information Engineering -- Signal Processing (hsv//eng)
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Nyckelord
- Linearizability
- Priority-queue
- Heap
- Elimination
- Concurrent heap
- Lock-free
Publikations- och innehållstyp
- kon (ämneskategori)
- ref (ämneskategori)
Hitta via bibliotek
Till lärosätets databas