Speaker: Yan Gu Carnegie Mellon University
Time: 2015-10-08 11:00-2015-10-08 12:00
Venue: FIT 1-222

Abstract:

Fifty years of algorithms research has focused on settings in which reads and writes have similar cost. However, 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 talk, we present models and algorithms that account for this difference.  First, we consider the PRAM model with asymmetric write cost, and show that sorting can be performed in $O(n)$ writes, $O(n\log n)$ reads, and logarithmic depth (parallel time).  Next, we consider a variant of the External Memory (EM) model that charges $ω > 1$ for writing a block of size $B$ to the secondary memory, and present variants of three EM sorting algorithms (multi-way mergesort, sample sort, and heapsort using buffer trees) that asymptotically reduce the number of writes over the original algorithms, and perform roughly $ω$ block reads for every block write.  Then, we define a variant of the Ideal-Cache model with asymmetric write costs, and introduce write-efficient, cache-oblivious parallel algorithms for sorting, FFTs, and matrix multiplication.  Lastly, we study lower and upper bounds for various problems on the asymmetric RAM model with a small memory with size M. We show a lower bound cost for FFT and sorting networks of $\Omega(ω(n \log_{ωM} n))$, and bound for computations on a diamond DAG. We also show upper bounds for the minimum edit distance problem with $O(n^2ω/ (M\min(ω^{1/3},M^{1/2})))$ costs, and for the single source shortest paths problem we show a variant of Dijkstra's that runs with cost $O(\min(n (ω+ m/M), ω(m+n\log n),m(ω+\log n)))$.

Short Bio:

Yan Gu is a fourth-year PhD student in Computer Science Department of Carnegie Mellon University, advised by Prof. Guy Blelloch. He received his Bachelor Degree from Tsinghua University in 2012. His research interests are broadly in algorithm designing, with an emphasis on parallel algorithms on sorting and searching on space with low dimensionality.