Spice: Kỹ thuật xử lý song song cực mịn trong Zig với chi phí dưới nano giây
(github.com/judofyr)Spice: Xử lý song song với chi phí dưới nano giây
Spice đạt được khả năng xử lý song song cực kỳ hiệu quả trong Zig bằng cách sử dụng heartbeat scheduling
- Chi phí dưới nano giây: Ngay cả khi thêm khả năng xử lý song song vào hàm, chi phí phát sinh vẫn chỉ ở mức dưới một nano giây
- Không tranh chấp: Các luồng không tranh chấp cùng một công việc. Ngay cả khi thêm luồng vào hệ thống, chương trình cũng không bị chậm đi
So sánh hiệu năng
- Rayon (Rust): Phát sinh khoảng 15ns chi phí trên 4 luồng. Đạt tăng tốc khoảng 14 lần trên 16 luồng
- Spice (Zig): Đạt tăng tốc khoảng 11 lần trên 16 luồng. Do chi phí thấp nên hiệu năng gần như tương đương bản gốc
Hiệu năng trên cây nhỏ
- Cây nhỏ: Tổng thời gian chạy của chương trình là 1.56 micro giây. Càng thêm luồng thì hiệu năng càng giảm
- Nhận thức phổ biến về xử lý song song: Nếu không có đủ công việc, xử lý song song không đáng để dùng
Mục tiêu của Spice
- Mục tiêu: Thêm xử lý song song mà không làm chương trình chậm đi
- Thời gian chạy ngắn: Nếu thời gian chạy quá ngắn thì đa luồng sẽ không phát huy tác dụng. Các luồng được thêm vào sẽ chuyển sang trạng thái chờ
Cách dùng 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;
}
- Mọi hàm song song đều phải nhận task làm tham số
- Không được gọi hàm trực tiếp mà phải dùng
t.call - Gọi
forkđể thiết lập công việc trên một luồng khác - Bản thân hàm phải tự thực hiện một lượng công việc đủ ý nghĩa
- Gọi
joinđể chờ công việc trên luồng khác hoàn tất - Nếu
jointrả vềnullthì phải tự thực hiện công việc đó
Work-stealing và sự kém hiệu quả
- Work-stealing: Mỗi luồng có hàng đợi công việc cục bộ riêng. Khi hàng đợi trống, nó sẽ lấy cắp công việc từ luồng khác
- Kém hiệu quả: Dynamic dispatch, hàng đợi công việc không cục bộ, spin lock
Chi tiết triển khai
Tối ưu static dispatch
- Chạy song song các khối mã: Dùng
forkvàjoinđể chạy song song các khối mã - Loại bỏ trùng lặp: Nếu khối mã không được chạy trên luồng khác thì nó sẽ được chạy tuần tự
Tín hiệu heartbeat chi phí thấp
- Heartbeat scheduling: Cứ mỗi 100 micro giây sẽ kiểm tra hàng đợi công việc cục bộ và chuyển việc sang luồng khác
- Hiệu quả: Khi heartbeat không xảy ra, hàm vẫn phải hoạt động hiệu quả
Global mutex
- Dùng global mutex: Global mutex không phải vấn đề khi không có tranh chấp
Danh sách liên kết kép không rẽ nhánh
- Danh sách liên kết kép: Được dùng để quản lý hàng đợi công việc. Hoạt động không cần rẽ nhánh
Giảm tối đa việc dùng stack
- Tối ưu sử dụng stack: Giảm trạng thái của
Futurexuống mức tối thiểu để giảm dùng stack
Truyền giá trị qua thanh ghi
- Dùng thanh ghi: Truyền các trường của cấu trúc
Taskqua thanh ghi để tối ưu hiệu năng
Benchmark
- Benchmark: Việc phát triển ban đầu xoay quanh một benchmark duy nhất
Lời cảm ơn
- Nghiên cứu heartbeat scheduling: Được phát triển dựa trên nhiều bài báo nghiên cứu
Hạn chế
- Ràng buộc: Nếu dùng sai có thể gây ra hành vi kỳ lạ
- Thiếu kiểm thử: Độ bao phủ kiểm thử còn thấp
- Thiếu hỗ trợ mảng/slice: Hỗ trợ xử lý song song cho mảng/slice còn hạn chế
- Thiếu tài liệu: Tài liệu hướng dẫn sử dụng còn ít
- Thiếu benchmark bổ sung: Cần thêm benchmark
- Xử lý lỗi: Chưa xem xét đầy đủ việc xử lý lỗi
- Thiếu kiểm thử ReleaseSafe: Cần kiểm thử trong chế độ ReleaseSafe
FAQ
- Nguồn gốc tên gọi: Mang ý nghĩa xử lý song song cực kỳ mịn
- Lý do được triển khai bằng Zig: Có thể triển khai trong nhiều ngôn ngữ khác nhau
- Xử lý song song an toàn trong Rust: Do ngữ nghĩa nghiêm ngặt của Rust, việc khám phá ý tưởng ban đầu khó khăn hơn
Tóm tắt của GN⁺
- Spice là một dự án nghiên cứu cung cấp khả năng xử lý song song rất hiệu quả trong Zig
- Chi phí dưới nano giây và xử lý song song không tranh chấp giúp tối đa hóa hiệu năng
- Heartbeat scheduling giúp phân phối công việc hiệu quả
- Có những hạn chế như ràng buộc và thiếu kiểm thử
- Cũng đáng để khám phá cách tiếp cận tương tự trong các ngôn ngữ khác như Rust
1 bình luận
Ý kiến Hacker News
Cách triển khai này dựa trên nghiên cứu gần đây có tên "heartbeat scheduling", phân tán chi phí tạo song song để đạt được cơ chế kiểm soát tự động phân nhỏ động
Tôi chưa đọc chi tiết mã nguồn, nhưng cụm "sub-nanosecond overhead" dễ gây hiểu lầm và mang tính marketing
Tôi không rành lĩnh vực này, nhưng thích mô hình đồng thời được đưa ra
Đây là một công trình nghiên cứu thú vị, và ngoài mã nguồn còn có lập luận tốt cùng tài liệu được viết chỉn chu
Danh sách giới hạn của dự án:
Theo phần mô tả, cách triển khai này dùng busy-wait để các worker đạt độ trễ ở mức nano giây
Tôi tự hỏi liệu có cách nhanh hơn để producer đánh thức consumer mà không cần busy-wait hay không
Rất thú vị và có liên kết đến những bài báo rất hay
Cooperative scheduling là nền tảng của nhiều mẫu thiết kế với các chỉ số rất tốt
Tuyệt vời
Xem thêm README về benchmark: