Estudo da Viabilidade de uma Interface para Memórias Transacionais em OpenMP
Abstract
Although modern programming language libraries and tools for parallel programming offer efficient hardware utilization, the support for data synchronization still reflects classic models based on critical sections. Transactional Memory (TM) is a high level concurrency control model that is usually not available in parallel programming tools. This paper presents an OpenMP extension for TM and analyses its support using two different implementations of TM. The results point to the viability of the proposed extension and show that design options used to manage the TM system directly influence the performance of programs.References
Ali-Reza Adl-Tabatabai, T. S. and Gottschlich, J. (2012). Draft Specication of Transactional Language Constructsfor C++. https://sites.google.com/site/tmforcplusplus/.
Baek, W., Minh, C. C., Trautmann, M., Kozyrakis, C., and Olukotun, K. (2007). The OpenTM transactional application programming interface. In Proc of the 16th International Conference on Parallel Architecture and Compilation Techniques, PACT '07, pages 376–387, Washington, DC. IEEE Computer Society.
Boyd-Wickizer, S., Clements, A. T., Mao, Y., Pesterev, A., Kaashoek, M. F., Morris, R. T., Zeldovich, N., et al. (2010). An analysis of Linux scalability to many cores. In USENIX Symposium on Operating Systems Design and Implementation, OSDI'10.
Dice, D., Shalev, O., and Shavit, N. (2006). Transactional Locking II. In Proc. of the 20th Int. Conf. on Distributed Computing, DISC'06, Berlin. Springer-Verlag.
Felber, P., Fetzer, C., and Riegel, T. (2008). Dynamic performance tuning of word-based software Transactional Memory. In Proceedings of the 13th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pages 237–246.
Free Software Foundation, Inc (2020). The GNU Transactional Memory Library. https://gcc.gnu.org/onlinedocs/libitm.pdf.
Guerraoui, R. and Kapaka, M. (2010). Principles of transactional memory. Synthesis Lectures on Distributed Computing Theory, 1(1):1–193.
Hansen, P. B., Dijkstra, E. W., and Hoare, C. A. R. (2002). The Origins of Concurrent Programming: From Semaphores to Remote Procedure Calls. Springer-Verlag, Berlin.
Harris, T., Larus, J., and Rajwar, R. (2010). Transactional Memory, 2nd edition. Synthesis Lectures on Computer Architecture, 5(1):1–263.
Jardim, A. D. (2020). Extensão para memórias transacionais nas modernas ferramentas para programação multithread. Proposta de Tese de Doutorado.
Milovanoviíc, M., Ferrer, R., Gajinov, V., Unsal, O. S., Cristal, A., Ayguadé, E., and Valero, M. (2007). Multithreaded software transactional memory and OpenMP. In Proc of the 2007 Workshop on Memory Performance: Dealing with Applications, Systems and Architecture, MEDEA '07, pages 81–88, New York. ACM.
Paznikov, A. A., Smirnov, V. A., and Omelnichenko, A. R. (2019). Towards efcient implementation of concurrent hash tables and search trees based on software transactional memory. In 2019 International Multi-Conference on Industrial Engineering and Modern Technologies (FarEastCon), pages 1–5.
Rigo, S., Centoducatte, P., and Baldassin, A. (2007). Memórias Transacionais: Uma nova alternativa para programaçao concorrente. Laboratório de Sistemas de Computação– Instituto de Computação–Unicamp.
Skillicorn, D. B. and Talia, D. (1998). Models and languages for parallel computation. ACM Comput. Surv., 30(2):123–169.
Süß, M. and Leopold, C. (2008). Common mistakes in Openmp and how to avoid them. In Mueller, M. S., Chapman, B. M., de Supinski, B. R., Malony, A. D., and Voss, M., editors, OpenMP Shared Memory Parallel Programming, Berlin. Springer.
Sutter, H. (2007). The Pillars of Concurrency. Dr. Dobbs.
Voss, M., Asenjo, R., and Reinders, J. (2019). SynchronizationSynchronization: Why and How to Avoid It, pages 137–178. Apress, Berkeley, CA.
Wilson, G. V. (1994). Assessing the usability of parallel programming systems: The Cowichan problems. In Decker, K. M. and Rehmann, R. M., editors, Programming Environments for Massively Parallel Distributed Systems, Basel. Birkhäuser Basel.
Wong, M., Ayguadé, E., Gottschlich, J., Luchangco, V., de Supinski, B. R., and Bihari, B. (2014). Towards transactional memory for OpenMP. In DeRose, L., de Supinski, B. R., Olivier, S. L., Chapman, B. M., and Müller, M. S., editors, Using and Improving OpenMP for Devices, Tasks, and More, pages 130–145, Cham. Springer International.
Baek, W., Minh, C. C., Trautmann, M., Kozyrakis, C., and Olukotun, K. (2007). The OpenTM transactional application programming interface. In Proc of the 16th International Conference on Parallel Architecture and Compilation Techniques, PACT '07, pages 376–387, Washington, DC. IEEE Computer Society.
Boyd-Wickizer, S., Clements, A. T., Mao, Y., Pesterev, A., Kaashoek, M. F., Morris, R. T., Zeldovich, N., et al. (2010). An analysis of Linux scalability to many cores. In USENIX Symposium on Operating Systems Design and Implementation, OSDI'10.
Dice, D., Shalev, O., and Shavit, N. (2006). Transactional Locking II. In Proc. of the 20th Int. Conf. on Distributed Computing, DISC'06, Berlin. Springer-Verlag.
Felber, P., Fetzer, C., and Riegel, T. (2008). Dynamic performance tuning of word-based software Transactional Memory. In Proceedings of the 13th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pages 237–246.
Free Software Foundation, Inc (2020). The GNU Transactional Memory Library. https://gcc.gnu.org/onlinedocs/libitm.pdf.
Guerraoui, R. and Kapaka, M. (2010). Principles of transactional memory. Synthesis Lectures on Distributed Computing Theory, 1(1):1–193.
Hansen, P. B., Dijkstra, E. W., and Hoare, C. A. R. (2002). The Origins of Concurrent Programming: From Semaphores to Remote Procedure Calls. Springer-Verlag, Berlin.
Harris, T., Larus, J., and Rajwar, R. (2010). Transactional Memory, 2nd edition. Synthesis Lectures on Computer Architecture, 5(1):1–263.
Jardim, A. D. (2020). Extensão para memórias transacionais nas modernas ferramentas para programação multithread. Proposta de Tese de Doutorado.
Milovanoviíc, M., Ferrer, R., Gajinov, V., Unsal, O. S., Cristal, A., Ayguadé, E., and Valero, M. (2007). Multithreaded software transactional memory and OpenMP. In Proc of the 2007 Workshop on Memory Performance: Dealing with Applications, Systems and Architecture, MEDEA '07, pages 81–88, New York. ACM.
Paznikov, A. A., Smirnov, V. A., and Omelnichenko, A. R. (2019). Towards efcient implementation of concurrent hash tables and search trees based on software transactional memory. In 2019 International Multi-Conference on Industrial Engineering and Modern Technologies (FarEastCon), pages 1–5.
Rigo, S., Centoducatte, P., and Baldassin, A. (2007). Memórias Transacionais: Uma nova alternativa para programaçao concorrente. Laboratório de Sistemas de Computação– Instituto de Computação–Unicamp.
Skillicorn, D. B. and Talia, D. (1998). Models and languages for parallel computation. ACM Comput. Surv., 30(2):123–169.
Süß, M. and Leopold, C. (2008). Common mistakes in Openmp and how to avoid them. In Mueller, M. S., Chapman, B. M., de Supinski, B. R., Malony, A. D., and Voss, M., editors, OpenMP Shared Memory Parallel Programming, Berlin. Springer.
Sutter, H. (2007). The Pillars of Concurrency. Dr. Dobbs.
Voss, M., Asenjo, R., and Reinders, J. (2019). SynchronizationSynchronization: Why and How to Avoid It, pages 137–178. Apress, Berkeley, CA.
Wilson, G. V. (1994). Assessing the usability of parallel programming systems: The Cowichan problems. In Decker, K. M. and Rehmann, R. M., editors, Programming Environments for Massively Parallel Distributed Systems, Basel. Birkhäuser Basel.
Wong, M., Ayguadé, E., Gottschlich, J., Luchangco, V., de Supinski, B. R., and Bihari, B. (2014). Towards transactional memory for OpenMP. In DeRose, L., de Supinski, B. R., Olivier, S. L., Chapman, B. M., and Müller, M. S., editors, Using and Improving OpenMP for Devices, Tasks, and More, pages 130–145, Cham. Springer International.
Published
2020-10-21
How to Cite
PEREIRA, Henry; DE OLIVEIRA, Kevin; JARDIM, André; DU BOIS, André; CAVALHEIRO, Gerson.
Estudo da Viabilidade de uma Interface para Memórias Transacionais em OpenMP. In: SYMPOSIUM ON HIGH PERFORMANCE COMPUTING SYSTEMS (SSCAD), 21. , 2020, Online.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2020
.
p. 37-48.
DOI: https://doi.org/10.5753/wscad.2020.14056.
