Good predictions are worth a few comparisons

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. 1998 ACM Subject Classification F.2.2 Nonnumerical Algorithms and Problems
Complete list of metadatas

Cited literature [13 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-01212840
Contributor : Carine Pivoteau <>
Submitted on : Wednesday, October 7, 2015 - 3:02:38 PM
Last modification on : Thursday, July 5, 2018 - 2:45:51 PM
Long-term archiving on : Friday, January 8, 2016 - 10:34:23 AM

File

aunipi2016-branch-predictions....
Files produced by the author(s)

Identifiers

Citation

Nicolas Auger, Cyril Nicaud, Carine Pivoteau. Good predictions are worth a few comparisons. STACS 2016, Feb 2016, Orléans, France. pp.12:1-12:14, ⟨10.4230/LIPIcs.STACS.2016.12⟩. ⟨hal-01212840⟩

Share

Metrics

Record views

814

Files downloads

492