Futhark 컴파일러의 scan-scatter fusion 최적화에 관한 글입니다.

Fusion(융합)​은 데이터 병렬 연산 간 중간 결과를 메모리에 저장하지 않고 결합하여 메모리 접근을 줄이는 최적화 기법으로, 특히 map-map fusion이 대표적입니다. 이 글에서는 scan(스캔)​과 scatter(스캐터) 연산을 효율적으로 융합하는 새로운 방식을 소개하며, 이를 통해 필터링과 같은 병렬 알고리즘에서 발생하는 중간 배열 저장 비용을 크게 줄일 수 있음을 설명합니다.

기존에는 scan 결과 전체를 메모리에 저장한 후 scatter에 전달하는 방식이었으나, scatter를 누적기(accumulators)로 표현함으로써 scan과 scatter를 하나의 데이터 병렬 연산으로 융합할 수 있게 되어 컴파일러 복잡도를 낮추고 성능을 개선하였습니다. 이 최적화는 GPU에서 2배 이상의 필터링 속도 향상을 보였으며, 단일 GPU 커널로 컴파일되어 메모리 트래픽을 크게 줄이는 실용적 가치를 지닙니다.

또한, 이 최적화를 적용하기 위해 Futhark 프로그래밍 스타일을 약간 수정해야 하지만, 이는 유지보수성과 추상화 수준을 해치지 않으면서도 성능 저하 없이 모듈화된 코드를 작성할 수 있게 해 줍니다. 향후 다양한 데이터 병렬 연산 조합에 대한 융합 연구와 실제 프로그램에서의 패턴 분석도 제안되고 있습니다.