A parallel priority queue with fast updates for GPU architectures

Ben Karsin; John Iacono; Kyle Berney; Nodari Sitchinava

REVIEW 3 major objections 6 minor 31 references

A parallel priority queue with fast updates for GPU architectures

T0 review · 3 major / 6 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper claims that a parallel bucket heap with bulk updates gives GPUs a work-efficient priority queue, making parallel Dijkstra up to 5.3x faster than nvGRAPH on dense high-diameter graphs.

desk verdict A worthwhile GPU bucket heap with bulk updates and a mostly coherent theory, but the schedule implementation is not demonstrated and the empirical claims need artifacts. read the letter →

arxiv 1908.09378 v2 pith:XPKBFH2R submitted 2019-08-25 cs.DS cs.DC

Kyle Berney , John Iacono , Ben Karsin , Nodari Sitchinava This is my paper · ORCID

classification cs.DScs.DC MSC 68W1068P0568R10

keywords parBucketHeappriorityqueueGPUsingle-sourceshortestpathbulkupdateDijkstraPRAMmodelcacheefficiency

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper claims that a parallel bucket heap, the parBucketHeap, brings a work-efficient priority queue to GPU architectures. The authors prove that with a parameter $d$, extractMin, update, delete, and bulkUpdate of up to $d$ elements each take $O(\log d)$ time and $O(d\log(n/d))$ work in the EREW PRAM model, and that the structure is cache-efficient in the PEM model. They implement it in CUDA and plug it into a parallel Dijkstra solver, reporting speedups of up to 5.3x over the leading GPU SSSP implementation on sufficiently dense, high-diameter graphs, together with lower GPU power draw. If correct, this would give GPU users a priority-queue-based shortest-path algorithm that stays work-efficient exactly where current GPU SSSP heuristics degrade.

What carries the argument

The central object is the parBucketHeap: levels consisting of a bucket $B_i$ of capacity $d2^{2i+1}$ and a signal buffer $S_i$ of capacity $d2^{2i}$, with extractMin scanning $B_0$, update and bulkUpdate inserting into $S_0$, and Resolve(i) merging, deleting duplicates, and moving elements between levels to maintain the heap property. The mechanism that carries the argument is the resolution schedule: for every $i>0$, Resolve(i) is triggered by the fourth Resolve(i-1), non-adjacent levels may resolve at the same time, and the recurrence for start and end times shows that with Resolve(0) in one timestep and $T(R_i)\le 2^{2i}$, $n$ operations complete in $O(n)$ timesteps. This is what converts a data structure with exponentially large levels into constant-time per-operation behavior.

What would settle it

Instrument the implementation so that each Resolve(i) records start and end wall-clock times as operations are issued at a steady rate; if the duration of Resolve(i) grows faster than its $2^{2i}$-timestep allowance, or if extractMin or update begins waiting for a high-level Resolve to finish, then the schedule's background-resolution premise fails and the claimed per-operation bounds do not transfer to the GPU.

Watch

Extended reading notes

Core claim

The paper's central claim is that the parBucketHeap gives GPU priority queues a combination not achieved before: constant-time per-operation cost (or $O(\log d)$ with bulk updates), optimal parallel work, and cache efficiency. The structure keeps the bucket heap's hierarchy of buckets $B_i$ and signal buffers $S_i$, scales their capacities by a parameter $d$, and replaces the sequential Fill/Empty triggers with a precomputed resolution schedule. Under that schedule, Resolve(i) runs after every fourth Resolve(i-1), non-adjacent levels resolve concurrently, and each operation touches only the first level while larger levels finish in the background. The consequence the authors draw is that a Dijkstra-based SSSP algorithm becomes work-optimal on GPUs and outruns the leading Bellman-Ford-based GPU SSSP implementation on dense, high-diameter graphs, while drawing less power.

Load-bearing premise

The load-bearing premise is that one operation plus the smallest level's cleanup step always fits in a single fixed time unit, while each larger level may take exponentially longer, and the GPU actually runs those larger cleanup steps in the background without stalling the operation stream.

Editorial extensions

If this is right

With $d=1$, extractMin, update, and delete each take $O(1)$ amortized time and $O(\log n)$ work in the EREW PRAM model, matching the best prior parallel priority queue while adding cache efficiency.
With $d>1$, bulkUpdate of up to $d$ elements takes $O(\log d)$ time and $O(d\log(n/d))$ work, so large batches of edge relaxations can be inserted as a single operation.
In the PEM model, extractMin, update, and delete take $O(\log(n/M)/(PB)+1/B)$ parallel I/Os, so the structure is cache-efficient when each processor has internal memory $M$ and block size is $B$.
parDijkstra is work-optimal, and on sufficiently dense high-diameter graphs it finishes up to 5.3x faster than the leading GPU SSSP implementation while drawing less power.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The same bulk-update design could help other GPU algorithms that currently avoid priority queues because updates arrive in batches; A* search and incremental graph algorithms are natural candidates, though the paper does not test them.
The schedule's slack could be exploited for energy control: if high-level resolutions genuinely hide behind operations, lowering thread occupancy or clock rate at those levels might reduce power without hurting wall-clock time; the paper measures power but does not propose this operating mode.
A stress test with graphs whose edge weights are nearly uniform, forcing many updates into the same bucket, would reveal whether the $O(\log d)$ bulk-update bound is robust in practice; synthetic complete graphs are used, so real-world road-network or social-graph variants remain open.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Punchline: this is a real data-structure paper. The parBucketHeap is a genuine extension of Brodal's bucket heap: the d parameter, the bulkUpdate of up to d elements, and the parallel resolve schedule are new, and the PRAM/PEM bounds are derived, not just asserted. I would not desk-reject it. But as written, the GPU speedups and power numbers are not reproducible, and the Section 4.1 trigger does not obviously implement the schedule proved in Theorem 3.1. Treat the experimental claims as unverified until code and data appear.

What is good: the theoretical core is mostly coherent. The capacity scaling by d, the amortization idea that Resolve(i) runs every 4^i operations, and the overlap of non-adjacent levels are the right ingredients. Lemma 3.2's O(log d + i + 1) time and O(d 2^{2i}) work are straightforward. The PEM analysis is a reasonable extension. The experiments target exactly the dense, high-diameter regime where delta-stepping and Bellman-Ford-style SSSP are weak, so the nvGRAPH comparison is meaningful in principle. The power measurement is a nice addition. Citation pattern is fine; the bucket heap, the parallel priority queue, and the PEM model are all credited.

Soft spots, in order. The biggest is the implementation trigger. If c_i is the number of completed Resolve(i) calls, then the condition c_{i-1} = 4 c_i fires every level at initialization, since all counts are zero, and it does not wait for four additional resolves from the level below. The next Resolve(i) should require c_{i-1} >= 4(c_i+1), not equality. Without code, one cannot tell whether the real implementation initializes counts differently, but as printed the trigger is not the schedule proved in Theorem 3.1. This matters because every O(1)/O(log d) operation bound rests on that schedule. Second, Lemma 3.3's proof has a real indexing typo: the larger-level term uses start_{i-1} where start_{i+1} is needed. With that correction the algebra closes, so I would call it a typo, but it must be fixed. Third, Table 1 lists extractMin as O(1) while Theorem 3.3 says O(log d) for d>1; minor but confusing. Fourth, the experiments are synthetic-only, with no error bars or artifacts, and the abstract names a Quadro M4000 while the body uses a GTX 1080. None of this makes me think the authors are misreporting what they saw; it just makes the results impossible to verify. The abstract's "work-optimal" also promises more than the theorems prove: the bounds are good, but optimality is not established.

Bottom line: a solid, citable contribution to parallel priority queues if the schedule gap is fixed and artifacts are released. It deserves real peer review, not a desk reject. I would ask for code/data and a corrected schedule trigger as major revision conditions.

Referee Report

3 major / 6 minor

Summary. The paper presents parBucketHeap, a parallel bucket heap designed for GPU architectures, derived from the cache-oblivious bucket heap of Brodal et al. It supports extractMin, update, delete, and a bulkUpdate of up to d elements. The theoretical sections analyze the structure in the EREW PRAM and PEM models, claiming O(1) amortized operation time for d=1, O(log d) time per operation for d>1, and corresponding parallel-I/O bounds. The authors implement parBucketHeap in CUDA and use it in parDijkstra, an SSSP solver, reporting speedups over nvGRAPH on dense, high-diameter graphs and lower GPU power consumption. The central correctness argument is the resolution schedule of Section 3.2, which determines how Resolve(i) calls at different levels are ordered and overlapped.

