Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH scholarly article en Auger, Nicolas; Nicaud, Cyril; Pivoteau, Carine http://www.dagstuhl.de/lipics License
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-57135
URL:

; ;

Good Predictions Are Worth a Few Comparisons

pdf-format:


Abstract

Most modern processors are heavily parallelized and use predictors to guess the outcome of conditional branches, in order to avoid costly stalls in their pipelines. We propose predictor-friendly versions of two classical algorithms: exponentiation by squaring and binary search in a sorted array. These variants result in less mispredictions on average, at the cost of an increased number of operations. These theoretical results are supported by experimentations that show that our algorithms perform significantly better than the standard ones, for primitive data types.

BibTeX - Entry

@InProceedings{auger_et_al:LIPIcs:2016:5713,
  author =	{Nicolas Auger and Cyril Nicaud and Carine Pivoteau},
  title =	{{Good Predictions Are Worth a Few Comparisons}},
  booktitle =	{33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)},
  pages =	{12:1--12:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-001-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{47},
  editor =	{Nicolas Ollinger and Heribert Vollmer},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/5713},
  URN =		{urn:nbn:de:0030-drops-57135},
  doi =		{10.4230/LIPIcs.STACS.2016.12},
  annote =	{Keywords: branch misses, binary search, exponentiation by squaring, Markov chains}
}

Keywords: branch misses, binary search, exponentiation by squaring, Markov chains
Seminar: 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)
Issue date: 2016
Date of publication: 2016


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI