@inproceedings{02c445c4b5964315bd9f0bc50e7b48bf,
title = "Branch-on-random",
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.",
keywords = "Branch, Instrumentation, LFSR, Profiling, Pseudo-random, Sampling",
author = "Edward Lee and Craig Zilles",
year = "2008",
doi = "10.1145/1356058.1356070",
language = "English (US)",
isbn = "9781595939784",
series = "Proceedings of the 2008 CGO - Sixth International Symposium on Code Generation and Optimization",
pages = "84--93",
booktitle = "Proceedings of the 2008 CGO - Sixth International Symposium on Code Generation and Optimization",
}