Significance. If the resolution schedule is sound, the paper makes a useful contribution: it combines cache-efficient bucket heaps with bulk updates, gives a self-contained PRAM/PEM analysis with no fitted parameters, and identifies a practical regime (dense, high-diameter graphs) where a work-optimal Dijkstra variant can beat the Bellman-Ford-based SSSP implementation in nvGRAPH. The power-consumption measurements add an interesting dimension that is rarely reported. The theoretical results are not circular: they are derived from the published bucket heap and standard parallel primitives. However, the correctness of the operation bounds and of the reported speedups rests entirely on the schedule in Theorem 3.1/Lemma 3.3, and that part of the manuscript currently contains an indexing error and an implementation trigger that does not obviously implement the analyzed schedule. These issues are local and likely fixable, but they are load-bearing.

major comments (3)

[§3.3, Lemma 3.3 proof] In the derivation of the dependence on the larger level, the text writes end_{i+1}((k-1)/4) = start_{i-1}((k-1)/4) + T(R_{i+1}); the first term should be start_{i+1}((k-1)/4). As printed, the induction does not compute the quantity it claims, so the closed-form expression for start_i(k) is not justified. With the corrected index the algebra appears to close, but please fix the typo and re-verify the proof.
[§4.1, trigger condition vs. Theorem 3.1] The implementation trigger 'each thread-block i > 0 performs Resolve(i) when c_{i-1} = 4·c_i and c_{i+1} ≥ 4·c_i' is not the schedule proved in Theorem 3.1 under the natural reading of c_i as the number of completed Resolve(i) calls. For the next Resolve(i) to satisfy its preconditions, it must wait until c_{i-1} ≥ 4(c_i+1), and the adjacent-level exclusion requires a completion dependency rather than count comparisons alone. With the printed trigger, level i can fire when c_{i-1}=c_i=0, before B_i and S_i meet the Resolve preconditions. Please define c_i precisely, prove that the trigger enforces the Theorem 3.1 schedule, and adjust the implementation accordingly; this is load-bearing because the O(1)/O(log d) operation bounds and the parDijkstra speedups presuppose the schedule.
[Table 1 vs. Theorem 3.3] Table 1 lists extractMin as O(1) for 'This work' in the RAM/PRAM column, but Theorem 3.3 states that with d>1 extractMin takes O(log d) time, and Section 3.2 explains that increasing the capacity of S0 forces extractMin to scan B0. Please reconcile the table entry with the theorem, or state explicitly that the O(1) entry applies only to the d=1 case.

minor comments (6)

[Abstract vs. Section 4] The abstract reports experiments on an RTX 2080 Ti and a Quadro M4000, but Section 4 says the second platform is a Pascal-generation GTX 1080. Please correct the hardware description.
[Introduction and experimental claims] The introduction reports a speedup 'by up to 5.3×' while the abstract reports factors of 2.8 and 5.4 on the two platforms; Section 4.3 and 4.4 give additional crossing points. Please quote consistent numbers and explain which graph family gives which speedup.
[Experimental reproducibility] No source code, input graph generators, or raw measurements are provided, which makes the experimental claims difficult to reproduce. At minimum, please state where artifacts will be made available and give precise graph-generation parameters (weight distributions, directed/undirected, D=V construction).
[Introduction, page 3] The sentence 'using nvGRAPH results int he GPU drawing up to 3.1× more power' contains a typo ('int he'); it should read 'results in the GPU drawing up to 3.1× more power'.
[References] References [1] and [28] are the same JaJa textbook; please merge or cite only once.
[Section 4.2, Figures 3 and 4] The plots show single average values with no error bars or variance information even though Section 4 states that experiments were repeated five times; please report the spread.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; the theoretical bounds are derived from the stated Resolve schedule and capacity invariants, not from the experimental results.

full rationale

