확장 가능한 GNN 학습을 위한
계산 가속

GNN[19]은 네트워크 임베딩[21], 추천 시스템[30] 등에서 입증된 효능으로 광범위하게 채택되었고, 그 결과 효율적 학습 방법론의 개발이 중심적이고 지속적인 연구 과제가 되었다. 미니배치 샘플링[4–7, 12, 15, 32, 33]이 대중적 패러다임으로 부상했으며, 그래프 구조 데이터의 고유한 계산 요구 때문에 PyG[8]·DGL[26] 같은 GPU 가속 특화 프레임워크가 필요하다 — 기존 딥러닝 시스템은 GNN 연산에 내재한 불규칙 데이터 접근 패턴을 처리할 수 없다.

지배적 학습 아키텍처는 역할을 분담한다 — CPU는 배치 샘플링과 특징 슬라이싱을, GPU는 핵심 모델 계산을 담당한다. 이 분리는 결정적인 파이프라인 의존성을 만든다. CPU의 느린 배치 준비는 GPU를 유휴 상태로 만들고[35], 이웃 폭발과 큰 특징 차원이 유발하는 막대한 전송량은 큰 통신 비용을 부과한다[10, 33]. 실증 연구들은 배치 준비와 CPU–GPU 데이터 전송을 현대 GNN 학습 시스템의 쌍둥이 병목으로 지목한다[10, 16, 20, 24, 27]. 파이프라인상 순차적 위치 탓에 이들은 하류 GPU 연산을 직접 조여 하드웨어 활용을 준최적으로 만든다. 최근 연구들이 대안적 디바이스 활용 패턴을 탐구하기 시작했으나 탐색된 설계 공간은 여전히 제약적이며, 특히 세밀한 연산자 스케줄링을 통한 파이프라인 병렬성의 잠재적 최적화를 간과한다.

연산자 수준에서는 희소 연산자(희소 텐서를 입력으로 받는 연산자)가 GNN에서 최적화되어야 할 중요한 부류다. SpMM(희소–조밀 행렬 곱)은 희소 행렬의 0과 관련된 곱셈–덧셈을 건너뛸 수 있고, SDDMM(샘플링된 조밀–조밀 행렬 곱)은 조밀 행렬 곱을 계산하되 결과의 일부만 샘플해 출력한다. GNN에서 희소 인접행렬[51, 67, 69]은 텐서에 다양한 희소 패턴을 가져온다.

다양한 희소 패턴에 대응하기 위해 여러 희소 포맷이 개발되었으나, 각각 서로 다른 패턴에서 장단점을 보이며 단일 포맷이 모든 희소 텐서에 적합할 수 없다는 것이 널리 인정된다. 게다가 하나의 희소 텐서가 영역별로 다른 희소 패턴을 가지면 최적 성능을 위해 포맷들을 결합해야 한다. 이에 하이브리드 포맷 — 희소 연산자를 고려해 텐서를 여러 희소 서브텐서로 분해하고 각각 최적 포맷을 선택한 뒤 그에 기반해 계산을 스케줄링[48, 55, 65, 66, 76, 78] — 이 시도되었다. 그러나 기존 연구는 대개 탐색 공간과 탐색 시간 사이에서 타협하며, 그 결과 탐색 공간이 일부 경우에 제한되어 달성 가능한 연산자 효율이 묶인다.

이 장은 먼저 §4.2에서 엔드투엔드 GNN 학습을 가속하는 데이터·하드웨어 인지 실행 계획 프레임워크 DAHA를, 이어 §4.3에서 유연한 희소 텐서 변환으로 너비를, 다중 수준 분해로 깊이를 확장해 더 높은 연산자 실행 효율을 달성하는 프레임워크 STile을 제안한다.

4.2.1동기

대부분의 GNN 프레임워크가 채택한 CPU-sample-GPU-train 실행은 낮은 학습 효율을 낳는다. DistDGLv2[36]·SALIENT[16] 같은 최근 프레임워크는 배치 준비·전송·계산을 겹치는 파이프라이닝을 채택하지만, 표준적인 CPU-샘플링/GPU-학습 모델을 고수하기 때문에 성능이 이 사슬에서 가장 느린 순차 연산에 근본적으로 묶인다. 다른 하드웨어 역할을 탐구한 시스템들 — CPU 효율의 ByteGNN[35], GPU 최적화의 GNNLab[31], Kim 등의 하이브리드 집계[18] — 도 한쪽 디바이스를 저활용하거나, CPU 병목에 부딪히거나, 성긴(coarse-grained) 스케줄링에 머문다. 결정적으로 대부분의 선행 연구는 배치 전체를 단일 덩어리로 스케줄링해 연산자 수준의 세밀한 파이프라인 병렬성을 놓친다.

