Yan Gu

Write-Efficient Algorithms Degree Type: Ph.D. in Computer Science
Advisor(s): Guy Blelloch
Graduated: December 2018

Abstract:

New non-volatile memory (NVM) technologies are projected to become the dominant type of main memory in the near future. They promise byte addressability, good read latencies, and significantly lower energy and higher density compared to DRAM. However, a key property of NVMs is the asymmetric read and write cost: write operations are much more expensive than reads regarding energy, bandwidth, and latency. This property contradicts fifty years of classic algorithms research that has focused on the setting in which reads and writes have similar cost, and poses the need to develop write-efficient algorithms that use fewer writes than the classic approaches.

This thesis provides a comprehensive study of the design and analysis of write-efficient algorithms, which includes computational models, lower bounds, algorithms, and experimental validations. More specifically, this thesis first presents and studies several models that account for read-write asymmetry in different settings (sequential, parallel, I/O models, etc.). Then, a number of lower bounds are shown, which indicate the hardness of asymptotically improving some classic algorithms under certain assumptions.

The main contribution of this thesis consists of new write-efficient algorithms for fundamental algorithms in Computer Science, from basic algorithmic building blocks (sorting, reduce, filter, etc.), to graph algorithms ((bi)connectivity, shortest paths, MST, BFS, etc.), geometric algorithms and data structures (convex hull, Delaunay triangulation, k-d trees, augmented trees, etc.), as well as many cache-oblivious algorithms for dynamic programming and linear algebra problems. The numbers of writes in all algorithms studied in this thesis are significantly reduced asymptotically. Furthermore, most of these algorithms are also highly parallel. Many techniques used to obtain these results are of independent interest, since they are applicable to many other problems outside those studied in this thesis, and lead to improved algorithms in the classic setting without read-write asymmetry.

This thesis also proposes the first experimental framework to analyze the performance of write-efficient algorithms in practice, and conducts experiments on a variety of algorithms. The experimental results show the effectiveness of write-efficient algorithms, and suggest that the algorithms developed in this thesis may be of both theoretical and practical interest.

Thesis Committee:
Guy E. Blelloch (Chair)
Phillip B. Gibbons
Anupam Gupta
Jeremy T. Fineman (Georgetown University)
Julian Shun (Massachusetts Institute of Technology)

Srinivasan Seshan, Head, Computer Science Department
Andrew W. Moore, Dean, School of Computer Science

Keywords:
Write-Efficient Algorithms, Non-Volatile Memory, Asymmetric Read and Write Cost, Computational Model, Parallel Algorithms