Spice: Zig में sub-nanosecond overhead के साथ सूक्ष्म parallel processing तकनीक

Spice: Sub-nanosecond Overhead वाली parallel processing

Spice Zig में heartbeat scheduling का उपयोग करके बेहद कुशल parallel processing हासिल करता है

• sub-nanosecond overhead: किसी फ़ंक्शन में parallel processing जोड़ने पर भी केवल एक nanosecond से कम overhead आता है
• कोई contention नहीं: threads एक ही काम के लिए प्रतिस्पर्धा नहीं करते। सिस्टम में threads जोड़ने पर भी प्रोग्राम धीमा नहीं होता

प्रदर्शन तुलना

• Rayon (Rust): 4 threads पर लगभग 15ns का overhead। 16 threads पर लगभग 14 गुना speedup
• Spice (Zig): 16 threads पर लगभग 11 गुना speedup। overhead इतना कम कि base performance के लगभग समान

छोटे tree में प्रदर्शन

• छोटा tree: प्रोग्राम का कुल execution time 1.56 microsecond। threads बढ़ने पर प्रदर्शन घटता है
• parallel processing की सामान्य समझ: पर्याप्त काम न हो तो parallel processing का फ़ायदा नहीं होता

Spice का लक्ष्य

• लक्ष्य: parallel processing जोड़ने पर भी प्रोग्राम धीमा न हो
• कम execution time: execution time छोटा हो तो multithreading काम नहीं करती। जोड़े गए अतिरिक्त threads wait state में चले जाते हैं

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. हर parallel फ़ंक्शन को पैरामीटर के रूप में task लेना चाहिए
2. फ़ंक्शन को सीधे call न करें, t.call का उपयोग करें
3. fork को call करके दूसरे thread पर काम सेट करें
4. फ़ंक्शन को अपने स्तर पर अर्थपूर्ण काम करना चाहिए
5. join को call करके दूसरे thread के काम पूरा होने का इंतज़ार करें
6. अगर join null लौटाए, तो काम खुद करना चाहिए

Work-stealing और अक्षमियाँ

• Work-stealing: हर thread की अपनी local work queue होती है। queue खाली होने पर वह दूसरे thread का काम चुरा लेता है
• अक्षमियाँ: dynamic dispatch, non-local work queue, spin lock

implementation details

static dispatch optimization

• code block का parallel execution: fork और join का उपयोग करके code blocks को parallel में चलाया जाता है
• duplication elimination: अगर code block दूसरे thread पर execute नहीं होता, तो उसे sequentially चलाया जाता है

कम-overhead heartbeat signal

• heartbeat scheduling: हर 100 microsecond में local work queue की जाँच करके काम दूसरे threads को भेजा जाता है
• efficiency: heartbeat न होने पर भी फ़ंक्शन को कुशलता से काम करना चाहिए

global mutex

• global mutex का उपयोग: contention न होने पर global mutex कोई समस्या नहीं है

branchless doubly linked list

• doubly linked list: work queue को manage करने के लिए इस्तेमाल होती है। यह बिना branching के काम करती है

stack usage को न्यूनतम करना

• stack usage optimization: Future की state को न्यूनतम रखकर stack usage कम किया जाता है

register के ज़रिए value passing

• register का उपयोग: performance optimization के लिए Task struct के fields को registers के ज़रिए pass किया जाता है

benchmark

• benchmark: शुरुआती development एक ही benchmark के इर्द-गिर्द हुआ

आभार

• heartbeat scheduling research: इसका development कई research papers के आधार पर हुआ

सीमाएँ

• constraints: गलत तरीके से उपयोग करने पर अजीब behavior हो सकता है
• testing की कमी: test coverage पर्याप्त नहीं है
• array/slice support की कमी: arrays/slices के लिए parallel processing support कम है
• documentation की कमी: उपयोग के बारे में documentation कम है
• अतिरिक्त benchmarks की कमी: और benchmarks की ज़रूरत है
• error handling: error handling पर पर्याप्त विचार नहीं किया गया है
• ReleaseSafe testing की कमी: ReleaseSafe mode में testing की ज़रूरत है

FAQ

• नाम की उत्पत्ति: इसका मतलब बहुत सूक्ष्म parallel processing है
• Zig में implement करने की वजह: इसे कई भाषाओं में implement किया जा सकता है
• Rust में safe parallel processing: Rust की सख्त semantics के कारण शुरुआती ideas को explore करना कठिन है

GN⁺ का सार

• Spice Zig में बेहद कुशल parallel processing देने वाला एक research project है
• sub-nanosecond overhead और contention-free parallel processing के साथ performance को अधिकतम करता है
• heartbeat scheduling के ज़रिए काम को कुशलता से वितरित करता है
• constraints और testing की कमी जैसी सीमाएँ मौजूद हैं
• Rust जैसी दूसरी भाषाओं में भी इसी तरह के approach को explore करना उपयोगी हो सकता है

[GN⁺]

Hacker News राय

• यह implementation हालिया research "heartbeat scheduling" पर आधारित है, और parallelism बनाने के overhead को वितरित करके dynamic automatic granularity control हासिल करता है

  • संबंधित पेपर:
    • (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

• मैंने code की details नहीं पढ़ीं, लेकिन "sub-nanosecond overhead" भ्रामक लगता है और marketing term जैसा है

  • पहली बात, measurement "per thing time" जैसी जटिल विधि से दिखता है, और threads की संख्या "thing" की संख्या से काफी कम है

• मैं इस क्षेत्र से परिचित नहीं हूँ, लेकिन प्रस्तुत concurrency model पसंद आया

  • README अच्छी तरह लिखा गया है, इसलिए सामग्री समझना आसान था, लेकिन कुछ हिस्से समझना कठिन थे
  • अच्छी बात यह है कि code पढ़ने में आसान है

• यह दिलचस्प research work है, और code के अलावा इसमें अच्छा तर्क और अच्छी तरह लिखा गया documentation भी है

  • 2018 का heartbeat scheduling paper भी दिलचस्प है

• project की limitations की सूची:

  • limitations सूची लिंक

• विवरण के अनुसार, यह implementation nanosecond-स्तर की latency पाने के लिए workers द्वारा busy-waiting का उपयोग करता है

  • मैं सोचता हूँ कि दसियों हज़ार tasks वाले बड़े application में busy-waiting कितनी व्यावहारिक होगी
  • अगर tasks asynchronous हों (यानी thread-based न हों), तो executor के thread pool size जितने waiters हो सकते हैं
  • ऐसी architecture की energy consumption अधिक होगी

• मैं सोचता हूँ कि क्या task producer, consumer को busy-waiting के बिना जगाने का कोई तेज़ तरीका है

  • क्या producer time slice में consumer को चलाकर यह संभव हो सकता है
  • क्या user-space FUTEX_WAKE operation के ज़रिए consumer को जगाने पर होने वाली सामान्य penalty को आधा किया जा सकता है

• यह दिलचस्प और बेहतरीन papers से जुड़ा हुआ है

  • काश OpenMP tasks के साथ तुलना भी होती
  • Rayon के बारे में थोड़ा धीमा होने की reputation है

• cooperative scheduling कई patterns की बुनियाद है जिनके metrics शानदार होते हैं

• शानदार

• benchmark से संबंधित README भी देखें:

  • benchmark README लिंक