Casey, Kevin and Ertl, Anton and Gregg, David
(2007)
Optimizing Indirect Branch Prediction Accuracy
in Virtual Machine Interpreters.
ACM Transactions on Programming Languages and Systems (TOPLAS), 29 (6:37).
ISSN 0164-0925
Abstract
Interpreters designed for efficiency execute a huge number of indirect branches and can spend more
than half of the execution time in indirect branch mispredictions. Branch target buffers (BTBs) are
the most widely available form of indirect branch prediction; however, their prediction accuracy for
existing interpreters is only 2%–50%. In this paper we investigate two methods for improving the
prediction accuracy of BTBs for interpreters: replicating virtual machine (VM) instructions and
combining sequences of VM instructions into superinstructions. We investigate static (interpreter
build-time) and dynamic (interpreter run-time) variants of these techniques and compare them
and several combinations of these techniques. To show their generality, we have implemented
these optimizations in VMs for both Java and Forth. These techniques can eliminate nearly all of
the dispatch branch mispredictions, and have other benefits, resulting in speedups by a factor of
up to 4.55 over efficient threaded-code interpreters, and speedups by a factor of up to 1.34 over
techniques relying on dynamic superinstructions alone.
| Item Type: |
Article
|
| Keywords: |
Interpreter; branch target buffer; branch prediction; code
replication; superinstruction |
| Academic Unit: |
Faculty of Science and Engineering > Research Institutes > Hamilton Institute |
| Item ID: |
10188 |
| Identification Number: |
https://doi.org/10.1145/1286821.1286828 |
| Depositing User: |
Hamilton Editor
|
| Date Deposited: |
07 Nov 2018 18:17 |
| Journal or Publication Title: |
ACM Transactions on Programming Languages and Systems (TOPLAS) |
| Publisher: |
ACM |
| Refereed: |
Yes |
| URI: |
|
| Use Licence: |
This item is available under a Creative Commons Attribution Non Commercial Share Alike Licence (CC BY-NC-SA). Details of this licence are available
here |
Repository Staff Only(login required)
 |
Item control page |
Downloads per month over past year
Origin of downloads
Altmetric
Altmetric