| Recently many numeric computing kernels such as matrix multiplication [ATLAS and PHiPAC],
sparse matrix vector product [Sparsity] the fast Fourier transform [FFTW, UHFFT], and
more general DSP transforms [SPIRAL] have utilized code generation and automated
performance tuning to obtain high-performance implementations tuned to specific
platforms. This talk outlines how these techniques may be applied to symbolic
computation and computer algebra systems.
Examples demonstrating the benefit of these techniques are drawn from the
papers [ISSAC06, ISSAC05] which show that the performance of the Taylor shift
operation used in real root isolation can be substantially improved through
delayed carry propagation, radix reduction, and an interlaced coefficient
representation combined with register tiling.
This speedup is obtained over a straightforward implementation that utilizes
the heavily optimized integer addition routines from GMP. The resulting
code is significantly more complicated that the original code utilizing GMP.
Moreover, the code can be tuned using different tile sizes, amounts of
unrolling and different scheduling strategies. Note that compilers are not
capable of performing this tuning due to various dependencies and lack
higher knowledge needed to transform the code.
The particular tuning parameters used depends on the platform (e.g. number
of registers, number of integer units, etc.) and furthermore, the optimal
parameter settings are not easily determined without runtime experiments.
This talk presents a code generator from [Richardson09] that produces code
with different tile sizes and empirically searches for the best implementation
on a given platform.
[ISSAC06] Jeremy Johnson, Werner Krandick, Kevin Lynch, David Richardson, and
Anatole Ruslanov, High-performance implementations of the Descartes method.
In J.-G. Dumas, editor, International Symposium on Symbolic and Algebraic Computation,
pp. 154-161, ACM Press, 2006.
[ISSAC05] Jeremy Johnson, Werner Krandick, and Anatole Ruslanov, Architecture-aware
classical Taylor shift by 1. In M. Kauers, editor, International Symposium on Symbolic
and Algebraic Computation, pp. 200-207, ACM Press, 2005.
[Richardson09] David Richardson, Efficient Programming Techniques for the SACLIB
Computer Algebra Library, Ph.D. Thesis, Drexel University, 2009. |