여기서 결정적 연구 공백이 드러난다 — 세밀한 연산자 수준에서 디바이스 활용 패턴의 조합 공간을 소진적으로 탐색하지 않았다는 것이다. 이 간과는 전역 최적 실행 계획을 발견하는 근본 최적화 문제를 풀 기회를 놓친다. DAHA는 효율 최적화의 탐색 공간을 확장해 이 공백을 메운다 — 배치 내 각 미세 연산이 가능한 어떤 디바이스에도 동적으로 배정될 수 있는 완전 하이브리드 CPU–GPU 패러다임을 가능하게 하고, 입력 데이터와 가용 하드웨어에 조건화된 최적 실행 계획을 알고리즘적으로 발견한다[29].

4.2.2데이터·하드웨어 인지 비용 모델

DAHA는 CPU/GPU에서의 신경 계산 시간과 양자 간 데이터 전송 시간을 함께 예측하는 비용 모델을 사용한다. 모델은 두 핵심 연산 — 조밀 행렬 곱(mm)과 희소–조밀 행렬 곱(spmm) — 에 초점을 둔다. GNN 레이어를 메시지 흐름 그래프(MFG)로 표현하면 핵심 요인은 각 MFG_i의 고유 노드 수 n_i와 간선 수 m_i다. 계산 비용은 이 변수들에 대한 3차 회귀로 모델링되며, 회귀 파라미터 {β_j}가 모델 아키텍처(은닉 차원 등)와 하드웨어 성능을 함께 인코딩한다.

MFG 단위 비용 모델은 배치 수준으로 자연스럽게 일반화된다 — 배치 B_j의 비용은 그 안의 MFG 비용들의 합(Eq 4.2)이다. 통신 시간은 고정 초기화 비용과 가변 데이터 의존 비용의 2성분으로 정식화한다. 실증 분석(Fig 4.2)은 첫 CPU–GPU 전송이 후속 전송보다 실질적으로 큰 지연을 겪음을 드러내며, 이는 통신 설정에 내재한 상당한 고정 오버헤드를 시사한다. 따라서 (1) 하드웨어 환경이 결정하고 통제된 전송 실험으로 측정되며 전체 N개 학습 배치에 상각되는 고정 비용 α와, (2) 계산 비용과 유사하게 모델링되는 가변 비용으로 분해한다 — 후자는 조밀 특징 행렬 전송(n_j, m_j, f_n, f_m)과 희소 인접행렬 전송(n_j, m_j)을 함께 설명한다.

계산 모델과 통신 모델이 함께, 이기종 디바이스 위에서 임의 입력 데이터에 대한 임의 미세 연산 시퀀스의 비용을 추정할 수 있게 한다. 연산별·디바이스별 회귀 파라미터를 학습함으로써, 배치 특성에 기반해 학습 단계의 파이프라인 병렬성을 최적화하는 데 필요한 예측적 기반이 마련된다.

4.2.3하이브리드 CPU–GPU 최적화

핵심 스케줄링 기준은 GPU의 기대 성능 이득이 필요한 데이터 이동을 보상한다면 GPU를 투입한다는 것이다. 이 기회를 활용하기 위해 DAHA는 세 가지 주요 하이브리드 최적화를 도입한다.

① 배치 준비와 모델 학습의 그룹 기반 파이프라이닝

전통적 파이프라인은 단일 배치 스트림 안에서 배치 준비(CPU 샘플링)와 신경 계산(GPU 학습)을 교차시킨다. 반면 DAHA의 그룹 기반 교대(in-turn) 파이프라이닝은 두 단계를 분리하고, 동질적 작업을 묶음으로써 데이터·디바이스 지역성을 높여 메모리 접근과 커널 실행 오버헤드를 배치들에 상각한다 — 생산의 규모의 경제에 유비되는 원리로 배치당 평균 비용이 감소한다. 다만 과도한 그룹화는 스케줄링 복잡도를 높이고 디바이스 메모리·계산 용량을 압박해 결국 단위 비용을 올린다 — 규모의 비경제다. DAHA는 이 상반된 효과를 동적으로 균형시켜 처리량을 최적화한다.

