{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,9,4]],"date-time":"2023-09-04T22:01:13Z","timestamp":1693864873411},"reference-count":23,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Archit. Code Optim."],"published-print":{"date-parts":[[2005,6]]},"abstract":"<jats:p>Java programs are increasing in popularity and prevalence on numerous platforms, including high-performance general-purpose processors. The success of Java technology largely depends on the efficiency in executing the portable Java bytecodes. However, the dynamic characteristics of the Java runtime system present unique performance challenges for several aspects of microarchitecture design. In this work, we focus on the effects of indirect branches on branch-target address prediction performance. Runtime bytecode translation, just-in-time (JIT) compilation, frequent calls to the native interface libraries, and dependence on virtual methods increase the frequency of polymorphic indirect branches. Therefore, accurate target address prediction for indirect branches is very important for Java code.This paper characterizes the indirect branch behavior in Java processing and proposes an adaptive branch-target buffer (BTB) design to enhance the predictability of the targets. Our characterization shows that a traditional BTB will frequently mispredict a few polymorphic indirect branches, significantly deteriorating predictor accuracy in Java processing. Therefore, we propose a rehashable branch-target buffer (R-BTB), which dynamically identifies polymorphic indirect branches and adapts branch-target storage to accommodate multiple targets for a branch.The R-BTB improves the target predictability of indirect branches without sacrificing overall target prediction accuracy. Simulations show that the R-BTB eliminates 61% of the indirect branch mispredictions suffered with a traditional BTB for Java programs running in interpreter mode (46% in JIT mode), which leads to a 57% decrease in overall target address misprediction rate (29% in JIT mode). With an equivalent number of entries, the R-BTB also outperforms the previously proposed target cache scheme for a majority of Java programs by adapting to a greater variety of indirect branch behaviors.<\/jats:p>","DOI":"10.1145\/1071604.1071605","type":"journal-article","created":{"date-parts":[[2005,8,1]],"date-time":"2005-08-01T17:31:42Z","timestamp":1122917502000},"page":"109-130","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["Adapting branch-target buffer to improve the target predictability of java code"],"prefix":"10.1145","volume":"2","author":[{"given":"Tao","family":"Li","sequence":"first","affiliation":[{"name":"University of Florida, Gainesville, Florida"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ravi","family":"Bhargava","sequence":"additional","affiliation":[{"name":"Advanced Micro Devices, Austin, Texas"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lizy Kurian","family":"John","sequence":"additional","affiliation":[{"name":"University of Texas at Austin, Austin, TX"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2005,6]]},"reference":[{"key":"e_1_2_2_1_1","volume-title":"Proceedings of 10th European Conference on Object Oriented Programming. 142--166","author":"Aigner G.","unstructured":"Aigner , G. and H\u00f6lzle , U . 1996. Eliminating virtual calls in C&plus;&plus; programs . In Proceedings of 10th European Conference on Object Oriented Programming. 142--166 .]] Aigner, G. and H\u00f6lzle, U. 1996. Eliminating virtual calls in C&plus;&plus; programs. In Proceedings of 10th European Conference on Object Oriented Programming. 142--166.]]"},{"key":"e_1_2_2_2_1","first-page":"323","article-title":"Quantifying behavioral differences between C and C&plus;&plus; programs","volume":"2","author":"Calder B.","year":"1994","unstructured":"Calder , B. , Grunwald , D. , and Zorn , B. 1994 a. Quantifying behavioral differences between C and C&plus;&plus; programs . J. Programming Languages. 2 , 4, 323 -- 351 .]] Calder, B., Grunwald, D., and Zorn, B. 1994a. Quantifying behavioral differences between C and C&plus;&plus; programs. J. Programming Languages. 2, 4, 323--351.]]","journal-title":"J. Programming Languages."},{"key":"e_1_2_2_3_1","volume-title":"Proceedings of the International Symposium on Principles of Programming Languages. 397--408","author":"Calder B.","unstructured":"Calder , B. and Grunwald , D . 1994b. Reducing indirect function call overhead in C&plus;&plus; programs , In Proceedings of the International Symposium on Principles of Programming Languages. 397--408 .]] 10.1145\/174675.177973 Calder, B. and Grunwald, D. 1994b. Reducing indirect function call overhead in C&plus;&plus; programs, In Proceedings of the International Symposium on Principles of Programming Languages. 397--408.]] 10.1145\/174675.177973"},{"key":"e_1_2_2_4_1","volume-title":"Proceedings of the 24th International Symposium on Computer Architecture. 274--283","author":"Chang P. Y.","unstructured":"Chang , P. Y. , Hao , E. , and Patt , Y. N . 1997. Target prediction for indirect jumps . In Proceedings of the 24th International Symposium on Computer Architecture. 274--283 .]] 10.1145\/264107.264209 Chang, P. Y., Hao, E., and Patt, Y. N. 1997. Target prediction for indirect jumps. In Proceedings of the 24th International Symposium on Computer Architecture. 274--283.]] 10.1145\/264107.264209"},{"key":"e_1_2_2_5_1","volume-title":"Proceedings of the 25th Annual International Symposium on Computer Architecture. 167--178","author":"Driesen K.","unstructured":"Driesen , K. and H\u00f6lzle , U . 1998a. Accurate indirect branch prediction . In Proceedings of the 25th Annual International Symposium on Computer Architecture. 167--178 .]] 10.1145\/279358.279380 Driesen, K. and H\u00f6lzle, U. 1998a. Accurate indirect branch prediction. In Proceedings of the 25th Annual International Symposium on Computer Architecture. 167--178.]] 10.1145\/279358.279380"},{"key":"e_1_2_2_6_1","volume-title":"Proceedings of the 31st Annual ACM\/IEEE International Symposium on Microarchitecture. 249--258","author":"Driesen K.","unstructured":"Driesen , K. and H\u00f6lzle , U . 1998b. The cascaded predictor: Economical and adaptive branch target prediction . In Proceedings of the 31st Annual ACM\/IEEE International Symposium on Microarchitecture. 249--258 .]] Driesen, K. and H\u00f6lzle, U. 1998b. The cascaded predictor: Economical and adaptive branch target prediction. In Proceedings of the 31st Annual ACM\/IEEE International Symposium on Microarchitecture. 249--258.]]"},{"key":"e_1_2_2_7_1","volume-title":"Proceedings of ACM Conference on Object-Oriented Programming, Systems, Languages, and Applications. 83--100","author":"Dean J.","unstructured":"Dean , J. , Defouw , G. , Grove , D. , Litvinov , V. , and Chambers , C . 1996. Vortex: An optimizing compiler for object-oriented languages . In Proceedings of ACM Conference on Object-Oriented Programming, Systems, Languages, and Applications. 83--100 .]] 10.1145\/236337.236344 Dean, J., Defouw, G., Grove, D., Litvinov, V., and Chambers, C. 1996. Vortex: An optimizing compiler for object-oriented languages. In Proceedings of ACM Conference on Object-Oriented Programming, Systems, Languages, and Applications. 83--100.]] 10.1145\/236337.236344"},{"key":"e_1_2_2_8_1","first-page":"403","article-title":"The behavior of efficient virtual machine interpreters on modern architectures","volume":"2001","author":"Ertl A. M.","year":"2001","unstructured":"Ertl , A. M. and Gregg , D. 2001 . The behavior of efficient virtual machine interpreters on modern architectures . In Proceedings of Euro-Par 2001. 403 -- 412 .]] Ertl, A. M. and Gregg, D. 2001. The behavior of efficient virtual machine interpreters on modern architectures. In Proceedings of Euro-Par 2001. 403--412.]]","journal-title":"Proceedings of Euro-Par"},{"key":"e_1_2_2_9_1","volume-title":"Proceedings of SIGPLAN'03 Conference on Programming Language Design and Implementation. 278--288","author":"Ertl A. M.","unstructured":"Ertl , A. M. and Gregg , D . 2003. Optimizing indirect branch prediction accuracy in virtual machine interpreters . In Proceedings of SIGPLAN'03 Conference on Programming Language Design and Implementation. 278--288 .]] 10.1145\/781131.781162 Ertl, A. M. and Gregg, D. 2003. Optimizing indirect branch prediction accuracy in virtual machine interpreters. In Proceedings of SIGPLAN'03 Conference on Programming Language Design and Implementation. 278--288.]] 10.1145\/781131.781162"},{"key":"e_1_2_2_10_1","volume-title":"Proceedings of COMPCON. 211--216","author":"Hsieh C. H. A.","unstructured":"Hsieh , C. H. A. , Conte , M. T. , Johnson , T. L. , Gyllenhaal , J. C. , and Hwu , W. W . 1997. A study of the cache and branch performance issues with running java on current hardware platforms . In Proceedings of COMPCON. 211--216 .]] Hsieh, C. H. A., Conte, M. T., Johnson, T. L., Gyllenhaal, J. C., and Hwu, W. W. 1997. A study of the cache and branch performance issues with running java on current hardware platforms. In Proceedings of COMPCON. 211--216.]]"},{"key":"e_1_2_2_11_1","volume-title":"Proceedings of the International Symposium on Microarchitecture","author":"Kalamatianos J.","year":"1998","unstructured":"Kalamatianos , J. and Kaeil , D. R. A. 2000. Predicting indirect branches via data compression . In Proceedings of the International Symposium on Microarchitecture , 1998 .]] Kalamatianos, J. and Kaeil, D. R. A. 2000. Predicting indirect branches via data compression. In Proceedings of the International Symposium on Microarchitecture, 1998.]]"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/MC.1984.1658927"},{"key":"e_1_2_2_13_1","volume-title":"Proceedings of ACM International Conference on Supercomputing. 22--33","author":"Li T.","unstructured":"Li , T. , John , L. K. , Vijaykrishnan , N. , Sivasubramaniam A. , Sabarinathan , J. , and Murthy , A . 2000. Using complete system simulation to characterize SPECjvm98 benchmarks . In Proceedings of ACM International Conference on Supercomputing. 22--33 .]] 10.1145\/335231.335234 Li, T., John, L. K., Vijaykrishnan, N., Sivasubramaniam A., Sabarinathan, J., and Murthy, A. 2000. Using complete system simulation to characterize SPECjvm98 benchmarks. In Proceedings of ACM International Conference on Supercomputing. 22--33.]] 10.1145\/335231.335234"},{"key":"e_1_2_2_14_1","volume-title":"Proceedings of the 2001 IEEE International Symposium on Performance Analysis of Systems and Software. 65--76","author":"Li T.","unstructured":"Li , T. and John , L. K . 2001. Understanding control-flow transfer and its predictability in java processing . In Proceedings of the 2001 IEEE International Symposium on Performance Analysis of Systems and Software. 65--76 .]] Li, T. and John, L. K. 2001. Understanding control-flow transfer and its predictability in java processing. In Proceedings of the 2001 IEEE International Symposium on Performance Analysis of Systems and Software. 65--76.]]"},{"key":"e_1_2_2_15_1","volume-title":"Proceedings of the 9th International High Performance Computing Conference. 597--608","author":"Li T.","unstructured":"Li , T. , Bhargava R. , and John , L. K . 2002. Rehashable BTB: An adaptive branch-target buffer to improve the target predictability of java code . In Proceedings of the 9th International High Performance Computing Conference. 597--608 .]] Li, T., Bhargava R., and John, L. K. 2002. Rehashable BTB: An adaptive branch-target buffer to improve the target predictability of java code. In Proceedings of the 9th International High Performance Computing Conference. 597--608.]]"},{"key":"e_1_2_2_16_1","unstructured":"Lindholm T. and Yellin F. 1999. The Java Virtual Machine Specification. 2nd Ed. Addison Wesley Reading MA.]]   Lindholm T. and Yellin F. 1999. The Java Virtual Machine Specification. 2nd Ed. Addison Wesley Reading MA.]]"},{"key":"e_1_2_2_17_1","volume-title":"Proceedings of the 6th International Conference on High Performance Computer Architecture. 387--398","author":"Radhakrishnan R.","unstructured":"Radhakrishnan , R. , Vijaykrishnan , N. , John , L. K. , and Sivasubramaniam , A . 2000. Architectural issue in java runtime systems . In Proceedings of the 6th International Conference on High Performance Computer Architecture. 387--398 .]] Radhakrishnan, R., Vijaykrishnan, N., John, L. K., and Sivasubramaniam, A. 2000. Architectural issue in java runtime systems. In Proceedings of the 6th International Conference on High Performance Computer Architecture. 387--398.]]"},{"key":"e_1_2_2_18_1","volume-title":"WRL Research Report","author":"Reinman G.","year":"2000","unstructured":"Reinman , G. and Jouppi , N. P . 2000. CACTI2.0: An integrated cache timing and power model . WRL Research Report , July , 2000 .]] Reinman, G. and Jouppi, N. P. 2000. CACTI2.0: An integrated cache timing and power model. WRL Research Report, July, 2000.]]"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/88.473612"},{"key":"e_1_2_2_20_1","unstructured":"SPEC JVM98 Benchmarks http:\/\/www.spec.org\/osg\/jvm98\/.]]  SPEC JVM98 Benchmarks http:\/\/www.spec.org\/osg\/jvm98\/.]]"},{"key":"e_1_2_2_21_1","volume-title":"Proceedings of the International Symposium on Microarchitecture. 77--86","author":"Vlaovic S.","unstructured":"Vlaovic , S. , Davidson E. S. , and Atyson , G. S . 2000. Improving BTB performance in the presence of DLLs . In Proceedings of the International Symposium on Microarchitecture. 77--86 .]] 10.1145\/360128.360138 Vlaovic, S., Davidson E. S., and Atyson, G. S. 2000. Improving BTB performance in the presence of DLLs. In Proceedings of the International Symposium on Microarchitecture. 77--86.]] 10.1145\/360128.360138"},{"key":"e_1_2_2_22_1","volume-title":"Proceedings of the 5th USENIX Conference of Object-Oriented Technologies and Systems. 217--228","author":"Vijaykrishnan N.","unstructured":"Vijaykrishnan , N. and Ranganathan , N . 1999. Tuning branch predictors to support virtual method invocation in java . In Proceedings of the 5th USENIX Conference of Object-Oriented Technologies and Systems. 217--228 .]] Vijaykrishnan, N. and Ranganathan, N. 1999. Tuning branch predictors to support virtual method invocation in java. In Proceedings of the 5th USENIX Conference of Object-Oriented Technologies and Systems. 217--228.]]"},{"key":"e_1_2_2_23_1","volume-title":"Proceedings of the 22nd Annual International Symposium on Computer Architecture. 257--266","author":"Yeh T.","unstructured":"Yeh , T. and Patt , Y . 1995. A comparison of dynamic branch predictors that use two levels of branch history . In Proceedings of the 22nd Annual International Symposium on Computer Architecture. 257--266 .]] 10.1145\/165123.165161 Yeh, T. and Patt, Y. 1995. A comparison of dynamic branch predictors that use two levels of branch history. In Proceedings of the 22nd Annual International Symposium on Computer Architecture. 257--266.]] 10.1145\/165123.165161"}],"container-title":["ACM Transactions on Architecture and Code Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1071604.1071605","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T13:17:17Z","timestamp":1672233437000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1071604.1071605"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,6]]},"references-count":23,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2005,6]]}},"alternative-id":["10.1145\/1071604.1071605"],"URL":"https:\/\/doi.org\/10.1145\/1071604.1071605","relation":{},"ISSN":["1544-3566","1544-3973"],"issn-type":[{"value":"1544-3566","type":"print"},{"value":"1544-3973","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,6]]},"assertion":[{"value":"2005-06-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}