GN⁺: Spice: Zig에서 서브나노초 오버헤드로 세밀한 병렬 처리 기술

Spice: Sub-nanosecond Overhead의 병렬 처리

Spice는 Zig에서 _heartbeat scheduling_을 사용하여 매우 효율적인 병렬 처리를 달성함

• 서브 나노초 오버헤드: 함수에 병렬 처리 기능을 추가해도 나노초 미만의 오버헤드만 발생함
• 경쟁 없음: 스레드가 동일한 작업을 두고 경쟁하지 않음. 시스템에 스레드를 추가해도 프로그램이 느려지지 않음

성능 비교

• Rayon (Rust): 4개의 스레드에서 약 15ns의 오버헤드 발생. 16개의 스레드에서 약 14배의 속도 향상
• Spice (Zig): 16개의 스레드에서 약 11배의 속도 향상. 오버헤드가 낮아 기본 성능과 거의 동일함

작은 트리에서의 성능

• 작은 트리: 프로그램의 총 실행 시간이 1.56 마이크로초. 스레드를 추가할수록 성능이 저하됨
• 병렬 처리의 일반적인 지혜: 충분한 작업이 없으면 병렬 처리가 가치가 없음

Spice의 목표

• 목표: 병렬 처리를 추가해도 프로그램이 느려지지 않도록 하는 것
• 짧은 실행 시간: 실행 시간이 짧으면 멀티스레딩이 작동하지 않음. 추가된 스레드는 대기 상태로 전환됨

Spice 사용법

const spice = @import("spice");

fn sum(t: *spice.Task, node: *const Node) i64 {
    var res: i64 = node.val;

    if (node.left) |left_child| {
        if (node.right) |right_child| {
            var fut = spice.Future(*const Node, i64).init();
            fut.fork(t, sum, right_child);
            res += t.call(i64, sum, left_child);

            if (fut.join(t)) |val| {
                res += val;
            } else {
                res += t.call(i64, sum, right_child);
            }
            return res;
        }
        res += t.call(i64, sum, left_child);
    }

    if (node.right) |right_child| {
        res += t.call(i64, sum, right_child);
    }

    return res;
}

1. 모든 병렬 함수는 _task_를 매개변수로 받아야 함
2. 함수를 직접 호출하지 말고 t.call을 사용해야 함
3. fork를 호출하여 다른 스레드에서 작업을 설정함
4. 함수는 자체적으로 의미 있는 작업을 수행해야 함
5. join을 호출하여 다른 스레드의 작업 완료를 기다림
6. join이 null을 반환하면 작업을 직접 수행해야 함

Work-stealing과 비효율성

• Work-stealing: 각 스레드는 자체 로컬 작업 큐를 가짐. 큐가 비면 다른 스레드의 작업을 훔침
• 비효율성: 동적 디스패치, 로컬이 아닌 작업 큐, 스핀 락

구현 세부 사항

정적 디스패치 최적화

• 코드 블록 병렬 실행: fork와 join을 사용하여 코드 블록을 병렬로 실행함
• 중복 제거: 코드 블록이 다른 스레드에서 실행되지 않으면 순차적으로 실행됨

저오버헤드 하트비트 신호

• 하트비트 스케줄링: 100 마이크로초마다 로컬 작업 큐를 확인하고 다른 스레드로 작업을 보냄
• 효율성: 하트비트가 발생하지 않을 때 함수가 효율적으로 동작해야 함

글로벌 뮤텍스

• 글로벌 뮤텍스 사용: 글로벌 뮤텍스는 경쟁이 없을 때 문제가 없음

분기 없는 이중 연결 리스트

• 이중 연결 리스트: 작업 큐를 관리하기 위해 사용됨. 분기 없이 동작함

스택 사용 최소화

• 스택 사용 최적화: Future의 상태를 최소화하여 스택 사용을 줄임

레지스터를 통한 값 전달

• 레지스터 사용: Task 구조체의 필드를 레지스터로 전달하여 성능 최적화

벤치마크

• 벤치마크: 초기 개발은 단일 벤치마크를 중심으로 이루어짐

감사의 글

• 하트비트 스케줄링 연구: 여러 연구 논문에 기반하여 개발됨

한계

• 제약 조건: 잘못 사용하면 이상한 동작이 발생할 수 있음
• 테스트 부족: 테스트 커버리지가 부족함
• 배열/슬라이스 지원 부족: 배열/슬라이스에 대한 병렬 처리 지원이 부족함
• 문서 부족: 사용법에 대한 문서가 부족함
• 추가 벤치마크 부족: 추가 벤치마크가 필요함
• 에러 처리: 에러 처리에 대한 고려가 부족함
• ReleaseSafe 테스트 부족: ReleaseSafe 모드에서의 테스트가 필요함

FAQ

• 이름의 유래: 매우 세밀한 병렬 처리를 의미함
• Zig로 구현된 이유: 다양한 언어에서 구현 가능함
• Rust에서의 안전한 병렬 처리: Rust의 엄격한 의미론으로 인해 초기 아이디어 탐색이 어려움

GN⁺의 정리

• Spice는 Zig에서 매우 효율적인 병렬 처리를 제공하는 연구 프로젝트임
• 서브 나노초 오버헤드와 경쟁 없는 병렬 처리로 성능을 극대화함
• 하트비트 스케줄링을 통해 작업을 효율적으로 분배함
• 제약 조건과 테스트 부족 등의 한계가 있음
• Rust와 같은 다른 언어에서도 유사한 접근 방식을 탐구할 가치가 있음