@inproceedings{sitchinava-spaa17,
  author = "Riko Jacob and Nodari Sitchinava",
  title = "Lower bounds in the Asymmetric External Memory model",
  booktitle = "Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures",
  series = "SPAA '17",
  pages = "247-254",
  year = 2017,
  month = 7,
  doi = "10.1145/3087556.3087583",
  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 $\omega$ between write and read costs, we show $\Omega(\min\{N, \frac{\omega N}{B}\log_{\frac{\omega M}{B}} \frac{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~$\omega$.  We also show a lower bound of  $\Omega\left(\min\left\{H,\frac{\omega H}{B} \log_{\frac{\omega M}{B}}  \frac{N}{\max\{\delta ,M\}} \right\} \right)$ for the cost of multiplying an $N \times N$ matrix with at most $H=\delta N$ non-empty entries by a vector with $N$ elements."
}