Computer Science Thesis Oral

  • Gates Hillman Centers
  • Traffic21 Classroom 6501
  • YAN GU
  • Ph.D. Student
  • Computer Science Department
  • Carnegie Mellon University
Thesis Orals

Write-Efficient Algorithms


The 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, 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.  Such property contradicts the fifty years of classic algorithm research that has focused on settings in which reads and writes have similar cost, and poses the desire of “write-efficient algorithms” that use much fewer writes compared to the classic approaches.

This thesis provides a comprehensive study of designing write-efficient algorithms, which includes computational models, lower bounds, algorithms, experiment verifications, as well as fault-tolerant programming on the new persistent memories.  More specifically, this thesis first presents and studies several models accounting for this asymmetry in various settings (sequential, parallel, I/O models, etc.). Then a number of lower bounds are shown, indicating the hardness of improving some algorithms under certain assumptions.

The main contribution of this thesis consists of a list of new write-efficient algorithms from the basic algorithmic building blocks (sorting, reduce, filter, etc.), to graph algorithms (e.g., (bi-)connectivity, shortest paths, MST, BFS), geometric algorithms and data structures (e.g., convex hull, Delaunay triangulation, k-d trees, augmented trees), as well as many cache-oblivious algorithms on dynamic programming and linear algebra problems.  The numbers of writes in all these algorithms are significantly reduced.  Also, most of these algorithms are highly parallelized.  Many techniques used in these algorithms are of independent interests, and can be applied to improving various algorithms in other settings.

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 which leads to many interesting findings and lessons.  Another contribution of this thesis is the first programming model to ensure fault-tolerant algorithm design on the new persistent main memories, and how to adapt the new write-efficient algorithms into this model.

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

For More Information, Please Contact: 
Keywords: