Sorting with Asymmetric Read and Write Costs
Friday, September 11th, 2015 from 12-1 pm in GHC 6501.
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.
The Student Seminar Series is an informal research seminar by and for SCS graduate students from noon to 1 pm on Mondays and Fridays. Lunch is provided by the Computer Science Department (personal thanks to Sharon Burks and Debbie Cavlovich!). At each meeting, a different student speaker will give an informal, 40-minute talk about his/her research, followed by questions/suggestions/brainstorming. We try to attract people with a diverse set of interests, and encourage speakers to present at a very general, accessible level.
So why are we doing this and why take part? In the best case scenario, this will lead to some interesting cross-disciplinary work among people in different fields and people may get some new ideas about their research. In the worst case scenario, a few people will practice their public speaking and the rest get together for a free lunch.
Note: Step #1 below are applicable to all SSS speakers. You can schedule AT MOST THREE talks per semester.
SSS is an ideal forum for SCS students to give presentations that count toward fulfilling their speaking requirements. The specifics, though, vary with each department. For instance, students in CSD will need to be familiar with the notes in Section 8 of the Ph.D. document and follow the instructions outlined on the Speakers Club homepage. Roughly speaking, these are the steps:
Armaghan Naik, Computational Biology