Lower Bounds in the Asymmetric External Memory Model

Riko Jacob, Nodari Sitchinava

Research output: Conference Article in Proceeding or Book/Report chapterArticle in proceedingsResearchpeer-review

Abstract

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.
Original languageEnglish
Title of host publicationSPAA '17 Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures
PublisherAssociation for Computing Machinery
Publication dateJul 2017
Pages247-254
ISBN (Print)978-1-4503-4593-4
DOIs
Publication statusPublished - Jul 2017

Fingerprint

Dive into the research topics of 'Lower Bounds in the Asymmetric External Memory Model'. Together they form a unique fingerprint.

Cite this