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

Info about event

Time

Monday 25 June 2018,  at 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 

Abstract:

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