Parallel reduction은 identity·associativity·compatibility 법칙이 필요하다
순차에서 우연히 맞는 비결합 연산은 partition 결합 순서가 바뀌면 다른 값을 냅니다.
| 법칙 | 조건 | 위반 결과 |
|---|---|---|
| identity | combine(id,x)=x | 빈 partition 왜곡 |
| associativity | a⊕(b⊕c)=(a⊕b)⊕c | 분할마다 결과 변경 |
| compatibility | combiner(u,acc(id,t))=acc(u,t) | 순차·병렬 불일치 |
| non-interference | source 미변경 | race·누락 |
핵심: accumulator와 combiner가 같은 수학적 의미를 공유해야 합니다.