Otimizando Estruturas de Grafos em Memória Persistente para Arquiteturas NUMA
Resumo
Estruturas de grafos dinâmicos desempenham papel fundamental em aplicações que demandam processamento eficiente de grandes volumes de dados conectados entre si, como redes sociais e sistemas de recomendação. Este trabalho apresenta uma implementação de grafos dinâmicos em memória persistente para ambientes NUMA, explorando o particionamento round-robin e a afinidade explícita de threads para otimizar o processamento. Os experimentos foram conduzidos com dois conjuntos de dados reais de grande escala extraídos do repositório SNAP (Orkut e LiveJournal), permitindo avaliar o impacto das características topológicas dos grafos nas otimizações propostas. Os resultados experimentais demonstraram ganhos expressivos de desempenho, com speedup de até 2,3× em algoritmos como Connected Components(CC), quando comparado à versão original. Por outro lado, evidenciaram-se limitações da abordagem em grafos de baixa densidade e em algoritmos sensíveis à latência de acesso remoto, como BFS, ressaltando a importância de considerar a topologia do grafo na escolha de estratégias de particionamento.Referências
Baldassin, A., Barreto, J., Castro, D., and Romano, P. (2021). Persistent memory: A survey of programming support and implementations. ACM Comput. Surv., 54(7).
Brin, S. and Page, L. (1998). The anatomy of a large-scale hypertextual web search engine. Computer Networks, 30:107–117.
Chen, Y., Qiu, K., Chen, L., Jia, H., Zhang, Y., Xiao, L., and Liu, L. (2022). Smart scheduler: an adaptive nvm-aware thread scheduling approach on numa systems. CCF Transactions on High Performance Computing, 4(4):394 – 406.
Chen, Z., Che, W., Hu, D., He, X., Sun, J., and Chen, H. (2023). On the performance intricacies of persistent memory aware storage engines. IEEE Transactions on Knowledge and Data Engineering, 35(10):10365–10382.
Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. (2009). Introduction to Algorithms. MIT press, Cambridge, MA, USA, 3rd edition.
Dashti, M., Fedorova, A., Funston, J., Gaud, F., Lachaize, R., Lepers, B., Quema, V., and Roth, M. (2013). Traffic management: a holistic approach to memory placement on numa systems. In Proceedings of the 18th International Conference on Architectural Support for Programming Languages and Operating Systems, page 381–394.
Drozdek, A. (2012). Data Structures and Algorithms in C++. Cengage Learning.
Efron, B. and Tibshirani, R. J. (1994). An Introduction to the Bootstrap. Chapman & Hall/CRC.
Freeman, L. C. (1977). A set of measures of centrality based on betweenness. Sociometry, 40(1):35–41.
Hagberg, A. A., Schult, D. A., and Swart, P. J. (2008). Exploring network structure, dynamics, and function using NetworkX. In Proceedings of the 7th Python in Science Conference (SciPy2008), pages 11–15.
Han, J., Byun, H., Kwon, H., Park, S., and Kim, Y. (2021). Is data migration evil in the nvm file system? In 2021 IEEE International Conference on Autonomic Computing and Self-Organizing Systems Companion (ACSOS-C), pages 26–31.
Hennessy, J. L. and Patterson, D. A. (2017). Computer Architecture: A Quantitative Approach. Morgan Kaufmann, 6th edition.
Islam, A. A. R. and Dai, D. (2023). Dgap: Efficient dynamic graph analysis on persistent memory. In Proc. of the SC’23.
Jamil, S., Salam, A., Khan, A., Burgstaller, B., Park, S.-S., and Kim, Y. (2023). Scalable numa-aware persistent B+-tree for non-volatile memory devices. Cluster Computing, 26(5):2865 – 2881.
Jia, W., Jiang, D., and Xiong, J. (2022). Napfs: A high-performance numa-aware pm file system. In 2022 IEEE 40th International Conference on Computer Design (ICCD), pages 593–601.
Kelly, T. (2020). Programming workbench: Compressed sparse row format for representing graphs. ;login: The USENIX Magazine, 45(4).
Li, Y., Tan, S., Wang, Z., and Li, D. (2022). A numa-aware key-value store for hybrid memory architecture. In IEEE INFOCOM 2022 - IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS), pages 1–6.
Liu, G., Chen, L., and Chen, S. (2023). Zen+: a robust numa-aware oltp engine optimized for non-volatile main memory. VLDB Journal, 32(1):123 – 148.
Memarzia, P., Ray, S., and Bhavsar, V. C. (2019). Toward efficient in-memory data analytics on NUMA systems. CoRR, abs/1908.01860.
Michailidis, T., Swanson, S., and Zhao, J. (2022). PMShifter: enabling persistent memory fluidness in Linux. In Proceedings of the 13th ACM SIGOPS Asia-Pacific Workshop on Systems, page 1–8.
Salam, A., Jamil, S., Jung, S., Park, S.-S., and Kim, Y. (2022). Future-based persistent spatial data structure for nvm-based manycore machines. IEEE Access, 10:114711–114724.
Scargall, S. (2020). Programming Persistent Memory - A Comprehensive Guide for Developers. Apress, 1st edition.
Wang, R., He, S., Zong, W., Li, Y., and Xu, Y. (2022). Xpgraph: Xpline-friendly persistent memory graph stores for large-scale evolving graphs. In 2022 55th IEEE/ACM International Symposium on Microarchitecture (MICRO), pages 1308–1325.
West, D. B. (2001). Introduction to Graph Theory. Prentice Hall, 2nd edition.
Wheatman, B. and Xu, H. (2018). Packed compressed sparse row: A dynamic graph representation. In 2018 IEEE High Performance extreme Computing Conference (HPEC), pages 1–7.
Xia, F., Sun, K., Yu, S., Aziz, A., Wan, L., Pan, S., and Liu, H. (2021). Graph learning: A survey. IEEE Transactions on Artificial Intelligence, 2(2):109–127.
Zhu, G., Han, J., Lee, S., and Son, Y. (2021). An empirical evaluation of nvm-aware file systems on intel optane dc persistent memory modules. Electronics, 10(16).
Brin, S. and Page, L. (1998). The anatomy of a large-scale hypertextual web search engine. Computer Networks, 30:107–117.
Chen, Y., Qiu, K., Chen, L., Jia, H., Zhang, Y., Xiao, L., and Liu, L. (2022). Smart scheduler: an adaptive nvm-aware thread scheduling approach on numa systems. CCF Transactions on High Performance Computing, 4(4):394 – 406.
Chen, Z., Che, W., Hu, D., He, X., Sun, J., and Chen, H. (2023). On the performance intricacies of persistent memory aware storage engines. IEEE Transactions on Knowledge and Data Engineering, 35(10):10365–10382.
Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. (2009). Introduction to Algorithms. MIT press, Cambridge, MA, USA, 3rd edition.
Dashti, M., Fedorova, A., Funston, J., Gaud, F., Lachaize, R., Lepers, B., Quema, V., and Roth, M. (2013). Traffic management: a holistic approach to memory placement on numa systems. In Proceedings of the 18th International Conference on Architectural Support for Programming Languages and Operating Systems, page 381–394.
Drozdek, A. (2012). Data Structures and Algorithms in C++. Cengage Learning.
Efron, B. and Tibshirani, R. J. (1994). An Introduction to the Bootstrap. Chapman & Hall/CRC.
Freeman, L. C. (1977). A set of measures of centrality based on betweenness. Sociometry, 40(1):35–41.
Hagberg, A. A., Schult, D. A., and Swart, P. J. (2008). Exploring network structure, dynamics, and function using NetworkX. In Proceedings of the 7th Python in Science Conference (SciPy2008), pages 11–15.
Han, J., Byun, H., Kwon, H., Park, S., and Kim, Y. (2021). Is data migration evil in the nvm file system? In 2021 IEEE International Conference on Autonomic Computing and Self-Organizing Systems Companion (ACSOS-C), pages 26–31.
Hennessy, J. L. and Patterson, D. A. (2017). Computer Architecture: A Quantitative Approach. Morgan Kaufmann, 6th edition.
Islam, A. A. R. and Dai, D. (2023). Dgap: Efficient dynamic graph analysis on persistent memory. In Proc. of the SC’23.
Jamil, S., Salam, A., Khan, A., Burgstaller, B., Park, S.-S., and Kim, Y. (2023). Scalable numa-aware persistent B+-tree for non-volatile memory devices. Cluster Computing, 26(5):2865 – 2881.
Jia, W., Jiang, D., and Xiong, J. (2022). Napfs: A high-performance numa-aware pm file system. In 2022 IEEE 40th International Conference on Computer Design (ICCD), pages 593–601.
Kelly, T. (2020). Programming workbench: Compressed sparse row format for representing graphs. ;login: The USENIX Magazine, 45(4).
Li, Y., Tan, S., Wang, Z., and Li, D. (2022). A numa-aware key-value store for hybrid memory architecture. In IEEE INFOCOM 2022 - IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS), pages 1–6.
Liu, G., Chen, L., and Chen, S. (2023). Zen+: a robust numa-aware oltp engine optimized for non-volatile main memory. VLDB Journal, 32(1):123 – 148.
Memarzia, P., Ray, S., and Bhavsar, V. C. (2019). Toward efficient in-memory data analytics on NUMA systems. CoRR, abs/1908.01860.
Michailidis, T., Swanson, S., and Zhao, J. (2022). PMShifter: enabling persistent memory fluidness in Linux. In Proceedings of the 13th ACM SIGOPS Asia-Pacific Workshop on Systems, page 1–8.
Salam, A., Jamil, S., Jung, S., Park, S.-S., and Kim, Y. (2022). Future-based persistent spatial data structure for nvm-based manycore machines. IEEE Access, 10:114711–114724.
Scargall, S. (2020). Programming Persistent Memory - A Comprehensive Guide for Developers. Apress, 1st edition.
Wang, R., He, S., Zong, W., Li, Y., and Xu, Y. (2022). Xpgraph: Xpline-friendly persistent memory graph stores for large-scale evolving graphs. In 2022 55th IEEE/ACM International Symposium on Microarchitecture (MICRO), pages 1308–1325.
West, D. B. (2001). Introduction to Graph Theory. Prentice Hall, 2nd edition.
Wheatman, B. and Xu, H. (2018). Packed compressed sparse row: A dynamic graph representation. In 2018 IEEE High Performance extreme Computing Conference (HPEC), pages 1–7.
Xia, F., Sun, K., Yu, S., Aziz, A., Wan, L., Pan, S., and Liu, H. (2021). Graph learning: A survey. IEEE Transactions on Artificial Intelligence, 2(2):109–127.
Zhu, G., Han, J., Lee, S., and Son, Y. (2021). An empirical evaluation of nvm-aware file systems on intel optane dc persistent memory modules. Electronics, 10(16).
Publicado
28/10/2025
Como Citar
SPAGNOL, Lucas; HONORIO, Bruno; SOUZA, Otávio Scarparo; BALDASSIN, Alexandro; FRANCESQUINI, Emilio.
Otimizando Estruturas de Grafos em Memória Persistente para Arquiteturas NUMA. In: SIMPÓSIO EM SISTEMAS COMPUTACIONAIS DE ALTO DESEMPENHO (SSCAD), 26. , 2025, Bonito/MS.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2025
.
p. 410-421.
DOI: https://doi.org/10.5753/sscad.2025.16740.
