MURAL - Maynooth University Research Archive Library



    Optimizing Indirect Branch Prediction Accuracy in Virtual Machine Interpreters


    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

    [img]
    Preview
    Download (374kB) | Preview


    Share your research

    Twitter Facebook LinkedIn GooglePlus Email more...



    Add this article to your Mendeley library


    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:

    Repository Staff Only(login required)

    View Item Item control page

    Downloads

    Downloads per month over past year