일괄 운용

집합 연산은 병렬 프로그래밍 컨텍스트의 SPMD 알고리즘에서 자주 사용되는 상호작용 패턴의 구성 블록입니다.따라서 이러한 운영의 효율적인 실현에 관심이 있다.

Message Passing^[1] Interface(MPI; 메시지 패싱 인터페이스)에 의해 일괄 조작이 실현됩니다.

정의들

모든 점근 런타임 함수에서 지연 $(\displaystyle \alpha$ $\beta$ 통신 비용 $\beta$ β(\ $displaystyle \beta$ 처리 $장치$ 수p(\ $displaystyle$ p $)$ 및 $p$ $노드당$ 입력 크기 n $(\displaystyle$ n $n$ 를 나타냅니다. 둘 이상의 노드에 초기 메시지가 있는 경우 가정합니다.모든 로컬메시지의 사이즈가 동일합니다. $p_{i}\in \{p_{0},p_{1},\dots ,p_{p-1}\}$ 처리 유닛에 대응하려면 p $p_{i}\in \{p_{0},p_{1},\dots ,p_{p-1}\}$ $p_{i}\in \{p_{0},p_{1},\dots ,p_{p-1}\}$ { $p_{i}\in \{p_{0},p_{1},\dots ,p_{p-1}\}$ , $p_{i}\in \{p_{0},p_{1},\dots ,p_{p-1}\}$ 1 , $p_{i}\in \{p_{0},p_{1},\dots ,p_{p-1}\}$ , $p_{i}\in \{p_{0},p_{1},\dots ,p_{p-1}\}$ - $p_{i}\in \{p_{0},p_{1},\dots ,p_{p-1}\}$ $}$ \ $display style$ p _ { $i$ } \ $in$ \ { p _ $0$ , $p$ _ { $1$ } , \ $dots$ , p $_$ { p - $1$ 를 $p_{i}\in \{p_{0},p_{1},\dots ,p_{p-1}\}$ 합니다.

분포가 동일하지 않은 경우( $node$ $p_{i}$ {\ $displaystyle p_{$ i $p_{i}$ }}, 즉 $n_{i}$ pi $n=\max(n_{0},n_{1},\dots ,n_{p-1})$ $displaystyle n_$ ${$ $i$ n $n=\max(n_{0},n_{1},\dots ,n_{p-1})$ ( $n=\max(n_{0},n_{1},\dots ,n_{p-1})$ $n=\max(n_{0},n_{1},\dots ,n_{p-1})$ , $n=\max(n_{0},n_{1},\dots ,n_{p-1})$ , $n=\max(n_{0},n_{1},\dots ,n_{p-1})$ , $n=\max(n_{0},n_{1},\dots ,n_{p-1})$ - $n=\max(n_{0},n_{1},\dots ,n_{p-1})$ 1 ){ $displaystyle n =$ \ $max$ ( $n$ _ 0 , n _ 0 , n _ 0 , n _ 0 , { n _ $n=\max(n_{0},n_{1},\dots ,n_{p-1})$ n _ { n _ { 1 } ), n _ { 1 $}$ ), n _ { 1 }, n _ { 1 $n=\max(n_{0},n_{1},\dots ,n_{p-1})$ n { 1 $},$ n { 1 }, n { 1 $n=\max(n_{0},n_{1},\dots ,n_{p-1})$ }, $n$

분산 메모리 모델을 가정합니다.공유 메모리 모델도 개념은 비슷합니다.다만, 공유 메모리 시스템은, 브로드캐스트() Broadcast)등의 일부의 조작에 하드웨어 서포트를 제공할 수 있습니다.이것에 의해, 편리한 동시 ^[2]읽기가 가능하게 됩니다.따라서 새로운 알고리즘의 가능성을 이용할 수 있습니다.

브로드캐스트

3개의 노드에서 실행된 브로드캐스트 동작의 정보 흐름.

브로드캐스트 패턴은 하나의 처리 장치에서 모든 처리 장치로 데이터를 배포하는 데 사용되며, 입력 또는 전역 값을 분배하기 위해 종종 SPMD 병렬 프로그램에서 필요합니다.브로드캐스트는 축소 패턴의 역버전(「Reduce」)으로 해석할 수 있습니다.처음에는 $루트$ $r$ {\ $displaystyle$ }0 {\ $displaystyle$ $0$ $}$ 만 $r$ $0$ $메시지$ m {\ $displaystyle$ m $m$ 을 저장합니다. $브로드캐스트$ m {\ $displaystyle$ m}이 $m$ 나머지 처리 장치로 전송되므로 최종적으로 $모든$ 처리 장치에서 m {\ $displaystyle$ m $}$ 을 $m$ 사용할 수 있습니다.

p $p-1$ - $p-1$ (\ $display style$ p-1) 반복을 $p-1$ $p-1$ 한 순차적인 for-loop을 통한 구현은 병목현상이 되기 때문에 분할 및 정복 접근법이 일반적입니다. $한$ 가지 방법은p\ $displaystyle$ p가 $p$ 2의 거듭제곱이어야 $하는$ 이항 트리 구조를 활용하는 것입니다.처리장치가 $처리장치$ i $.\$ $displaystyle$ i $.$ 에m{ $displaystyle$ m $}$ 을 $m$ 보내는 책임을 지는 경우. $j$ 、 $m$ { $displaystyle$ m $m$ } {\ $\left\lceil (i+j)/2\right\rceil$ $\left\lceil (i+j)/2\right\rceil$ + $\left\lceil (i+j)/2\right\rceil$ ） / $\left\lceil (i+j)/2\right\rceil$ （ \ $displaystyle \ lceil ( i$ + $j$ ) / $\left\lceil (i+j)/2\right\rceil ..\left\lceil (i+j)-1\right\rceil$ \ $right$ \ $rceil$ }으로 $\left\lceil (i+j)/2\right\rceil$ $m$ 하여 처리장치 $\left\lceil (i+j)/2\right\rceil ..\left\lceil (i+j)-1\right\rceil$ ( $\left\lceil (i+j)/2\right\rceil ..\left\lceil (i+j)-1\right\rceil$ + $\left\lceil (i+j)/2\right\rceil ..\left\lceil (i+j)-1\right\rceil$ ) / $2$ ⌉ ⌈ $\left\lceil (i+j)/2\right\rceil ..\left\lceil (i+j)-1\right\rceil$ + $\left\lceil (i+j)/2\right\rceil ..\left\lceil (i+j)-1\right\rceil$ ) - $\left\lceil (i+j)/2\right\rceil ..\left\lceil (i+j)-1\right\rceil$ ⌉ ⌉ display $displaydisplaydisplaydisplaydisplay$ 、 \ display $styleft$ \ lefault \ $lceil$ ( i ) / lceil ( $i)$ 에 대한 책임을 위임합니다 $.$ $\left\lceil (i+j)-1\rceil.$ 단 $\left\lceil (i+j)/2\right\rceil ..\left\lceil (i+j)-1\right\rceil$ , 그 책임은 i $i..\left\lceil (i+j)/2\right\rceil -1$ ( $i..\left\lceil (i+j)/2\right\rceil -1$ / $i..\left\lceil (i+j)/2\right\rceil -1$ $i..\left\lceil (i+j)/2\right\rceil -1$ - 1 $({display$ i})로 축소됩니다. $\left\lceil(i+j)/2\right\rceil-1$

이항 트리에서 긴 $메시지$ m $\displaystyle$ m에 문제가 있습니다.수신 유닛 $m$ {\ $displaystyle$ m $}$ 은 $m$ 메시지 전체를 수신한 후에만 메시지를 다른 유닛에 전파할 수 있습니다.한편, 통신 네트워크는 이용되지 않는다.따라서 바이너리 트리의 파이프라이닝이 $사용$ 됩니다. $m$ 서m ${\$ $displaystyle$ k $}$ 패킷은 $m$ $k$ $\left\lceil n/k\right\rceil$ n / ${\$ \ $displaystyle$ \ $lceil n$ / $k$ \ $rceil$ }의k $패킷$ 배열로 분할됩니다.그 후 패킷은 차례로 브로드캐스트되어 데이터가 통신 네트워크에서 빠르게 전달됩니다.

평형 바이너리 트리의 파이프라인 브로드캐스트는 ${\mathcal {O}}(\alpha \log p+\beta n)$ log ${\mathcal {O}}(\alpha \log p+\beta n)$ + ${\mathcal {O}}(\alpha \log p+\beta n)$ n ${\mathcal {O}}(\alpha \log p+\beta n)$ )({ $displaystyle {O}(alpha \log$ p $+\$ beta n ${\mathcal {O}}(\alpha \log p+\beta n)$ 에서 $가능합니다.$

줄이다

There are three squares vertically aligned on the left and three squares vertically aligned on the right. A circle with the letter f inside is placed between the two columns. Three solid lines connect the circle with the left three squares. One solid line connects the circle and the high right square. The letters a, b and c are written in the left squares from high to low. The letter alpha is written in the top right square.

3개의 노드에 대해 수행된 축소 작업의 정보 흐름입니다.f는 연관 연산자이고 α는 감소의 결과이다.

축소 패턴은 서로 다른 처리 단위에서 데이터 또는 부분 결과를 수집하여 선택한 연산자에 의해 전역 결과로 결합하는 데 사용됩니다.p $\displaystyle$ p_{i $p$ $}$ 처리단위가 $p$ 되면 $m_{i}$ $mi$ 는 처음에 $p_{i}$ $\$ }에 $p_{i}$ 있습니다.모든 $(\$ })는 $m_{i}$ $"\displaystyle\otimes"$ 에 $\otimes$ 의해 집계되며 $p_{0}$ 는 p 0 $(\$ 에 저장됩니다.감소 연산자 $\otimes$ {\(\ $displaystyle \otimes)$ 는 $\otimes$ 적어도 연관성이 있어야 합니다.일부 알고리즘에서는 중립 요소를 가진 교환 연산자가 필요합니다. $s$ $u$ m\ $displaystyle$ sum $sum$ , $m$ $i n$ \ $displaystyle$ min $min$ , $m$ $x$ \ $displaystyle$ max $max$ 와 같은 $sum$ 가 일반적입니다.

구현에 관한 고려사항은 브로드캐스트( broadcast Broadcast)와 유사합니다.바이너리 트리의 파이프라인의 경우 메시지는 컴포넌트별 축소를 위해 작은 객체의 벡터로 표시할 수 있어야 합니다.

평형 바이너리 트리의 파이프라인 감소는 ${\mathcal {O}}(\alpha \log p+\beta n)$ ( ${\mathcal {O}}(\alpha \log p+\beta n)$ ${\mathcal {O}}(\alpha \log p+\beta n)$ ${\mathcal {O}}(\alpha \log p+\beta n)$ + ${\mathcal {O}}(\alpha \log p+\beta n)$ n ) { $displaystyle {Mathcal {O}(alpha$ \ $log$ p $+\beta$ n ${\mathcal {O}}(\alpha \log p+\beta n)$ 에서 가능합니다.

올 리듀스

3개의 노드에서 수행된 All-Reduce 작업의 정보 흐름입니다.f는 연관 연산자이고 α는 감소의 결과이다.

all-reduce 패턴(allreduce라고도 함)은 축소 연산 결과(θ Reduce)를 모든 처리 장치에 배포해야 할 경우 사용됩니다.p $\displaystyle$ p_{i $p$ $}$ 처리단위가 $p$ 되면 $m_{i}$ $mi$ 는 처음에 $p_{i}$ $\$ }에 $p_{i}$ 있습니다.모든 $(\$ $displaystyle$ $m_{i$ })는 $m_{i}$ 연산자 $\otimes$ {\(\ $displaystyle$ \otimes $)$ 에 $\otimes$ 의해 집계되며, 그 $p_{i}$ 는 모든 $p_{i}$ (\ $displaystyle p_$ i})에 최종적으로 저장됩니다.리덕션 조작과 마찬가지로 연산자 $\otimes$ {\(\ $displaystyle \otimes)$ 는 $\otimes$ 적어도 관련성이 있어야 합니다.

all-reduce는 후속 브로드캐스트( broadcast Broadcast)에서의 축소 동작으로 해석할 수 있습니다.긴 메시지의 경우 대응하는 구현이 적합하지만 짧은 메시지의 경우 p $\display$ p가 $p$ 2의 거듭제곱인 $경우$ 하이퍼큐브 (Hypercube(통신 패턴) all All-Gather / All-Reduce) 토폴로지를 사용하여 지연을 줄일 수 있습니다.

O ${\mathcal {O}}(\alpha \log p+\beta n)$ ${\mathcal {O}}(\alpha \log p+\beta n)$ ${\mathcal {O}}(\alpha \log p+\beta n)$ ${\mathcal {O}}(\alpha \log p+\beta n)$ p ${\mathcal {O}}(\alpha \log p+\beta n)$ + $β$ n $)$ 에서는 감소 및 브로드캐스트가 가능하므로 O $($ $α log$ ${\mathcal {O}}(\alpha \log p+\beta n)$ p + $β$ ${\mathcal {O}}(\alpha \log p+\beta n)$ $n$ 에서는 O $($ $α log p$ p + ${\mathcal {O}}(\alpha \log p+\beta n)$ n $)$ 에서는 ${\mathcal {O}}(\alpha \log p+\beta n)$ 감소가 가능하다.

프리픽스-합계/스캔

3개의 노드에서 수행된 Prefix-Sum/Scan 작업의 정보 흐름입니다.연산자 +는 모든 연관 연산자가 될 수 있습니다.

프리픽스 합 또는 스캔 연산은 다른 처리 단위에서 데이터 또는 부분 결과를 수집하고 연산자에 의한 중간 결과를 계산하기 위해 사용되며, 이러한 처리 단위에 저장됩니다.환원 연산( reduce Reduced)의 일반화라고 볼 수 있다.p $\displaystyle$ p_{i $p$ $}$ 처리단위를 $p$ 하면 $m_{i}$ $mi$ 는 $p_{i}$ $\$ 에 있습니다.연산자 $"\displaystyle\otimes"$ 는 $\otimes$ 적어도 연관성이 있어야 하며, 일부 알고리즘에는 교환 연산자와 중립 요소도 필요합니다.일반 사업자 ⊗ 나는}{\displaystyle m_{나는 '}′<>)나는}{\displaystyle \otimes_{i'<, =i}m나는′m{\displaystyle 합}, 너 나 그냥 x{맥스\displaystyle}m. 나는{\displaystyle p_{나는}결국 처리 장치 p}{\displaystyle분}의 스녀 mso-calle의 경우 접두사 합을 저장합니다의 있다.dexclusive prefix sum, processing $p_{i}$ $pi$ {\ $displaystyle$ p_ $p_{i}$ ${$ $i$ }}는 $\otimes _{i'<i}$ prefix sum ' $\otimes _{i'<i}$ < $\otimes _{i'<i}$ { $displaystyle$ $\otimes$ _ { $i'}$ ${\$ {\ 。알고리즘에 따라서는 prefix sum 외에 각 처리 유닛에 합계도 저장해야 합니다.

단문 메시지의 경우 p $\displaystyle$ p가 $p$ 2의 거듭제곱인 $경우$ 하이퍼큐브 토폴로지로 이를 달성할 수 있습니다.긴 메시지의 경우 하이퍼큐브(Hypercube(통신 패턴)) prefix프리픽스 합계, 프리픽스 합계 distrib분산 메모리: 하이퍼큐브 알고리즘) 토폴로지는 모든 처리 장치가 모든 단계에서 활성화되어 파이프라이닝을 사용할 수 없기 때문에 적합하지 않습니다.바이너리 트리 토폴로지는 $p$ 의 p $\displaystyle$ p $}$ 및 $p$ 긴 메시지(프리픽스 합계 large 대용량 메시지 크기: 파이프라인 바이너리 트리)에 적합합니다.

바이너리 트리의 프리픽스 합은 상향 및 하향 위상으로 구현할 수 있습니다.상향 위상 감소는 하향 위상이 방송과 비슷하지만, 좌우 자녀에게 다른 데이터를 송신해 프리픽스 합계를 산출한다.이 어프로치에서는, 파이프 라이닝이 가능하게 됩니다.이것은, 조작이 삭감( reduce Reduce) 및 브로드캐스트( broadcast Broadcast)와 같기 때문입니다.

바이너리 트리의 파이프라인 프리픽스 합계는 O ${\mathcal {O}}(\alpha \log p+\beta n)$ log ${\mathcal {O}}(\alpha \log p+\beta n)$ + ${\mathcal {O}}(\alpha \log p+\beta n)$ n ${\mathcal {O}}(\alpha \log p+\beta n)$ )({ $displaystyle {O}(alpha \log$ p $+\beta$ n ${\mathcal {O}}(\alpha \log p+\beta n)$ 로 $가능합니다.$

장벽

장벽은 분산 컴퓨팅에서 사용할 수 있는 장벽 개념의 일반화입니다.처리 장치가 장벽을 호출하면 다른 모든 처리 장치도 장벽을 호출할 때까지 기다립니다.따라서 장벽은 분산 컴퓨팅에서 글로벌 동기화를 달성하기 위해 사용됩니다.

장벽을 구현하는 방법 중 하나는 빈 피연산자/더미 피연산자를 사용하여 All-Reduce(uce All-Reduce)를 호출하는 것입니다.All-reduce의 실행 ${\mathcal {O}}(\alpha \log p+\beta n)$ 은 ${\mathcal {O}}(\alpha \log p+\beta n)$ O( ${\mathcal {O}}(\alpha \log p+\beta n)$ ${\mathcal {O}}(\alpha \log p+\beta n)$ ${\mathcal {O}}(\alpha \log p+\beta n)$ + ${\mathcal {O}}(\alpha \log p+\beta n)$ n ${\mathcal {O}}(\alpha \log p+\beta n)$ ) { $displaystyle$ {O $}($ alpha $\log p+\beta$ n ${\mathcal {O}}(\alpha \log p+\beta n)$ 입니다.더미 피연산자를 사용하면 $크기$ n(\ $displaystyle$ n $)$ 이 $n$ 상수 계수로 축소되고 ${\mathcal {O}}(\alpha \log p)$ ( ${\mathcal {O}}(\alpha \log p)$ ${\mathcal {O}}(\alpha \log p)$ p $)$ {o $} \style$ p}(\ $log p}$ \ $style).$

모으다

There are three squares vertically aligned on the left and three rectangles vertically aligned on the right. A dotted line connects the high left square with the high right rectangle. Two solid lines connect the mid and low left squares with the high right rectangle. The letters a, b and c are written in the left squares from high to low. The letters a, b and c are written in the high right rectangle in a row.

3개의 노드에서 수행된 Gather 작업의 정보 흐름입니다.

수집 통신 패턴은 모든 처리 장치의 데이터를 단일 처리 장치에 저장하는 데 사용됩니다. $\displaystyle$ p_{i $p$ $m_{i}$ $}$ $p_{i}$ 의 $m_{i}$ $mi\displaystyle$ p_{ $i$ $p_{j}$ $p_{j}$ {\ $displaystyle p_{$ j $p_{j}$ 의 $m_{1}\cdot m_{2}\cdot \ldots \cdot m_{p}$ $m_{1}\cdot m_{2}\cdot \ldots \cdot m_{p}$ m1 $m_{1}\cdot m_{2}\cdot \ldots \cdot m_{p}$ $m_{1}\cdot m_{2}\cdot \ldots \cdot m_{p}$ $m_{1}\cdot m_{2}\cdot \ldots \cdot m_{p}$ … $m_{1}\cdot m_{2}\cdot \ldots \cdot m_{p}$ m ${$ $displaystyle m_1 }$ \ $cdots$ \ cdots } \ cdots 。 $p_{j}$ {\ $displaystyle p_{$ j $p_{j}$ gather는 연결 연산자를 사용하는 축소 연산자( reduce Reduce)로 간주할 수 있습니다.이것은 연결은 연관성이 있기 때문에 작동합니다.동일한 이항 트리 감소 알고리즘을 사용하면 O $(α$ log $p$ + ${\mathcal {O}}(\alpha \log p+\beta pn)$ $pn$ $)$ 의 ${\mathcal {O}}(\alpha \log p+\beta pn)$ 런타임을 얻을 수 있다. 점근 런타임이 ${\mathcal {O}}(\alpha \log p+\beta n)$ O $α log$ + ${\mathcal {O}}(\alpha \log p+\beta pn)$ ${\mathcal {O}}(\alpha \log p+\beta n)$ n $)$ 의 점근 $런타임$ 과 유사함을 알 수 $있다.$ 인수 p를 $\beta n$ $\beta n$ n(\ $displaystyle\displayn$ 에 부가합니다.이 추가 요인은 메시지가 연결됨에 따라 각 단계에서 메시지 크기가 증가하기 때문입니다.이를 비교하여 메시지 $크기$ 가 mi n $\displaystyle$ min과 $같은$ 연산자의 상수인 경우 이를 줄입니다.

총집합

There are three squares vertically aligned on the left and three rectangles vertically aligned on the right. Three dotted lines connect the high left square with the high right rectangle, the mid left square with the mid right rectangle and the low left square with the low right rectangle. Two solid lines connect the mid and low left squares with the high right rectangle. Two solid lines connect the high and low left squares with the mid right rectangle. Two solid lines connect the high and mid left squares with the low right rectangle. The letters a, b and c are written in the left squares from high to low. The letters a, b and c are written in all right rectangles in a row.

3개의 노드에서 수행된 All-Gather 작업의 정보 흐름입니다.

전체 수집 통신 패턴은 모든 처리 장치에서 데이터를 수집하고 수집된 데이터를 모든 처리 장치에 저장하는 데 사용됩니다. $p_{i}$ { $display$ $style$ $p$ $_$ { i $p$ $p_{i}$ } 、 $m_{i}$ $m_{i}$ i { $displaystyle$ m $p_{i}$ $_$ { $m_{i}$ $i$ } $p_{i}$ 、 m $m_{1}\cdot m_{2}\cdot \ldots \cdot m_{p}$ $m_{1}\cdot m_{2}\cdot \ldots \cdot m_{p}$ m m $m_{1}\cdot m_{2}\cdot \ldots \cdot m_{p}$ p { $displaystyle$ m _ { 1 } \ $cdot m$ _ { 2 } $m_{1}\cdot m_{2}\cdot \ldots \cdot m_{p}$ p p p m p { $cdot$ _ $cdots$ } $p_{j}$ the theinginging m $m_{1}\cdot m_{2}\cdot \ldots \cdot m_{p}$ p p p p p p m j the the the m j m j the the p p p p p p p p the the m j m given the the the the m j m given given given given p p p $laystyle p_{j$ 입니다.

그것은 여러 가지로 생각할 수 있다.첫 번째는 연산자와 연결된 전체 감소 연산(θ All-Reduce)으로서, 수집이 감소로 표현될 수 있는 것과 같은 방법입니다.두 번째는 수집 조작에 이어 $pn$ 의 $pn$ 새 메시지 브로드캐스트입니다. 이를 통해 O ${\mathcal {O}}(\alpha \log p+\beta pn)$ log $⁡$ + ${\mathcal {O}}(\alpha \log p+\beta pn)$ ${\mathcal {O}}(\alpha \log p+\beta pn)$ n $)(\displaystyle {O}(\alpha \log$ p $+\beta$ pn $))$ 의 ${\mathcal {O}}(\alpha \log p+\beta pn)$ 올 수집이 가능합니다.

흩어지다

There are three rectangles vertically aligned on the left and three squares vertically aligned on the right. A dotted line connects the high left rectangle with the high right square. Two solid lines connect the high left rectangle with the mid and low right squares. The letters c, b and a are written in the high left rectangle in a row. The letters a, b and c are written in the right right squares from high to low.

3개의 노드에서 수행된 산란 작업의 정보 흐름입니다.

산란 통신 패턴은 하나의 처리 장치에서 모든 처리 장치로 데이터를 분배하는 데 사용됩니다.브로드캐스트와 다른 점은 모든 처리 장치에 동일한 메시지를 보내지 않는다는 점입니다.대신 메시지를 분할하여 그 일부를 각 처리 장치에 전달합니다.

$p$ { $display$ $style$ $p$ { i $}$ $p_{i}$ $p_{j}$ 、 $m=m_{1}\cdot m_{2}\cdot \ldots \cdot m_{p}$ $m=m_{1}\cdot m_{2}\cdot \ldots \cdot m_{p}$ $m=m_{1}\cdot m_{2}\cdot \ldots \cdot m_{p}$ $m=m_{1}\cdot m_{2}\cdot \ldots \cdot m_{p}$ $m=m_{1}\cdot m_{2}\cdot \ldots \cdot m_{p}$ $m=m_{1}\cdot m_{2}\cdot \ldots \cdot m_{p}$ … $m=m_{1}\cdot m_{2}\cdot \ldots \cdot m_{p}$ p { $display style$ m = $m_{1}\cdot m_{2}\cdot \ldots$ \ $cdot m_{p}$ } $m_{i}$ {\ {\ {\ $m_{i}$ m m m m m m m m the the the the the the the the the the the the the the the the the the the the the the the the the the the the the the $p_{j}$ the the p p j j the the ${\$ {\ {\ {\ {\ {\ {\ ${\$ j j j j j j j j j j $p_{i}$ 에 $p_{i}$ i $p_{i}$ Gather( gather Gather)와 같은 구현 문제가 적용됩니다.이를 통해 O ${\mathcal {O}}(\alpha \log p+\beta pn)$ log ${\mathcal {O}}(\alpha \log p+\beta pn)$ + ${\mathcal {O}}(\alpha \log p+\beta pn)$ p ${\mathcal {O}}(\alpha \log p+\beta pn)$ ) { $displaystyle {Mathcal {O}(alpha \log$ p $+\beta$ pn ${\mathcal {O}}(\alpha \log p+\beta pn)$ 에서 ${\mathcal {O}}(\alpha \log p+\beta pn)$ 의 실행 시간이 생성됩니다.

올투올

올투올은 가장 일반적인 커뮤니케이션 패턴입니다. ${\displaystyle 0\leq i,j0<semantics><mrow class=$ i ${\displaystyle 0\leq i,j<semantics><mrow class=$ ${\displaystyle 0\leq i,j<semantics><mrow class=$ < \ ${\displaystyle 0\leq i,j<semantics><annotation encoding=$ \ ${\displaystyle 0\leq i,j<semantics><annotation encoding=$ , ${\displaystyle 0\leq i,j<semantics><annotation encoding=$ < p ${\displaystyle 0\leq i,j </math></span><img alt=$ $예$ 를 들어 $p_{k}$ $p_{k}$ 로부터의 $메시지$ m { $displaystyle$ $p_$ ${k$ $}$ 의 $m$ $p_{k}$ 브로드캐스트는 i $m_{i,j}=m$ $i=k$ $= k$ = $i=k$ = $m$ $m_{i,j}=m$ } $setting$ 、 $m_{l,j}$ $m_{i,j}=m$ $m_{l,j}$ , $m_{l,j}$ 、 j \ $displaystyle m$ _ { l $m_{l,j}$ , $j$ } $l\neq k$ $l\neq k$ 、 l $l\neq k$ l $m_{l,j}$ for for for k $、$ j \ $displaystyle$ l . $neq$ 。

네트워크가 완전히 연결되어 있다고 가정할 때 All-to-all에 가장 적합한 실행시간은 ${\mathcal {O}}(p(\alpha +\beta n))$ ( ${\mathcal {O}}(p(\alpha +\beta n))$ ( ${\mathcal {O}}(p(\alpha +\beta n))$ + ${\mathcal {O}}(p(\alpha +\beta n))$ n ${\mathcal {O}}(p(\alpha +\beta n))$ ) \ $displaystyle$ {\ $mathcal {O}$ （ ${\mathcal {O}}(p(\alpha +\beta n))$ p ( \alpha + \ $beta$ n ) ${\mathcal {O}}(p(\alpha +\beta n))$ ）。 $이는$ p\ $displaystyle$ p의 $p$ 다이렉트메시지 교환을 $통해$ 실현됩니다.p $(\displaystyle$ p $)$ 의 $p$ 2승의 $경우$ 통신 $라운드$ k(\ $displaystyle$ k $)$ 에서 $p_{i}$ $(\$ })는 $p_{i}$ $p_{j},j=i\oplus k$ $p_{j},j=i\oplus k$ j $p_{j},j=i\oplus k$ $p_{j},j=i\oplus k$ $p_{j},j=i\oplus k$ $(\displaystyle p_{j},j=i\oplus$ k}) $p_{j},j=i\oplus k$ 와 메시지를 교환합니다.

메시지 크기가 작고 지연이 통신을 지배하는 경우 하이퍼 큐브알고리즘을 사용하여 ${\mathcal {O}}(\log p(\alpha +\beta pn))$ O ${\mathcal {O}}(\log p(\alpha +\beta pn))$ ⁡ ${\mathcal {O}}(\log p(\alpha +\beta pn))$ ( ${\mathcal {O}}(\log p(\alpha +\beta pn))$ + ${\mathcal {O}}(\log p(\alpha +\beta pn))$ ${\mathcal {O}}(\log p(\alpha +\beta pn))$ n $)\displaystyle {O}$ (\ $log$ p $(\$ alpha +\ $beta$ pn))}) ${\mathcal {O}}(\log p(\alpha +\beta pn))$ 내에 메시지를 배포할 수 있습니다.

There are three rectangles vertically aligned on the left and three rectangles vertically aligned on the right. The rectangles are three time higher as wide. The terms a1, a2 and a3 are written in the high left rectangle one below the other. The terms b1, b2 and b3 are written in the mid left rectangle one below the other. The terms c1, c2 and c3 are written in the low left rectangle one below the other. The terms a1, b1 and c1 are written in the high right rectangle one below the other. The terms a2, b2 and c2 are written in the mid right rectangle one below the other. The terms a3, b3 and c3 are written in the low right rectangle one below the other. A dotted line connects a1 from the high left rectangle and a1 from the high right rectangle. A dotted line connects b2 from the mid left rectangle and b2 from the mid right rectangle. A dotted line connects c3 from the low left rectangle and c3 from the low right rectangle. Solid lines connect the other corresponding terms between the left and right rectangles.

3개의 노드에서 수행된 All-to-All 작업의 정보 흐름입니다.문자는 노드를 나타내고 숫자는 정보 항목을 나타냅니다.

런타임의 개요

이 표에서는 네트워크토폴로지를 자유롭게 선택할 수 있다고 가정하여 가장 잘 알려진 점근 런타임에 대한 개요를 나타냅니다.

최적의 런타임에 필요한 토폴로지의 예로는 바이너리 트리, 이항 트리, 하이퍼 큐브가 있습니다.

실제로 우리는 이용 가능한 물리적 토폴로지에 맞춰야 합니다. 예를 들어 잠자리, 팻 트리, 그리드 네트워크(다른 토폴로지도 참조).

자세한 내용은 네트워크토폴로지를 참조해 주세요.

각 동작에 대해 최적의 알고리즘은 입력 $크기$ n ${displaystyle$ n $n$ 에 따라 달라질 수 있습니다.예를 들어, 짧은 메시지의 브로드캐스트는 이항 트리를 사용하여 구현되는 것이 가장 좋은 반면 긴 메시지의 경우 균형 잡힌 이진 트리의 파이프라인 통신이 최적입니다.

표에 기재된 복잡도는 처리단위 $p$ 의 $수$ 및 노드 $n$ 의 $입력메시지$ 크기 외에 $\alpha$ $displaystyle$ \alpha $\alpha$ $n$ 와 $p$ 워드당 $\beta$ 통신비용β $(\$ $displaystyle$ $\$ $beta)$ 에 $\beta$ 따라 달라집니다.# senders 열과 # receivers 열은 각각 작업에 관련된 송신자 및 수신자의 수를 나타냅니다.# messages 열에는 입력 메시지 수와 Computations가 표시됩니다.컬럼은 메시지에 대한 계산이 수행되었는지 또는 메시지가 처리되지 않고 전달되었는지 여부를 나타냅니다.복잡성은 토폴로지의 자유로운 선택 하에 최적의 구현의 점근적 런타임 복잡성을 제공합니다.


이름.	송신자수	리시버 수	메시지 수	계산?	복잡성
브로드캐스트	$1$	$p$	$1$	아니요.	${\displaystyle {O}}(\alpha \log p+\beta n)$
줄이자	$p$	$1$	$p$	네.	${\displaystyle {O}}(\alpha \log p+\beta n)$
모두 감소	$p$	$p$	$p$	네.	${\displaystyle {O}}(\alpha \log p+\beta n)$
프리픽스 합계	$p$	$p$	$p$	네.	${\displaystyle {O}}(\alpha \log p+\beta n)$
장벽	$p$	$p$	$0$	아니요.	${O}}(\alpha \log p)$
모이다	$p$	$1$	$p$	아니요.	${O}}(\alpha \log p+\beta pn)$
총집합	$p$	$p$	$p$	아니요.	${O}}(\alpha \log p+\beta pn)$
흩어지다	$1$	$p$	$p$	아니요.	${O}}(\alpha \log p+\beta pn)$
올투올	$p$	$p$	$p^{2}$	아니요.	${\mathcal {O}}(\log p(\alpha +\beta pn))$ ( log ${\mathcal {O}}(\log p(\alpha +\beta pn))$ ( ${\mathcal {O}}(\log p(\alpha +\beta pn))$ $α$ + $β$ ${\mathcal {O}}(\log p(\alpha +\beta pn))$ { $displaystyle$ \ $mathcal$ { $O$ } （ \ $log$ p ( \ $alpha$ + \ $beta$ pn ) } ${\mathcal {O}}(p(\alpha +\beta n))$ o O ( $α$ + ${\mathcal {O}}(p(\alpha +\beta n))$ n ) ${\mathcal {O}}(p(\alpha +\beta n))$ ）、、 $displaystyle$ \ $mathcal$ { $O （$ \ alpha + \ $beta$ n ${\mathcal {O}}(p(\alpha +\beta n))$ ）））。

메모들

^ 인터커뮤니케이터 일괄 운용MPI(Message Passing Interface) 표준, 7.3.1장.아르곤 국립 연구소 수학 및 컴퓨터 과학 부서.
^ Sanders, Melhorn, Dietzfelbinger, Dementiev 2019, 페이지 395
^ 샌더스, 멜혼, 디츠펠빙거, 데멘티예프 2019, 페이지 396-401
^ 샌더스, 멜혼, 디츠펠빙거, 데멘티예프 2019, 페이지 402-403
^ 샌더스, 멜혼, 디츠펠빙거, 데멘티예프 2019, 페이지 403-404
^ 샌더스, 멜혼, 디츠펠빙거, 데멘티예프 2019, 페이지 404-406
^ Sanders, Melhorn, Dietzfelbinger, Dementiev 2019, 페이지 408
^ ^a ^b Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, 페이지 412-413
^ Sanders, Melhorn, Dietzfelbinger, Dementiev 2019, 페이지 413
^ Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, 페이지 413-418
^ Sanders, Melhorn, Dietzfelbinger, Dementiev 2019, 페이지 394

레퍼런스

Sanders, Peter; Mehlhorn, Kurt; Dietzfelbinger, Martin; Dementiev, Roman (2019). Sequential and Parallel Algorithms and Data Structures - The Basic Toolbox. Springer Nature Switzerland AG. ISBN 978-3-030-25208-3.

[1] 인터커뮤니케이터 일괄 운용MPI(Message Passing Interface) 표준, 7.3.1장.아르곤 국립 연구소 수학 및 컴퓨터 과학 부서.

[:1-2] Sanders, Melhorn, Dietzfelbinger, Dementiev 2019, 페이지 395

[:2-3] 샌더스, 멜혼, 디츠펠빙거, 데멘티예프 2019, 페이지 396-401

[:3-4] 샌더스, 멜혼, 디츠펠빙거, 데멘티예프 2019, 페이지 402-403

[:4-5] 샌더스, 멜혼, 디츠펠빙거, 데멘티예프 2019, 페이지 403-404

[:5-6] 샌더스, 멜혼, 디츠펠빙거, 데멘티예프 2019, 페이지 404-406

[:6-7] Sanders, Melhorn, Dietzfelbinger, Dementiev 2019, 페이지 408

[:7-8] Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, 페이지 412-413

[:8-9] Sanders, Melhorn, Dietzfelbinger, Dementiev 2019, 페이지 413

[:9-10] Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, 페이지 413-418

[:10-11] Sanders, Melhorn, Dietzfelbinger, Dementiev 2019, 페이지 394

[1]

[2]

Search