The paper's central theoretical results (Theorems 3.2, 3.3, and Lemma 3.4) follow from the capacity invariants, the Resolve operation in Algorithm 5, and the dependency schedule proven in Theorem 3.1 and Lemma 3.3. The parBucketHeap is an extension of the external bucket heap of Brodal et al. [4], and the new parallel resolution schedule is derived in the paper rather than imported. The only self-citation is to [3] for the PEM model, which is used as a computational model for analysis and is not load-bearing for the claimed bounds. No fitted parameter is renamed as a prediction: the experimental section tunes implementation parameters such as d and thread-block size against microbenchmarks and then reports measured comparisons with nvGRAPH, which are empirical evaluations rather than predictions derived from the model. The apparent indexing typo in the proof of Lemma 3.3 and the possible divergence between the implementation trigger in Section 4.1 and the analyzed schedule are correctness risks, not evidence of circularity. The derivation chain is therefore self-contained with respect to its inputs.

Assumptions & free parameters 2 free parameters · 5 assumptions · 0 invented entities

The central theoretical claims introduce one structural parameter d and rely on standard model assumptions and the prior bucket heap. No new physical or mathematical entities are postulated.

free parameters (2)

d (bucket capacity multiplier and max bulkUpdate size) = max out-degree of the input graph in experiments
The structure's capacities are scaled by d; in the SSSP experiments d is set to the maximum out-degree so all relaxations from a settled vertex form one bulkUpdate. This is a tunable knob, not fitted to the target speedup.
number of warps per thread-block = 8 warps (256 threads)
Determined by microbenchmark in Section 4.2; affects implementation performance, not the theoretical bounds.

assumptions (5)

standard math Sequential bucket heap invariants of Brodal et al. (heap property across levels, Fill/Empty semantics)
Section 3.1 builds directly on the cache-oblivious bucket heap of Brodal et al. [4].
standard math Complexities of parallel Merge, Select, DeleteDuplicates (parallel scan and prefix sums) in the EREW PRAM model
Used in Lemma 3.2 proof; cites [27] and standard PRAM results.
standard math The PEM model definitions and cost accounting
Section 3.4 uses the private-cache PEM model from [3], including one or P processors and M/B block transfer costs.
domain assumption Updates only decrease priority (p < p')
Footnote 1 states this assumption and notes it can be removed with timestamps; it is used throughout the priority queue ADT definition.
domain assumption Non-negative edge weights for SSSP
Section 2 assumes all edges have non-negative weight, required for Dijkstra's algorithm.

how reviews work

0 comments

Cite this review

Pith. "Pith review of A parallel priority queue with fast updates for GPU architectures." pith.science (2026). https://pith.science/paper/XPKBFH2R

@misc{pith2026190809378,
  author       = {Pith},
  title        = {Pith review of: A parallel priority queue with fast updates for GPU architectures},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/XPKBFH2R}},
  note         = {Machine review of arXiv:1908.09378}
}

abstract

The single-source shortest path (SSSP) problem is a well-studied problem that is used in many applications. In the parallel setting, a work-efficient algorithm that additionally attains $o(n)$ parallel depth has been elusive. Alternatively, various approaches have been developed that take advantage of specific properties of a particular class of graphs. On a graphics processing unit (GPU), the current state-of-the-art SSSP algorithms are implementations of the Delta-stepping algorithm, which does not perform well for graphs with large diameters. The main contribution of this work is to provide an algorithm designed for GPUs that runs efficiently for such graphs. We present the parallel bucket heap, a parallel cache-efficient data structure adapted for modern GPU architectures that supports standard priority queue operations, as well as bulk update. We analyze the structure in several well-known computational models and show that it provides both optimal parallelism and is cache-efficient. We implement the parallel bucket heap and use it in a parallel variant of Dijkstra's algorithm to solve the SSSP problem. Experimental results indicate that, for sufficiently large, dense graphs with high diameter, we outperform the current state-of-the-art SSSP implementations on an NVIDIA RTX 2080 Ti and Quadro M4000 by up to a factor of 2.8 and 5.4, respectively.

Figures

Figures reproduced from arXiv: 1908.09378 by the authors.

