Theory seminar- Nodari Sitchinava: Sorting in the Asymmetric External Memory Model

2018.06.22 | Dorthe Haagen Nielsen

Date Mon 25 Jun
Time 14:15 15:00
Location 5335-298 Nygaard Møderum (14);

Speaker: Nodari Sitchinava (University of Hawaii)

Title: Sorting in the Asymmetric External Memory Model 


Asymmetric External Memory (AEM) model, introduced by Blelloch et al. at SPAA 2015, models computations on new non-volatile memory (NVM), rather than tradition DRAM technology for storage purposes. The significant difference in NVMs is the fact that the cost of writing data is significantly more expensive than the cost of reading it.  This asymmetry requires new algorithmic techniques that emphasize the ability to trade-off write accesses for extra read accesses during computation.

In this talk I will present sorting algorithms, which achieve such trade-off between read and write accesses in the AEM model. I will also show a lower bound that proves that these algorithms are asymptotically optimal.

This is joint work with Riko Jacob, and appeared in SPAA 2017.

Host: Peyman Afshani  

Site Specific, CS frontpage, Featured, Lecture / talk