그래프BLAS

GraphBLAS 사양

GraphBLAS API의 로고
상태	방출된
초간출판	2017년 5월 29일 (2017-05-29)
최신 버전	2.0.0 2021년 11월 15일(2021-11-15)
도메인	그래프 알고리즘
면허증	Creative Commons Attribution(CC BY) 4.0
웹사이트	graphblas.org

GraphBLAS(/ˈræfˌblɑz/ (듣기))는 선형대수 언어로 그래프 알고리즘에 대한 표준 구성 블록을 정의하는 API 규격이다.^[1][2]GraphBLAS는 희소성 행렬을 그래프를 인접 행렬 또는 입사 행렬로 나타내기 위해 사용할 수 있다는 개념에 기초한다.GraphBLAS 규격은 그래프 연산(예: 그래프 통과 및 변환)을 다른 의미에 걸쳐 선형 대수적 방법(예: 행렬 곱하기)을 통해 효율적으로 구현할 수 있는 방법을 설명한다.^[3]

GraphBLAS의 개발과 그 다양한 구현은 산학관 및 정부 연구소의 대표자를 포함한 지속적인 지역사회 노력이다.^[4][5]

배경

그래프 알고리즘은 오래 전부터 그래프를 행렬로 나타낼 수 있다는 생각을 이용했으며, 그래프 연산은 희박한 행렬에서 선형 변환 및 기타 선형 대수 연산으로 수행할 수 있다.^{[6]: xxv–xxvi} 예를 들어, 매트릭스 벡터 곱셈을 사용하여 너비 우선 검색에서 한 단계를 수행할 수 있다.^{[6]: 32–33}

GraphBLAS 규격(및 이를 구현하는 다양한 라이브러리)은 이러한 선형 대수 연산 계산을 위한 데이터 구조와 함수를 제공한다.특히, GraphBLAS는 정점이 상대적으로 적은 이웃에 연결되었을 가능성이 높은 그래프에 잘 매핑되는 희박한 행렬 객체를 지정한다(즉, 정점 정도는 그래프의 정점 총 개수보다 현저히 작다).또한 규격은 다양한 수학적 맥락에서 연산을 수행하기 위해 서로 다른 의미들을 사용할 수 있도록 한다.

원래 GraphBLAS 표준의 명칭인 BLAS와 유사하게 그래프 분석에서 표준화의 필요성에 의해 동기부여된 ^[7]GraphBLAS 표준은 또한 머신러닝과 ^[8]생물정보학 연구자를 포함한 그래프 커뮤니티 밖의 사람들에게 관심을 갖기 시작했다.^[9]GraphBLAS 구현은 Redis와 같은 고성능 그래프 데이터베이스 애플리케이션에도 사용되었다.^{[10][11][12][13][14]}

사양

GraphBLAS 사양은 2013년부터 개발 중에 있으며,^[15] 2021년 11월 현재 버전 2.0.0에 도달했다.^[16]정식으로 C 프로그래밍 언어에 대한 명세서를 작성하는 한편, C++,^[17] 자바,^[18] 엔비디아 CUDA 등 GraphBLAS의 정신으로 구현을 전개하기 위해 다양한 프로그래밍 언어가 사용되어 왔다.^[19]

호환되는 구현 및 언어 바인딩

현재 GraphBLAS 사양의 두 가지 완전 호환 참조 구현이 있다.^[20][21]Python,^[22] MATLAB ^[23]및 Julia^[24][25] 프로그래밍 언어에 대한 준수 규격이 존재한다고 가정하는 바인딩.

선형대수기초

그래프의 광범위한 첫 번째 검색에서 한 단계 계산.매트릭스 벡터 곱셈은 주어진 소스 꼭지점(빨간색으로 표시)의 아웃바운드 인접(수직 1과 3, 파란색으로 표시)을 계산하는 데 사용할 수 있다.$행렬{\displaystyle }$ A ${\displaystyle$ A}은$($는) 왼쪽에 표시된 그래프의 인접 행렬이며, 아웃바운드 에지(4,1) 및 (4,3)는 녹색으로 표시된다는 점에 유의하십시오.

GraphBLAS의 수학적 기초는 선형 대수학 및 행렬과 그래프 사이의 이중성에 기초한다.^[26][27]

GraphBLAS의 각 그래프 연산은 다음과 같은 요소로 구성되는 세밀링에서 작동한다.

• 스칼라 추가 연산자${\displaystyle }$ ${\displaystyle \oplus }$)
• 스칼라 곱셈 연산자${\displaystyle }$ ${\displaystyle \otimes }$)
• 세트(또는 도메인)

0 요소(즉, 그래프에 에지가 없음을 나타내는 요소)도 재해석할 수 있다는 점에 유의하십시오.^{[26]: "VII. 0-Element: No Graph Edge"} 예를 들어 다음과 같은 알헤브라를 GraphBLAS에서 구현할 수 있다.