이기종 하드웨어를 준비·학습 양쪽에 효과적으로 쓰려면 샘플링 시간과 MFG 통계의 정확한 예측이 필요하다. 그러나 샘플링 알고리즘의 확률적 성질, 겹치는 이웃의 복잡한 위상 구조, 셔플링이 유발하는 배치 구성의 불확실성 탓에 정확하고 효율적인 추정은 자명하지 않다. DAHA는 이를 적응적 셔플링과 점진적 스케줄링으로 극복한다.

② 배치 내 실행 계획 그래프(EPG) 재작성 규칙

파이프라인의 분리 설계로 배치 통계 전체를 사전에 확보할 수 있어, DAHA는 비용 모델(Eq 4.1–4.3)로 매 에폭 두 단위(배치 내·배치 간)의 정밀한 실행 계획을 수립한다. 기존 접근이 CPU를 그래프 연산에, GPU를 신경 계산에 묶는 경직된 하드웨어 이분법을 강요하는 것과 달리, DAHA는 양쪽 모두를 임의 연산 수행이 가능한 범용 프로세서로 취급한다. 이 관점은 GNN 학습을 그 핵심 선형대수 성분들로 재구성한다 — 전형적 순전파는 Z^l+1 = A H^lW^l, H^l+1 = σ(Z^l+1) (Eq 4.4)로 표현되며, A는 희소 인접행렬, H^l는 조밀 노드 임베딩, W^l는 조밀 가중치 행렬이다.

스케줄링을 추론하기 위해 이 계산을 실행 계획 그래프(EPG) — 노드가 미세 연산(데이터 전송, spmm, mm)이고 간선이 데이터 의존을 나타내는 방향 비순환 그래프 — 로 추상화한다.

EPG 재작성 모듈 HybridPU는 병렬성을 높이는 하이브리드 CPU–GPU 실행 계획을 생성한다. 핵심 규칙인 사전 변환(pre-transformation)은 조밀 곱 HW를 CPU로 옮겨 데이터 전송과 겹치게 하고 결과만 전송해 통신량을 줄인다 — 추론과 순전파에 매우 효과적이다. 대안인 사전 집계(pre-aggregation) 규칙은 희소 집계 AH를 CPU에서 수행한다 — 단일 배치에는 보통 더 느리지만, 다중 배치 파이프라인에서 유휴 CPU 자원을 더 잘 활용할 수 있다. DAHA는 비용 모델과 배치 통계로 주어진 맥락에 가장 유익한 규칙을 자동 선택하며, 이 최적화는 풀그래프 학습에도 적용 가능하다.

③ 배치 간 스케줄링 최적화

배치 간 스케줄링 문제는 PCIe 대역폭을 공유하는 CPU·GPU 워커에 분산된, 의존 작업들의 DAG인 다수 배치의 연산들을 연산별 비용 추정치를 이용해 스케줄링하여 전체 완료시간을 최소화하는 것이다. 이 정식화는 배치 내 EPG 재작성을 포섭한다 — 의존성을 위배하지 않는 한 연산 순서를 바꿀 수 있어 스케줄러가 배치 내 최적화를 직접 계승한다. 준비된 연산을 가용 GPU에 동적 디스패치해 GPU 유휴를 더 줄이고, 유계 신선도(bounded staleness)로 파이프라인 기회를 늘린다.

이 문제는 NP-hard인 유연 잡숍 문제(FJSP)의 변형이다[2]. FJSP는 가장 어려운 조합 문제 중 하나로 악명 높고 기존 근사법은 대개 강한 성능 한계를 갖지 못하며[3, 11], 고려해야 할 배치 내 실행 계획의 방대한 공간이 난도를 더한다. DAHA는 기댓값 최대화(EM)와 그룹화 원리에서 착안한 휴리스틱 이중 수준(bi-level) 최적화로 대응한다[9] — 유한한 하드웨어 자원과 작업 전환 오버헤드 탓에 긴밀히 교차 실행 가능한 배치 수가 제한적이라는 통찰에서, 배치를 가용 워커 수로 결정되는 크기의 그룹으로 분할해 탐색 공간을 크게 줄인다.

