통신 회피 알고리즘

Communication-avoiding algorithm

통신 회피 알고리즘은 실행 시간과 에너지 소비를 개선하기 위해 메모리 계층 내에서 데이터의 이동을 최소화한다.이는 총 2가지 비용(시간과 에너지 측면에서)을 최소화한다. 산술과 통신이다.통신, 이 맥락에서, 통신이란 메모리 레벨 사이 또는 네트워크를 통한 다중 프로세서 사이에서 데이터를 이동하는 것을 말한다.산수보다 훨씬 비싸다.[1]

동기

다음 런타임 모델을 고려하십시오.[2]

  • 계산 측정 = FLOP당 시간 = γ
  • 통신 측정 = 이동된 데이터의 단어 수 = β

③ 총 주행시간 = γ·(FLOPs no.), + β·(단어 no.)

시간과 에너지로 측정된 β >> γ에서 보면 통신비가 연산비를 지배한다.기술 동향은[3] 클라우드 컴퓨팅에서 슈퍼컴퓨터, 모바일 기기에 이르기까지 다양한 플랫폼에서 통신의 상대적 비용이 증가하고 있음을 나타낸다.보고서는 또 향후 10년간 D램 접속 시간과 FLOP 간 격차가 100배 이상 늘어나 프로세서와 D램 간 전력 사용량 균형을 맞출 것으로 전망했다.[1]

FLOP 속도(계속) DRAM 대역폭(β) 네트워크 대역폭(β)
59%/년 연 23% 연 26%
2010년 데이터 이동 에너지 비용: 온칩 대 오프칩

에너지 소비량은 우리가 메모리 계층 구조에서 더 높아질수록 크기순으로 증가한다.[4]버락 오바마 미국 대통령은 2012 회계연도 에너지부 예산안 제출에서 의사 소통을 기피하는 알고리즘을 의회에 다음과 같이 언급했다.[1]

새로운 알고리즘이 초고밀도 컴퓨팅 시스템의 성능과 정확성을 개선한다.현대의 컴퓨터 아키텍처에서 프로세서 사이의 통신은 주어진 프로세서에 의한 부동 소수점 산술 연산의 성능보다 더 오래 걸린다.ASCR 연구진은 알고리즘 내에서 지정된 통신 패턴을 재구성하여 프로세서와 메모리 계층 간의 통신을 최소화하기 위해 일반적으로 사용되는 선형 대수법에서 파생된 새로운 방법을 개발했다.이 방법은 전 세계 연구자들이 크고 복잡한 다물리학 문제를 해결할 수 있는 기능을 제공하는 소프트웨어 제품군인 트릴리노스 프레임워크에서 구현되었다.

목표

통신 회피 알고리즘은 다음과 같은 목적으로 설계된다.

  • 알고리즘을 재구성하여 모든 메모리 계층에 걸친 통신을 줄이십시오.
  • 가능한 경우 통신 하한을 달성하십시오.

다음의 간단한 예는[1] 이러한 것들이 어떻게 달성되는지를 보여준다.

행렬 곱하기 예제

A, B, C를 순서 n × n의 제곱 행렬로 한다.다음의 순진한 알고리즘은 C = C + A * B를 구현한다.

Matrix multiplication algorithm diagram.png 

i = 1 ~ n의 경우 j = 1 ~ n의 경우 1 ~ n(i,j) = C(i,j) + A(i,k) * B(k,j)

산술비용(시간복잡도): n2(2n - 1) 충분히 큰 n 또는 O(n3)에 대한 값.

각 단계에서 라벨이 표시된 통신 비용으로 이 알고리즘 재작성

for i = 1 to n      {read row i of A into fast memory}               - n² reads      for j = 1 to n          {read C(i,j) into fast memory}               - n² reads          {read column j of B into fast memory}        - n³ reads          for k = 1 to n              C(i,j) = C(i,j) + A(i,k) * B(k,j)          {write C(i,j) back to slow memory}- n² 쓰기

고속 메모리는 크기 M의 로컬 프로세서 메모리(CPU 캐시)로 정의될 수 있으며 저속 메모리는 DRAM으로 정의할 수 있다.

통신비(읽기/쓰기): n3 + 3n2 또는 O(n3)

총 주행시간 = γ·O(n3) + β·O(n3) 및 β >>> γ 통신비가 우세하다.차단된(타일화된) 행렬 곱셈 알고리즘은 다음과[1] 같은 주요 항을 줄인다.

차단된(타일화된) 행렬 곱하기

