프리픽스 합계

컴퓨터 과학에서, 프리픽스 합계, 누적 합계, 스캔, 또는 단순히 일련의 $숫자 0$ x $, x 1 2,$ x $,$ ...의 스캔은 입력 시퀀스의 프리픽스 합계(실행 합계)인 y, $y 1 2,$ y, $...$ 의₀ 두 번째 시퀀스입니다.

y 0 = x 0

y 1 = x 0 + x 1

y 2 = x 0 + x 1 + x 2

...

예를 들어, 자연수의 프리픽스 합계는 삼각수입니다.

입력 번호	1	2	3	4	5	6	...
접두사 합계	1	3	6	10	15	21	...

접두사 $합계$ 는_{i − 1} $y i$ = y + x $공식$ 을_i 사용하여 각 출력 값을 순차적으로 계산하여 계산하기 쉽습니다.그러나 계산의 용이함에도 불구하고 프리픽스 합계는 카운트 ^[1]^[2]정렬과 같은 특정 알고리즘에서 유용한 원시이며 기능 프로그래밍 언어에서 스캔 고차 함수의 기초를 형성합니다.프리픽스 합계는 또한 병렬 알고리즘에서 해결해야 할 테스트 문제로서 그리고 다른 병렬 ^[3]^[4]^[5]알고리즘에서 서브루틴으로 사용되는 유용한 프리미티브로서 많이 연구되어 왔다.

추상적으로 프리픽스 합은 2진수 대응 연산자 θ만을 필요로 하기 때문에 포인트의 잘 분리된 쌍 분해 계산부터 문자열 ^[6]^[7]처리에 이르기까지 많은 응용 프로그램에서 유용하다.

수학적으로 프리픽스 합계를 취하는 연산은 유한 시퀀스에서 무한 시퀀스로 일반화할 수 있습니다.이 문맥에서 프리픽스 합계는 급수의 부분 합계로 알려져 있습니다.접두사 합산 또는 부분 합산은 유한 또는 무한 시퀀스의 벡터 공간에서 선형 연산자를 형성합니다. 그 역수는 유한 차분 연산자입니다.

고차 스캔 기능

기능 프로그래밍 용어로 프리픽스 합은 임의의 2진수 연산(더하기 연산뿐만 아니라)으로 일반화 될 수 있다.이 일반화로부터 생기는 고차 함수를 스캔이라고 하며, 폴드 연산과 밀접하게 관련되어 있다.스캔 연산과 폴드 연산 모두 주어진 이진 연산을 동일한 값의 시퀀스에 적용하지만 스캔이 이진 연산의 전체 결과 시퀀스를 반환하는 반면 폴드는 최종 결과만 반환한다는 점에서 다릅니다.예를 들어, 요인 번호의 시퀀스는 덧셈 대신 곱셈을 사용하여 자연수를 스캔하여 생성할 수 있습니다.

입력 번호	1	2	3	4	5	6	...
프리픽스 제품	1	2	6	24	120	720	...

포괄적 및 배타적 검사

