Branch-on-random

Edward Lee, Craig Zilles

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We propose a new instruction, branch-on-random, that is like a standard conditional branch, except rather than specifying the condition on which the branch should be taken, it specifies a frequency at which the branch should be taken. We show that branchon-random is useful for reducing the overhead of program instrumentation, via sampling. Specifically, branch-on-random provides an order-of-magnitude reduction in execution time overhead compared to previously proposed software-only frameworks for instrumentation sampling. Furthermore, we demonstrate that branch-on-random can be cleanly architected and implemented simply and efficiently. For simple processors, we estimate that branch-on-random can be implemented with 20 bits of state and less than 100 gates; for aggressive superscalars, this grows to less than 100 bits of state and at most a few hundred gates.

Original languageEnglish (US)
Title of host publicationProceedings of the 2008 CGO - Sixth International Symposium on Code Generation and Optimization
Pages84-93
Number of pages10
DOIs
StatePublished - May 19 2008

Publication series

NameProceedings of the 2008 CGO - Sixth International Symposium on Code Generation and Optimization

Keywords

  • Branch
  • Instrumentation
  • LFSR
  • Profiling
  • Pseudo-random
  • Sampling

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Branch-on-random'. Together they form a unique fingerprint.

  • Cite this

    Lee, E., & Zilles, C. (2008). Branch-on-random. In Proceedings of the 2008 CGO - Sixth International Symposium on Code Generation and Optimization (pp. 84-93). (Proceedings of the 2008 CGO - Sixth International Symposium on Code Generation and Optimization). https://doi.org/10.1145/1356058.1356070