SegFold: 미세 조정된 동적 데이터플로우(Fine-Grained Dynamic Dataflow)를 통한 희소 GEMM(Sparse

일반화된 희소 행렬-행렬 곱셈 (SpGEMM)은 많은 영역에서 매우 중요합니다. 기존의 CPU와 GPU, 그리고 특화된 가속기들은 정적 데이터플로우 (예: 내적 (inner product), 외적 (outer product), Gustavson 등)에 의존합니다. 각 정적 데이터플로우는 데이터 재사용 기회를 일부 희생하며 부하 균형 (load balance)에 제약을 가합니다. 이러한 비효율성을 해결하기 위해, 우리는 동적 특성 (dynamism)을 고려하여 전형적인 SpGEMM 데이터플로우를 확장합니다. 구체적으로, 재사용을 최적화하고 자원 경합 (resource contention)을 줄이기 위해 미세 조정된 동적 스케줄링 (fine-grained dynamic scheduling)을 추가합니다. 또한 부하 균형과 병렬성 (parallelism)을 개선하기 위해 부분적으로 완료된 작업의 동적 리매핑 (dynamic remapping)을 개발합니다. 이러한 아이디어들은 Segment라고 불리는 특정 데이터플로우로 공식화됩니다. Segment를 입증하기 위해, 우리는 SegFold라고 불리는 SpGEMM 가속기를 공동 설계 (codesign)합니다. SegFold는 스테이셔너리 입력 배열 (stationary input array)의 로컬 윈도우 내에서 미세 조정된 재사용 기회를 식별하고, 동적 작업 할당을 통해 이를 활용하는 메모리 컨트롤러를 포함합니다. 또한 각 PE에 할당된 작업을 동적으로 리매핑하여 부하를 균형 있게 맞추는 동안, 입력을 계산을 위한 적절한 프로세싱 엘리먼트 (PEs)로 라우팅하는 머지 네트워크 (merge network)를 통합합니다. 다양한 밀도와 행렬 크기에 걸쳐, SegFold는 최첨단 SpGEMM 가속기 대비 기하 평균 $1.95 imes$의 속도 향상을 달성하였고, 최상의 정적 데이터플로우 구성 대비 $5.3 imes$의 속도 향상을 달성하였습니다. 이는 데이터플로우 설계 공간에 동적 특성을 추가하는 것이, 어떤 정적 스케줄링 선택도 단독으로는 달성할 수 없는 재사용 및 부하 균형 이득을 끌어낼 수 있음을 입증합니다.