하위 수준은 주어진 그룹화 𝒢 = {𝒢_i}에서 배치 내 전략의 유효한 EPG 재작성 규칙을 활용해 각 그룹의 실행 계획을 최적화한다. 상위 수준은 각 그룹 최적 계획의 파이프라인 효율을 평가하고, 비효율적 그룹의 배치를 재그룹화해 그룹화 자체를 정제한다 — 새 그룹은 하위 수준으로 되돌려 재최적화된다. 그룹화 정제와 그룹 내 최적화 사이의 이 반복적·피드백 주도 과정이 EM 알고리즘을 닮는다.

복잡도. 상위 수준의 반복당 복잡도는 정렬과 효율적 이웃 탐색을 포함하는 그룹화 갱신이 지배해 O(n log n)이다. 하위 수준은 그룹 크기 β가 가용 워커 수로 유계이므로 O(β! · n)에 묶인다. 전형적 값 β < 10, n < 100에서 총 반복당 복잡도 O(n log n + β! · n)은 계산적으로 관리 가능하다.

4.2.4실험

설정. 두 하드웨어 구성에서 수행한다 — 기본 머신 M1(Intel i9-12900KF, DDR5 32 GB, RTX 3080 Ti 12 GB, PyTorch 1.12 · DGL 0.9 · CUDA 11.6)과, 하드웨어 적응성 평가용 M2(Intel Xeon Gold 6240, RTX 2080 Ti, CUDA 10.1)다. 모델은 세 가지 널리 쓰이는 메시지 패싱 아키텍처 — 풀그래프로 학습하는 GCN[19], 노드 단위 미니배치 샘플링의 GraphSAGE[12], 서브그래프 수준 샘플링의 GraphSAINT[33] — 이며 모두 100 에폭 학습한다(미니배치 배치 크기 8192, GraphSAINT 노드 샘플러 예산 16384). 베이스라인은 PyTorch[22], DGL[26](고전적 CPU 샘플링 + GPU 학습), DGL+(순수 GPU 변형), ByteGNN[35](CPU 전용 설계이므로 공정성을 위해 GPU에서 DGL+와 짝지음), SALIENT[16]다. 모든 베이스라인에서 일관성을 위해 DGL 샘플러를 사용한다.

전체 성능

분해 분석 (Breakdown)

성능 이득의 출처를 규명하기 위해 3대 구성요소를 분리한 네 변형을 평가한다 — "intra"(DGL CPU 샘플러 + 배치 내 최적화), "inter"(DGL CPU 샘플러 + 배치 내·간 최적화), "H+intra"(그룹 기반 교대 파이프라이닝 + 배치 내 최적화), "H+inter"(파이프라이닝 + 배치 내·간 최적화, DAHA 기본값). Table 4.3과 Fig 4.7의 결과는 세 가지를 보여준다 — (1) 배치 내 EPG 재작성이 DGL 대비 학습을 가속하고(intra > DGL), (2) 배치 간 스케줄링이 배치 내 최적화를 개선하며(inter > intra), (3) 그룹 기반 교대 파이프라이닝이 효율을 한층 높인다(H+intra > intra, H+inter > inter).

비용 모델의 효과

비용 모델의 효율과 정확도를 검증한다(Table 4.4–4.5). Pubmed 서브그래프 10개로 적합된 모델이 데이터 전송을 포함해 데이터셋·디바이스 전반의 연산 비용을 정확히 예측한다. 특히 mm보다 spmm에서 GPU 가속 폭이 더 크다는 사실을 올바르게 포착해 사전 변환 전략의 타당성을 뒷받침한다. 이 머신당 일회성 캘리브레이션은 빠르고(데이터 수집 M1 0.0205 s / M2 0.2793 s, 회귀 M1 37.86 s / M2 64.21 s), 런타임 오버헤드가 무시할 만하며(100회 예측당 0.005 s) 일반화도 양호해 DAHA의 데이터·하드웨어 인지성을 입증한다.

4.3.1동기 — 포맷의 트레이드오프와 탐색 공간의 한계

기존 희소 포맷들은 서로 다른 희소 패턴에서 상반된 장단점을 보인다.

