27 병렬 되풀이와 원자 연산

먼저 알아야 할 것

12장 빌리기 · 읽기 여럿 또는 쓰기 하나

26장 태스크와 채널 · 흐름은 블록에 묶이고 모든 차례를 시험할 수 있다

16장 권한 · effects atomic 은 cap atomic 과 짝이다

돌아보기

12장의 배타 규칙(“읽기 여럿 또는 쓰기 하나”)이 멀티스레드 프로그램과 무슨 관계가 있다고 했는가?

답. 한 흐름 안에서 그 규칙이 지켜지면, 여러 흐름으로 나누었을 때 데이터 경합이 없다는 것까지 따라 나온다고 했다. 이 장은 그 성질을 실제로 쓴다 — 되풀이 하나를 조각으로 나누어 여러 흐름이 함께 돌게 하고, 나누어도 답이 같다는 것을 번역이 확인한다.

이 장의 필요성과 맥락

같은 계산을 여러 코어에 나누는 것은 가장 흔한 병렬화이고, 가장 흔한 결함의 자리다. 나눈 조각이 서로의 원소를 읽거나, 같은 변수에 누적하거나, 차례에 따라 답이 달라지는 연산을 쓰면 “빠르지만 가끔 틀린” 프로그램이 된다. Lowent 는 나눌 수 있다는 선언을 믿지 않고 확인한다. 확인할 수 없으면 나누지 않는 것이 아니라 번역을 거절한다. 그리고 여러 흐름이 정말로 같은 메모리를 만져야 하는 드문 자리에는 원자 연산을 이름으로 고르게 한다. 제7부의 마지막 장이다.

이 장이 끝나면

op 머리의 parallel <슬라이스> split . 으로 되풀이를 나눌 수 있다고 밝히는 법과, 처리기가 확인하는 세 조건(자기 몫만 읽기·자기 몫만 쓰기·걸음을 넘어 사는 자리에 쓰지 않기)을 익힌다. 누적을 reduce <자리> <연산> . 으로 밝히고, 결합적이지 않은 연산이 거절되는 이유를 알게 된다. atomic_add·atomic_load 같은 원자 연산과 기억 차례(order), 그 조합 규칙도 보게 된다.

이 장에서 답할 질문

원자 연산이 있는데 자물쇠(lock)는 왜 없는가?

27.1 나눌 수 있다고 밝힌다#

examples/ch27/split.low

module split .
rem run: double_all [1,2,3,4,5,6]
rem run: total [1,2,3,4,5,6]

proc double_all input s mut slice u8 . output u64 . effects none .
  parallel s split .
do
  var i u64 be 0 .
  while lt i (len s) . do
    set (index s i) (wrap_mul (index s i) 2) .
    set i (add i 1) .
  end
  return len s .
end

fn total input s slice u8 . output u64 .
  parallel s split .
  reduce acc add .
do
  var acc u64 be 0 .
  var i u64 be 0 .
  while lt i (len s) . do
    set acc (add acc (widen u64 (index s i))) .
    set i (add i 1) .
  end
  return acc .
end

실행 결과

$ lowentc --run double_all split.low [1,2,3,4,5,6]
double_all([2,4,6,8,10,12]) = 6
  arg0 (written) = [2,4,6,8,10,12]
$ lowentc --run total split.low [1,2,3,4,5,6]
total([1,2,3,4,5,6]) = 21
  arg0 (written) = [1,2,3,4,5,6]

double_all 의 머리에 parallel s split . 이 있다. “이 되풀이는 s 를 조각으로 나누어 여럿이 함께 돌아도 된다” 는 선언이다. 각 걸음은 index s i — 자기 원소 — 만 읽고 쓴다.
total 은 합을 누적한다. 누적 변수 acc 는 걸음을 넘어 살기 때문에 그대로는 나눌 수 없다. reduce acc add . 로 “조각마다 따로 누적한 뒤 add 로 합친다” 고 밝힌다.

두 선언이 무엇을 허락하는지 그림으로 보면 이렇다.

 split --- 조각마다 제 몫만 만진다
   s:  [ 0 1 2 3 | 4 5 6 7 | 8 9 10 11 ]
         조각 A     조각 B     조각 C         ← 셋이 동시에 돌아도 서로 닿지 않는다

 reduce acc add --- 조각마다 따로 모은 뒤 합친다
   조각 A: acc_A = 0+1+2+3      = 6  ─┐
   조각 B: acc_B = 4+5+6+7      = 22 ─┼─ add ─▶ acc = 66
   조각 C: acc_C = 8+9+10+11    = 38 ─┘

add 는 묶는 차례가 달라도 답이 같으므로(결합적) 어떻게 나누어도 순차 결과와 같다. 부동소수 덧셈은 그렇지 않아서 reduce 로 나눌 수 없다(아래 «모으는 연산은 결합적이어야 한다»).

처리기가 이 선언을 확인하면 W-PAR-OK 로 알린다. 그 알림에는 중요한 말이 들어 있다. VM 은 여전히 순차로 돈다. 그것이 올바른 구현인 것은, 나눌 수 있는 조건을 만족하면 병렬 결과가 순차 결과와 비트까지 같다는 정리가 증명되어 있기 때문이다(45장). 네이티브 코드는 실제로 조각을 나누어 여러 스레드로 돈다. 두 백엔드가 같은 답을 내는 것이 곧 그 정리의 실측이다.

27.2 처리기가 확인하는 세 조건#

조건	어기면	무엇이 어긋나는가
자기 몫만 읽는다	`E-PAR-READ`	남의 자리를 읽으면 그 값이 옛것인지 새것인지가 누가 먼저 도느냐에 달린다
자기 몫만 쓴다	`E-PAR-WRITE`	두 걸음이 같은 자리에 쓰면 남는 값이 차례에 달린다
걸음을 넘어 사는 자리에 쓰지 않는다	`E-PAR-CARRY`	그런 자리는 걸음들을 묶는다. 모아야 하면 `reduce` 로 밝힌다

표 27.1 — 나누어 돌 수 있는 되풀이의 조건

examples/ch27/par_read.low

module par_read .
rem expect: E-PAR-READ

proc relative input s mut slice u8 . output u64 . effects none .
  parallel s split .
do
  var i u64 be 0 .
  while lt i (len s) . do
    set (index s i) (wrap_sub (index s i) (index s 0)) .
    set i (add i 1) .
  end
  return len s .
end

실행 결과

$ lowentc --check par_read.low
par_read.low:9:0 E-PAR-READ: a splittable loop may only read its OWN element of the split slice — reading another index creates a cross-iteration dependence (Bernstein: rd ∩ wr = ∅)

모든 원소에서 첫 원소를 빼는 되풀이다. 첫 조각이 index s 0 을 먼저 바꾸면, 다른 조각이 읽는 첫 원소는 이미 바뀐 값이다. 순차로 돌려도 첫 걸음 이후에는 0 을 빼게 되는 결함이 있는데, 나누면 그 결함이 차례에 따라 달라진다.

examples/ch27/par_carry.low

module par_carry .
rem expect: E-PAR-CARRY

fn total input s slice u8 . output u64 .
  parallel s split .
do
  var acc u64 be 0 .
  var i u64 be 0 .
  while lt i (len s) . do
    set acc (add acc (widen u64 (index s i))) .
    set i (add i 1) .
  end
  return acc .
end

실행 결과

$ lowentc --check par_carry.low
par_carry.low:10:0 E-PAR-CARRY: a splittable loop may not write a local that lives across iterations (a loop-carried dependence) — declare it: `reduce <acc> <op> .`

reduce 없이 acc 에 누적했다. 진단이 고치는 법을 그대로 알려 준다.

흔한 오해. 병렬로 돌려서 답이 가끔 다르면 그건 성능 조정의 문제다

답이 차례에 따라 달라지는 프로그램은 느린 프로그램이 아니라 틀린 프로그램이다. Lowent 에서 parallel 절은 뜻을 바꾸지 않는다. 나누어 돈 답과 하나씩 돈 답은 언제나 같아야 하고, 그 조건을 확인할 수 없으면 번역이 거절한다. “빠르지만 가끔 틀림” 은 이 언어가 파는 물건이 아니다.

27.3 모으는 연산은 결합적이어야 한다#

reduce 로 모을 때, 조각을 어떻게 나누느냐에 따라 합치는 나무의 모양이 달라진다. 연산이 결합적이면 모양이 답을 바꾸지 않고, 결합적이지 않으면 바꾼다.

examples/ch27/par_assoc.low

module par_assoc .
rem expect: E-PAR-ASSOC

fn diff input s slice u8 . output u64 .
  parallel s split .
  reduce acc sub .
do
  var acc u64 be 1000 .
  var i u64 be 0 .
  while lt i (len s) . do
    set acc (sub acc (widen u64 (index s i))) .
    set i (add i 1) .
  end
  return acc .
end

실행 결과

$ lowentc --check par_assoc.low
par_assoc.low:4:0 E-PAR-ASSOC: this reduction operator is not associative, so the shape of the reduction tree changes the result — a split tree is not deterministic (★ nonassoc_shape_matters, Qed — docs/proofs/coq/LowentPar.v)
par_assoc.low:4:0 W-PAR-OK: this loop satisfies the Bernstein conditions and may be split (DET-1 proves the parallel result is bit-identical to the sequential one — docs/proofs/coq/LowentPar.v). Execution is still sequential, which is a VALID implementation precisely because of that theorem

sub 는 결합적이지 않다. (1000 − 1) − 2 와 1000 − (1 − 2) 는 다르다. 두 명제 — 결합적이면 모양이 상관없고, 결합적이지 않으면 모양이 결과를 바꾼다 — 는 둘 다 Coq 로 증명되어 있고, 진단이 그 정리의 이름을 인용한다. 부동소수의 덧셈도 차례에 따라 답이 달라지므로 따로 막는다(E-PAR-FLOAT).

27.4 원자 연산#

나누어 돈 조각들이 한 자리를 함께 갱신해야 할 때가 있다. 조각마다 센 개수를 공유 카운터에 더하는 경우다. 보통의 add 로는 두 스레드가 같은 값을 읽고 각자 더해 써서 하나가 사라진다. 원자 연산은 쪼개지지 않는다 — 다른 흐름이 그 중간을 볼 수 없다.