대수학	$\displaystyle \oplus }$	$\displaystyle \otimes }$	도메인	제로 원소
표준 산술	${\디스플레이 스타일 +}$	$\displaystyle \reason }$	${\displaystyle \mathb {R} }$	0
최대 플러스 대수	$\displaystyle \max }$	${\디스플레이 스타일 +}$	$\displaystyle \{-\inful \}\컵 \mathb {R}}$	$-\displaystyle -\fully }$
Min-plus 대수	$\displaystyle \min }$	${\디스플레이 스타일 +}$	$\displaystyle \{+\inful \}\컵 \mathb {R}}$	$♪ 디스플레이 스타일 +\flatty }$
최대-민 대수	$\displaystyle \max }$	$\displaystyle \min }$	$(\displaystyle [0,+\fty )}$	0
최소-최대 대수	$\displaystyle \min }$	$\displaystyle \max }$	${\displaystyle(-\fty,0])}$	0
갈루아 밭	XOR	AND	${\displaystyle \{0,1}$	0

위의 모든 예는 각각의 영역에서 다음의 두 가지 조건을 만족한다.

• 추가 ID,${\displaystyle }$⊕ ${\displaystyle 0}$ =${\displaystyle a}$ ${\displaystyle a\oplus 0=a}$
• 다중 소멸, ${\displaystyle \otimes }$ ${\displaystyle 0}$= 0 ${\displaystyle a\otimes$ 0$=0}$

예를 들어, 사용자는 다음과 같은 두 개의 정밀 부동소수점 번호의 도메인에 min-plus 대수학을 지정할 수 있다.GrB_Semiring_new(&min_plus_semiring, GrB_MIN_FP64, GrB_PLUS_FP64).

기능

GraphBLAS 규격은 일반적으로 구현에서 상당한 유연성을 허용하지만, 일부 기능 및 구현 세부사항은 명시적으로 설명된다.

• 행렬과 벡터를 포함한 graphBLAS 객체는 불투명한 데이터 구조다.^{[16]: 2.4 GraphBLAS Opaque Objects}
• 비차단 실행 모드. 특정 작업에 대해 게으름 또는 비동기 평가를 허용한다.^{[16]: 2.5.1 Execution modes}
• 마스크된 할당, $A{\displaystyle }$⟨ ${\displaystyle M}$ ${\displaystyle ⟩}$= B ${\displaystyle A\langle M\rangle =B}$로 표시되며$,$ 마스크 $매트릭스{\displaystyle }$ M ${\displaystyle$M}이$$(가) 0이 아닌 위치에서만$$ $매트릭스{\displaystyle }$ B ${\displaystystyle$ A$}$의 요소를 $매트릭스{\displaystyle }$ A ${\\displaystystystystystystytype$ A}에 할당한다.^{[16]: 3.5.4 Masks}

또한 GraphBLAS 규격은 라이브러리 구현이 스레드 안전하다고 규정한다.^{[16]: 2.5.2 Multi-threaded execution}

예시 코드

다음은 C 프로그래밍 언어의 너비 우선 검색에 대한 GraphBLAS 2.0 호환 사례.^{[16]: 283}

#include <stdlib.h> #include <stdio.h> #include <stdint.h> #include <stdbool.h> #include "그래프BLAS.h"  /* * 부울 n x 인접 행렬 A와 소스 꼭지점 s가 지정되면 BFS 횡단을 수행하십시오. * 그래프의 v[i]를 정점 i가 방문되는 수준으로 설정하십시오(v[s] == 1). * s에서 연결할 수 없는 경우 v[i] = 0에 저장된 요소가 없음 * 벡터 v는 입력 시 초기화되지 않아야 한다. */ GRB_Info BFS(GRB_벡터 *v, GrB_Matrix A, GrB_Index s) {   GrB_Index n;   GrB_Matrix_nrows(&n,A);                  // n = A 행 수    GrB_Vector_new(v,GrB_INT32,n);           // 벡터 <int32_t> v(n)    GRB_벡터 q;                            // 각 레벨에서 방문한 정점   GrB_Vector_new(&q, GRB_BOL, n);         // 벡터 q(n)   GrB_Vector_setElement(q, (바가지 긁다)진실의, s); // q[s] = 참, 다른 모든 곳에서 거짓    /* * BFS 통과 및 정점 레이블 지정 */   int32_t 수평을 이루다 = 0;                                       // 레벨 = BFS 통과 깊이   GrB_Index 엔벨스;   하다 {     ++수평을 이루다;                                               // 다음 레벨(1로 시작)     GRB_apply(*v, GrB_NULL, GrB_PLUS_INT32,               GrB_SECUT_INT32, q, 수평을 이루다, GrB_NULL);       // v[q] = 레벨     GrB_vxm(q, *v, GrB_NULL, GrB_LOR_LAND_SEMING_BOL,             q, A, GrB_DESC_RC);                            // q[!v] = q .&A; 모든 항목 찾기                                                            // 현재 q에서 방문하지 않은 후계자     GrB_Vector_nvals(&엔벨스, q);   } 하는 동안에 (엔벨스);                                         // q에 후계자가 없다면 우리는 끝이다.    GRB_free(&q);                                            // q 벡터는 더 이상 필요하지 않음    돌아오다 GrB_SUPTION; } 

참고 항목

• 기본 선형 대수 하위 프로그램(BLAS)
• 레몬 그래프 라이브러리

참조

외부 링크

• GraphBLAS 포럼