SpMM에서는 각 GPU 스레드가 출력의 한 행을 계산하게 하는 것이 일반적인데, CSR의 압축 후 불규칙 행 길이는 스레드 간 워크로드 불균형을 일으켜 연산자 효율을 훼손한다. ELL은 각 행에 0을 패딩해 정규 행렬을 반환함으로써 CSR의 ptr 배열을 제거하고 유효 열 인덱스 획득 과정을 단순화하며, 스레드의 제어 흐름 분기를 없애고 열 우선 저장에서 메모리 병합(coalescing)을 가능하게 한다. BSR은 비영 원소 대신 블록의 열 인덱스를 저장해 희소 구조 정보의 메모리 사용을 줄이고 벡터화·하드웨어 인트린식[46]의 기회를 제공한다 — SpMM에서 스레드 블록 하나가 출력 행 집합을 계산하게 해 강력한 GPU Tensor Core에서 실행할 수 있다. 다만 패딩이 가져오는 추가 계산 부담은 ELL·BSR 모두에게 심각한 문제일 수 있다.

두 갈래 분해 방법과 그 한계

다양한 희소 패턴 대응을 위해 사람들은 하이브리드 포맷을 시도한다 — 분해된 서브텐서가 교집합을 가질 수 있는 집합 커버 기반 분해[78]와, 교집합이 없는 분할 기반 분해[48, 55, 65, 66, 76]다. 아래 예시들은 블록 형상 1×1, 2×2, 4×4의 비용을 각각 2, 4, 15로 가정한다(하위 작업 1개당 1개 블록, 단일 계산 유닛).

집합 커버 기반 분해는 원 텐서의 모든 비영 원소가 덮이도록 최적의 블록 컬렉션을 찾는다. 이 부류의 기존 연구[78]는 블록 포맷만 고려해 블록 전체(0과 비영 모두)를 메모리에 저장하며, 국소 희소 패턴에 대한 다른 포맷이나 행렬 행·열 재정렬 같은 변환을 수행하지 않아 분해 해의 탐색 공간이 제한된다. 분할 기반 분해는 국소 희소 패턴에 맞는 포맷을 찾을 수 있도록 행렬을 여러 부분으로 분할하며, 패턴을 뚜렷하게 하려고 행당 비영 수로 행을 재정렬하는 등의 변환을 적용한다[48, 55, 76]. 그러나 서브행렬 안에 선택된 포맷에 맞지 않는 비영 원소가 있을 수 있어 — 그런 원소를 별도 포맷으로 저장하는 편이 낫다 — 탐색 공간이 역시 제한된다.

따라서 두 가지 주요 도전이 남는다 — (1) 너비와 깊이가 확장된 큰 탐색 공간을 어떻게 구성하는가, (2) 그 큰 공간에서 어떻게 효율적으로 탐색해 좋은 하이브리드 포맷을 찾는가.

형식적 정의와 문제의 난도

4.3.2자동 하이브리드 희소 포맷 탐색 프레임워크

STile은 MSFD 문제를 다음 흐름으로 해결한다 — 희소 연산자 O와 입력 텐서가 주어지면 (1) 가능한 희소 타일과 작업 분할 방식의 탐색 공간을 설계해 하위 작업의 탐색 공간을 결정하고, (2) 비용 모델로 하위 작업의 비용을 추정하며, (3) 이에 기반해 철회형 그리디(greedy-with-withdraw) 알고리즘으로 O의 작업 분할을 얻는다.

탐색 공간 — 6개 변환 프리미티브와 3개 기본 포맷

희소 타일에는 세 기본 포맷을 고려한다 — "Squeeze"를 적용하지 않아 0이 유지된 타일에는 블록 포맷, "flatten"을 사용한 타일(이때 squeeze도 필수이므로 비영 원소가 연속 저장됨)에는 1D 포맷, 그 외에는 항상 "Squeeze" 후 "Zero padding"을 적용해 ELL 포맷을 쓴다. 블록 포맷 타일의 계산은 GPU Tensor Core에서 실행하므로 서브텐서가 wmma 같은 하드웨어 인트린식과 정합하는 특정 형상 — (16, 16), (8, 16) 등 — 이어야 하고, 그 밖의 포맷은 CUDA Core에서 실행한다. ELL 포맷 타일에는 유지 원소(비영 + 0) 총수에 대한 제약[76]이 있어 이를 만족하는 타일만 공간에 허용한다. 작업 분할 시에는 희소 연산자 계산의 각 조밀 루프(어떤 점도 건너뛰지 않는 루프)를 파라미터로 통제되는 크기로 균등 분할한다. 분할된 조밀 루프와 후보 희소 타일이 함께 후보 하위 작업을 결정한다 — 예컨대 SpMM의 조밀 루프 J가 길이 64이고 두 부분으로 분할되면, 하위 작업 공간은 {E₁, …, E_m} × {J₁, J₂}에서 나온다.

