Abstract
We present a dynamic dependence analyzer whose goal is to compute dependences from instrumented execution samples of loop nests. The resulting information serves as a prediction of the execution behavior during the remaining iterations and can be used to select and apply a speculatively optimizing and parallelizing polyhedral transformation of the target sequential loop nest. Thus, a parallel lock-free version can be generated which should not induce any rollback if the prediction is correct. The dependence analyzer computes distance vectors and linear functions interpolating the memory addresses accessed by each memory instruction, and the values of some scalars. Phases showing a changing memory behavior are detected thanks to a dynamic adjustment of the instrumentation frequency.
The dependence analyzer takes part of a whole framework dedicated to speculative parallelization of loop nests which has been implemented with extensions of the LLVM compiler and an x86-64 runtime system.
Chapter PDF
Similar content being viewed by others
Keywords
References
Arnold, M., Ryder, B.G.: A framework for reducing the cost of instrumented code. In: Proceedings of the ACM SIGPLAN 2001 Conference on Programming Language Design and Implementation, PLDI 2001, pp. 168–179. ACM, New York (2001)
Banerjee, U.: Loop Transformations for Restructuring Compilers - The Foundations. Kluwer Academic Publishers (1993)
Faxén, K.-F., Popov, K., Jansson, S., Albertsson, L.: Embla - data dependence profiling for parallel programming. In: Proceedings of the 2008 International Conference on Complex, Intelligent and Software Intensive Systems, CISIS 2008, pp. 780–785. IEEE Computer Society, Washington (2008)
Jimborean, A., Clauss, P., Pradelle, B., Mastrangelo, L., Loechner, V.: Adapting the polyhedral model as a framework for efficient speculative parallelization. In: PPoPP 2012 (2012)
Jimborean, A., Herrmann, M., Loechner, V., Clauss, P.: VMAD: A virtual machine for advanced dynamic analysis of programs. In: Proceedings of the IEEE International Symposium on Performance Analysis of Systems and Software, ISPASS 2011, pp. 125–126. IEEE Computer Society, Washington (2011)
Jimborean, A., Mastrangelo, L., Loechner, V., Clauss, P.: VMAD: An Advanced Dynamic Program Analysis and Instrumentation Framework. In: O’Boyle, M. (ed.) CC 2012. LNCS, vol. 7210, pp. 220–239. Springer, Heidelberg (2012)
Ketterlin, A., Clauss, P.: Profiling Data-Dependence to Assist Parallelization: Framework, Scope, and Optimization. In: The 45th Annual IEEE/ACM International Symposium on Microarchitecture, MICRO-45, Canada (2012)
Kim, H., Johnson, N.P., Lee, J.W., Mahlke, S.A., August, D.I.: Automatic speculative doall for clusters. In: CGO 2012. ACM (2012)
Kim, M., Kim, H., Luk, C.-K.: SD3: a scalable approach to dynamic data-dependence profiling. In: MICRO 1943. IEEE Computer Society Press (2010)
LLVM compiler infrastructure, http://llvm.org
Oancea, C.E., Mycroft, A.: Set-congruence dynamic analysis for thread-level speculation (TLS). In: Amaral, J.N. (ed.) LCPC 2008. LNCS, vol. 5335, pp. 156–171. Springer, Heidelberg (2008)
Polybenchs, http://www-rocq.inria.fr/pouchet/software/polybenchs
SPEC CPU2000 and SPEC CPU2006, http://www.spec.org
Tzenakis, G., Papatriantafyllou, A., Kesapides, J., Pratikakis, P., Vandierendonck, H., Nikolopoulos, D.S.: BDDT: block-level dynamic dependence analysisfor deterministic task-based parallelism. In: Proceedings of the 17th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 2012, pp. 301–302. ACM, New York (2012)
Vanka, R., Tuck, J.: Efficient and accurate data dependence profiling using software signatures. In: Proceedings of the Tenth International Symposium on Code Generation and Optimization, CGO 2012, NY, USA, pp. 186–195 (2012)
von Praun, C., Bordawekar, R., Cascaval, C.: Modeling optimistic concurrency using quantitative dependence analysis. In: Proceedings of the 13th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 2008, pp. 185–196. ACM, New York (2008)
Zhang, X., Navabi, A., Jagannathan, S.: Alchemist: A transparent dependence distance profiling infrastructure. In: CGO 2009. IEEE Computer Society Press (2009)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Jimborean, A., Clauss, P., Martinez, J.M., Sukumaran-Rajam, A. (2013). Online Dynamic Dependence Analysis for Speculative Polyhedral Parallelization. In: Wolf, F., Mohr, B., an Mey, D. (eds) Euro-Par 2013 Parallel Processing. Euro-Par 2013. Lecture Notes in Computer Science, vol 8097. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-40047-6_21
Download citation
DOI: https://doi.org/10.1007/978-3-642-40047-6_21
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-40046-9
Online ISBN: 978-3-642-40047-6
eBook Packages: Computer ScienceComputer Science (R0)