TL;DR

  • 희소 야코비안 행렬 계산을 위해 그래프 색칠은 CPU에서, 후속 계산은 GPU에서 실행해야 하지만 Futhark의 메모리 배치 방식이 이를 어렵게 만듦.
  • Futhark GPU 백엔드는 기본적으로 모든 배열을 GPU 메모리에 두므로, 순차 CPU 코드가 배열 원소에 접근할 때 원소별 복사와 통신으로 성능이 크게 저하됨.
  • 이상적인 해결책은 배열의 실제 사용 위치에 따라 CPU·GPU 메모리를 배치하고 복사 수와 메모리 점유를 관리하는 컴파일러 최적화임.
  • 당장의 해결책으로 함수 본문과 중간 배열을 CPU에서 처리하는 #[cpu_function] 속성을 추가했으며, 함수 반환값은 GPU 메모리로 복사함.
  • 이 방식은 복사 비용이 따르는 다소 거친 해킹이지만, 같은 Futhark 프로그램에서 효율적인 순차 그래프 색칠과 병렬 GPU 계산을 함께 가능하게 함.

문제의 배경

  • 올해 초 Elias Smedegaard는 자동 미분(automatic differentiation)을 통한 희소 야코비안 행렬의 효율적 계산을 주제로 학사 논문을 작성함. 이 글에서 중요한 부분은 행렬의 희소 패턴에 대응하는 그래프를 색칠하는 단계임.
  • 최적 그래프 색칠은 유명한 NP-난해 문제지만, 최적해가 아니라 적절한 색칠을 효율적인 알고리즘으로 구하는 것으로 충분함. Elias는 거리 2 색칠(distance-2 colouring)을 위한 꽤 빠른 탐욕 알고리즘을 찾았지만, 알고리즘 자체는 순차적임.
  • 전체 프로그램은 그래프 색칠 단계와 색칠 결과를 사용해 대규모 병렬성으로 야코비안 행렬을 계산하는 단계로 구성됨. 두 번째 단계는 GPU 같은 병렬 하드웨어에서 실행하고 첫 번째 단계는 CPU에서 실행하는 것이 바람직함.
  • Futhark의 효율적인 제자리 갱신(in-place update) 기능은 순차 알고리즘에 적합하지만, 구현상의 선택 때문에 두 단계를 서로 다른 하드웨어에서 실행하기가 까다로움.

문제가 발생하는 방식

  • Futhark의 컴파일 모델에서는 배열이 메모리에 저장되며, GPU 파이프라인을 사용하면 모든 배열이 GPU 메모리에 배치됨. 내부 표현이 CPU·GPU 메모리의 혼합을 지원하지 못해서가 아니라 구현 편의에 따른 선택임.
  • 이 설계는 CPU 코드가 비용이 큰 API를 통해 GPU 메모리에 접근할 수 있지만 GPU 코드가 일반적으로 CPU 메모리에 접근할 수 없다는 점에서 안전함. 다만 접근 가능하다는 사실이 빠르다는 뜻은 아님.
  • GPU 메모리에 저장된 배열에서 CPU 코드가 반복문 안에서 원소 하나를 읽으면, 해당 원소를 GPU 메모리에서 CPU 메모리의 어딘가로 복사한 뒤 합산해야 함. 원소 하나의 복사 자체는 거의 시간이 들지 않지만, 통신 설정과 복사 완료 대기에 원소당 몇 마이크로초가 걸릴 수 있어 성능을 크게 해침.
  • 배열 전체를 반복문 전에 한 번 복사하면 통신 비용을 분산할 수 있지만, GPU 배열의 인덱스 접근이 CPU 코드에 남아 있으면 특히 반복문 안에서 매우 느린 GPU 메모리 읽기가 발생함.
  • Elias의 거리 2 그래프 색칠 알고리즘은 그래프와 스택을 나타내는 배열을 조작하는 몇 겹의 순차 반복문으로 이루어짐. GPU 백엔드로 컴파일하면 순차 C 백엔드보다 성능이 쉽게 세 자릿수 배 이상 저하됨.
  • C 백엔드에서는 C로 작성한 것과 거의 같은 우수한 성능을 얻지만, 전체 프로그램의 두 번째 단계까지 순차 실행됨. 다중 코어 백엔드는 병렬 CPU 코드를 생성하는 절충안이지만, 야코비안 계산은 GPU에서 실행하는 것이 바람직함.

