Optimizing Capacitance and Switching Activity to Reduce Dynamic Power - Computer Architecture Techniques for Power-Efficiency - page 112

Operand 1 Operand 2

Division
Unit

Memo
Ta b l e

operation
completed
line

hit/miss line

MUX

Result

FIGURE 4.33: Operation-level Memoization: The Memo-table in this particular example captures
inputs and results from a division unit. When inputs previously seen are detected the result is read from
the Memo-table and the computation the division unit ceases.

4.10.1 Work Reuse
Work reuse appears at various granularities. Here, we start at the operation level (finer granu-
larity) and proceed towards instruction, basic block, and trace level (coarser granularities).
Operation level : Citron, Feitelson, and Rudolph proposed memoization (or memoing )for
multicycle floating point operations [ 56 ]. Memoization is the act of remembering the result of
an operation in relation to its inputs. A memoization cache or Memo-table, as is called by Citron
et al. [ 56 ], stores the input operands and the result of floating point operations. Upon seeing the
same operands the result is retrieved from the Memo-table and is multiplexed onto the output
(Figure 4.33). The Memo-table access and the floating point operation start simultaneously.
However, accessing the Memo-table is much faster (single-cycle) than performing the actual
multi-cycle operation. Since the result is available much earlier this translates into performance
benefits but also (by gating the floating point unit before it completes the operation) to power
benefits. The power benefits are commensurable to the energy differential between accessing
the cache and performing the operation to completion.
Unfortunately, the work of Citron et al. does not contain an evaluation on the power
impact of their technique. However, they do give memoization statistics for multimedia ap-
plications (Perfect benchmark suite, SPEC FP95, and imaging/DSP applications) which, in
conjunction with simple power models for the floating point unit and the memo-tables, can
be used to derive power estimates. For their workloads, 59% of integer multiplies, 43% of FP