LTMS: Um escalonador NUMA-Aware para STM
Resumo
As transações em sistemas com Memória Transacional são, usualmente, realizadas de forma otimista, de forma a promover a exploração do paralelismo do hardware, mas aumentando a probabilidade de conflitos nos acessos. Neste trabalho é proposta uma estratégia de escalonamento baseada na migração de threads entre núcleos de processamento, apoiada pela observação da localidade de referência de acesso à memória dos threads em execução. Em experimentos realizados com o benchmark STAMP, para a maioria das aplicações, o escalonador proposto produziu menor taxa de aborts e menor tempo de execução em função do agrupamento de threads conforme a possibilidade de conflitos e o custo no acesso à memória.
Referências
Adl-Tabatabai, A.-R., Lewis, B. T., Menon, V., Murphy, B. R., Saha, B., and Shpeisman, T. (2006). Compiler and runtime support for efficient software transactional memory. SIGPLAN Not., 41(6):26-37.
Baek, W., Minh, C. C., Trautmann, M., Kozyrakis, C., and Olukotun, K. (2007). The OpenTM transactional application programming interface. In Proceedings of PACT '07, pages 376-387, Washington, DC, USA. IEEE Computer Society.
Baeza-Yates, R. A. and Ribeiro-Neto, B. (1999). Modern Information Retrieval. Addison-Wesley Longman Publishing Co., Inc., USA.
Bienia, C., Kumar, S., Singh, J. P., and Li, K. (2008). The PARSEC benchmark suite: Characterization and architectural implications. In Proceedings of PACT'08, pages 72-81.
Broquedis, F., Clet-Ortega, J., Moreaud, S., Furmento, N., Goglin, B., Mercier, G., Thibault, S., and Namyst, R. (2010). hwloc: A generic framework for managing hardware affinities in hpc applications. In 2010 18th Euromicro Conference on Parallel, Distributed and Network-based Processing, pages 180-186.
Cascaval, C., Blundell, C., Michael, M., Cain, H. W., Wu, P., Chiras, S., and Chatterjee, S. (2008). Software transactional memory: Why is it only a research toy? Queue, 6(5):46-58.
Di Sanzo, P. (2017). Analysis, classification and comparison of scheduling techniques for software transactional memories. IEEE Transactions on Parallel and Distributed Systems, 28(12):3356-3373.
Dolev, S., Hendler, D., and Suissa, A. (2008). CAR-STM: Scheduling-based collision avoidance and resolution for software transactional memory. In Proceedings of PODC '08, pages 125-134, New York, NY, USA. ACM.
DragojevicÌ, A., Guerraoui, R., Singh, A. V., and Singh, V. (2009). Preventing versus curing: Avoiding conflicts in transactional memories. In Proceedings of PODC '09, pages 7-16, New York, NY, USA. ACM.
Felber, P., Fetzer, C., and Riegel, T. (2008). Dynamic performance tuning of word-based software transactional memory. In Proceedings of PPoPP '08, pages 237-246, New York, NY, USA. ACM.
Guerraoui, R. and Romano, P., editors (2015). Transactional Memory. Foundations, Algorithms, Tools, and Applications, volume 8913 of LNCS. Springer.
Minh, C. C., Chung, J., Kozyrakis, C., and Olukotun, K. (2008). STAMP: Stanford transactional applications for multi-processing. In Proceedings of IISWC 2008.
Nicácio, D., Baldassin, A., and Araújo, G. (2012). Transaction scheduling using dynamic conflict avoidance. International Journal of Parallel Programming, 41(1):89-110.
Owens, S. (2010). Reasoning about the implementation of concurrency abstractions on x86-tso. In D'Hondt, T., editor, Proceedings of ECOOP 2010, pages 478-503.
Pasqualin, D. P., Diener, M., Du Bois, A. R., and Pilla, M. L. (2020). Online sharingaware thread mapping in software transactional memory. In Proceedings of SBAC-PAD'22.
Rito, H. and Cachopo, J. (2015). Adaptive transaction scheduling for mixed transactional workloads. Parallel Computing, 41:31-49.
Ruan, W., Liu, Y., and Spear, M. (2014). STAMP need not be considered harmful. Proceedings of TRANSACT 2014.
Yoo, R. M. and Lee, H.-H. S. (2008). Adaptive transaction scheduling for transactional memory systems. In Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures, pages 169-178. ACM.
Baek, W., Minh, C. C., Trautmann, M., Kozyrakis, C., and Olukotun, K. (2007). The OpenTM transactional application programming interface. In Proceedings of PACT '07, pages 376-387, Washington, DC, USA. IEEE Computer Society.
Baeza-Yates, R. A. and Ribeiro-Neto, B. (1999). Modern Information Retrieval. Addison-Wesley Longman Publishing Co., Inc., USA.
Bienia, C., Kumar, S., Singh, J. P., and Li, K. (2008). The PARSEC benchmark suite: Characterization and architectural implications. In Proceedings of PACT'08, pages 72-81.
Broquedis, F., Clet-Ortega, J., Moreaud, S., Furmento, N., Goglin, B., Mercier, G., Thibault, S., and Namyst, R. (2010). hwloc: A generic framework for managing hardware affinities in hpc applications. In 2010 18th Euromicro Conference on Parallel, Distributed and Network-based Processing, pages 180-186.
Cascaval, C., Blundell, C., Michael, M., Cain, H. W., Wu, P., Chiras, S., and Chatterjee, S. (2008). Software transactional memory: Why is it only a research toy? Queue, 6(5):46-58.
Di Sanzo, P. (2017). Analysis, classification and comparison of scheduling techniques for software transactional memories. IEEE Transactions on Parallel and Distributed Systems, 28(12):3356-3373.
Dolev, S., Hendler, D., and Suissa, A. (2008). CAR-STM: Scheduling-based collision avoidance and resolution for software transactional memory. In Proceedings of PODC '08, pages 125-134, New York, NY, USA. ACM.
DragojevicÌ, A., Guerraoui, R., Singh, A. V., and Singh, V. (2009). Preventing versus curing: Avoiding conflicts in transactional memories. In Proceedings of PODC '09, pages 7-16, New York, NY, USA. ACM.
Felber, P., Fetzer, C., and Riegel, T. (2008). Dynamic performance tuning of word-based software transactional memory. In Proceedings of PPoPP '08, pages 237-246, New York, NY, USA. ACM.
Guerraoui, R. and Romano, P., editors (2015). Transactional Memory. Foundations, Algorithms, Tools, and Applications, volume 8913 of LNCS. Springer.
Minh, C. C., Chung, J., Kozyrakis, C., and Olukotun, K. (2008). STAMP: Stanford transactional applications for multi-processing. In Proceedings of IISWC 2008.
Nicácio, D., Baldassin, A., and Araújo, G. (2012). Transaction scheduling using dynamic conflict avoidance. International Journal of Parallel Programming, 41(1):89-110.
Owens, S. (2010). Reasoning about the implementation of concurrency abstractions on x86-tso. In D'Hondt, T., editor, Proceedings of ECOOP 2010, pages 478-503.
Pasqualin, D. P., Diener, M., Du Bois, A. R., and Pilla, M. L. (2020). Online sharingaware thread mapping in software transactional memory. In Proceedings of SBAC-PAD'22.
Rito, H. and Cachopo, J. (2015). Adaptive transaction scheduling for mixed transactional workloads. Parallel Computing, 41:31-49.
Ruan, W., Liu, Y., and Spear, M. (2014). STAMP need not be considered harmful. Proceedings of TRANSACT 2014.
Yoo, R. M. and Lee, H.-H. S. (2008). Adaptive transaction scheduling for transactional memory systems. In Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures, pages 169-178. ACM.
Publicado
19/10/2022
Como Citar
COSTA, Michael Alexandre; PERLIN, Tiago; DU BOIS, André Rauber; CAVALHEIRO, Gerson.
LTMS: Um escalonador NUMA-Aware para STM. In: SIMPÓSIO EM SISTEMAS COMPUTACIONAIS DE ALTO DESEMPENHO (SSCAD), 23. , 2022, Florianópolis/SC.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2022
.
p. 37-48.
DOI: https://doi.org/10.5753/wscad.2022.226303.
