Sun and Oracle Community Voices How to Buy Log In United States [Change] English

»  1992
»  1993
»  1994
»  1995
»  1996
»  1997
»  1998
»  1999
»  2000
»  2001
»  2002
»  2003
»  2004
»  2005
»  2006

Caching Function Results: Faster Arithmetic by Avoiding Unnecessary Computation

Author(s):
Stephen E. Richardson
Report Number: Date Published: Available Formats:
TR-92-1 September 1992 Portable Document Format (PDF)
Postscript (PS)
Request Hard Copy
Abstract


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:
    • [General]

Keywords and Phrases: Memoization, Multiplication, Result cache