|
This report introduces the notion of trivial computation, where the appearance of simple operands reduces the complexity of a potentially difficult operation. An example of a trivial operation is integer divide-by-two; the division becomes a simple shift operation. Also discussed is the concept of redundant computation, where some operation repeatedly does the same function because it repeatedly sees the same operands. Using two separate benchmark suites, the SPEC benchmarks and the Perfect Club, and concentrating on multiplication, we 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, memoization, and the result cache.
Categories and Subject Descriptors:
- B.6.1 Hardware
- [Logic Design]: Design Styles - Memory used as logic
- F.2.0 Theory of Computation:
- [Analysis of Algorithms and Problem Complexity]: General
- G.0 Mathematics of Computing:
Keywords and Phrases: Memoization, Multiplication, Result cache
|