프로그래밍 언어 및 라이브러리 검색 구현은 포함 또는 배타적일 수 있습니다.출력 $y i$ (예: $y_{i}=\bigoplus _{j=0}^{i}x_{j}$ i $y_{i}=\bigoplus _{j=0}^{i}x_{j}$ $y_{i}=\bigoplus _{j=0}^{i}x_{j}$ j $y_{i}=\bigoplus _{j=0}^{i}x_{j}$ $y_{i}=\bigoplus _{j=0}^{i}x_{j}$ $y_{i}=\bigoplus _{j=0}^{i}x_{j}$ $y_{i}=\bigoplus _{j=0}^{i}x_{j}$ {i $}$ \ $bigoplus$ _ { j $y_{i}=\bigoplus _{j=0}^{i}x_{j}$ = $0$ }^{i}^{i} $x_{j$ 를 계산할 때 포함된 스캔에는 $입력 i$ x가 포함되지만, 배타적 스캔에는 포함되지 않습니다( $y_{i}=\bigoplus _{j=0}^{i-1}x_{j}$ : $y_{i}=\bigoplus _{j=0}^{i-1}x_{j}$ $y_{i}=\bigoplus _{j=0}^{i-1}x_{j}$ 0 - $y_{i}=\bigoplus _{j=0}^{i-1}x_{j}$ $y_{i}=\bigoplus _{j=0}^{i-1}x_{j}$ $display$ y = $0$ - 1 x display $y_{i}=\bigoplus _{j=0}^{i-1}x_{j}$ { $i}).$ 후자의 경우 구현은 y를 정의되지 않은 $상태$ 로₀ 두거나 별도의 " $x -1$ " 값을 사용하여 검색을 시드합니다.어느 타입의 스캔도 다른 타입의 스캔으로 변환할 수 있습니다.포함 스캔은 스캔에 의해 생성된 어레이를 한 요소만 이동시키고 어레이 왼쪽에 ID 값을 삽입함으로써 전용 스캔으로 변환할 수 있습니다.반대로 스캔에 의해 생성된 어레이를 왼쪽으로 이동하고 스캔의 마지막 요소와 입력 어레이의 마지막 요소의 합을 ^[8]어레이 오른쪽에 삽입함으로써 배타적 스캔을 포함 스캔으로 변환한다.

다음 표에는 몇 가지 프로그래밍 언어 및 라이브러리에서 제공하는 포함 및 배타적 스캔 기능의 예가 나와 있습니다.

언어/도서관	포괄적 스캔	전용 스캔
APL	`+\`
하스켈	`scanl1`	`scanl`
MPI	`MPI_Scan`	`MPI_Exscan`
C++	`std::inclusive_scan`	`std::exclusive_scan`
스칼라	`scan`
녹	`scan`

병렬 알고리즘

프리픽스 합계를 병렬로 계산하기 위한 두 가지 주요 알고리즘이 있습니다.첫 번째는 짧은 스팬과 병렬성을 제공하지만 작업 효율은 낮습니다.두 번째는 작업 효율이 높지만 두 배의 스팬이 필요하고 병렬 처리도 적습니다.이것들은 다음에 차례로 제시된다.

알고리즘 1: 짧은 스팬, 더 병렬

고병렬 16 입력 병렬 프리픽스 합계의 회로 표현

Hillis와 Steel은 다음 병렬 프리픽스 합계 ^[9]알고리즘을 제공합니다.

위해서

i\gets 0

로.

\displaystyle \lceil \log _{2}n\rceil -1}

하다

위해서

j\gets 0

로.

n-1

병행하여 하다

한다면

j<2^{i}}

그리고나서

x_{j}^i+1}\gets x_{j}^i

또 다른

x_{j}^{i+1}\gets x_{j}^{i}+x_{j-2^{i}^{i}}^{i}

여기서 $x_{j}^{i}$ i(\ $displaystyle x_{j}^i})$ 는 $x_{j}^{i}$ $timesep$ i에서의 $배열$ x의 j번째 요소의 값을 의미한다.

1개의 프로세서에서는 이 알고리즘은 O( $nlog$ n $)$ 시간 $내$ 에 실행됩니다.단, 이너 루프를 병렬로 실행하는 프로세서가 $적어도$ n개 있는 경우 알고리즘은 전체적으로 아우터 루프의 반복 횟수인 $O$ ( $log$ n $)$ 시간 $내$ 에 실행된다.

알고리즘 2: 효율적인 작업

효율적인 16 입력 병렬 프리픽스 합계의 회로 표현

작업 효율이 뛰어난 병렬 프리픽스 합계는 다음 ^[3]^[10]^[11]단계로 계산할 수 있습니다.

z = x + x, $z 1 1 = x 0 2$ + $x 3$ $등$ 의₀ 짝수 지수를 갖는 연속된 항목 쌍들의 합계를 계산합니다.
$시퀀스 0$ z $, z 1$ , $z 2$ , z $,$ ...의 접두사 $합계 0$ w $, w 1$ , $w 2,$ ...를 재귀적으로 계산합니다.
y = $x 1,$ $y 2 =$ $z 0 0$ , $y 2$ = z, y = $z 0$ + $x 2$ , $y 1 3$ = w 등 $중간 0$ 시퀀스의 최대 두 항의 합으로 최종 $시퀀스 0$ y, y, y, y, y, ...의₁ 각 항을 표현합니다.첫 번째 값 이후, 각 $연속수 i$ $y$ 는 w계열의 절반까지의 위치에서 복사되거나 $x계열$ 의 한 값에 이전 값이 가산된다.

입력 시퀀스에 n개의 스텝이 $있는$ 경우 재귀는 O $(log$ n $)$ $깊이$ 까지 계속됩니다.이것은 이 알고리즘의 병행 실행 시간에 대한 바인딩이기도 합니다.알고리즘의 스텝 수는 O $(n)$ 이며 ^[3]프로세서보다 요소가 많은 알고리즘 라운드에서 각 프로세서에 여러 인덱스를 할당함으로써 점근적 감속 없이 O $(n / log$ n $)$ 프로세서를 $갖춘$ 병렬 랜덤 액세스 머신에 구현할 수 있습니다.

논의

위의 각 알고리즘은 O $(log$ n $)$ 시간으로 $실행$ 됩니다.단, 전자는 정확히 $로그 2$ n개의 스텝을 실행하는데 반해 후자는 $2개$ 의₂ 로그 n - $2개의 스텝$ 이 필요합니다.그림 16 입력의 예에서는 알고리즘1은 12방향 병렬(49단위 작업스팬 4로 나누기)이지만 알고리즘2는 4방향 병렬(26단위 작업스팬 6으로 나누기)에 불과합니다.단, 알고리즘2는 작업 효율적입니다.알고리즘1은 작업 효율이 낮지만 순차적으로 필요한 작업량보다 점근적으로 많은 작업량(대수 계수)을 수행합니다.따라서 Algorithm 1은 충분한 병렬성을 이용할 수 있을 때 성능이 향상되지만 Algorithm 2는 병렬성이 제한될 때 성능이 향상됩니다.

프리픽스 합계의 병렬 알고리즘은 종종 관련 바이너리 ^[3]^[4]연산의 다른 스캔 연산에 일반화할 수 있으며 ^[12]GPU와 같은 최신 병렬 하드웨어에서도 효율적으로 계산할 수 있습니다.다중 파라미터 프리픽스 합 계산 전용 기능 유닛을 하드웨어에 구축하는 아이디어는 Uzi Vishkin에 ^[13]의해 특허되었습니다.

많은 병렬 구현에서는 각 처리 장치의 첫 번째 패스로 부분 프리픽스 합계가 계산되는 2패스 절차를 따릅니다.그 후 이들 부분 프리픽스 합계가 계산되어 현재 알려진 프리픽스를 초기 값으로 사용하여 두 번째 패스를 위해 처리 장치에 브로드캐스트됩니다.점근적으로 이 방법은 항목당 약 2개의 읽기 작업과 1개의 쓰기 작업이 필요합니다.

프리픽스 합계 알고리즘의 구체적인 실장

병렬 프리픽스 합계 알고리즘의 실장은 다른 병렬 알고리즘과 마찬가지로 플랫폼의 병렬화 아키텍처를 고려해야 합니다.보다 구체적으로 말하면, 공유 메모리에서 동작하는 플랫폼에 적합한 알고리즘과 프로세스 간 통신의 유일한 형태로서 메시지 전달에 의존하는 분산 메모리를 사용하는 플랫폼에 적합한 알고리즘이 여러 개 존재합니다.

공유 메모리:2레벨 알고리즘

다음 알고리즘은 공유 메모리머신 모델을 전제로 하고 있습니다.모든 Processing Element(PE; 프로세싱 엘리먼트)가 같은 메모리에 액세스 할 수 있습니다.이 알고리즘의 버전은 Multi-Core Standard Template Library(MCSTL;^[14]^[15] 멀티코어 표준 템플릿 라이브러리)에 구현됩니다.MCSTL은 다양한 알고리즘의 병렬 컴퓨팅에 적합한 버전을 제공하는 C+ 표준 템플릿 라이브러리의 병렬 구현입니다.

p ${\$ $displaystyle$ p $}$ 처리 $n$ $p$ 요소를 $p$ 하여 n개의 $데이터$ 요소에 $대한$ 프레픽스 합계를 동시에 계산하기 위해 데이터는 $p+1$ p + $p+1$ (\ $displaystyle$ p $+1$ ) $p+1$ 으로 $p+1$ 분할되며 각 ${\frac {n}{p+1}}$ 은 ${\frac {n}{p+1}}$ 의 ${\frac {n}{p+1}}$ p + ${\frac {n}{p+1}}$ (\ $displaystyle {n}{p+1})$ 요소를 포함합니다 ${\frac {n}{p+1}}$ (간단히 하기 위해 $p+1$ p + $1$ 이라고 $p+1$ 합니다). $style$ p $+1}$ 은 $p+1$ $n을 나눕니다.$ 이 알고리즘은 데이터를 p $p+1$ + $(\displaystyle$ p $+1)$ 으로 $p+1$ 분할하지만 동시에 병렬로 실행되는 처리 $p$ $p$ 는p(\ $displaystyle$ p $)$ 뿐입니다.

첫 번째 스위프에서는 각 PE는 블록의 로컬프리픽스 합계를 계산합니다.마지막 블록은 계산할 필요가 없습니다.이러한 프리픽스 합계는 후속 블록의 프리픽스 합계에 대한 오프셋으로만 계산되며 마지막 블록은 정의상 성공하지 못하기 때문입니다.

$각$ 블록의 마지막 위치에 저장된 p $\displaystyle$ p 오프셋은 $p$ 자체 프리픽스 합계로 누적되어 다음 위치에 저장됩니다.p $\displaystyle$ p가 작은 수치인 $p$ $경우$ 순차적으로 실행하는 것이 빠르며, $큰$ p $\displaystyle$ p에 대해서도 $p$ 이 단계를 병렬로 수행할 수 있습니다.

두 번째 스위프가 수행됩니다.이 경우 첫 번째 블록은 이전 블록의 오프셋을 고려할 필요가 없기 때문에 처리할 필요가 없습니다.그러나 이 스위프에서는 마지막 블록이 대신 포함되며 이전 스위프에서 계산된 프레픽스 합계 블록 오프셋을 고려하여 각 블록의 프레픽스 합계가 계산됩니다.

기능. prefix_sum(요소들) {     n := 크기(요소들)     p := 번호 의 처리. 요소들     prefix_sum := [0...0] 의 크기 n          하다 평행한 i = 0 로. p-1 {         // i : = 현재 PE 인덱스         부터 j = i * n / (p+1) 로. (i+1) * n / (p+1) - 1 하다 {             // 로컬블록의 프리픽스 합계만 저장됩니다.             store_sum_with_sum_in(요소들, 0, prefix_sum)         }     }          x = 0          위해서 i = 1 로. p {                        // 블록의 총합 시리얼 누계         x +=  prefix_sum[i * n / (p+1) - 1] // 첫 번째 p개 블록에 대한 프레픽스 합계를 작성합니다.         prefix_sum[i * n / (p+1)] = x       // 두 번째 스위프에서 오프셋으로 사용할 결과 저장     }          하다 평행한 i = 1 로. p {         // i : = 현재 PE 인덱스         부터 j = i * n / (p+1) 로. (i+1) * n / (p+1) - 1 하다 {             오프셋 := prefix_sum[i * n / (p+1)]             // 이전 블록의 합계를 오프셋으로 하여 프리픽스 합계를 계산합니다.             store_sum_with_sum_in(요소들, 오프셋, prefix_sum)         }     }          돌아가다 prefix_sum }

개선점:블록 수가 너무 많아 단일 프로세서를 배치하여 시리얼 스텝에 시간이 걸리는 경우 Hillis 및 Steel 알고리즘을 사용하여 두 번째 단계를 가속화할 수 있습니다.

분산 메모리:하이퍼큐브 알고리즘

Hypercube Prefix Sum^[16] 알고리즘은 분산 메모리 플랫폼에 적합하며 처리 요소 간의 메시지 교환과 함께 작동합니다.이 알고리즘에는 p $p=2^{d}$ $p=2^{d}$ \ $displaystyle$ p $=2^{d}$ 프로세서 $p=2^{d}$ 요소(PE)가 d\ $displaystyle$ d $}$ 하이퍼큐브의 모서리 수와 같다고 가정합니다.

노드 수에 따라 다른 하이퍼 큐브

알고리즘 전체에 걸쳐 각 PE는 가상 하이퍼 큐브 내의 코너로 간주되며, 각 PE는 자체 하이퍼 큐브 내의 모든 요소의 프리픽스 합계(\ $displaystyle$ \sigma $)$ $\sigma$ (PE 내의 순서 있는 인덱스에 따라) 자신의 프리픽스 $(\displaystyle$ $\sigma$ x $)$ 를 알고 $x$ 있습니다.

알고리즘은 모든 PE가 0차원 하이퍼 큐브의 단일 코너라고 가정하고 시작하며 $,$ $\sigma$ \ $displaystyle$ \sigma $}$ 와 $\sigma$ x\ $displaystyle$ x는 $x$ 자체 요소의 로컬 프리픽스 합계와 동일합니다.
알고리즘은 1차원을 따라 인접한 하이퍼큐브를 통합함으로써 계속됩니다.각 통합 중에 $\sigma$ 2개의 하이퍼 큐브 간에 $교환$ 및 집약됩니다.이것에 $\sigma$ 의해, 이 새로운 하이퍼 큐브의 모서리에 있는 모든 PE는, 새롭게 통합된 이 하이퍼 큐브의 합계 프리픽스 합계가 변수 $「\displaystyle \sigma$ 에 격납됩니다.다만, PE를 포함한 하이퍼 큐브만이 다릅니다.또한 인덱스가 높을수록 $\sigma$ \ $displaystyle$ \sigma가 $\sigma$ $로컬$ 변수x\ $displaystyle$ x $\$ displaystyle $\sigma$ x $\$ 되므로 x $\$ displaystyle x는 $x$ 자신의 인덱스와 같거나 작은 PE의 모든 요소의 프리픽스 합계 값만 $x$ 합니다.

모서리에 $2^{d}$ 의 $2^{d}$ PE가 $2^{d}$ $2^{d}$ d ${$ $displaystyle$ d $}$ 하이퍼 큐브에서 $2^{d}$ 의 ${$ 2 $^{d}$ 개의 $2^{d}$ 0차원 하이퍼 큐브를 $d$ 의d{ $displaystyle$ d $}$ 차원 $d$ 하이퍼 큐브로 통합하려면 알고리즘을 d ${displaystyle$ d $}$ 반복해야 합니다.서로 다른 하이퍼 큐브에 있는 2개의 인접 PE의 ${\(\displaystyle\$ displaystyle\ $display$ $)$ 를 $\sigma$ 한 통신 단계에서 양방향으로 교환할 수 있는 듀플렉스 통신 모델을 가정하면 d $=$ $d=\log _{2}p$ $d=\log _{2}p$ $d=\log _{2}p$ p \ $displaystyle$ d $=$ \ $log$ _ ${$ 2}p } 통신 $d=\log _{2}p$ $d=\log _{2}p$ 를 의미합니다.

i := 색인 의 소유하다 프로세서 요소 (PE) m := 접두사 합 의 현지의 요소들 의 이것. PE d := 번호 의 치수 의 그 들뜬 입방체  x = m;     // 불변:현재 서브큐브의 이 PE까지의 프레픽스 합계 σ = m;     // 불변:현재 하위 큐브에 있는 모든 요소의 접두사 합계  위해서 (k=0; k <=> d-1; k++) {     y = σ @ PE(i xor 2^k)  // 차원 k를 따라 반대쪽 하위 큐브의 총 접두사 합계를 가져옵니다.     σ = σ + y              // 양쪽 서브큐브의 프리픽스 합계를 집계합니다.      한다면 (i & 2^k) {         x = x + y  // 이 PE가 상위 인덱스인 경우 다른 서브큐브에서 프리픽스 합만 집계합니다.     } }

대용량 메시지 크기: 파이프라인 바이너리 트리

파이프라인 바이너리 트리^[17] 알고리즘은 대용량 메시지 크기에 특히 적합한 분산 메모리 플랫폼용 알고리즘입니다.

하이퍼큐브 알고리즘과 마찬가지로 특별한 통신 구조를 가정합니다.처리 요소(PE)는 PE 내의 지수에 따른 인픽스 수치와 함께 바이너리 트리(예를 들어 피보나치 트리)에 가정적으로 배치된다.이러한 트리의 통신은 항상 상위 노드와 하위 노드 간에 발생합니다.

infix numberation에 의해 임의의_j PE에 대해 왼쪽 $\mathbb {[l...j-1]}$ 서브트리 $\mathbb {[l...j-1]}$ [ $\mathbb {[l...j-1]}$ . $\mathbb {[l...j-1]}$ . $\mathbb {[l...j-1]}$ j $\mathbb {[l...j-1]}$ - $\mathbb {[l...j-1]}$ ]{ $displaystyle \mathbb$ { [ $l$ ... j - 1 $]}}$ 에서 $\mathbb {[l...j-1]}$ 도달 가능한 모든 노드의 인덱스가j {\ $displaystyle$ j $}$ 및 $\mathbb {[j+1...r]}$ $\mathbb {[j+1...r]}$ + $\mathbb {[j+1...r]}$ 1...]보다 작음을 보증합니다. $]$ {\ $displaystyle \mathbb$ {[ $j+1$ ... $r]}$ 이 $\mathbb {[j+1...r]}$ $($ 가)j ${\$ $displaystyle$ j $j$ 보다 $큽니다$ .부모 인덱스는 PE가 왼쪽 자식인 경우_j PE 하위 트리의 인덱스보다_j 크고 PE가 오른쪽 자식인 경우_j 더 작습니다.이를 통해 다음과 같은 추론을 할 수 있습니다.

파이프라인 바이너리 트리 프리픽스 합계 알고리즘의 상향(파란색) 단계와 하향(빨간색) 단계에서의 처리 요소 간의 정보 교환.

왼쪽 서브트리의 로컬프리픽스 합계 $\mathbb {\oplus [l..j-1]}$ [ $\mathbb {\oplus [l..j-1]}$ . . $\mathbb {\oplus [l..j-1]}$ - $]{$ $displaystyle$ \ $mathbb$ { $oplus [ l$ . j - $1 ]}$ 를 $\mathbb {\oplus [l..j-1]}$ 집계하여 PE의 로컬프리픽스 합계 $\mathbb {\oplus [l..j]}$ [ $\mathbb {\oplus [l..j]}$ . $]\$ $displaystyle$ \ $mathbbb { ]$ 를 계산해야_j 합니다. $j]}$ $\mathbb {\oplus [l..j]}$ } $。$
로컬 프리픽스 합계 $\mathbb {\oplus [j+1..r]}$ [ $\mathbb {\oplus [j+1..r]}$ + $\mathbb {\oplus [j+1..r]}$ ] $]$ 오른쪽 서브트리의 r $]}}}$ 을 $\mathbb {\oplus [j+1..r]}$ (를) 집계하여 상위 레벨의_h PE 로컬프리픽스 합계를 계산해야 합니다.이 합계는 왼쪽 자녀 접속을 포함하는 경로( $h>j$ ,h $h>j$ > $h>j$ \ $displaystyle$ h $> j$ $h>j$ )로 도달합니다.
프리픽스 합계 $\mathbb {\oplus [0..j]}$ [ $\mathbb {\oplus [0..j]}$ . $]$ 오른쪽_j 서브트리의 총 프레픽스 합계를 계산하려면 PE의 j $]}}$ 이 $\mathbb {\oplus [0..j]}$ $필요$ 합니다(예를 들어 서브트리에서 가장 높은 인덱스노드의 경우 $\mathbb {\oplus [0..j..r]}$ \ $mathbb \oplus [0..j..$ r $\mathbb {\oplus [0..j..r]}$ ]} $\mathbb {\oplus [0..j..r]}$ ）。
PE 에는_j, 프리픽스의 합계 $\mathbb {\oplus [0..l-1]}$ 0 $\mathbb {\oplus [0..l-1]}$ ]를 포함할 필요가 있습니다. $\mathbb {\oplus [0..l-1]}$ - $]{$ $displaystyle \mathbb$ [ $0$ . l - 1 } $。$ 이 $\mathbb {\oplus [0..l-1]}$ 노드는 오른쪽 자식 연결을 포함한 상향 경로를 통해 도달하여 총 프레픽스 합계를 계산합니다.

서브트리 로컬과 총 프레픽스 합계의 구별에 주의해 주세요.2번, 3번, 4번 포인트는 순환의존관계를 형성할 것이라고 믿을 수 있지만 그렇지 않다.낮은 레벨의 PE에서는, 높은 레벨의 PE 의 합계 프리픽스 합계가 프리픽스 합계를 계산하기 위해서 필요한 경우가 있습니다만, 높은 레벨의 PE 에서는 프리픽스 합계를 계산하기 위해서 필요한 것은 서브 트리 로컬프리픽스 합계뿐입니다루트 노드는 최상위 노드로서 좌측 서브트리의 로컬프리픽스 합계를 계산하기 위해서만 필요합니다.PE에서 루트₀ PE로 가는 경로상의 각 PE는 왼쪽 서브트리의 로컬프리픽스 합계를 계산하기 위해서만 필요합니다만, PE(마지막 PE)에서_p-1 PE로_root 가는 경로상의 모든 노드는, 자신의 합계 프리픽스 합계를 계산하기 위해서 부모 노드의 합계 프리픽스 합계가 필요합니다.

이것에 의해, 2상 알고리즘이 발생합니다.

상향 단계
서브트리의 로컬프리픽스 합계 $\mathbb {\oplus [l..j..r]}$ . $\mathbb {\oplus [l..j..r]}$ . $\mathbb {\oplus [l..j..r]}$ . r $\mathbb {\oplus [l..j..r]}$ ]{ $displaystyle \mathbb$ \ $mathbb \ plus$ [l . j . $r$ ] $}$ 를 $\mathbb {\oplus [l..j..r]}$ 각_j PE의 부모에게 전파합니다.

하향 단계
배타적(배타적_j PE 및 왼쪽 서브트리의 PE)의 합계 프리픽스합 $\mathbb {\oplus [0..l-1]}$ [ 0 $\mathbb {\oplus [0..l-1]}$ . $\mathbb {\oplus [0..l-1]}$ - $]$ PE의 주소_j 지정 하위 트리에 포함되지 않은 모든 하위 인덱스 PE의 $\mathbb \mathbb$ [ 0 . l - 1 ] $。$ PE의 $\mathbb {\oplus [0..l-1]}$ 좌측_j 하위 트리의 하위 레벨 PE로 이동합니다.포함 프리픽스 합계 $\mathbb {\oplus [0..j]}$ [ $\mathbb {\oplus [0..j]}$ . $]$ $j]} }$ 을 $\mathbb {\oplus [0..j]}$ (를) PE의 오른쪽_j 하위 트리로 이동합니다.

알고리즘은 각 PE에서 병렬로 실행되며 자녀 또는 부모가 패킷을 제공할 때까지 PE는 수신 시 차단됩니다.

k := 번호 의 패킷 에 a 메세지 m 의 a PE m @ {왼쪽, 맞다, 부모, 이것.} := // 다른 PE 메시지  x = m @ 이것.  // 상향 단계 - 하위 트리 로컬 프리픽스 합계 계산 위해서 j=0 로. k-1: // 파이프라인:메시지의 각 패킷에 대해     한다면 has Left Child(왼쪽 아이):         막는 받다 m[j] @ 왼쪽 // 로컬 m[j]가 수신된 m[j]로 대체됩니다.         // 낮은 인덱스 PE로부터의 로컬프리픽스 합계(포함)         x[j] = m[j] ⨁ x[j]      한다면 has Right Child(오른쪽 아이):         막는 받다 m[j] @ 맞다         // 오른쪽 아이는 상위 인덱스 PE이기 때문에 로컬 프리픽스 합계에 m[j]를 집계하지 않습니다.         보내세요 x[j] ⨁ m[j] 로. 부모     또 다른:         보내세요 x[j] 로. 부모  // 하향 단계 위해서 j=0 로. k-1:     m[j] @ 이것. = 0      한다면 부모:         막는 받다 m[j] @ 부모         // 왼쪽 자녀의 경우 m[j]는 부모 전용 접두사 합계이고 오른쪽 자녀의 경우 포함 접두사 합계입니다.         x[j] = m[j] ⨁ x[j]           보내세요 m[j] 로. 왼쪽  // 이 값보다 작은 모든 PE 또는 왼쪽 서브트리의 임의의 PE의 총 프레픽스 합계     보내세요 x[j] 로. 맞다 // 이 PE보다 작거나 같은 모든 PE의 프리픽스 합계

파이프라인

$길이$ n의 $메시지$ m을 k개의 $패킷$ 으로 분할하여 대응하는 메시지 패킷별로 연산자 can를 사용할 수 있으면 파이프라이닝이 가능하다.^[17]

파이프라인 없이 이 알고리즘을 사용하는 경우, 다른 모든 PE가 대기하고 있는 동안 동작하는 바이너리 트리의 레벨은 항상 2개(송신 PE와 수신 PE)뿐입니다.p 처리 요소가 $있고$ 균형 잡힌 바이너리 트리가 사용되는 경우 트리는 $\log _{2}p$ 2 $\log _{2}p$ p \ $displaystyle$ \ $log$ _ { { $\log _{2}p$ $}$ $p$ to $PE_{0}$ to to, 。 $PE_{\mathbb {root} }$ $PE_{0}$ E 0 { $displaystyle PE$ $_$ { 0 } $PE_{\mathbb {root} }$ $PE_{\mathbb {root} }$ _ { \ $mathbb {$ root $}$ } 까지의 $PE_{\mathbb {root} }$ 경로 길이는 $\log _{2}p-1$ 2 $\log _{2}p-1$ - { $log$ style $}$ 입니다.는 상향 단계에서의 비병렬 통신 동작의 최대 수를 나타냅니다.또, 하향 경로에서의 통신도 $\log _{2}p-1$ p - $\log _{2}p-1$ \ $displaystyle \log$ _ ${ 2$ } $p-1$ 의 기동으로 $\log _{2}p-1$ 됩니다.통신 시작 시간을 T $T_{\mathbb {start} }$ $T_{\mathbb {start} }$ {\ $displaystyle$ $T_{\mathbb {start} }$ T_ ${\mathbb {start}}$ 로 $T_{\mathbb {start} }$ 하고 $(2\log _{2}p-2)(T_{\mathbb {start} }+n\cdot T_{\mathbb {byte} })$ 단위 전송 시간을 T $T_{\mathbb {byte} }$ $T_{\mathbb {byte} }$ e $(2\log _{2}p-2)(T_{\mathbb {start} }+n\cdot T_{\mathbb {byte} })$ $displaystyle T_{\mathbb {byte$ $(2\log _{2}p-2)(T_{\mathbb {start} }+n\cdot T_{\mathbb {byte} })$ 로 $(2\log _{2}p-2)(T_{\mathbb {start} }+n\cdot T_{\mathbb {byte} })$ 했을 경우, 위상과 아래 $(2\log _{2}p-2)(T_{\mathbb {start} }+n\cdot T_{\mathbb {byte} })$ 은 ( $(2\log _{2}p-2)(T_{\mathbb {start} }+n\cdot T_{\mathbb {byte} })$ a $(2\log _{2}p-2)(T_{\mathbb {start} }+n\cdot T_{\mathbb {byte} })$ + n $(2\log _{2}p-2)(T_{\mathbb {start} }+n\cdot T_{\mathbb {byte} })$ 2 $)$ 로 제한됩니다 $.$ 파이프라인되지 않은 시나리오에서는 \ $mathbb {start}+n\cdot T_{\mathbb {byte}}}$ 을 $(2\log _{2}p-2)(T_{\mathbb {start} }+n\cdot T_{\mathbb {byte} })$ $($ 를) 사용합니다.

k개의 패킷(각각 ${\tfrac {n}{k}}$ k \ ${\tfrac {n}{k}}$ \ $tfrac$ { n $}$ { k $}$ { k } { $(\log _{2}p-1)\left(T_{\mathbb {start} }+{\frac {n}{k}}\cdot T_{\mathbb {byte} }\right)$ k } )으로 ${\tfrac {n}{k}}$ 분할하여 개별적으로 송신하면 첫 번째 $(\log _{2}p-1)\left(T_{\mathbb {start} }+{\frac {n}{k}}\cdot T_{\mathbb {byte} }\right)$ 은 여전히 $(\log _{2}p-1)\left(T_{\mathbb {start} }+{\frac {n}{k}}\cdot T_{\mathbb {byte} }\right)$ $(\log _{2}p-1)\left(T_{\mathbb {start} }+{\frac {n}{k}}\cdot T_{\mathbb {byte} }\right)$ 2 $(\log _{2}p-1)\left(T_{\mathbb {start} }+{\frac {n}{k}}\cdot T_{\mathbb {byte} }\right)$ p - $(\log _{2}p-1)\left(T_{\mathbb {start} }+{\frac {n}{k}}\cdot T_{\mathbb {byte} }\right)$ ) ( $T$ $(\log _{2}p-1)\left(T_{\mathbb {start} }+{\frac {n}{k}}\cdot T_{\mathbb {byte} }\right)$ $(\log _{2}p-1)\left(T_{\mathbb {start} }+{\frac {n}{k}}\cdot T_{\mathbb {byte} }\right)$ $(\log _{2}p-1)\left(T_{\mathbb {start} }+{\frac {n}{k}}\cdot T_{\mathbb {byte} }\right)$ r + $(\log _{2}p-1)\left(T_{\mathbb {start} }+{\frac {n}{k}}\cdot T_{\mathbb {byte} }\right)$ k $(\log _{2}p-1)\left(T_{\mathbb {start} }+{\frac {n}{k}}\cdot T_{\mathbb {byte} }\right)$ $(\log _{2}p-1)\left(T_{\mathbb {start} }+{\frac {n}{k}}\cdot T_{\mathbb {byte} }\right)$ b $(\log _{2}p-1)\left(T_{\mathbb {start} }+{\frac {n}{k}}\cdot T_{\mathbb {byte} }\right)$ t $(\log _{2}p-1)\left(T_{\mathbb {start} }+{\frac {n}{k}}\cdot T_{\mathbb {byte} }\right)$ e $)\ displaystyle$ ( \ $log _$ { { { { { { { { { { { { { \ $mathbbb$ } p - 1 })\ $fr$ })\ frac })\ frac })\ frac { start } )PEr에 Gated}}로컬 접두사 금액의 일부로 간주하며, k입니다. 이 다시 마지막 패킷에 의해 발생할 것이다;로그 2⁡ p{\displaystyle k>, \log_{2}p}. OOOt{\displaystyle PE_{\mathbb{뿌리}제일의 것이다 하지만, 중간에, 모든 PEs의 길을 따라 평행하고 매일 3통신 운용( 받고, 할아버지가 왼쪽을 받는다 일할 수 있다.보내세요parent)에 의해 패킷이 다음 레벨로 송신되기 때문에, 2개의 로그2 $2\log _{2}p-1+3(k-1)$ p $2\log _{2}p-1+3(k-1)$ - $2\log _{2}p-1+3(k-1)$ + $2\log _{2}p-1+3(k-1)$ $2\log _{2}p-1+3(k-1)$ - $2\log _{2}p-1+3(k-1)$ $){$ $displaystyle$ 2 \ $log$ _ { $2$ $(4\cdot \log _{2}p-2+6(k-1))\left(T_{\mathbb {start} }+{\frac {n}{k}}\cdot T_{\mathbb {byte} }\right)$ $p$ - 1 + $3$ ( k - $2\log _{2}p-1+3(k-1)$ 1 )통신 $2\log _{2}p-1+3(k-1)$ $2\log _{2}p-1+3(k-1)$ 과 양쪽 페이즈가 동시에 필요( $(4\cdot \log _{2}p-2+6(k-1))\left(T_{\mathbb {start} }+{\frac {n}{k}}\cdot T_{\mathbb {byte} }\right)$ $(4\cdot \log _{2}p-2+6(k-1))\left(T_{\mathbb {start} }+{\frac {n}{k}}\cdot T_{\mathbb {byte} }\right)$ 2 $(4\cdot \log _{2}p-2+6(k-1))\left(T_{\mathbb {start} }+{\frac {n}{k}}\cdot T_{\mathbb {byte} }\right)$ - $(4\cdot \log _{2}p-2+6(k-1))\left(T_{\mathbb {start} }+{\frac {n}{k}}\cdot T_{\mathbb {byte} }\right)$ + $(4\cdot \log _{2}p-2+6(k-1))\left(T_{\mathbb {start} }+{\frac {n}{k}}\cdot T_{\mathbb {byte} }\right)$ ( $(4\cdot \log _{2}p-2+6(k-1))\left(T_{\mathbb {start} }+{\frac {n}{k}}\cdot T_{\mathbb {byte} }\right)$ - $(4\cdot \log _{2}p-2+6(k-1))\left(T_{\mathbb {start} }+{\frac {n}{k}}\cdot T_{\mathbb {byte} }\right)$ ) $(4\cdot \log _{2}p-2+6(k-1))\left(T_{\mathbb {start} }+{\frac {n}{k}}\cdot T_{\mathbb {byte} }\right)$ ( $(4\cdot \log _{2}p-2+6(k-1))\left(T_{\mathbb {start} }+{\frac {n}{k}}\cdot T_{\mathbb {byte} }\right)$ $(4\cdot \log _{2}p-2+6(k-1))\left(T_{\mathbb {start} }+{\frac {n}{k}}\cdot T_{\mathbb {byte} }\right)$ ) $-2+6(k-1)\left(T_{\mathbb {start}}+{\frac {n}{k}}\cdot T_{\mathbb {byte}} }\$ right)로 $(4\cdot \log _{2}p-2+6(k-1))\left(T_{\mathbb {start} }+{\frac {n}{k}}\cdot T_{\mathbb {byte} }\right)$ , 큰 메시지 $크기$ n에 적합합니다.

알고리즘은 전이중 또는 전화 모델 통신을 사용하여 상향 및 하향 단계를 ^[17]겹침으로써 더욱 최적화할 수 있습니다.

데이터 구조

데이터 세트를 동적으로 업데이트할 수 있는 경우 펜윅 트리 데이터 구조에 저장할 수 있습니다.이 구조에서는 개개의 프리픽스 합계값의 룩업과 ^[18]동작당 로그시간에서의 배열값의 수정이 모두 가능하게 됩니다.그러나 1982년 이전의 논문은 펜윅 나무와 겹치는 것으로 보이는 부분합 나무(섹션 5.1 참조)라는 데이터 구조를 제시한다. 1982년에는 접두사합이라는 용어가 오늘날처럼 일반적이지 않았다.

고차원 배열의 경우, 집계 영역 테이블은 임의의 직사각형 서브 어레이의 합계를 계산하기 위한 프리픽스 합계에 근거한 데이터 구조를 제공한다.이는 이미지 컨볼루션 ^[20]작업에서 유용한 프리미티브가 될 수 있습니다.

적용들

카운트 정렬은 키 주파수 히스토그램의 프리픽스 합계를 사용하여 정렬된 출력 배열에서 각 키의 위치를 계산하는 정수 정렬 알고리즘입니다.항목 수보다 작은 정수 키에 대해 선형 시간으로 실행되며 크기가 ^[1]덜 제한되는 정수를 정렬하는 빠른 알고리즘인 기수 정렬의 일부로 자주 사용됩니다.

리스트 랭킹은 링크된 리스트를 같은 아이템의 시퀀스를 나타내는 배열로 변환하는 문제로서 시퀀스 1, 1, 1, 1, ...의 프리픽스 합계를 계산하여 각 아이템을 프리픽스 합계에 의해 주어진 배열 위치에 매핑하는 것으로 간주할 수 있습니다.리스트 랭킹, 프리픽스 합계 및 오일러 투어의 많은 중요한 문제를 조합함으로써 가능합니다.es는 효율적인 병렬 ^[4]알고리즘으로 해결할 수 있습니다.

병렬 프리픽스 섬 알고리즘의 초기 적용은 2개의 n비트 이진수를 추가할 수 있는 부울 회로인 바이너리 가산기 설계에 있었습니다.이 어플리케이션에서 부가된 반송 비트의 시퀀스는 입력 비트 쌍의 시퀀스에 대한 스캔 동작으로 나타낼 수 있으며, 마조리티 함수를 사용하여 이전 반송 비트와 이들 2비트를 결합할 수 있습니다.출력 번호의 각 비트는 배타적 비트 또는 대응하는 반송 비트와 함께 2개의 입력 비트로 찾을 수 있습니다.병렬 프리픽스 합계 알고리즘의 연산을 실시하는 회로를 이용하는 것으로, O $(n)$ 논리 $게이트$ 와 O $(log$ n $)$ 타임 ^[3]^[10]^[11]스텝을 $이용$ 하는 가산기를 설계할 수 있다.

병렬 랜덤 액세스 머신 모델에서 프리픽스 합계는 동시 액세스를 금지하는 병렬 머신 상에서 여러 프로세서가 동시에 동일한 메모리 셀에 액세스하는 능력을 가정하는 병렬 알고리즘을 시뮬레이션하기 위해 사용할 수 있습니다.정렬 네트워크에 의해, 일련의 병렬 메모리 액세스 요구를 시퀀스내에서 연속하는 순서로 정렬할 수 있다.그 후, 스캔 조작을 사용해, 어느 쪽의 액세스가 요구된 셀에의 기입에 성공하는지를 판단해, 메모리 읽기 조작의 결과를 mu에 분배할 수 있다.동일한 ^[21]결과를 요구하는 여러 프로세서가 있습니다.

Guy Belloch 박사 논문에서 ^[22]병렬 접두사 연산은 Connection Machine과 같은 기계에 의해 제공되는 데이터 병렬화 모델의 공식화의 일부를 형성합니다.Connection Machine CM-1 및 CM-2는 위의 알고리즘1을 실장할 수 있는 하이퍼 큐빅네트워크를 제공했지만 CM-5는 알고리즘2를 ^[23]실장하기 위한 전용 네트워크를 제공했습니다.

그레이 코드 구성에서 연속되는 시퀀스 값이 단일 비트 위치에서 서로 다른 특성을 가진 바이너리 값의 시퀀스는 단순히 배타적 또는 $n$ 과n/ $2$ (n을 1비트 pos 오른쪽으로 $이동함$ 으로써 형성되는 수)를 취함으로써 $시퀀스$ $위치$ n에서 그레이 코드 값으로 변환할 수 있다.역연산은 그레이 코드 $값$ x를 2진수로 디코딩하는 것이 더 복잡하지만 x $비트$ 의 프리픽스 합계로 표현할 수 있습니다.여기서 프리픽스 합계 내의 각 합계 연산은 모듈로 2를 수행합니다.이 유형의 프리픽스 합계는 x를 왼쪽으로 $이동$ 시켜 형성된 각각의 숫자로 x의 배타적 또는 $x$ 의 배타적 연산을 ^[24]2의 거듭제곱인 비트 수로 계산함으로써 효율적으로 수행될 수 있다.

병렬 접두사(기본 연관 연산으로 곱셈 사용)를 사용하여 병렬 다항식 보간을 위한 빠른 알고리즘을 구축할 수도 있습니다.특히 보간 ^[25]다항식의 뉴턴 형식의 분할 차분 계수를 계산하는 데 사용할 수 있다.이 프리픽스 베이스의 어프로치는, (일관한) Hermite 보간 뿐만이 아니라, Vandermonde ^[26]시스템의 병렬 알고리즘의 일반화된 분할 차이를 취득하기 위해서도 사용할 수 있습니다.

「」를 참조해 주세요.

레퍼런스

^ ^a ^b 를 클릭합니다Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), "8.2 Counting Sort", Introduction to Algorithms (2nd ed.), MIT Press and McGraw-Hill, pp. 168–170, ISBN 0-262-03293-7.
^ Cole, Richard; Vishkin, Uzi (1986), "Deterministic coin tossing with applications to optimal parallel list ranking", Information and Control, 70 (1): 32–53, doi:10.1016/S0019-9958(86)80023-7
^ ^a ^b ^c ^d ^e 를 클릭합니다Ladner, R. E.; Fischer, M. J. (1980), "Parallel Prefix Computation", Journal of the ACM, 27 (4): 831–838, CiteSeerX 10.1.1.106.6247, doi:10.1145/322217.322232, MR 0594702.
^ ^a ^b ^c 를 클릭합니다Tarjan, Robert E.; Vishkin, Uzi (1985), "An efficient parallel biconnectivity algorithm", SIAM Journal on Computing, 14 (4): 862–874, doi:10.1137/0214061.
^ 를 클릭합니다Lakshmivarahan, S.; Dhall, S.K. (1994), Parallelism in the Prefix Problem, Oxford University Press, ISBN 0-19508849-2.
^ 를 클릭합니다Blelloch, Guy (2011), Prefix Sums and Their Applications (Lecture Notes) (PDF), Carnegie Mellon University.
^ 를 클릭합니다Callahan, Paul; Kosaraju, S. Rao (1995), "A Decomposition of Multi-Dimensional Point Sets with Applications to k-Nearest-Neighbors and n-Body Potential Fields", Journal of the ACM, 42 (1): 67–90, doi:10.1145/200836.200853.
^ "GPU Gems 3".
^ Hillis, W. Daniel; Steele, Jr., Guy L. (December 1986). "Data parallel algorithms". Communications of the ACM. 29 (12): 1170–1183. doi:10.1145/7902.7903.
^ ^a ^b Ofman, Yu. (1962), Об алгоритмической сложности дискретных функций, Doklady Akademii Nauk SSSR (in Russian), 145 (1): 48–51, MR 0168423. 영어 번역, "이산함수의 알고리즘 복잡성에 대하여", 소련 물리학자 Doklady 7: 589-591 1963.
^ ^a ^b Khrapchenko, V. M. (1967), "Asymptotic Estimation of Addition Time of a Parallel Adder", Problemy Kibernet. (in Russian), 19: 107–122. 시스템에서의 영어 번역. 이론 제19호; 105~122, 1970.
^ Sengupta, Shubhabrata; Harris, Mark; Zhang, Yao; Owens, John D. (2007). Scan primitives for GPU computing. Proc. 22nd ACM SIGGRAPH/EUROGRAPHICS Symposium on Graphics Hardware. pp. 97–106. Archived from the original on 2014-09-03. Retrieved 2007-11-29.
^ Vishkin, Uzi (2003). Prefix sums and an application thereof. U.S. Patent 6,542,918.
^ Singler, Johannes. "MCSTL: The Multi-Core Standard Template Library". Retrieved 2019-03-29.
^ Singler, Johannes; Sanders, Peter; Putze, Felix (2007). "MCSTL: The Multi-core Standard Template Library". Euro-Par 2007 Parallel Processing. Lecture Notes in Computer Science. Vol. 4641. pp. 682–694. doi:10.1007/978-3-540-74466-5_72. ISBN 978-3-540-74465-8. ISSN 0302-9743.
^ Ananth Grama; Vipin Kumar; Anshul Gupta (2003). Introduction to Parallel Computing. Addison-Wesley. pp. 85, 86. ISBN 978-0-201-64865-2.
^ ^a ^b ^c Sanders, Peter; Träff, Jesper Larsson (2006). "Parallel Prefix (Scan) Algorithms for MPI". Recent Advances in Parallel Virtual Machine and Message Passing Interface. Lecture Notes in Computer Science. Vol. 4192. pp. 49–57. doi:10.1007/11846802_15. ISBN 978-3-540-39110-4. ISSN 0302-9743.
^ Fenwick, Peter M. (1994), "A new data structure for cumulative frequency tables", Software: Practice and Experience, 24 (3): 327–336, doi:10.1002/spe.4380240306
^ Shiloach, Yossi; Vishkin, Uzi (1982b), "An O(n² log n) parallel max-flow algorithm", Journal of Algorithms, 3 (2): 128–146, doi:10.1016/0196-6774(82)90013-X
^ 를 클릭합니다Szeliski, Richard (2010), "Summed area table (integral image)", Computer Vision: Algorithms and Applications, Texts in Computer Science, Springer, pp. 106–107, ISBN 9781848829350.
^ 를 클릭합니다Vishkin, Uzi (1983), "Implementation of simultaneous memory address access in models that forbid it", Journal of Algorithms, 4 (1): 45–50, doi:10.1016/0196-6774(83)90033-0, MR 0689265.
^ Blelloch, Guy E. (1990). Vector models for data-parallel computing. Cambridge, MA: MIT Press. ISBN 026202313X. OCLC 21761743.
^ Leiserson, Charles E.; Abuhamdeh, Zahi S.; Douglas, David C.; Feynman, Carl R.; Ganmukhi, Mahesh N.; Hill, Jeffrey V.; Hillis, W. Daniel; Kuszmaul, Bradley C.; St. Pierre, Margaret A. (March 15, 1996). "The Network Architecture of the Connection Machine CM-5". Journal of Parallel and Distributed Computing. 33 (2): 145–158. doi:10.1006/jpdc.1996.0033. ISSN 0743-7315.
^ 를 클릭합니다Warren, Henry S. (2003), Hacker's Delight, Addison-Wesley, p. 236, ISBN 978-0-201-91465-8.
^ 를 클릭합니다Eğecioğlu, O.; Gallopoulos, E.; Koç, C. (1990), "A parallel method for fast and practical high-order Newton interpolation", BIT Computer Science and Numerical Mathematics, 30 (2): 268–288, doi:10.1007/BF02017348.
^ Eğecioğlu, O.; Gallopoulos, E.; Koç, C. (1989), "Fast computation of divided differences and parallel Hermite interpolation", Journal of Complexity, 5 (4): 417–437, doi:10.1016/0885-064X(89)90018-6

외부 링크

Weisstein, Eric W. "Cumulative Sum". MathWorld.

[clrs-1] 를 클릭합니다Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), "8.2 Counting Sort", Introduction to Algorithms (2nd ed.), MIT Press and McGraw-Hill, pp. 168–170, ISBN 0-262-03293-7.

[cv86-2] Cole, Richard; Vishkin, Uzi (1986), "Deterministic coin tossing with applications to optimal parallel list ranking", Information and Control, 70 (1): 32–53, doi:10.1016/S0019-9958(86)80023-7

[lf80-3] 를 클릭합니다Ladner, R. E.; Fischer, M. J. (1980), "Parallel Prefix Computation", Journal of the ACM, 27 (4): 831–838, CiteSeerX 10.1.1.106.6247, doi:10.1145/322217.322232, MR 0594702.

[tv85-4] 를 클릭합니다Tarjan, Robert E.; Vishkin, Uzi (1985), "An efficient parallel biconnectivity algorithm", SIAM Journal on Computing, 14 (4): 862–874, doi:10.1137/0214061.

[Prefix.book.92-5] 를 클릭합니다Lakshmivarahan, S.; Dhall, S.K. (1994), Parallelism in the Prefix Problem, Oxford University Press, ISBN 0-19508849-2.

[blelloch11-6] 를 클릭합니다Blelloch, Guy (2011), Prefix Sums and Their Applications (Lecture Notes) (PDF), Carnegie Mellon University.

[callahan1995-7] 를 클릭합니다Callahan, Paul; Kosaraju, S. Rao (1995), "A Decomposition of Multi-Dimensional Point Sets with Applications to k-Nearest-Neighbors and n-Body Potential Fields", Journal of the ACM, 42 (1): 67–90, doi:10.1145/200836.200853.

[8] "GPU Gems 3".

[hs1986-9] Hillis, W. Daniel; Steele, Jr., Guy L. (December 1986). "Data parallel algorithms". Communications of the ACM. 29 (12): 1170–1183. doi:10.1145/7902.7903.

[offman-10] Ofman, Yu. (1962), Об алгоритмической сложности дискретных функций, Doklady Akademii Nauk SSSR (in Russian), 145 (1): 48–51, MR 0168423. 영어 번역, "이산함수의 알고리즘 복잡성에 대하여", 소련 물리학자 Doklady 7: 589-591 1963.

[krapchenko-11] Khrapchenko, V. M. (1967), "Asymptotic Estimation of Addition Time of a Parallel Adder", Problemy Kibernet. (in Russian), 19: 107–122. 시스템에서의 영어 번역. 이론 제19호; 105~122, 1970.

[12] Sengupta, Shubhabrata; Harris, Mark; Zhang, Yao; Owens, John D. (2007). Scan primitives for GPU computing. Proc. 22nd ACM SIGGRAPH/EUROGRAPHICS Symposium on Graphics Hardware. pp. 97–106. Archived from the original on 2014-09-03. Retrieved 2007-11-29.

[13] Vishkin, Uzi (2003). Prefix sums and an application thereof. U.S. Patent 6,542,918.

[14] Singler, Johannes. "MCSTL: The Multi-Core Standard Template Library". Retrieved 2019-03-29.

[SinglerSanders2007-15] Singler, Johannes; Sanders, Peter; Putze, Felix (2007). "MCSTL: The Multi-core Standard Template Library". Euro-Par 2007 Parallel Processing. Lecture Notes in Computer Science. Vol. 4641. pp. 682–694. doi:10.1007/978-3-540-74466-5_72. ISBN 978-3-540-74465-8. ISSN 0302-9743.

[GramaKumar2003-16] Ananth Grama; Vipin Kumar; Anshul Gupta (2003). Introduction to Parallel Computing. Addison-Wesley. pp. 85, 86. ISBN 978-0-201-64865-2.

[SandersTraeff2006-17] Sanders, Peter; Träff, Jesper Larsson (2006). "Parallel Prefix (Scan) Algorithms for MPI". Recent Advances in Parallel Virtual Machine and Message Passing Interface. Lecture Notes in Computer Science. Vol. 4192. pp. 49–57. doi:10.1007/11846802_15. ISBN 978-3-540-39110-4. ISSN 0302-9743.

[18] Fenwick, Peter M. (1994), "A new data structure for cumulative frequency tables", Software: Practice and Experience, 24 (3): 327–336, doi:10.1002/spe.4380240306

[19] Shiloach, Yossi; Vishkin, Uzi (1982b), "An O(n² log n) parallel max-flow algorithm", Journal of Algorithms, 3 (2): 128–146, doi:10.1016/0196-6774(82)90013-X

[20] 를 클릭합니다Szeliski, Richard (2010), "Summed area table (integral image)", Computer Vision: Algorithms and Applications, Texts in Computer Science, Springer, pp. 106–107, ISBN 9781848829350.

[21] 를 클릭합니다Vishkin, Uzi (1983), "Implementation of simultaneous memory address access in models that forbid it", Journal of Algorithms, 4 (1): 45–50, doi:10.1016/0196-6774(83)90033-0, MR 0689265.

[22] Blelloch, Guy E. (1990). Vector models for data-parallel computing. Cambridge, MA: MIT Press. ISBN 026202313X. OCLC 21761743.

[23] Leiserson, Charles E.; Abuhamdeh, Zahi S.; Douglas, David C.; Feynman, Carl R.; Ganmukhi, Mahesh N.; Hill, Jeffrey V.; Hillis, W. Daniel; Kuszmaul, Bradley C.; St. Pierre, Margaret A. (March 15, 1996). "The Network Architecture of the Connection Machine CM-5". Journal of Parallel and Distributed Computing. 33 (2): 145–158. doi:10.1006/jpdc.1996.0033. ISSN 0743-7315.

[24] 를 클릭합니다Warren, Henry S. (2003), Hacker's Delight, Addison-Wesley, p. 236, ISBN 978-0-201-91465-8.

[25] 를 클릭합니다Eğecioğlu, O.; Gallopoulos, E.; Koç, C. (1990), "A parallel method for fast and practical high-order Newton interpolation", BIT Computer Science and Numerical Mathematics, 30 (2): 268–288, doi:10.1007/BF02017348.

[26] Eğecioğlu, O.; Gallopoulos, E.; Koç, C. (1989), "Fast computation of divided differences and parallel Hermite interpolation", Journal of Complexity, 5 (4): 417–437, doi:10.1016/0885-064X(89)90018-6

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

Search

프리픽스 합계

네임스페이스

더

목차

고차 스캔 기능

포괄적 및 배타적 검사

병렬 알고리즘

알고리즘 1: 짧은 스팬, 더 병렬

알고리즘 2: 효율적인 작업

논의

프리픽스 합계 알고리즘의 구체적인 실장

공유 메모리:2레벨 알고리즘

분산 메모리:하이퍼큐브 알고리즘

대용량 메시지 크기: 파이프라인 바이너리 트리

파이프라인

데이터 구조

적용들

「」를 참조해 주세요.

레퍼런스

외부 링크

Search

프리픽스 합계

고차 스캔 기능

포괄적 및 배타적 검사

병렬 알고리즘

알고리즘 1: 짧은 스팬, 더 병렬

알고리즘 2: 효율적인 작업

논의

프리픽스 합계 알고리즘의 구체적인 실장

공유 메모리:2레벨 알고리즘

분산 메모리:하이퍼큐브 알고리즘

대용량 메시지 크기: 파이프라인 바이너리 트리

파이프라인

데이터 구조

적용들

「 」를 참조해 주세요.

레퍼런스

외부 링크

「」를 참조해 주세요.