A Branch-Free General Renormalization Scheme for Pair Arithmetic and Its Performance Evaluation
Abstract
Pair arithmetic omits the renormalization stage performed at the end of each operation of multi-component multiple-precision arithmetic, reducing the operation count and, by eliminating conditional branches, easing SIMD vectorization. Renormalization cannot be omitted entirely, however, because iterative solvers may then fail to converge. We propose RenormBF-pair, a branch-free fixed-trip-count renormalizer parameterized by the word count K and the input length n: a VecSum sweep, a tail fold, and r rounds of a FastTwoSum chain, costing 6(n−1)+(n−K)+3r(K−1) flops. Over 200,000 trials per condition, the smallest round count producing no non-overlap violation was r=1 for K ≤ 3 and r=2 for K=4, whereas the same cost spent on a VecSumK-style TwoSum chain fails for K=4. We delimit with explicit counterexamples both the input condition under which the sum relation holds and the fact that the scheme does not, in general, guarantee a correctly rounded lowest component. Integrating it into CG and BiCGStab over pair arithmetic in binary64 and binary32, we sweep 240 paired runs including real matrices screened from SuiteSparse. The proposed scheme and VecSumK returned bitwise identical words wherever both succeeded, so they are indistinguishable for CG in binary64; differences appear only where VecSumK breaks, namely binary32 and BiCGStab. There the 22--16 win--loss record is not significant (sign test, p=0.42); the clear bias is structural, non-overlap violations dropping from 66 rows to 37. The cost is +3.4% for the whole CG solver.
Related
- Performance Evaluation of an Adaptive Quadrature and a Double Exponential Formula Using Arbitrary-Precision Floating-Point Arithmetic
- On the arithmetic Siegel--Weil formula for orthogonal Shimura varieties over a general totally real field
- Application of spectroscopic and multispectral imaging technologies on the assessment of ready-to-eat pineapple quality: A performance evaluation study of machine learning models generated from two commercial data analytics tools
- On the Performance Evaluation of Anytime Algorithms in Noisy Optimization
- Performance Evaluation of Fast Fourier Transforms on Emerging RISC-V Hardware with Vector Extension Support
BibTeX
@misc{kouya2026branchfree,
title = {{A Branch-Free General Renormalization Scheme for Pair Arithmetic and Its Performance Evaluation}},
author = {Tomonori Kouya},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.35844},
eprint = {2609.35844},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.35844},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - A Branch-Free General Renormalization Scheme for Pair Arithmetic and Its Performance Evaluation
AU - Tomonori Kouya
PY - 2026
DA - 2026/09/25
PB - arXiv
DO - 10.48550/arxiv.2609.35844
UR - https://arxiv.org/abs/2609.35844
AB - Pair arithmetic omits the renormalization stage performed at the end of each operation of multi-component multiple-precision arithmetic, reducing the operation count and, by eliminating conditional branches, easing SIMD vectorization. Renormalization cannot be omitted entirely, however, because iterative solvers may then fail to converge. We propose RenormBF-pair, a branch-free fixed-trip-count renormalizer parameterized by the word count K and the input length n: a VecSum sweep, a tail fold, and r rounds of a FastTwoSum chain, costing 6(n−1)+(n−K)+3r(K−1) flops. Over 200,000 trials per condition, the smallest round count producing no non-overlap violation was r=1 for K ≤ 3 and r=2 for K=4, whereas the same cost spent on a VecSumK-style TwoSum chain fails for K=4. We delimit with explicit counterexamples both the input condition under which the sum relation holds and the fact that the scheme does not, in general, guarantee a correctly rounded lowest component. Integrating it into CG and BiCGStab over pair arithmetic in binary64 and binary32, we sweep 240 paired runs including real matrices screened from SuiteSparse. The proposed scheme and VecSumK returned bitwise identical words wherever both succeeded, so they are indistinguishable for CG in binary64; differences appear only where VecSumK breaks, namely binary32 and BiCGStab. There the 22--16 win--loss record is not significant (sign test, p=0.42); the clear bias is structural, non-overlap violations dropping from 66 rows to 37. The cost is +3.4% for the whole CG solver.
ER -