4 papers
Implicit Decomposition for Write-Efficient Connectivity Algorithms
Naama Ben-David, Guy E. Blelloch, Jeremy T. Fineman +4
The future of main memory appears to lie in the direction of new technologies that provide strong capacity-to-performance ratios, but have write operations that are much more expen…
Parallel Shortest-Paths Using Radius Stepping
Guy E. Blelloch, Yan Gu, Yihan Sun +1
The single-source shortest path problem (SSSP) with nonnegative edge weights is a notoriously difficult problem to solve efficiently in parallel---it is one of the graph problems s…
Sorting with Asymmetric Read and Write Costs
Guy E. Blelloch, Jeremy T. Fineman, Phillip B. Gibbons +2
Emerging memory technologies have a significant gap between the cost, both in time and in energy, of writing to memory versus reading from memory. In this paper we present models a…
Selective Memoization
Umut A. Acar, Guy E. Blelloch, Robert Harper
This paper presents language techniques for applying memoization selectively. The techniques provide programmer control over equality, space usage, and identification of precise de…