examples/ch27/counter.low

module atomic_counter .
rem run: main

proc count_par input k cap atomic . input data slice u8 . input counter mut slice u64 .
  output void .
  effects atomic .
  parallel data split .
do
  var i u64 be 0 .
  while lt i (len data) . do
    atomic_add counter 0 1 .
    set i (add i 1) .
  end
  return .
end

proc main input k cap atomic . input al cap allocator . output u8 . effects atomic alloc .
do
  let g option mut slice u8 be alloc_bytes al capacity 8 .
  guard is_some g . else return 1 .
  var cells mut slice u64 be view_array u64 (some_value g) .
  atomic_store cells 0 0 .
  count_par k "abcdefghij" cells .
  return narrow u8 (atomic_load cells 0) .
end

실행 결과

$ lowentc --run main counter.low
main() = 10

atomic_add counter 0 1 은 슬라이스 counter 의 0 번 자리에 원자적으로 1 을 더한다. 자리는 슬라이스와 색인으로 가리킨다.
count_par 는 data 를 나누어 돌면서 공유 카운터를 갱신한다. 열 바이트를 세었으므로 10 이다.
원자 연산은 atomic 효과이고, cap atomic 을 받아야 한다. main 은 시작점에서 cap atomic 을 받는다.
view_array u64 는 할당받은 8 바이트를 베끼지 않고 u64 하나의 슬라이스로 본다(13장).

권한 없이 원자 효과를 적으면 거절된다.

examples/ch27/nocap.low

module nocap .
rem expect: E-ATOMIC-NOCAP

proc bump input s mut slice u64 . output u64 . effects atomic .
do
  atomic_add s 0 1 .
  return atomic_load s 0 .
end

실행 결과

$ lowentc --check nocap.low
nocap.low:4:0 E-ATOMIC-NOCAP: this op declares the `atomic` effect but receives NO `cap atomic`. Like `io`, `alloc` and `heap`, `atomic` is an effect you are HANDED the right to: `input k cap atomic .` (§7.2 (6))

원자 연산은 공짜가 아니다. 한 흐름만 만지는 값에 쓰면 느려지기만 한다. 그래서 기본으로 두지 않고 이름으로 고르게 하며, 그 비용이 머리의 효과와 권한에 적힌다.

문. 원자 연산이 있는데 자물쇠(lock)는 왜 없는가?

답. 나누어 가지는 자물쇠 상태는 이 판에서 아직 짓지 않았고, 쓰면 E-LOCK-NOTYET 으로 없다고 말한다. 대신 표준 라이브러리에 원자 연산으로 지은 자료구조가 있다. spsc 는 락 없이 한 생산자와 한 소비자가 값을 넘기는 링 버퍼이고, 그 정확성은 약한 메모리 모델의 증명을 빌려 확인되었다(34·47장).

27.5 기억 차례#

원자 연산 뒤에 order <이름> 을 붙여 다른 흐름에게 무엇이 언제 보이는지 정할 수 있다.

이름	뜻
`seq_cst`	모든 흐름이 같은 하나의 차례를 본다. 가장 강하고, 적지 않으면 이것이다
`acq_rel`	읽고 쓰는 연산에서 앞뒤 모두 새어 나가지 않는다
`acquire`	이 읽기 뒤의 일이 앞으로 새어 나가지 않는다
`release`	이 쓰기 앞의 일이 뒤로 새어 나가지 않는다
`relaxed`	원자성만 있고 차례는 없다

표 27.2 — 기억 차례

가장 강한 것이 기본인 까닭은 그것이 가장 추론하기 쉽기 때문이다. 모든 접근이 seq_cst 이면 순서대로 사고해도 된다는 것이 증명되어 있다. 약하게 하는 것은 그 값을 아는 사람이 적어서 고르는 일이다.

연산에 따라 뜻이 없는 조합은 거절된다.

차례 넷을 짝이 맞는 연산에 쓰면 이렇다.

examples/ch27/orders.low

module orders .
rem run: main

rem 적지 않으면 seq_cst — 모든 흐름이 같은 차례를 본다
rem 읽고 쓰는 연산(atomic_swap)에는 acq_rel, 쓰기에는 release, 읽기에는 acquire
proc main input k cap atomic . input al cap allocator . output u8 . effects atomic alloc .
do
  let g option mut slice u8 be alloc_bytes al capacity 8 .
  guard is_some g . else return 250 .
  var cells mut slice u64 be view_array u64 (some_value g) .
  atomic_store cells 0 5 order seq_cst .
  let old u64 be atomic_swap cells 0 7 order acq_rel .
  atomic_store cells 0 (add old 10) order release .
  return narrow u8 (atomic_load cells 0 order acquire) .
end

실행 결과

$ lowentc --run main orders.low
main() = 15

atomic_store … order seq_cst 로 5 를 쓰고, 읽고 쓰는 atomic_swap … order acq_rel 로 7 과 바꾸며 옛값 5 를 얻는다. order release 로 15 를 쓰고 order acquire 로 읽어 15 를 돌려준다. 짝이 맞지 않는 조합은 거절된다.

examples/ch27/order_bad.low

module order_bad .
rem expect: E-ATOMIC-ORDER

proc peek input k cap atomic . input s mut slice u64 . output u64 . effects atomic .
do
  return atomic_load s 0 order release .
end

실행 결과

$ lowentc --check order_bad.low
order_bad.low:6:0 E-ATOMIC-ORDER: this memory ordering is not valid for this atomic op (a load cannot be `release`, a store cannot be `acquire`, a fence cannot be `relaxed`) — RFC-0018 §6.1

읽기가 무엇을 내보낸다는 말인가. C 는 이런 조합을 정의되지 않은 동작으로 둔다. 쓰기는 acquire 일 수 없고, 차례만 정하는 울타리(atomic_fence)는 relaxed 일 수 없다.

27.6 레인 — 값 여럿을 한 번에 셈한다#

parallel 이 되풀이를 흐름 여럿에 나눈다면, vec 은 한 흐름 안에서 값 여럿을 한 값으로 들고 한 번에 셈한다(SIMD). vec u32 4 는 u32 네 개를 담는 레인 넷짜리 값이고, 레인 수는 타입의 일부다. 기계가 한 번에 셈하든 하나씩 셈하든 답은 같다(정본 6.2.11).

examples/ch27/lanes.low

module lanes .
rem run: capped_sum [1,0,0,0,9,0,0,0,3,0,0,0,7,0,0,0]
rem run: extremes [1,0,0,0,9,0,0,0,3,0,0,0,7,0,0,0]
rem run: turned [1,0,0,0,9,0,0,0,3,0,0,0,7,0,0,0] [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
rem run: lanes_here

rem 네 레인을 한 값으로 읽고, 5 보다 큰 레인은 5 로 눌러 모두 더한다
proc capped_sum input b slice u8 . output u32 . effects none .
  requires ge (len b) 16 .
do
  var xs slice u32 be view_array u32 b .
  var v vec u32 4 be load xs 0 .
  var lim vec u32 4 be splat 5 .
  var over mask 4 be gt v lim .
  var capped vec u32 4 be select over lim v .
  return reduce_add capped .
end

rem 레인을 가로질러 가장 큰 것 · 가장 작은 것 · 모두 곱한 것
proc extremes input b slice u8 . output u32 . effects none .
  requires ge (len b) 16 .
do
  var xs slice u32 be view_array u32 b .
  var v vec u32 4 be load xs 0 .
  return add (mul (reduce_max v) 1000) (add (mul (reduce_min v) 100) (reduce_mul v)) .
end

rem 레인의 차례를 뒤집고, 한 칸 돌려 메모리에 쓴다
proc turned input b slice u8 . input out mut slice u8 . output u32 . effects none .
  requires ge (len b) 16 .
  requires ge (len out) 16 .
do
  var xs slice u32 be view_array u32 b .
  var ys mut slice u32 be view_array u32 out .
  var v vec u32 4 be load xs 0 .
  var r vec u32 4 be reverse v .
  var t vec u32 4 be rotate r 1 .
  store ys 0 t .
  return reduce_add t .
end

rem 이 기계가 u32 레인을 한 번에 몇 개 다루나 --- 번역 시점의 수
fn lanes_here output u64 .
do
  return native_lanes u32 .
end

실행 결과

$ lowentc --run capped_sum lanes.low [1,0,0,0,9,0,0,0,3,0,0,0,7,0,0,0]
capped_sum([1,0,0,0,9,0,0,0,3,0,0,0,7,0,0,0]) = 14
  arg0 (written) = [1,0,0,0,9,0,0,0,3,0,0,0,7,0,0,0]
$ lowentc --run extremes lanes.low [1,0,0,0,9,0,0,0,3,0,0,0,7,0,0,0]
extremes([1,0,0,0,9,0,0,0,3,0,0,0,7,0,0,0]) = 9289
  arg0 (written) = [1,0,0,0,9,0,0,0,3,0,0,0,7,0,0,0]
$ lowentc --run turned lanes.low [1,0,0,0,9,0,0,0,3,0,0,0,7,0,0,0] [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
turned([1,0,0,0,9,0,0,0,3,0,0,0,7,0,0,0], [3,0,0,0,9,0,0,0,1,0,0,0,7,0,0,0]) = 20
  arg0 (written) = [1,0,0,0,9,0,0,0,3,0,0,0,7,0,0,0]
  arg1 (written) = [3,0,0,0,9,0,0,0,1,0,0,0,7,0,0,0]
$ lowentc --run lanes_here lanes.low
lanes_here() = 4

load xs 0 은 슬라이스의 0 번 자리부터 레인 넷을 읽는다. store ys 0 t 는 거꾸로 쓴다.
splat 5 는 모든 레인에 5 를 채운다. 레인 수는 담는 이름의 타입(vec u32 4)이 알려 준다.
gt v lim 처럼 vec 끼리 비교하면 레인마다 참거짓이 담긴 가림막 mask 4 가 나온다. select over lim v 는 가림막이 켜진 레인에서 lim 을, 꺼진 레인에서 v 를 고른다. 갈래(if) 없이 레인마다 고르므로 기계가 한 명령으로 처리한다.
reduce_add·reduce_max·reduce_min·reduce_mul 은 레인을 가로질러 하나로 모은다. [1,9,3,7] 을 5 로 누르면 [1,5,3,5] 라서 합이 14 다.
reverse 는 레인의 차례를 뒤집고, rotate r 1 은 한 칸 돌린다. [7,3,9,1] 을 돌린 [3,9,1,7] 이 메모리에 쓰였다.
native_lanes u32 는 이 기계가 u32 레인을 한 번에 몇 개 다루는지를 번역 시점에 준다. 레인 수를 그 수로 고르면 한 번에 더 많이 셈할 뿐 답은 같다.

가림막으로 일부 레인만 읽거나 쓸 수도 있다.

examples/ch27/masked.low

module masked .
rem run: keep_big [1,0,0,0,9,0,0,0,3,0,0,0,7,0,0,0] [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
rem run: read_big [1,0,0,0,9,0,0,0,3,0,0,0,7,0,0,0]

rem 5 보다 큰 레인만 쓴다 --- 가려진 레인의 자리는 건드리지 않는다
proc keep_big input b slice u8 . input out mut slice u8 . output u64 . effects none .
  requires ge (len b) 16 .
  requires ge (len out) 16 .
do
  var xs slice u32 be view_array u32 b .
  var v vec u32 4 be load xs 0 .
  var lim vec u32 4 be splat 5 .
  var m mask 4 be gt v lim .
  store_masked out 0 v m .
  return 0 .
end

rem 켜진 레인만 읽고 나머지 레인에는 기본값 100 을 둔다
proc read_big input b slice u8 . output u32 . effects none .
  requires ge (len b) 16 .
do
  var xs slice u32 be view_array u32 b .
  var v vec u32 4 be load xs 0 .
  var lim vec u32 4 be splat 5 .
  var m mask 4 be gt v lim .
  var fallback vec u32 4 be splat 100 .
  var r vec u32 4 be load_masked xs 0 m fallback .
  return reduce_add r .
end

실행 결과

$ lowentc --run keep_big masked.low [1,0,0,0,9,0,0,0,3,0,0,0,7,0,0,0] [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
keep_big([1,0,0,0,9,0,0,0,3,0,0,0,7,0,0,0], [0,0,0,0,9,0,0,0,0,0,0,0,7,0,0,0]) = 0
  arg0 (written) = [1,0,0,0,9,0,0,0,3,0,0,0,7,0,0,0]
  arg1 (written) = [0,0,0,0,9,0,0,0,0,0,0,0,7,0,0,0]
$ lowentc --run read_big masked.low [1,0,0,0,9,0,0,0,3,0,0,0,7,0,0,0]
read_big([1,0,0,0,9,0,0,0,3,0,0,0,7,0,0,0]) = 216
  arg0 (written) = [1,0,0,0,9,0,0,0,3,0,0,0,7,0,0,0]

store_masked out 0 v m 은 켜진 레인(9 와 7)의 자리에만 쓰고 나머지 자리는 건드리지 않는다. load_masked xs 0 m fallback 은 켜진 레인만 읽고 꺼진 레인에는 기본값 100 을 둔다. 슬라이스 끝에 네 칸이 다 남지 않을 때 꼬리를 처리하는 모양이 이것이다.

op	무엇을 하나	적어 둘 것
`load` · `store` · `load_masked` · `store_masked`	메모리와 레인 사이를 읽고 쓴다	가림막 판은 켜진 레인만
`splat` · `select`	한 값을 모든 레인에 · 가림막으로 레인마다 고르기	`splat` 은 타입 문맥이 필요하다(아래)
`reduce_add` · `reduce_max` · `reduce_min` · `reduce_mul`	레인을 하나로 모은다	결과는 원소 타입
`reverse` · `rotate`	레인의 차례를 뒤집는다 · 돌린다	칸 수는 번역 시점 상수
`native_lanes`	이 기계의 레인 수(번역 시점)	답을 바꾸지 않는다
`sum_neumaier` · `sum_seq`	`view_array` 로 본 부동소수 조각을 모두 더한다	레인 op 이 아니다 — 이름이 더하는 방법을 말한다(보정 · 앞에서 뒤로)
`avg`	레인마다 반올림하는 평균	값이 `(a+b+1)>>1` 로 정해져 있다 — 레인이 넘치지 않도록 넓혀 더한다
`prefetch xs i`	곧 쓸 자리를 미리 캐시로 끌어 온다	뜻을 바꾸지 않는 성능 힌트

표 27.3 — 레인과 배열을 다루는 내장 op

두 가지를 조심한다. 첫째, splat 은 레인 수를 선언된 타입에서 받으므로 식 안에 바로 쓸 수 없다. 둘째, 레인을 더하는 것과 조각을 더하는 것은 다른 op 이다 — 레인은 reduce_add, 부동소수 조각은 sum_neumaier·sum_seq 다. 2026-09-17 까지는 뒤엣것의 이름이 sum·sum_fast 였고, 정본은 같은 이름으로 «레인을 더한다» 를 적고 있었다. 한 이름이 두 가지를 뜻했으므로 이름을 갈랐다(정본 6.3.7.1).

반례. splat 을 식 안에 바로 적는다

examples/ch27/mistake_splatinline.low

module mistake_splatinline .
rem expect: E-VEC-SPLAT

fn capped input b slice u8 . output u32 .
do
  var xs slice u32 be view_array u32 b .
  var v vec u32 4 be load xs 0 .
  rem ✘ `splat` 을 식 안에 바로 적었다 --- 레인 수를 말해 줄 타입이 없다
  var over mask 4 be gt v (splat 5) .
  return reduce_add (select over v v) .
end

실행 결과

$ lowentc --check mistake_splatinline.low
mistake_splatinline.low:9:0 E-VEC-SPLAT: `splat` fills every lane of a vector, and how many lanes there are comes from the declared type — inside an expression there is nothing to say it, so the value is read as a plain scalar and the surrounding comparison stops matching its `mask` type. Bind it first, with the lane count written down: `var lim vec u32 4 be splat 5 .`, then use `lim`
mistake_splatinline.low:9:0 E-TYPE-VAR: the initializer's type does not match the declared type — expected `mask`, found `bool`

splat 은 한 값을 모든 레인에 채우는데, 레인이 몇인지는 선언된 타입만이 말한다. 식 안에는 그것을 말해 줄 자리가 없어 값이 스칼라로 읽히고, 감싼 비교가 mask 타입과 어긋난다. E-VEC-SPLAT 으로 거절하며, 고치는 길은 레인 수를 적은 이름에 먼저 담는 것이다 — var lim vec u32 4 be splat 5 . 뒤에 gt v lim 이다.

27.7 자리를 어떻게 쓰는지 적는다 — `access`#

access <이름> <모드> . 절은 op 이 입력 자리를 읽기만 하는지, 쓰기만 하는지 머리에 적는다. 부르는 쪽과 스케줄러가 그 약속을 믿고 판단한다.

examples/ch27/access.low

module access .
rem run: peek [9,8,7]

rem access data shared_read — 이 op 은 data 를 읽기만 한다. 여러 태스크가 함께 쥘 수 있다는 약속이다
fn peek input data slice u8 . output u64 .
  access data shared_read .
do
  return widen u64 (index data 0) .
end

실행 결과

$ lowentc --run peek access.low [9,8,7]
peek([9,8,7]) = 9
  arg0 (written) = [9,8,7]

shared_read 는 “읽기만 한다” 이다. 쓰기가 없으면 경합도 없으므로 여러 태스크가 같은 자리를 함께 쥘 수 있다. write_only 는 “쓰기만 한다” 이고, 아직 채워지지 않은 버퍼를 넘겨도 된다는 뜻이다. 두 모드는 도구가 몸을 보고 검사한다. sequential 같은 나머지 모드는 커널 스케줄링 힌트라 아직 아무것도 강제하지 않으며, 적으면 W-NOT-YET 이 그렇다고 말한다.

27.8 흔한 실수#

반례. 나누어 도는 조각들이 공유 카운터를 보통 연산으로 올린다

examples/ch27/mistake_sharedwrite.low

module mistake_sharedwrite .
rem expect: E-PAR-WRITE

proc count_par input data slice u8 . input counter mut slice u64 . output void . effects none .
  parallel data split .
do
  var i u64 be 0 .
  while lt i (len data) . do
    rem ✘ 모든 조각이 같은 자리 `index counter 0` 에 읽고 더해 쓴다
    set (index counter 0) (wrap_add (index counter 0) 1) .
    set i (add i 1) .
  end
  return .
end

실행 결과

$ lowentc --check mistake_sharedwrite.low
mistake_sharedwrite.low:10:0 E-PAR-WRITE: a splittable loop may only write its OWN element `index <s> <i>` — this write can collide with another iteration (Bernstein: wr ∩ wr = ∅)

조각마다 index counter 0 을 읽고 1 을 더해 쓴다. 두 스레드가 같은 값을 읽고 각자 더해 쓰면 하나가 사라진다. 이것은 자기 몫이 아닌 자리에 쓰는 것이라 E-PAR-WRITE 로 거절된다. 공유 자리를 함께 갱신해야 하면 cap atomic 을 받고 atomic_add counter 0 1 을 쓴다(이 장의 counter.low). 대개는 그보다 조각마다 센 값을 reduce 로 모으는 편이 빠르다.

반례. 부동소수의 합을 나누어 모은다

examples/ch27/mistake_floatreduce.low

module mistake_floatreduce .
rem expect: E-PAR-FLOAT

fn mean input s slice f64 . output f64 .
  parallel s split .
  rem ✘ 부동소수의 덧셈은 묶는 차례에 따라 답이 달라진다
  reduce acc add .
do
  var acc f64 be 0.0 .
  var i u64 be 0 .
  while lt i (len s) . do
    set acc (add acc (index s i)) .
    set i (add i 1) .
  end
  return acc .
end

실행 결과

$ lowentc --check mistake_floatreduce.low
mistake_floatreduce.low:9:0 E-PAR-IDENTITY: the accumulator this reduction starts from is not the IDENTITY of its operator, so a split answer is not the sequential one: every piece starts again from that value and it is counted once per piece (measured: sequential 121, native split 621). DET-1 promises a split is bit-identical — that holds only from the identity (`add`/`bit_or`/`bit_xor` → 0, `mul` → 1, `max` → 0 on an unsigned width). Start from the identity and add the offset once, after the loop
mistake_floatreduce.low:9:0 E-PAR-FLOAT: a FLOAT reduction cannot be split: float addition is not associative, so the tree shape changes the result and the answer would depend on the schedule (★ nonassoc_shape_matters, Qed). Use the sequential `sum` (Neumaier) — determinism is part of the meaning, not a detail
mistake_floatreduce.low:4:0 W-PAR-OK: this loop satisfies the Bernstein conditions and may be split (DET-1 proves the parallel result is bit-identical to the sequential one — docs/proofs/coq/LowentPar.v). Execution is still sequential, which is a VALID implementation precisely because of that theorem

부동소수의 덧셈은 결합적이지 않다. 조각을 어떻게 나누느냐에 따라 반올림이 달라져 답이 코어 수에 달린다. 그래서 E-PAR-FLOAT 다. 진단이 권하는 대로 순차의 sum_neumaier(오차를 보정하는 합)를 쓴다. 결정성은 성능 옵션이 아니라 뜻의 일부다.

반례. reduce 의 누산을 항등원이 아닌 값에서 시작한다

examples/ch27/mistake_reduceinit.low

module mistake_reduceinit .
rem expect: E-PAR-IDENTITY

fn total input s slice u8 . output u64 .
  parallel s split .
  reduce acc add .
do
  rem ✘ 누산을 100 에서 시작한다 --- 나누면 조각마다 100 에서 시작한다
  var acc u64 be 100 .
  var i u64 be 0 .
  while lt i (len s) . do
    set acc (add acc (widen u64 (index s i))) .
    set i (add i 1) .
  end
  return acc .
end

실행 결과

$ lowentc --check mistake_reduceinit.low
mistake_reduceinit.low:9:0 E-PAR-IDENTITY: the accumulator this reduction starts from is not the IDENTITY of its operator, so a split answer is not the sequential one: every piece starts again from that value and it is counted once per piece (measured: sequential 121, native split 621). DET-1 promises a split is bit-identical — that holds only from the identity (`add`/`bit_or`/`bit_xor` → 0, `mul` → 1, `max` → 0 on an unsigned width). Start from the identity and add the offset once, after the loop
mistake_reduceinit.low:4:0 W-PAR-OK: this loop satisfies the Bernstein conditions and may be split (DET-1 proves the parallel result is bit-identical to the sequential one — docs/proofs/coq/LowentPar.v). Execution is still sequential, which is a VALID implementation precisely because of that theorem

순차로 돌면 total [1,2,3,4,5,6] 은 100 + 21 = 121 이다. 나누어 돌면 조각마다 acc 가 100 에서 시작한다. 네이티브에서 여섯 조각으로 나누면 621 이 나왔다 — 나눈 답이 순차와 같아야 한다는 약속이 깨지는 자리다. 그래서 E-PAR-IDENTITY 로 거절한다(2026-09-16 까지는 W-PAR-OK 로 통과했다). reduce 의 시작값은 모으는 연산의 항등원이어야 한다 — add·bit_or·bit_xor 는 0, mul 은 1, 부호 없는 폭의 max 는 0. 더할 값이 있으면 되풀이 밖에서 결과에 더한다.

반례. 나눌 되풀이를 다른 모양으로 적는다

examples/ch27/mistake_noloop.low

module mistake_noloop .
rem expect: E-PAR-NOLOOP

proc smooth input s mut slice u8 . output u64 . effects none .
  parallel s split .
do
  var i u64 be 0 .
  rem ✘ 나눌 되풀이는 `while lt i (len s)` 모양이어야 한다 --- 이웃 원소를 읽는 되풀이이기도 하다
  while lt (add i 1) (len s) . do
    set (index s i) (div (wrap_add (index s i) (index s (add i 1))) 2) .
    set i (add i 1) .
  end
  return len s .
end

실행 결과

$ lowentc --check mistake_noloop.low
mistake_noloop.low:4:0 E-PAR-NOLOOP: the `parallel` clause names a slice, but no `while lt <i> (len <slice>) . do … end` loop was found to split. That clause is a CLAIM — DET-1 proves a split is bit-identical only when there IS a loop to split — so with no loop the compiler verifies NOTHING while the annotation still tells every reader it was checked. An unchecked promise is the lie PRINCIPLES.md §0 is about; the same judgement already refused `mailbox unbounded` and `bounded 0`. Delete the clause (it means nothing here) or write the loop it describes

처리기는 while lt i (len s) . do … end 모양의 되풀이만 나눌 대상으로 알아본다. while lt (add i 1) (len s) 는 그 모양이 아니라서 E-PAR-NOLOOP 다. 진단의 말대로 parallel 절은 주장이고, 나눌 되풀이를 찾지 못하면 아무것도 확인하지 못한 채 주장만 남는다. 게다가 이 되풀이는 이웃 원소 index s (add i 1) 을 읽는다. 모양을 고쳐도 E-PAR-READ 로 거절될 것이다 — 이웃을 읽는 계산(평활화 따위)은 결과를 다른 슬라이스에 쓰는 순차 되풀이로 적는다.

반례. write_only 라고 적고 읽는다

examples/ch27/mistake_access.low

module mistake_access .
rem expect: E-ACCESS-MODE

rem ✘ write_only 라고 적고 읽는다 — 아직 채워지지 않은 자리일 수 있다
proc bad_fill input out mut slice u8 . . output u64 . effects state .
  access out write_only .
do
  let x u8 be index out 0 .
  return widen u64 x .
end

실행 결과

$ lowentc --check mistake_access.low
mistake_access.low:5:0 E-ACCESS-MODE: `access <p> write_only` says this op never READS that place — but it does. A write_only place may be uninitialised: reading it is reading garbage, and the declaration is what told the caller it was safe
mistake_access.low:7:1 W-EFFECT-OVER: this op DECLARES `state` but never PERFORMS it. A declared effect is a cost the caller must budget for (a pure caller cannot call an `io` op). Drop it, or — if a future version will perform it — say so (RFC-0007)

write_only 자리는 채워지지 않았을 수 있으므로, 읽으면 쓰레기를 읽는 것이다. 부르는 쪽은 그 선언을 믿고 빈 버퍼를 넘긴다. 그래서 E-ACCESS-MODE 로 거절한다. 함께 붙은 W-EFFECT-OVER 는 호출자 버퍼 쓰기를 효과로 세는 판정이 갈라진 결함 탓이다(24장). 읽어야 한다면 모드를 지우고 보통 입력으로 받는다.

흔한 오해. reduce 로 모을 수 있는 것은 덧셈뿐이다

examples/ch27/max_gather.low

module max_gather .
rem run: biggest [3,9,2,7]
rem `max` 도 결합적이고 0 이 항등원이라 나누어 모을 수 있다
fn biggest input s slice u8 . output u64 .
  parallel s split .
  reduce best max .
do
  var best u64 be 0 .
  var i u64 be 0 .
  while lt i (len s) . do
    set best (max best (widen u64 (index s i))) .
    set i (add i 1) .
  end
  return best .
end

실행 결과

$ lowentc --run biggest max_gather.low [3,9,2,7]
biggest([3,9,2,7]) = 9
  arg0 (written) = [3,9,2,7]

결합적인 연산이면 모을 수 있다. max 는 결합적이고 u64 에서 0 이 항등원이라 조각마다 가장 큰 값을 구해 다시 max 로 합쳐도 답이 같다. min·mul·비트 연산도 같은 원리다. 거절되는 것은 sub 처럼 묶는 차례가 답을 바꾸는 연산(E-PAR-ASSOC)과 부동소수 연산(E-PAR-FLOAT)이다.

27.9 이 장의 문법 한눈에#

모양	뜻	왜 이렇게
`parallel s split .`(op 머리)	`s` 를 조각으로 나누어 여럿이 돌아도 된다는 선언	주장을 믿지 않고 확인한다 — 확인되면 `W-PAR-OK`
`while lt i (len s) . do … end`	나눌 수 있는 되풀이의 모양	다른 모양이면 `E-PAR-NOLOOP`
`index s i` 만 읽고 쓰기	자기 몫만	남의 자리는 `E-PAR-READ` · `E-PAR-WRITE`
`reduce acc add .`	조각마다 누적한 뒤 연산으로 합친다	시작값은 항등원 — 연산은 결합적(`E-PAR-ASSOC`)
`atomic_add counter 0 1` · `atomic_load cells 0`	슬라이스와 색인으로 가리킨 자리를 원자적으로	`effects atomic` + `cap atomic`
`… order seq_cst` · `acq_rel` · `acquire` · `release` · `relaxed`	기억 차례 — 적지 않으면 `seq_cst`	가장 추론하기 쉬운 것이 기본
읽기에 `order release` 따위	거절(`E-ATOMIC-ORDER`)	뜻 없는 조합을 정의되지 않은 동작으로 두지 않는다
`view_array u64 bytes`	바이트를 베끼지 않고 `u64` 슬라이스로 본다	원자 칸을 할당받은 창 위에 둔다
`var v vec u32 4 be load xs 0 .` · `reduce_add v`	레인 넷을 한 값으로 읽기 · 레인 모으기	한 흐름 안의 SIMD — 레인 수는 타입의 일부
`access data shared_read .` · `access out write_only .`	읽기만 · 쓰기만 한다는 약속 — 몸을 검사한다	읽기만이면 여러 태스크가 함께 쥔다 · 어기면 `E-ACCESS-MODE`

표 27.4 — 병렬과 원자 연산의 문법 — 모양 · 뜻 · 왜 이렇게 생겼나

복습 정리

parallel <슬라이스> split . 은 되풀이를 나눌 수 있다는 선언이고, 처리기는 자기 몫만 읽고 쓰며 걸음을 넘어 사는 자리에 쓰지 않는지 확인한다. 누적은 reduce <자리> <연산> . 으로 밝히고 연산은 결합적이어야 한다. 나누어 돈 답은 순차와 비트까지 같다. 공유 자리를 함께 갱신할 때는 cap atomic 을 받아 원자 연산을 쓰고, order 로 기억 차례를 고르되 기본은 seq_cst 이며 뜻 없는 조합은 거절된다.

← 이전목차로다음 →