비용 모델 — 루프라인과 원자적 연산 보정

세 포맷의 하위 작업 비용을 각기 다르게 추정한다. 블록 포맷 하위 작업은 반복 공간에서 어떤 점도 건너뛰지 않으므로 반복 공간 형상이 같으면 비용도 같다 — 탐색 공간에 포함된 모든 형상을 열거해 사전 측정한 비용 표(cost table)를 쓴다. ELL·1D 포맷 하위 작업은 다음으로 추정한다.

g(x)는 결과를 GPU 전역 메모리에 되쓸 때 원자적 연산(atomicAdd() 등)을 쓰지 않고 x를 마치는 지연이며, R(x)는 원자적 연산이 없을 때의 루프라인 모델[74] 결과다 — AI는 x의 산술 강도(FLOPs / 총 데이터 이동량 Bytes), PEAK는 GPU 최대 성능(FLOP/s) 대 최대 대역폭(Byte/s)의 비다. 서로 다른 GPU 스레드가 같은 주소의 값을 함께 계산할 때 원자적 연산이 필요한데(예: A를 1×2 블록으로 분할해 A_1,1은 블록 포맷, A_1,2는 ELL 포맷으로 저장하면 두 스레드 집합이 모두 C에 쓴다), 추가 메모리 연산과 충돌 연산의 직렬화 탓에 여분 오버헤드가 발생한다. 원자적 연산이 없으면 Atomic(x) = 1이며(1D 포맷은 SDDMM에 주로 쓰이고 비영 출력 점이 독립·병렬 계산되므로 통상 1), 있으면 Atomic(x) = c·R_atomic(x)/R(x) + d다. 상수 a, b, c, d는 사전 수집한 측정 결과에 선형 함수를 적합해 얻는다(Algorithm 5).

철회형 그리디 (Greedy with Withdraw)

기본 흐름은 이렇다 — 1수준 타일 기반 하위 작업 공간 Y를 얻고, U′를 U로 초기화한 뒤 반복적으로 하위 작업을 선택해 U′의 모든 점을 덮는다. 각 반복에서 cost(x_i)를 |u_i ∩ U′|(x_i가 덮을 수 있는 미커버 점 수)로 나눈 평균 비용을 계산해 최소인 것을 선택하고 U′ ← U′ − u_i로 갱신한다. 다중 수준을 허용하므로, 선택 후 잔여 비영 원소를 재조직해 다음 수준 타일과 새 하위 작업 공간을 생성하고 그중에서 다음을 선택한다. 여기에 두 기법을 더한다.

4.3.3구현

블록·ELL·1D 포맷 하위 작업별 템플릿을 준비하고, 서로 다른 하위 작업의 코드를 수평 융합(horizontal fusion)[59]으로 단일 GPU 커널에 합친다 — 융합 커널은 분기문으로 두 하위 작업의 명령을 결합하고, 분기 조건이 현재 스레드 블록 ID를 검사해 해당 하위 작업의 명령 경로로 실행을 디스패치한다. 융합 커널의 분기 수는 템플릿 수(실험에서 32 이하)로 제한된다. 템플릿은 스레드 수, 벡터화 로드/스토어 크기, 루프 명시적 언롤 여부 같은 구현 선택에 대해 파라미터화되어 있어, 파라미터를 열거해 커널 지연 기준 최선 구현을 선택한다(파라미터 공간이 100 미만으로 매우 작아 열거 오버헤드가 낮다).

