Monday, September 14, 2015 - 12:00pm
Location:Traffic 21 Classroom 6501 Gates & Hillman Centers
Speaker:YAN GU, Ph.D. Student http://www.cs.cmu.edu/~ygu1/
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, with a focus on two models and associated sorting algorithms. First, we consider the RAM model with asymmetric write cost, and show that sorting can be performed in O(n) writes, O(n log n) reads. Next, we consider a variant of the External Memory (EM) model that charges w > 1 for writing a block of size B to the secondary memory, and present a multi-way mergesort that asymptotically reduce the number of writes over the original algorithms, and perform roughly w block reads for every block write. Lastly, we will briefly introduce some other results of related research. Joint work with Guy Blelloch, Jeremy Fineman, Phil Gibbons, and Julian Shun. Presented in Partial Fulfillment of the CSD Speaking Skills Requirement.