Exploiting trivial and redundant computation

Abstract

The notion of trivial computation, in which the appearance of simple operands renders potentially complex operations simple, is discussed. An example of a trivial operation is integer division, where the divisor is two; the division becomes a simple shift operation. The concept of redundant computation, in which some operation repeatedly does the same function because it repeatedly sees the same operands, is also discussed. Experiments on two separate benchmark suites, the SPEC benchmarks and the Perfect Club, find a surprising amount of trivial and redundant operation. Various architectural means of exploiting this knowledge to improve computational efficiency include detection of trivial operands and the result cache. Further experimentation shows significant speedup from these techniques, as measured on three different styles of machine architecture.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>