Lower Bounds in the Asymmetric External Memory Model

Riko Jacob, Nodari Sitchinava

Publikation: Konference artikel i Proceeding eller bog/rapport kapitelKonferencebidrag i proceedingsForskningpeer review


Motivated by the asymmetric read and write costs of emerging non-volatile memory technologies, we study lower bounds for the problems of sorting, permuting and multiplying a sparse matrix by a dense vector in the asymmetric external memory model (AEM). Given an AEM with internal (symmetric) memory of size M, transfers between symmetric and asymmetric memory in blocks of size B and the ratio ω between write and read costs, we show Ω(min (N, ωN/B logω M/B N/B) lower bound for the cost of permuting N input elements. This lower bound also applies to the problem of sorting N elements. This proves that the existing sorting algorithms in the AEM model are optimal to within a constant factor for reasonable ranges of parameters N, M, B, and ω. We also show a lower bound of Ω(min {H, ω H/B logω M/B N/ max{δ ,M}}) for the cost of multiplying an N x N matrix with at most H= δ N non-empty entries by a vector with N elements.
TitelSPAA '17 Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures
ForlagAssociation for Computing Machinery
Publikationsdatojul. 2017
ISBN (Trykt)978-1-4503-4593-4
StatusUdgivet - jul. 2017


Dyk ned i forskningsemnerne om 'Lower Bounds in the Asymmetric External Memory Model'. Sammen danner de et unikt fingeraftryk.