crosetto / cupq Goto Github PK
View Code? Open in Web Editor NEWa CUDA implementation of a priority queue
License: Apache License 2.0
a CUDA implementation of a priority queue
License: Apache License 2.0
First of all, I want to point out this library has been valuable material for my master thesis, so many thanks for making it available under a permissive license. I am implementing a parallel heap with generic key types (+ comparators) and generic value types based on this one for branch-and-bound algorithms. While working on this, I noticed an issue with the implementation of the insertion procedure, so I thought I should contribute a little back.
Lines 172 to 218 in e4dec3b
It concerns an insertion where the last node in the heap is full (sPosition == WarpSize
) so that the heap has to be grown with a new node. If the inserted key is greater than the smallest item in the last node (n.first > sTops[mSize - 1]
), the implementation grows the heap by initializing a new node with the inserted item as the smallest (only) item of the node (as seen on lines 189-192).
Lines 189 to 192 in e4dec3b
In many cases, the heap property is preserved, but not all. The heap property may be violated if the previous last node and the newly initialized node are not siblings, in other words if they do not have the same parent.
Let a
be the (zero-indexed) index of the last node prior to the insertion, and assume the heap property is preserved prior to the insertion. We know that sTops[parent(a)] <= sTops[a]
(the heap property) is true both prior to the insertion and following the insertion because node a
and its parent are both left unmodified by the insertion procedure. Then let b = a + 1
be the index of the newly initialized node following the insertion. Following the insertion, we know that sTops[a] < sTops[b]
, which transitively implies that sTops[parent(a)] < sTops[b]
.
Only if parent(a) == parent(b)
do we know that the heap property is preserved between node b
and its parent. If node a
is the last child of its parent, node b
gets a different parent than node a
. Specifically, node b
gets a different parent whenever a % arity == 0
.
This creates an issue where node b
may be inserted without regard for the heap property between it and its parent. As an example, consider this binary heap containing only keys, with two items per node:
1,2
8,9 3,4
If we were to insert 5, it would be compared with 3. Because the last node is full and 5 > 3, the implementation initializes a new node as such, violating the heap property:
1,2
8,9 3,4
5,_
I was curious to see whether this issue can actually cause the priority queue work incorrectly, and I found an example to prove it. Consider the following heap state created by inserting 6, 7, 7, 8, 8 into the above heap:
1,2
8,9 3,4
5,6 7,7 8,8
If we were to pop five items, we would expect to pop 1, 2, 3, 4, 5 in that order. However, after popping the first four, the heap looks like this:
7,7
8,9 8,8
5,6
This would pop 7 instead of 5 off the heap.
To solve the issue, the item in the newly inserted node would have to be propagated up if the nodes are not siblings.
In my implementation (which will be published in a month or so), I have resorted to always propagate the item up whenever a new node has to be inserted, and only comparing the inserted item with the smallest item in the last node if the node has space for another item.
I hope this description of the issue is helpful if you intend to resolve it.
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.