HP Labs Technical Reports

Acceleration of Algebraic Recurrences on Processors with Instruction Level Parallelism

Schlansker, Michael S.; Kathail, Vinod

HPL-93-55

Keyword(s):

Abstract: This report describes parallelization techniques for accelerating a broad class of recurrences on processors with instruction level parallelism. We introduce a new technique, called blocked back-substitution, which has lower operation count and higher performance than previous methods. The blocked back-substitution technique requires unrolling and non-symmetric optimization of innermost loop iteration. We present metrics to characterize the performance of software-pipelined loops and compare these metrics for a range of height reduction techniques and processor architectures.

Back to Index