**Figure 2.** Illustration of the dependencies when performing a series of operations. Small green boxes [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗

**Figure 3.** The impact of d (size of S0) on the time to perform a Resolve(0) operation. While increasing d increases the runtime of Resolve(0), the increase is small compared to the number of elements being added to the parBucketHeap, showing that the bulkUpdate operation is efficient for large d. 1 3 5 7 9 11 Warps per threadblock 0 50 100 Time (s) RTX Pascal [PITH_FULL_IMAGE:figures/full_fig_p016_3.png] view at source ↗

Figures from the paper (3 more)

**Figure 5.** Figure 5: Average time to solve the single-source shortest path problem on a DAG of [PITH_FULL_IMAGE:figures/full_fig_p016_5.png]

**Figure 6.** Figure 6: Average runtime for complete, undirected graphs with [PITH_FULL_IMAGE:figures/full_fig_p017_6.png]

**Figure 7.** Figure 7: GPU power usage while computing SSSP on a graph with [PITH_FULL_IMAGE:figures/full_fig_p018_7.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

31 extracted references · 29 canonical work pages

[1]

JaJa, Introduction to Parallel Algorithms

J. JaJa, Introduction to Parallel Algorithms . Reading, MA: Addison-Wesley, 1992

work page 1992
[2]

The input/output coplexity of sorting and related problems,

A. Aggarwal and J. Vitter, “The input/output coplexity of sorting and related problems,” Commun. ACM, vol. 31, no. 11, 1988

work page 1988
[3]

Fundamental parallel algorithms for private-cache chip multiprocessors,

L. Arge, M. Goodrich, M. Nelson, and N. Sitchinava, “Fundamental parallel algorithms for private-cache chip multiprocessors,” in Proc. of SPAA, Munich, Germany, 6 2008, pp. 235–246

work page 2008
[4]

Cache-oblivious data structures and algorithms for undirected breadth-ﬁrst search and shortest paths,

G. S. Brodal, R. Fagerberg, U. Meyer, and N. Zeh, “Cache-oblivious data structures and algorithms for undirected breadth-ﬁrst search and shortest paths,” in Algorithm Theory - SWAT 2004 , T. Hagerup and J. Katajainen, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2004, pp. 480–492

work page 2004
[5]

A parallel priority queue with constant time operations,

G. S. Brodal, J. L. Tr¨ aﬀ, and C. D. Zaroliagis, “A parallel priority queue with constant time operations,” J. Parallel Distrib. Comput. , vol. 49, no. 1, pp. 4–21, Feb. 1998

work page 1998
[6]

CUDA nvgraph library,

NVIDIA, “CUDA nvgraph library,” 2019. [Online]. Available: https://docs.nvidia.com/cuda/nvgraph/ index.html

work page 2019
[7]

T. H. Cormen, C. Stein, R. L. Rivest, and C. E. Leiserson, Introduction to Algorithms , 2nd ed. McGraw-Hill Higher Education, 2001. 18

work page 2001
[8]

The pairing heap: A new form of self-adjusting heap,

M. L. Fredman, R. Sedgewick, D. D. Sleator, and R. E. Tarjan, “The pairing heap: A new form of self-adjusting heap,” Algorithmica, vol. 1, no. 1, pp. 111–129, Jan. 1986. [Online]. Available: http://dx.doi.org/10.1007/BF01840439

doi:10.1007/bf01840439 1986

Show all 31 references

[9]

Very fast optimal parallel algorithms for heap construction,

P. F. Dietz and R. Ramant, “Very fast optimal parallel algorithms for heap construction,” in Proceedings of 1994 6th IEEE Symposium on Parallel and Distributed Processing , Oct 1994, pp. 514–521

1994
[10]

Fibonacci heaps and their uses in improved network optimization algorithms,

M. L. Fredman and R. E. Tarjan, “Fibonacci heaps and their uses in improved network optimization algorithms,” in 25th Annual Symposium on Foundations of Computer Science , Oct 1984, pp. 338–346

1984
[11]

An eﬃcient algorithm for concurrent priority queue heaps,

G. C. Hunt, M. M. Michael, S. Parthasarathy, and M. L. Scott, “An eﬃcient algorithm for concurrent priority queue heaps,” Inf. Process. Lett., vol. 60, no. 3, pp. 151–157, Nov. 1996. [Online]. Available: http://dx.doi.org/10.1016/S0020-0190(96)00148-2

1996 doi
[12]

Cache-oblivious shortest paths in graphs using buﬀer heap,

R. A. Chowdhury and V. Ramachandran, “Cache-oblivious shortest paths in graphs using buﬀer heap,” in Proceedings of the Sixteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures, ser. SPAA ’04. New York, NY, USA: ACM, 2004, pp. 245–254. [Online]. Available:...

2004
[13]

Performance evaluation of priority queues for ﬁne-grained parallel tasks on gpus,

N. Baudis, F. Jacob, and P. Andelﬁnger, “Performance evaluation of priority queues for ﬁne-grained parallel tasks on gpus,” in 2017 IEEE 25th International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems (MASCOTS) , Sep. 2017, pp. 1–11

2017
[14]

Design and implementation of a parallel priority queue on many-core architectures,

X. He, D. Agarwal, and S. K. Prasad, “Design and implementation of a parallel priority queue on many-core architectures,” 2012 19th International Conference on High Performance Computing , pp. 1–10, 2012

2012
[15]

Undirected single source shortest paths in linear time,

M. Thorup, “Undirected single source shortest paths in linear time,” in Proceedings 38th Annual Symposium on Foundations of Computer Science , Oct 1997, pp. 12–21

1997
[16]

A parallelization of dijkstra’s shortest path algorithm,

A. Crauser, K. Mehlhorn, U. Meyer, and P. Sanders, “A parallelization of dijkstra’s shortest path algorithm,” in Proceedings of the 23rd International Symposium on Mathematical Foundations of Computer Science, 1998, pp. 722–731

1998
[17]

Delta-stepping: A parallel single source shortest path algorithm,

U. Meyer and P. Sanders, “Delta-stepping: A parallel single source shortest path algorithm,” in Proceedings of the 6th Annual European Symposium on Algorithms , ser. ESA ’98, 1998, pp. 393–404

1998
[18]

Handbook of theoretical computer science (vol. a),

R. M. Karp and V. Ramachandran, “Handbook of theoretical computer science (vol. a),” J. van Leeuwen, Ed. Cambridge, MA, USA: MIT Press, 1990, ch. Parallel Algorithms for Shared-memory Machines, pp. 869–941. [Online]. Available: http://dl.acm.org/citation.cfm?id=114872.114889

1990
[19]

Arora and B

S. Arora and B. Barak, Computational Complexity: A Modern Approach , 1st ed. New York, NY, USA: Cambridge University Press, 2009

2009
[20]

Eﬃcient parallel algorithms for computing all pair shortest paths in directed graphs,

Y. Han, V. Pan, and J. Reif, “Eﬃcient parallel algorithms for computing all pair shortest paths in directed graphs,” in Proceedings of the Fourth Annual ACM Symposium on Parallel Algorithms and Architectures, ser. SPAA ’92. New York, NY, USA: ACM, 1992, pp. 353–362. [Online]. ...

1992
[21]

Parallel shortest paths using radius stepping,

G. E. Blelloch, Y. Gu, Y. Sun, and K. Tangwongsan, “Parallel shortest paths using radius stepping,” in Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures , 2016, pp. 443–454

2016
[22]

Accelerating large graph algorithms on the gpu using cuda,

P. Harish and P. J. Narayanan, “Accelerating large graph algorithms on the gpu using cuda,” in Proceedings of the 14th International Conference on High Performance Computing , ser. HiPC’07. Berlin, Heidelberg: Springer-Verlag, 2007, pp. 197–208. [Online]. Available: http://dl....

2007
[23]

All-pairs shortest-paths for large graphs on the gpu,

G. J. Katz and J. T. Kider, Jr, “All-pairs shortest-paths for large graphs on the gpu,” in Proceedings of the 23rd ACM SIGGRAPH/EUROGRAPHICS Symposium on Graphics Hardware , ser. GH ’08. Aire-la-Ville, Switzerland, Switzerland: Eurographics Association, 2008, pp. 47–55. [Onlin...

2008
[24]

Work-eﬃcient parallel gpu methods for single- source shortest paths,

A. Davidson, S. Baxter, M. Garland, and J. D. Owens, “Work-eﬃcient parallel gpu methods for single- source shortest paths,” in Proceedings of the 2014 IEEE 28th International Parallel and Distributed Processing Symposium, ser. IPDPS ’14, 2014, pp. 349–359

2014
[25]

Gunrock: A high-performance 19 graph processing library on the gpu,

Y. Wang, A. Davidson, Y. Pan, Y. Wu, A. Riﬀel, and J. D. Owens, “Gunrock: A high-performance 19 graph processing library on the gpu,” SIGPLAN Not., vol. 51, no. 8, pp. 11:1–11:12, Feb. 2016

2016
[26]

CUDA programming guide 10.0,

NVIDIA, “CUDA programming guide 10.0,” 2019. [Online]. Available: http://docs.nvidia.com/cuda

2019
[27]

Merge path - A visually intuitive approach to parallel merging,

O. Green, S. Odeh, and Y. Birk, “Merge path - A visually intuitive approach to parallel merging,” CoRR, vol. abs/1406.2628, 2014

2014 arXiv
[28]

JaJa, An Introduction to Parallel Algorithms

J. JaJa, An Introduction to Parallel Algorithms . Reading, Mass.: Addison-Wesley Publishing Co., 1992

1992
[29]

Geneva, Switzerland: International Organization for Standardization, Feb

ISO, ISO/IEC 14882:2011 Information technology — Programming languages — C++ . Geneva, Switzerland: International Organization for Standardization, Feb. 2012. [Online]. Available: http://www.iso.org/iso/iso catalogue/catalogue tc/catalogue detail.htm?csnumber=50372

2011
[30]

Thrust: A parallel template library,

J. Hoberock and N. Bell, “Thrust: A parallel template library,” 2010, version 1.7.0. [Online]. Available: http://thrust.github.io/

2010
[31]

Proﬁler user’s guide,

NVIDIA, “Proﬁler user’s guide,” 2019. [Online]. Available: http://docs.nvidia.com/cuda/ proﬁler-users-guide 20

2019

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [1]

JaJa, Introduction to Parallel Algorithms

J. JaJa, Introduction to Parallel Algorithms . Reading, MA: Addison-Wesley, 1992

work page 1992

[2] [2]

The input/output coplexity of sorting and related problems,

A. Aggarwal and J. Vitter, “The input/output coplexity of sorting and related problems,” Commun. ACM, vol. 31, no. 11, 1988

work page 1988

[3] [3]

Fundamental parallel algorithms for private-cache chip multiprocessors,

L. Arge, M. Goodrich, M. Nelson, and N. Sitchinava, “Fundamental parallel algorithms for private-cache chip multiprocessors,” in Proc. of SPAA, Munich, Germany, 6 2008, pp. 235–246

work page 2008

[4] [4]

Cache-oblivious data structures and algorithms for undirected breadth-ﬁrst search and shortest paths,

G. S. Brodal, R. Fagerberg, U. Meyer, and N. Zeh, “Cache-oblivious data structures and algorithms for undirected breadth-ﬁrst search and shortest paths,” in Algorithm Theory - SWAT 2004 , T. Hagerup and J. Katajainen, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2004, pp. 480–492

work page 2004

[5] [5]

A parallel priority queue with constant time operations,

G. S. Brodal, J. L. Tr¨ aﬀ, and C. D. Zaroliagis, “A parallel priority queue with constant time operations,” J. Parallel Distrib. Comput. , vol. 49, no. 1, pp. 4–21, Feb. 1998

work page 1998

[6] [6]

CUDA nvgraph library,

NVIDIA, “CUDA nvgraph library,” 2019. [Online]. Available: https://docs.nvidia.com/cuda/nvgraph/ index.html

work page 2019

[7] [7]

T. H. Cormen, C. Stein, R. L. Rivest, and C. E. Leiserson, Introduction to Algorithms , 2nd ed. McGraw-Hill Higher Education, 2001. 18

work page 2001

[8] [8]

The pairing heap: A new form of self-adjusting heap,

M. L. Fredman, R. Sedgewick, D. D. Sleator, and R. E. Tarjan, “The pairing heap: A new form of self-adjusting heap,” Algorithmica, vol. 1, no. 1, pp. 111–129, Jan. 1986. [Online]. Available: http://dx.doi.org/10.1007/BF01840439

doi:10.1007/bf01840439 1986