비용 모델 구축에서도 하위 작업 비용은 템플릿 기반 코드를 실행해 측정한다. GPU 코어가 포화된 상태의 실행시간을 수집해야 SM 실행시간을 하위 작업 비용의 합으로 추정하는 것이 정확하므로, 주어진 하위 작업으로 워크로드를 충분히 많이 분할할 수 있는 가짜(fake) 희소 연산자를 만들고 총 지연을 (하위 작업 수 / SM 수)로 나눠 비용으로 삼는다. 다만 희소 연산자가 너무 희소해 선택된 작업 분할의 하위 작업 수가 부족하면 이 비용 모델 기반 성능이 충분하지 않을 수 있다. 따라서 그리디가 찾은 분할 외에 단일 포맷만 쓰는 최선 분할(블록만, ELL만, 1D만)도 각각 탐색해, 네 후보의 지연을 비교해 최선을 골라 최종 코드를 생성한다.

4.3.4실험

실험은 세 질문에 답한다 — (1) STile이 연산자 효율에서 경쟁자를 능가하는가, (2) 그리디 알고리즘의 기법들이 유용한가, (3) 다중 수준 분해와 둘 이상의 기본 포맷이 필요한가.

설정. SparseTIR[76] 기반으로 Python 3.9로 구현했고 코드는 GitHub에 공개되어 있다. 장비는 AMD EPYC 7413 24-Core × 2, NVIDIA A100-SXM4-80GB, RAM 1006 GB, Ubuntu 20.04.5, CUDA 11.7이며 데이터 타입은 float16이다. 경쟁자는 다섯 — cuSPARSE[47](CSR 커널), DGL[71](SDDMM은 FeatGraph[56] 기반), VectorSparse[42](1D-벡터 포맷 + Tensor Core), Triton[70](블록 희소 구현), SparseTIR[76](합성 가능 포맷·스케줄 변환의 최신 기법)이며, STile의 r은 1.2로 설정한다. 앞의 네 경쟁자는 단일 포맷 연산자만 지원하고 SparseTIR만 하이브리드 포맷을 지원한다. Triton은 SparseTIR 실험 관행에 따라 블록 프루닝 행렬과 희소 어텐션 행렬에서만 시험한다.

SpMM 결과 (Fig 4.14–4.15)

왜 더 빠른가. 첫째, 탐색 공간에 블록 포맷과 ELL 포맷 하위 작업을 모두 담아 최선 조합을 찾으므로 — 희소 행렬의 조밀한 부분에만 Tensor Core를 쓸 수 있다. 둘째, ELL 포맷 템플릿이 GPU 공유 메모리를 활용해 전역 메모리 → 로컬 레지스터의 값비싼 데이터 이동을 줄인다. 셋째, 행·열 재정렬로 국소 밀도를 높일 수 있고 블록 포맷의 후보 형상이 더 다양해 더 나은 하이브리드 포맷을 찾을 수 있다. SparseTIR의 hyb 포맷은 열 방향 분할 후 행당 비영 수로 행을 버킷에 넣고 각 버킷을 별도 ELL로 저장해 캐시 지역성과 부하 균형을 개선하지만 Tensor Core를 쓰지 않는다. VectorSparse의 1D-벡터 포맷은 단순 블록보다 0을 덜 저장하지만 행렬이 충분히 조밀하지 않으면 여전히 부족하다.

메모리 사용. cuSPARSE의 CSR과 비교하면, "hyb"·"ELL"은 행 길이가 상수라 행 길이 배열이 불필요하고 "1D-vector"·"block"은 원소가 아닌 벡터·블록의 위치를 CSR식으로 저장해 메모리가 덜 든다. 그러나 CSR만이 0을 패딩하지 않는다 — 이 때문에 cora·citeseer 등에서는 절감이, proteins·reddit 등에서는 증가가 나타난다. STile은 ppi·proteins·reddit에서 선택 하위 작업 다수가 블록 포맷이라 모든 베이스라인보다 메모리를 많이 쓰지만(VectorSparse의 1D-벡터 길이가 STile의 블록 높이보다 짧아 더 유연하고, SparseTIR의 hyb는 0 패딩이 적어 더 효율적), 블록 포맷이 가능하게 한 Tensor Core 계산과 효율적 커널 템플릿 덕에 여전히 더 낮은 지연을 달성한다.

SDDMM 결과 (Fig 4.16–4.17)

