Abstract
This paper extends our early investigations in which we compared transactional memory to traditional OpenMP synchronization mechanisms [7, 8]. We study similar issues for algebraic multigrid (AMG) smoothers in hypre [16], a mature and widely used production-quality linear solver library. We compare the transactional version of the Gauss-Seidel AMG smoother to an omp critical version and the default hybrid Gauss-Seidel smoother, as well as the \(l_1\) variations of both Gauss-Seidel and Jacobi smoothers. Importantly, we present results for real-life 2-D and 3-D problems discretized by the finite element method that demonstrate the TM option can outperform the existing methods, often by orders of magnitude, in terms of the recently introduced performance measure of run time per quality.
The rights of this work are transferred to the extent transferable according to title 17 U.S.C. 105.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Abdelkhalek, A., Bilas, A.: Parallelization and performance of interactive multiplayer game servers. In: IPDPS (2004)
Ansari, M., Kotselidis, C., Jarvis, K., Lujan, M., Kirkham, C.: Watson, I.: Lee-TM: a nontrivial benchmark for transactional memory. In: ICA3PP (2008)
Bae, H., Cownie, J., Klemm, M., Terboven, C.: A user-guided locking API for the OpenMP* application program interface. In: DeRose, L., de Supinski, B.R., Olivier, S.L., Chapman, B.M., Müller, M.S. (eds.) IWOMP 2014. LNCS, vol. 8766, pp. 173–186. Springer, Heidelberg (2014)
Baek, W., Minh, C.C., Trautmann, M., Kozyrakis, C., Olukotun, K.: The OpenTM transactional application programming interface. In: PACT, pp. 376–387 (2007)
Baker, A.H., Falgout, R.D., Kolev, T.V., Yang, U.M.: Multigrid smoothers for ultraparallel computing. SIAM J. Sci. Comput. 33, 2864–2887 (2011)
Bihari, B.L.: Applicability of transactional memory to modern codes. In: ICNAAM, pp. 1764–1767. APS, Rodos, Greece (2010)
Bihari, Barna L., Bae, Hansang, Cownie, James, Klemm, Michael, Terboven, Christian, Diachin, Lori: On the algorithmic aspects of using openmp synchronization mechanisms II: user-guided speculative locks. In: Terboven, C., et al. (eds.) IWOMP 2015. LNCS, vol. 9342, pp. 133–148. Springer, Heidelberg (2015). doi:10.1007/978-3-319-24595-9_10
Bihari, B.L., Wong, M., de Supinski, B.R., Diachin, L.: On the algorithmic aspects of using OpenMP synchronization mechanisms: the effects of transactional memory. In: DeRose, L., de Supinski, B.R., Olivier, S.L., Chapman, B.M., Müller, M.S. (eds.) IWOMP 2014. LNCS, vol. 8766, pp. 115–129. Springer, Heidelberg (2014)
Bihari, B.L., Wong, M., Wang, A., de Supinski, B.R., Chen, W.: A case for including transactions in OpenMP II: hardware transactional memory. In: Chapman, B.M., Massaioli, F., Müller, M.S., Rorro, M. (eds.) IWOMP 2012. LNCS, vol. 7312, pp. 44–58. Springer, Heidelberg (2012)
De Sterck, H., Falgout, R.D., Nolting, J.W., Yang, U.M.: Distance-two interpolation for parallel algebraic multigrid. Numer. Linear Algebra Appl. 15, 115–139 (2008)
De Sterck, H., Yang, U.M., Heys, J.J.: Reducing complexity in parallel algebraic multigrid preconditioners. SIAM J. Matrix Anal. Appl. 27, 1019–1039 (2006)
Falgout, R.D., Jones, J.E., Yang, U.M.: Pursuing scalability for hypre’s conceptual interfaces. ACM Trans. Math. Softw. 31, 326–350 (2005)
Gajinov, V., Zyulkyarov, F., Unsal, O.S., Cristal, A., Ayguade, E., Harris, T., Valero, M.: QuakeTM: parallelizing a complex sequential application using transactional memory. In: ICS, pp. 126–135 (2009)
Transactional Memory Specification Drafting Group. Transactional language constructs for C++, May 2014. https://sites.google.com/site/tmfor+/
Guerraoui, R., Kapalka, M., Vitek, J.: STMBench7: a benchmark for software transactional memory. In: EuroSys, pp. 315–324 (2007)
hypre: High performance preconditioners. http://www.llnl.gov/CASC/hypre/
Kang, S., Bader, D.A.: An efficient transactional memory algorithm for computing minimum spanning forest of sparse graphs. In: PPoPP, pp. 15–24 (2009)
Kestor, G., Stipic, S., Unsal, O., Cristal, A., Valero, M.: RMS-TM: a transactional memory benchmark for recognition, mining and synthesis applications. In: Proceedings of 4th ACM SIGPLAN Workshop on Transactional Computing TRANSACT (2009)
Luchangco, V., Wong, M.: Transactional Memory Support for C++, February 2014. http://www.openstd.org/jtc1/sc22/wg21/docs/papers/2014/n3919.pdf
Lupei, D., Simion, B., Pinto, D., Misler, M., Burcea, M., Krick, W., Amza, C.C.: Transactional memory support for scalable and transparent parallelization of multiplayer games. In: EuroSys, pp. 41–54 (2010)
MFEM: Modular parallel finite element methods library. http://mfem.googlecode.com
Milovanović, M., Ferrer, R., Unsal, O.S., Cristal, A., Martorell, X., Ayguadé, E., Labarta, J., Valero, M.: Transactional memory and OpenMP. In: Chapman, B., Zheng, W., Gao, G.R., Sato, M., Ayguadé, E., Wang, D. (eds.) IWOMP 2007. LNCS, vol. 4935, pp. 37–53. Springer, Heidelberg (2008)
Minh, C.C., Chung, J., Kozyrakis, C., Olukotun, K.: STAMP: stanford transactional applications for multi-processing. In: IISWC, pp. 315–324 (2008)
Pankratius, V., Adl-Tabatabai, A.: A study of transactional memory vs. locks in practice. In: SPAA, pp. 43–52 (2011)
Rossbach, C.J., Hofmann, O.S., Witchel, W.: Is transactional programming actually easier?. In: PPoPP, pp. 47–56 (2010)
Schindewolf, M., Gyllenhaal, J., Bihari, B.L., Wang, A., Schulz, M., Karl, W.: What scientific applications can benefit from hardware transacional memory?. In: SC12 (2012)
Scott, M.L., Spear, M.F., Dalessandro, L., Marathe, V.J.: Delaunay triangulation with transactions and barriers. In: IISWC (2007)
Stüben, K.: An introduction to algebraic multigrid. In: Trottenberg, U., Oosterlee, C., Schüller, A. (eds.) Multigrid, pp. 413–528 (2001)
Wang, A., Gaudet, M., Wu, P., Ohmacht, M., Amaral, J.N., Barton, C., Silvera, R., MIchael, M.: Evaluation of blue gene/Q hardware support for transactional memories. In: PACT (2012)
Wong, M., Ayguadé, E., Gottschlich, J., Luchangco, V., de Supinski, B.R., Bihari, B., other members of the WG21 SG5 Transactional Memory Sub-Group: Towards Transactional Memory for OpenMP. In: DeRose, L., Supinski, B.R., Olivier, S.L., Chapman, B.M., Müller, M.S. (eds.) IWOMP 2014. LNCS, vol. 8766, pp. 130–145. Springer, Heidelberg (2014)
Wong, M., Bihari, B.L., de Supinski, B.R., Wu, P., Michael, M., Liu, Y., Chen, W.: A case for including transactions in OpenMP. In: Sato, M., Hanawa, T., Müller, M.S., Chapman, B.M., de Supinski, B.R. (eds.) IWOMP 2010. LNCS, vol. 6132, pp. 149–160. Springer, Heidelberg (2010)
Wong, M., Gottschlich, J.: SG5: Software Transactional Memory (TM) Status Report. http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3422.pdf, September 2012
Yoo, R., Hughes, C., Lai, K., Rajwar, R.: Performance evaluation of Intel transactional synhcornization extensions for high-performance computing. In: SC13 (2013)
Zyulkyarov, F., Gajinov, V., Unsal, O.S., Cristal, A., Ayguade, E., Harris, T., Valero, M., Quake, A.: Using transactional memory in an interactive multiplayer game server. In: PPoPP, pp. 25–34 (2009)
Acknowledgments
The authors thank the anonymous reviewers for their constructive comments. We are also grafetul to Lori Diachin of LLNL for the many discussions and ideas on this subject matter and for her continuing support of this research. Finally, we thank Tzanio Kolev of LLNL for his help in generating the relevant matrices using MFEM.
This article (LLNL-PROC-528852) has been authored in part by Lawrence Livermore National Security, LLC under Contract DE-AC52-07NA27344 with the U.S. Department of Energy. Accordingly, the United States Government retains and the publisher, by accepting the article for publication, acknowledges that the United States Government retains a non-exclusive, paid-up, irrevocable, world-wide license to publish or reproduce the published form of this article or allow others to do so, for United States Government purposes.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing Switzerland
About this paper
Cite this paper
Bihari, B.L., Yang, U.M., Wong, M., de Supinski, B.R. (2016). Transactional Memory for Algebraic Multigrid Smoothers. In: Maruyama, N., de Supinski, B., Wahib, M. (eds) OpenMP: Memory, Devices, and Tasks. IWOMP 2016. Lecture Notes in Computer Science(), vol 9903. Springer, Cham. https://doi.org/10.1007/978-3-319-45550-1_23
Download citation
DOI: https://doi.org/10.1007/978-3-319-45550-1_23
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-45549-5
Online ISBN: 978-3-319-45550-1
eBook Packages: Computer ScienceComputer Science (R0)