Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, EpiSciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation
Conference papers

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 metadata

Cited literature [13 references]  Display  Hide  Download
Contributor : Carine Pivoteau Connect in order to contact the contributor
Submitted on : Wednesday, October 7, 2015 - 3:02:38 PM
Last modification on : Saturday, January 15, 2022 - 3:59:25 AM
Long-term archiving on: : Friday, January 8, 2016 - 10:34:23 AM


Files produced by the author(s)



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⟩



Record views


Files downloads