Logo image
Back
Architecture-aware classical Taylor shift by 1
Conference proceeding

Architecture-aware classical Taylor shift by 1

Jeremy Johnson, Werner Krandick and Anatole Ruslanov
Proceedings of the 2005 international symposium on symbolic and algebraic computation, v 2005, pp 200-207
24 Jul 2005
DOI: https://doi.org/10.1145/1073884.1073913

Abstract

code generation delayed carry propagation high-performance computing ILP scheduling loop unrolling memory hierarchy multiprecision arithmetic performance tuning polynomials register tiling Taylor shift
We present algorithms that outperform straightforward implementations of classical Taylor shift by 1. For input poly-nomials of low degrees a method of the SACLIB library is faster than straightforward implementations by a factor of at least 2; for higher degrees we develop a method that is faster than straightforward implementations by a factor of up to 7. Our Taylor shift algorithm requires more word additions than straightforward methods but it reduces the number of cycles per word addition by reducing memory traffic and the number of carry computations. The introduction of signed digits, suspended normalization, radix reduction, and delayed carry propagation enables our algorithm to take advantage of the technique of register tiling which is commonly used by optimizing compilers. While our algorithm is written in a high-level language, it depends on several parameters that can be tuned to the underlying architecture.

Metrics

3 Record Views
11 citations in Scopus

Details

Logo image