b를 블록 크기라고 하는 b-b-b 하위 블록의 매트릭스 A, B, C를 n/b-by-n/b로 간주하고, 고속 메모리에 맞는 b-b-b 블록 3개를 가정한다.

Tiled matrix multiplication diagram.png 

for i = 1 to n/b      for j = 1 to n/b          {read block C(i,j) into fast memory}           - b² × (n/b)² = n² reads          for k = 1 to n/b              {read block A(i,k) into fast memory}       - b² × (n/b)³ = n³/b reads               {read block B(k,j) into fast memory}       - b² × (n/b)³ = n³/b reads              C(i,j) = C(i,j) + A(i,k) * B(k,j) - {블록에서 매트릭스 곱하기} {쓰기 블록 C(i,j)를 느린 메모리로 되돌리기} - b² × (n/b)² = n² 쓰기

통신비: 2n3/b + 2n2 읽기/쓰기 << 2n3 산술비>

b를 최대한 크게 만드는 방법:

3b2 ≤ M

다음 통신 하한선을 달성한다.

3n1/23/M1/2 + 2n2 또는 Ω(FLOP/M의1/2 번호)

통신 감소를 위한 이전 접근 방식

이 문제를 해결하기 위해 과거에 조사된 대부분의 접근법은 연산과의 통신을 중첩하는 것을 목표로 하는 스케줄링 또는 튜닝 기법에 의존한다.그러나 이러한 접근방식은 기껏해야 2인자의 개선으로 이어질 수 있다.고스팅(Ghosting)은 통신 감소를 위한 다른 기법으로, 프로세서가 미래의 연산을 위해 이웃 프로세서의 중복 데이터를 저장하고 계산한다.캐시-관심 알고리즘은 빠른 푸리에 변환을 위해 1999년에 도입된 다른 접근방식을 나타낸다.[5] 그리고 나서 그래프 알고리즘, 동적 프로그래밍 등으로 확장된다.그것들은 또한 고밀도 LU와 QR 인자화로서 선형대수학에서[6][7][8] 여러 연산에도 적용되었다.아키텍처별 알고리즘의 설계는 병렬 알고리즘에서 통신을 줄이는 데 사용할 수 있는 또 다른 접근법이며, 주어진 통신 위상에 적응하는 알고리즘의 문헌에는 많은 예가 있다.[9]

참고 항목

참조

  1. ^ a b c d e 뎀멜, 짐 "알고리즘을 피하는 통신" 2012년 SC 컴패니언:고성능 컴퓨팅, 네트워킹 스토리지 및 분석.IEEE, 2012.
  2. ^ 뎀멜, 제임스, 캐시 옐릭."통신 회피(CA) 및 기타 혁신적인 알고리즘"Berkeley Par Lab: 병렬 컴퓨팅 환경의 발전: 243–250.
  3. ^ Bergman, Keren 등. "Exascale Computing study: 엑사스케일 컴퓨팅 시스템의 기술 과제."DARPA IPTO(Defense Advanced Research Projects Agency Information Processing Technologies Office, DARPA IPTO), Tech.의원 15명(2008년).
  4. ^ 샬프, 존, 수디프 도산지, 존 모리슨."Exascale Computing Technology 과제".컴퓨팅 과학을 위한 고성능 컴퓨팅VECPAR 2010.스프링거 베를린 하이델베르크, 2011. 1 대 25.
  5. ^ M. Frigo, C. E. Leiserson, H. Prokop, S. Ramachandran, "Cacheoblivous 알고리즘", In FOCS '99: 컴퓨터 과학의 기초에 관한 제 40회 연례 심포지엄의 진행, 1999.IEEE 컴퓨터 협회.
  6. ^ S. 톨레도, "부분 피벗이 있는 LU 분해에서 참조의 지역성," SIAM J. 매트릭스 Anal.1997년 제 18권 제 4호
  7. ^ F. Gustavson, "Recursion Leads for automatic Variable Blocking for Closed Linear-Algebra 알고리즘," IBM Journal of Research and Development, vol. 41, no. 6, 페이지 737–755, 1997.
  8. ^ E. 엘름로스, F.구스타프슨, I. 존슨, B.Kagstrom, "밀도 매트릭스 라이브러리 소프트웨어에 대한 반복 차단 알고리즘과 하이브리드 데이터 구조," SIAM Review, vol. 46, no. 1, 페이지 3–45, 2004.
  9. ^ 그리고리, 로라."고성능 컴퓨팅에서 선형 대수 알고리즘을 피하는 커뮤니케이션의 도입.