원칙적인 해결책의 형태

  • Futhark는 프로그램의 서로 다른 부분을 서로 다른 백엔드로 컴파일하는 별도 컴파일(separate compilation)을 지원하지 않으며, 이를 추가하는 방법도 다소 어색한 해결책임.
  • 더 나은 방법은 배열이 실제로 어떻게, 어디에서 사용되는지 살펴 CPU 또는 GPU 메모리에 배치하고, 프로그램에 따라 양쪽에 중복 배치하는 것임.
  • Philip Børgesen이 구현한 기존 최적화는 데이터가 아니라 단순 순차 계산을 GPU로 옮김. 결과가 어차피 GPU에서만 사용되고 계산이 단순할 때, 원소 몇 개를 복사하는 데 시간이 대부분 쓰인다면 단일 스레드 GPU 커널에서 순차 계산을 수행해 통신을 줄이는 방식임.
  • 이 최적화는 반복문이 있는 거리 2 색칠 알고리즘에는 적용되지 않음. 검사를 비활성화해 GPU 실행을 강제해도, 반복이 많은 순차 코드를 GPU 단일 스레드에서 실행하는 성능은 예상대로 매우 낮음.
  • 이상적인 세계에서는 계산 대신 데이터를 옮기는 대응 최적화를 생각할 수 있음. 이때도 과도한 복사를 막고, 메모리 사용량을 늘리는 복사본을 불필요하게 오래 유지하지 않도록 해야 함.
  • 이런 최적화의 윤곽은 보이지만, 제대로 구현하려면 현재 투입할 수 있는 시간보다 더 많은 검토와 주의가 필요함.

대신 적용한 해킹

  • 컴파일러에 더 정교한 기능을 넣는 대신 #[cpu_function]이라는 새 속성을 추가함. 초기 설계에서는 보통 #[noinline]로 강제하는 인라인 비대상 함수에 속성을 붙이면 함수 본문을 CPU 코드로 컴파일하고, 입력·중간·출력 배열을 백엔드 종류와 관계없이 CPU 메모리에 저장하는 방식임.
  • 호출자는 배열 인수가 올바른 메모리 공간에 있는지 책임지며, 컴파일러는 이를 보장하는 코드를 삽입함. 메모리 중간 표현은 메모리 공간별로 매개변수화된 mem 유형을 통해 여러 종류의 메모리를 동시에 처리하도록 명시적으로 설계됐지만, 이 기능을 폭넓게 사용한 적이 없어 몇 가지 문제가 드러남.
  • GPU 커널 코드 생성은 본문에서 참조하는 배열이 모두 GPU 메모리에 있다고 가정함. 따라서 #[cpu_function] 함수가 CPU 메모리에 생성한 배열을 호출자 쪽 GPU 커널에서 사용하면 유효하지 않은 상태가 됨.
  • 원칙적인 해결책은 GPU 커널 내부에서 실제로 접근하는 배열을 확인해 필요할 때 GPU로 복사하는 것임. 다만 GPU 커널이 반복문에서 호출될 때 매 반복마다 복사하지 않아야 하고, 동시에 배열 복사본은 가능한 한 짧게 유지해야 함.
  • 선택한 해결책은 #[cpu_function]의 의미를 조정하는 것임. 입력과 모든 중간 결과는 CPU 메모리에 두되, 함수의 반환값은 함수 끝에서 복사해 GPU 메모리에 둠. 이에 따라 해당 속성이 붙은 함수 안을 제외하면 배열이 GPU 메모리에 있다는 컴파일러의 기존 가정을 대체로 유지할 수 있음.
  • 속성이 붙은 함수 내부에서는 GPU 백엔드가 iota와 replicate 같은 중간 표현 기본 연산의 결과도 GPU 메모리에 있다고 가정하는 문제가 추가로 드러남. 이 부분은 어렵지 않게 수정했지만 비슷한 버그가 다른 곳에도 있을 가능성이 있음.
  • #[cpu_function]을 map에 적용할 때의 동작도 결정해야 했음. 임의로 속성을 무시하고 일반적인 병렬 리프트 함수(parallel lifted function)를 생성하도록 정했지만, 순차 함수를 생성해야 한다는 주장도 가능함.

현재 상태

  • 다소 다루기 까다로운 해킹이지만 #[cpu_function]은 당장의 문제를 해결함. 이제 매우 효율적인 순차 코드로 그래프 색칠을 수행하면서 같은 Futhark 프로그램 안에서 병렬 연산도 실행할 수 있음.
  • 그래프 색칠은 전체 실행 시간에서 매우 작은 부분이 됐으며, 이후의 수치 계산이 실행 시간을 지배함. 이 속성은 함수 호출 시 비용이 큰 복사를 수반하지만, 원소별 복사가 아니라 일괄 복사이므로 오버헤드는 크지 않음.
  • 컴파일러 수정 규모는 비교적 작았으며 대부분 버그 수정으로 분류할 수 있음. Futhark 컴파일러가 배열의 저장 위치를 자동으로 결정하는 원칙적인 기능을 갖추더라도, 이 속성은 유용한 힌트로 남을 가능성이 있음.