Balancing reuse opportunities and performance gains with subblock value reuse

Jian Huang, David J. Lilja

Research output: Contribution to journalArticlepeer-review

Abstract

The fact that instructions in programs often produce repetitive results has motivated researchers to explore various technique, such as value prediction and value reuse, to exploit this behavior. Value prediction improves the available Instruction-Level Parallelism (ILP) in superscalar processors by allowing dependent instructions to be executed speculatively after predicting the values of their input operands. Value reuse, on the other hand, tries to eliminate redundant computation by storing the previously produced results of instructions and skipping the execution of redundant instructions. Previous value reuse mechanisms use a single instruction or a naturally formed instruction group, such as a basic block, a trace, or a function, as the reuse unit. These naturally-formed instruction groups are readily identifiable by the hardware at runtime without compiler assistance. However, the performance potential of a value reuse mechanism depends on its reuse detection time, the number of reuse opportunities, and the amount of work saved by skipping each reuse unit. Since larger instruction groups typically have fewer reuse opportunities than smaller groups, but they provide greater benefit for each reuse-detection process, it is very important to find the balance point that provides the largest overall performance gain. In this paper, we propose a new mechanism called subblock reuse. Subblocks are created by slicing basic blocks either dynamically or with compiler guidance. The dynamic approaches use the number of instructions, numbers of inputs and outputs, or the presence of store instructions to determine the subblock boundaries. The compiler-assisted approach slices basic blocks using data-flow considerations to balance the reuse granularity and the number of reuse opportunities. The results show that subblocks, which can produce up to 36 percent speedup if reused properly, are better candidates for reuse units than basic blocks. Although subblock reuse with compiler assistance has a substantial and consistent potential to improve the performance of superscalar processors, this scheme is not always the best performer. Subblocks restricted to two consecutive instructions demonstrate surprisingly good performance potential as well.

Original languageEnglish (US)
Pages (from-to)1032-1050
Number of pages19
JournalIEEE Transactions on Computers
Volume52
Issue number8
DOIs
StatePublished - Aug 2003

Bibliographical note

Funding Information:
This work was supported in part by the US National Science Foundation under Grant Nos. CCR-9900605, EIA-9971666, and MIP-9610379, by the Minnesota Supercomputing Institute, and by the IBM Corporation.

Keywords

  • Block reuse
  • Compiler flow analysis
  • Subblock reuse
  • Value locality
  • Value reuse

Fingerprint

Dive into the research topics of 'Balancing reuse opportunities and performance gains with subblock value reuse'. Together they form a unique fingerprint.

Cite this