SDDMM에서는 출력 점별 계산 워크로드가 서로 독립이고 양도 동일해, 1D 포맷으로 저장하고 출력 점 계산을 스레드에 배정하면 부하 균형 문제가 없다 — 벡터화 로드/스토어 인트린식과 축약 루프 병렬화 같은 최적화까지 더해 SparseTIR가 DGL 대비 1.4–5.6× 가속을 얻는다. VectorSparse는 Tensor Core와 축약 루프 병렬화를 쓰지만 성능이 훨씬 나쁘다 — 단순히 1D-벡터 포맷을 쓰는 것이 이 행렬들에 좋은 선택이 아님을 보여준다. STile은 블록 포맷(Tensor Core)과 1D 포맷 하위 작업을 모두 탐색 공간에 두어 양쪽의 이점을 취한다 — reddit, K = 32에서 1D만 3.24 ms, 블록만 2.66 ms, 둘 다 고려하면 2.07 ms로 각각 1.6×·1.3× 개선된다. 메모리에서는 1D 포맷이 비영 원소마다 행·열 인덱스를 저장하는 반면 블록·1D-벡터는 위치 정보에 메모리를 덜 쓰되 여분 0을 저장할 수 있다 — STile은 조밀한 부분에서 위치 정보를 절약하고 희소한 부분에서 패딩을 피해 DGL과 같거나 더 우수하다(reddit 0.9×).

탐색 시간·절제 연구·탐색 공간 연구·비용 모델

Fig 4.18은 설정별로 얻어지는 SDDMM on Strided의 희소 포맷을 보여준다(초록은 블록 포맷, 파랑은 1D 포맷). 기본 설정에서는 행렬 A의 조밀 부분과 희소 부분을 두 부분으로 잘 분리해 각각 적합한 포맷으로 저장한다. 깊이가 1이면 더 희소한 부분의 비영 원소를 저장할 때 잔여 원소에 대한 새 1D 타일을 생성할 수 없어 일부 비영 원소를 중복 저장해야 하고, 이는 계산 낭비가 된다. 블록 기본 포맷만 고려해도 계산이 낭비되고, 1D 기본 포맷만 고려하면 Tensor Core를 쓰지 못한다.

비용 모델 성능. SpMM에서 5,000개, SDDMM에서 13,060개 하위 작업을 무작위 표집해(각각 ELL·1D 포맷 — 블록 포맷은 이미 비용 표가 있으므로 제외) GPU 코어 포화 상태의 지연을 측정하면 예측과 실측 사이에 선형 상관이 나타난다 — 피어슨 상관계수는 ELL 0.9243, 1D 0.9997(양쪽 p = 0.0), RMSE는 1.4e-4, 4.8e-05다. 1D에서 매우 정확한 이유는 탐색 공간에 한 종류의 1D 타일만 고려하기 때문이다. ELL 쪽은 덜 정확하지만(경험적 근사 한계 24%) Tensor Core를 쓰는 블록 포맷 하위 작업이 한 자릿수 배 더 빠를 수 있다는 점에서 여전히 좋은 하이브리드 포맷을 찾는 데 유용하다. ELL용 비용 모델로 MLP[64]도 시도했는데 RMSE는 3.3e-05로 거의 한 자릿수 작았으나, 달성 연산자 지연은 동일하면서 예측용 특징 계산이 늘어 탐색 시간이 1.1–6.1× 증가했다. 즉 이 비용 모델은 예측 성능과 실행 효율을 함께 달성한다.

이 장은 확장 가능한 GNN 학습의 계산을 가속하는 두 방법을 제시했다 — DAHA는 세밀한 데이터·하드웨어 인지 실행 계획을 위한 모델 수준 프레임워크로, 새로운 하이브리드 CPU–GPU 파이프라인, 배치 내 실행 계획 재작성, 효율적 배치 간 스케줄링을 도입해 유의미한 엔드투엔드 가속을 달성했다. STile은 희소 계산을 자동 최적화하는 연산자 수준 프레임워크로, 유연한 텐서 변환과 다중 수준 타일링을 통해 확장된 탐색 공간을 탐색함으로써 하이브리드 희소 포맷 선택 문제를 해결하고 SpMM에서 cuSPARSE 대비 최대 18× 가속을 산출했다. 향후 과제로는 DAHA에 캐싱 전략을 통합하는 것과 탐색 과정을 한층 최적화하는 것이 남는다.