Дизайн GraphBLAS-подобного API с использованием возможностей функциональных языков программирования
Аннотация
Стандарт 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
Материал публикуется под лицензией:
