Дизайн GraphBLAS-подобного API с использованием возможностей функциональных языков программирования
DOI:
https://doi.org/10.32603/2071-2340-2026-1-105-114Ключевые слова:
анализ графов, разреженная линейная алгебра, GraphBLAS API, GPGPU, параллельное программирование, функциональное программирование, .NET, OpenCL, FSharpАннотация
Стандарт GraphBLAS API описывает примитивы и операции разреженной линейной алгебры для построения параллельных алгоритмов анализа графов. Использование GraphBLAS является перспективным подходом к высокопроизводительному анализу графов, но у него есть ряд недостатков, таких как сложный API, сложность реализации для GPGPU и проблема явного использования нулей. В данной работе мы показываем, что использование возможностей функционального программирования может помочь решить некоторые проблемы проектирования GraphBLAS-подобных API.
Библиографические ссылки
J. Kepner et al., "Mathematical foundations of the graphblas," in 2016 IEEE High Perform. Extreme Comput. Conf. (HPEC), Waltham, MA, USA, 2016, pp. 1-9; doi:10.1109/HPEC.2016.7761646
O. Selvitopi et al., "Distributed many-to-many protein sequence alignment using sparse matrices," in Proc. Int. Conf. High Perform. Comput., Netw., Storage Anal. (SC '20), Atlanta, GA, USA, 2020, pp. 1-14; doi:10.1109/SC41405.2020.000792020
J. Kepner et al., "Enabling massive deep neural networks with the graphblas," in 2017 IEEE High Perform. Extreme Comput. Conf. (HPEC), Waltham, MA, USA, 2017, pp. 1-10; doi:10.1109/HPEC.2017.8091098
T. A. Davis, "Algorithm 1000: Suitesparse: graphblas: Graph algorithms in the language of sparse linear algebra," ACM Trans. Math. Softw., vol. 45, no. 4, pp. 1-25, 2019; doi:10.1145/3322125
A. Buluc and J. R. Gilbert, "The combinatorial blas: Design, implementation, and applications," Int. J. High Perform. Comput. Appl., vol. 25, no. 4, pp. 496-509, 2011; doi:10.1177/1094342011403516
C. Yang, A. Buluc, and J. D. Owens, "Graphblast: A high-performance linear algebra-based graph framework on the gpu," ACM Trans. Math. Softw., vol. 48, no. 1, pp. 1-51, 2022; doi:10.1145/3466795
T. Henriksen et al., "Futhark: Purely functional gpu-programming with nested parallelism and in-place array updates," in Proc. 38th ACM SIGPLAN Conf. Program. Lang. Design Implement. (PLDI 2017), Barcelona, Spain, 2017, pp. 556-571; doi:10.1145/3062341.3062354
T. L. McDonell, M. M. Chakravarty, G. Keller, and B. Lippmeier, "Optimising purely functional gpu programs," SIGPLAN Not., vol. 48, no. 9, pp. 49-60, 2013; doi:10.1145/2544174.2500595
R. Leißa et al., "Anydsl: A partial evaluation framework for programming high-performance libraries," Proc. ACM Program. Lang., vol. 2, no. OOPSLA, 2018; doi:10.1145/3276489
Загрузки
Опубликован
Выпуск
Раздел
Лицензия
Copyright (c) 2026 Кирилл Анатольевич Гарбар, Игорь Антонович Ерин, Артём Александрович Черников, Дмитрий Викторович Панфилёнок, Семён Вячеславович Григорьев
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
Материал публикуется под лицензией:
