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

(github.com/judofyr)

2P by neo 1달전 | favorite | 댓글 1개

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;
}

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

Work-stealing과 비효율성

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

구현 세부 사항

정적 디스패치 최적화

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

저오버헤드 하트비트 신호

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

글로벌 뮤텍스

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

분기 없는 이중 연결 리스트

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

스택 사용 최소화

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

레지스터를 통한 값 전달

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

벤치마크

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

감사의 글

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

한계

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

FAQ

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

GN⁺의 정리

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

▲

neo 1달전 [-]

Hacker News 의견

이 구현은 최근 연구인 "heartbeat scheduling"에 기반을 두고 있으며, 병렬성 생성의 오버헤드를 분산시켜 동적 자동 세분화 제어를 달성함
- 관련 논문:
  - (2018) Heartbeat Scheduling: Provable Efficiency for Nested Parallelism
  - (2021) Task Parallel Assembly Language for Uncompromising Parallelism
  - (2024) Compiling Loop-Based Nested Parallelism for Irregular Workloads
  - (2024) Automatic Parallelism Management
코드의 세부 사항을 읽어보진 않았지만 "sub-nanosecond overhead"는 오해의 소지가 있으며 마케팅 용어임
- 첫 번째로, 측정은 "thing 당 시간"이라는 복잡한 방식으로 보이며, 스레드 수는 "thing" 수보다 훨씬 적음
이 분야에 익숙하지 않지만, 제시된 동시성 모델이 마음에 듦
- README가 잘 작성되어 있어 내용을 이해하기 쉬웠지만, 몇몇 부분은 이해하기 어려웠음
- 다행히 코드가 읽기 쉬움
흥미로운 연구 작업이며, 코드 외에도 좋은 논리와 잘 작성된 문서가 있음
- 2018년 heartbeat scheduling 논문도 흥미로움
프로젝트의 한계 목록:
- 한계 목록 링크
설명에 따르면, 이 구현은 작업자들이 나노초 수준의 지연 시간을 달성하기 위해 바쁜 대기를 사용함
- 수만 개의 작업을 가진 대형 애플리케이션에서 바쁜 대기가 얼마나 현실적인지 궁금함
- 작업이 비동기적이라면 (즉, 스레드 기반이 아닌) 실행자의 스레드 풀 크기만큼의 대기자가 있을 수 있음
- 이러한 아키텍처의 에너지 소비가 더 높을 것임
작업 생산자가 소비자를 바쁜 대기 없이 깨우는 더 빠른 방법이 있는지 궁금함
- 생산자 시간 슬라이스에서 소비자를 실행하여 가능할지 궁금함
- 사용자 공간 FUTEX_WAKE 작업을 통해 소비자를 깨우는 일반적인 페널티를 절반으로 줄일 수 있을지 궁금함
흥미롭고 훌륭한 논문들과 연결되어 있음
- OpenMP 작업과의 비교가 있었으면 좋겠음
- Rayon이 약간 느리다는 평판이 있음
협력적 스케줄링은 훌륭한 메트릭을 가진 많은 패턴의 기초임
훌륭함
벤치마크 관련 README도 참고:
- 벤치마크 README 링크

답변달기