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

> Clean Markdown view of GeekNews topic #16307. Use the original source for factual precision when an external source URL is present.

## Metadata

- GeekNews HTML: [https://news.hada.io/topic?id=16307](https://news.hada.io/topic?id=16307)
- GeekNews Markdown: [https://news.hada.io/topic/16307.md](https://news.hada.io/topic/16307.md)
- Type: GN+
- Author: [neo](https://news.hada.io/@neo)
- Published: 2024-08-14T09:43:26+09:00
- Updated: 2024-08-14T09:43:26+09:00
- Original source: [github.com/judofyr](https://github.com/judofyr/spice)
- Points: 2
- Comments: 1

## Topic Body

### Spice: Sub-nanosecond Overhead의 병렬 처리

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

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

#### 성능 비교

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

#### 작은 트리에서의 성능

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

#### Spice의 목표

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

#### Spice 사용법

```zig
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**와 같은 다른 언어에서도 유사한 접근 방식을 탐구할 가치가 있음

## Comments



### Comment 27994

- Author: neo
- Created: 2024-08-14T09:43:26+09:00
- Points: 1

###### [Hacker News 의견](https://news.ycombinator.com/item?id=41230344) 
- 이 구현은 최근 연구인 "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 논문도 흥미로움

- 프로젝트의 한계 목록:
  - [한계 목록 링크](https://github.com/judofyr/spice?tab=readme-ov-file#limitations)

- 설명에 따르면, 이 구현은 작업자들이 나노초 수준의 지연 시간을 달성하기 위해 바쁜 대기를 사용함
  - 수만 개의 작업을 가진 대형 애플리케이션에서 바쁜 대기가 얼마나 현실적인지 궁금함
  - 작업이 비동기적이라면 (즉, 스레드 기반이 아닌) 실행자의 스레드 풀 크기만큼의 대기자가 있을 수 있음
  - 이러한 아키텍처의 에너지 소비가 더 높을 것임

- 작업 생산자가 소비자를 바쁜 대기 없이 깨우는 더 빠른 방법이 있는지 궁금함
  - 생산자 시간 슬라이스에서 소비자를 실행하여 가능할지 궁금함
  - 사용자 공간 FUTEX_WAKE 작업을 통해 소비자를 깨우는 일반적인 페널티를 절반으로 줄일 수 있을지 궁금함

- 흥미롭고 훌륭한 논문들과 연결되어 있음
  - OpenMP 작업과의 비교가 있었으면 좋겠음
  - Rayon이 약간 느리다는 평판이 있음

- 협력적 스케줄링은 훌륭한 메트릭을 가진 많은 패턴의 기초임

- 훌륭함

- 벤치마크 관련 README도 참고:
  - [벤치마크 README 링크](https://github.com/judofyr/spice/blob/main/bench/README.md)