Abstract
Recently, there has been a growing interest in exploiting profile information in adaptive systems such as just-in-time compilers, dynamic optimizers and, binary translators. In this paper, we show that sophisticated software profiling schemes that provide highly accurate information in an offline setting are ill-suited for these dynamic code generation systems. We experimentally demonstrate that hot path predictions must be made early in order to control the rising cost of missed opportunity that result from the prediction delay. We also show that existing sophisticated path profiling schemes, if used in an online setting, offer no prediction advantages over simpler schemes that exhibit much lower runtime overheads.Based on these observation we developed a new low-overhead software profiling scheme for hot path prediction. Using an abstract metric we compare our scheme to path profile based prediction and show that our scheme achieves comparable prediction quality. In our second set of experiments we include runtime overhead and evaluate the performance of our scheme in a realistic application: Dynamo, a dynamic optimization system. The results show that our prediction scheme clearly outperforms path profile based prediction and thus confirm that less profiling as exhibited in our scheme will actually lead to more effective hot path prediction.
- 1 Ammons, G., Ball, T., and Larus, J.R. Exploiting hardware performance counters with flow and context sensitive profiling. In Proc. of the 1997 Conf. on Programming Language Design and Implementation, June 1997. Google ScholarDigital Library
- 2 Anderson, J.M., Bere, L.M., Dean, J., Ghemawat, S., Henzinger, M.R., Leung, S.A., Sites, R.L., Vandevoorde, M.T., Waldspurger, C.A., and Weihl, W.E. Continuous profiling: Where have all the cycles gone? In Proc. of the 16 th ACM Syrup. on Operating Systems Principles, St. Malo, France. October 1997. Google ScholarDigital Library
- 3 Bala, V., Duesterwald, E., and Banerjia, S. Transparent dynamic optimization: The design and implementation of Dynamo. Hewlett Packard Laboratories Technical Report HPL-1999-78. June 1999.Google Scholar
- 4 Bala, V., Duesterwald, E., and Banerjia, S. Dynamo: A transparent runtime optimization system. In Proc. of the 2000 Conf. on Programming Language Design and Implementation. Vancouver, B.C., June 2000. Google ScholarDigital Library
- 5 Ball, T. and Larus, J.R. Efficient path profiling. In Proc. of the 29 th Int. Symp. on Microarchitecture, Paris. 1996. Google ScholarDigital Library
- 6 Ball, T., Mataga, P. and Sagiv, M. Edge profiling versus path profiling: The showdown. In Proc. of the 25 th Symp. on Principles of Programming Languages, San Diego, CA, January 1998. Google ScholarDigital Library
- 7 Burke, M., Choi, J.-D., Fink, S., Grove, D., Hind, M., Sarkar, V., Serrano, M.J., Sreedhar, V.C., Srinivasa, H. The Jalapeno Dynamic Optimizing Compiler for Java. In Proc. of the 1999 ACM dava Grande Conference, San Francisco, CA. June 1999. Google ScholarDigital Library
- 8 Chang, P., Mahlke, S.A., and Hwu, W.M. Using profile information to assist classic code optimization. Software - Practice and Experience, Vol. 21, No. 12, December 1991. Google ScholarDigital Library
- 9 Calder, B. and Grunwald, D. Fast and accurate instruction fetch and branch prediction. In Proc. of the 21st Int. Syrup. on Computer Architecture. April 1994. Google ScholarDigital Library
- 10 Cmelik, R.F. and Keppel, D. Shade: a fast instruction set simulator for execution profiling. Technical Report UWCSE- 93-06-06, Dept. Comp. Science and Engineering, Univ. Washington. 1993.Google ScholarDigital Library
- 11 Ebeioglu, K., Altrnan E., Sathaye, S., and Gschwind, M. Execution-based scheduling for VLIW architectures. In Proc. of Europar'99, Lecture Notes in Computer Science 1685, Springer-Verlag 1999. Google ScholarDigital Library
- 12 McFarling, S., and Hennesy, J. Reducing the cost of branches. In Proc. of the 13 th lnt. Syrup. on Computer Architecture. 1986. Google ScholarDigital Library
- 13 Merten, C.M., Trick, A., George, C.N., Gyllenhaal, J.C., and Hwu, W.-M.W. A hardware-driven profiling scheme for identifying program hot spots to support runtime optimization. In Proc. of the 26 th Int. Syrup. on Computer Architecture. Atlanta, Georgia. 1999, Google ScholarDigital Library
- 14 Pan, S, So, K., and Rahmeh, J. Improving the accuracy of dynamic branch prediction using branch correlation. In Proc. of the 5th Int. Conf. on Architectural Support for Programming Languages and Operating Systems. 1992. Google ScholarDigital Library
- 15 Rotenberg, E., Bennett, S., and Smith, J.E. Trace cache: a low latency approach to high bandwidth instruction fetching. In Proc. of the 29 th lnt. Symp. on Microarchitecture, Paris. 1996. Google ScholarDigital Library
- 16 Sannella, M., Maloney, J., Freeman-Benson, B., and Borning, A. Multi-way versus one-way constraints in user interfaces: experiences with the DeltaBlue algorithm. Software - Practice and Experience 23, 5 (May). 529-566. 1993. Google ScholarDigital Library
- 17 Sathaye, S., Ledak, P., LeBlanc, J., Kosonocky, S., Gschwind, M., Fritts, J., Filan, Z., Bright, A., AppenzeUer, D., Airman, E., and Agricola, C. BOA: Targeting multigigahertz with binary translation. In Proc. of the 1999 Workshop on Binary Translation, Newport Beach, CA., October 1999.Google Scholar
- 18 Smith, M. Private communication, March 2000.Google Scholar
- 19 Yeh, T. and Patt, Y. A comparison of dynamic branch predictors that use two levels of branch history. In Proc. of the 20 th Int. Symp. on Computer Architecture. 1993. Google ScholarDigital Library
- 20 Young, C. and Smith, M. Static correlated branch prediction. ACM Transactions on Programming Languages and Systems, Vol. 21, No. 5, September 1999. Google ScholarDigital Library
- 21 Zhang, X. et al. System support for automatic profiling and optimization. In Proc. of the 16 th ACM Symposium on Operating Systems Principles, St. Malo, France. Oct. 1997. Google ScholarDigital Library
Index Terms
- Software profiling for hot path prediction: less is more
Recommendations
Software profiling for hot path prediction: less is more
Special Issue: Proceedings of the ninth international conference on Architectural support for programming languages and operating systems (ASPLOS '00)Recently, there has been a growing interest in exploiting profile information in adaptive systems such as just-in-time compilers, dynamic optimizers and, binary translators. In this paper, we show that sophisticated software profiling schemes that ...
Software profiling for hot path prediction: less is more
Recently, there has been a growing interest in exploiting profile information in adaptive systems such as just-in-time compilers, dynamic optimizers and, binary translators. In this paper, we show that sophisticated software profiling schemes that ...
Software profiling for hot path prediction: less is more
ASPLOS IX: Proceedings of the ninth international conference on Architectural support for programming languages and operating systemsRecently, there has been a growing interest in exploiting profile information in adaptive systems such as just-in-time compilers, dynamic optimizers and, binary translators. In this paper, we show that sophisticated software profiling schemes that ...
Comments