Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2016.12
URN: urn:nbn:de:0030-drops-57135
URL: https://drops.dagstuhl.de/opus/volltexte/2016/5713/
Auger, Nicolas ; Nicaud, Cyril ; Pivoteau, Carine
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: | 16.02.2016 |
