Spice: เทคนิคการประมวลผลแบบขนานที่ละเอียดมากใน Zig ด้วยโอเวอร์เฮดต่ำกว่าระดับนาโนวินาที

 (github.com/judofyr)
2 คะแนน โดย GN⁺ 2024-08-14 | 1 ความคิดเห็น | แชร์ทาง WhatsApp

Spice: การประมวลผลแบบขนานที่มีโอเวอร์เฮดต่ำกว่าระดับนาโนวินาที

Spice ใช้ heartbeat scheduling ใน Zig เพื่อให้ได้การประมวลผลแบบขนานที่มีประสิทธิภาพสูงมาก

  • โอเวอร์เฮดต่ำกว่าระดับนาโนวินาที: แม้เพิ่มความสามารถด้านการประมวลผลแบบขนานให้กับฟังก์ชัน ก็เกิดโอเวอร์เฮดเพียงต่ำกว่าหนึ่งนาโนวินาที
  • ไม่มีการแย่งงานกัน: เธรดจะไม่แย่งงานเดียวกัน แม้เพิ่มเธรดเข้าไปในระบบ โปรแกรมก็ไม่ช้าลง

การเปรียบเทียบประสิทธิภาพ

  • Rayon (Rust): มีโอเวอร์เฮดราว 15ns บน 4 เธรด และทำความเร็วได้เพิ่มขึ้นราว 14 เท่าบน 16 เธรด
  • Spice (Zig): ทำความเร็วได้เพิ่มขึ้นราว 11 เท่าบน 16 เธรด โดยมีโอเวอร์เฮดต่ำจนแทบไม่ต่างจากประสิทธิภาพพื้นฐาน

ประสิทธิภาพบนต้นไม้ขนาดเล็ก

  • ต้นไม้ขนาดเล็ก: เวลารวมของการรันโปรแกรมอยู่ที่ 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: แต่ละเธรดมีคิวงานภายในของตัวเอง และเมื่อคิวว่างก็จะไปขโมยงานจากเธรดอื่น
  • ความไม่มีประสิทธิภาพ: dynamic dispatch, คิวงานที่ไม่อยู่ใน local และ spin lock

รายละเอียดการติดตั้งใช้งาน

การปรับแต่ง static dispatch

  • รันบล็อกโค้ดแบบขนาน: ใช้ fork และ join เพื่อรันบล็อกโค้ดแบบขนาน
  • ตัดความซ้ำซ้อน: หากบล็อกโค้ดไม่ได้ถูกรันบนเธรดอื่น ก็จะรันแบบลำดับตามปกติ

สัญญาณ heartbeat ที่มีโอเวอร์เฮดต่ำ

  • heartbeat scheduling: ทุก ๆ 100 ไมโครวินาที จะตรวจสอบคิวงานภายในและส่งงานไปยังเธรดอื่น
  • ประสิทธิภาพ: ฟังก์ชันต้องทำงานได้อย่างมีประสิทธิภาพแม้ในช่วงที่ heartbeat ไม่เกิดขึ้น

global mutex

  • การใช้ global mutex: global mutex ไม่เป็นปัญหาเมื่อไม่มีการแย่งกันใช้งาน

doubly linked list แบบไร้การแตกแขนง

  • doubly linked list: ใช้สำหรับจัดการคิวงาน และทำงานโดยไม่ต้องมี branch

การใช้สแตกให้น้อยที่สุด

  • การปรับการใช้สแตก: ลดการใช้สแตกด้วยการทำให้สถานะของ Future มีขนาดน้อยที่สุด

การส่งค่าผ่านรีจิสเตอร์

  • การใช้รีจิสเตอร์: ปรับประสิทธิภาพโดยส่งฟิลด์ของโครงสร้าง Task ผ่านรีจิสเตอร์

เบนช์มาร์ก

  • เบนช์มาร์ก: การพัฒนาในช่วงแรกขับเคลื่อนโดยเบนช์มาร์กเพียงตัวเดียวเป็นหลัก

คำขอบคุณ

  • งานวิจัย heartbeat scheduling: พัฒนาขึ้นโดยอิงจากงานวิจัยหลายฉบับ

ข้อจำกัด

  • ข้อจำกัด: หากใช้งานผิดวิธีอาจเกิดพฤติกรรมแปลก ๆ ได้
  • การทดสอบยังไม่พอ: test coverage ยังไม่เพียงพอ
  • รองรับอาร์เรย์/สไลซ์ไม่เพียงพอ: การรองรับการประมวลผลแบบขนานสำหรับอาร์เรย์/สไลซ์ยังไม่มากพอ
  • เอกสารไม่เพียงพอ: ยังมีเอกสารอธิบายวิธีใช้งานไม่มากพอ
  • เบนช์มาร์กเพิ่มเติมยังไม่พอ: ยังต้องมีเบนช์มาร์กเพิ่มเติม
  • การจัดการข้อผิดพลาด: ยังพิจารณาเรื่อง error handling ไม่มากพอ
  • การทดสอบ ReleaseSafe ยังไม่พอ: ต้องมีการทดสอบในโหมด ReleaseSafe

FAQ

  • ที่มาของชื่อ: สื่อถึงการประมวลผลแบบขนานที่ละเอียดมาก
  • เหตุผลที่สร้างด้วย Zig: แนวคิดนี้สามารถนำไปสร้างได้ในหลายภาษา
  • การประมวลผลแบบขนานที่ปลอดภัยใน Rust: semantics ที่เข้มงวดของ Rust ทำให้สำรวจแนวคิดตั้งต้นได้ยาก

สรุปโดย GN⁺

  • Spice เป็นโครงการวิจัยที่มอบการประมวลผลแบบขนานที่มีประสิทธิภาพสูงมากใน Zig
  • โอเวอร์เฮดต่ำกว่าระดับนาโนวินาที และการประมวลผลแบบขนานที่ ไม่มีการแย่งงานกัน ช่วยดันประสิทธิภาพให้สูงสุด
  • ใช้ heartbeat scheduling เพื่อกระจายงานอย่างมีประสิทธิภาพ
  • ยังมีข้อจำกัด เช่น เงื่อนไขการใช้งาน และ การทดสอบที่ยังไม่เพียงพอ
  • แนวทางลักษณะเดียวกันนี้น่าลองศึกษาต่อในภาษาอื่นอย่าง Rust ด้วย

บทความที่เกี่ยวข้อง

1 ความคิดเห็น

 
GN⁺ 2024-08-14
ความคิดเห็นจาก 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" มาก

  • ไม่คุ้นกับสาขานี้มากนัก แต่ชอบโมเดล concurrency ที่นำเสนอ

    • README เขียนได้ดี ทำให้เข้าใจเนื้อหาได้ง่าย แต่บางส่วนก็ยังเข้าใจยาก
    • โชคดีที่โค้ดอ่านง่าย

  • เป็นงานวิจัยที่น่าสนใจ และนอกจากโค้ดแล้วยังมีเหตุผลประกอบที่ดีและเอกสารที่เขียนมาอย่างดี

    • งานวิจัย heartbeat scheduling ปี 2018 ก็น่าสนใจเช่นกัน

  • รายการข้อจำกัดของโปรเจกต์:

  • ตามคำอธิบาย การติดตั้งใช้งานนี้ใช้การ busy wait เพื่อให้ worker บรรลุ latency ระดับนาโนวินาที

    • สงสัยว่าการ busy wait จะใช้งานได้จริงแค่ไหนในแอปพลิเคชันขนาดใหญ่ที่มีงานหลายหมื่นชิ้น
    • ถ้างานเป็นแบบ asynchronous (กล่าวคือไม่อิงเธรด) ก็อาจมีตัวรออยู่ได้มากเท่ากับขนาด thread pool ของ executor
    • การใช้พลังงานของสถาปัตยกรรมแบบนี้น่าจะสูงกว่า

  • สงสัยว่ามีวิธีที่เร็วกว่านี้ไหมที่ผู้ผลิตงานจะปลุกผู้บริโภคโดยไม่ต้อง busy wait

    • สงสัยว่าจะทำได้ไหมด้วยการรันผู้บริโภคใน time slice ของผู้ผลิต
    • สงสัยว่าจะลดโทษโดยทั่วไปของการปลุกผู้บริโภคผ่านงานผู้ใช้พื้นที่ FUTEX_WAKE ลงครึ่งหนึ่งได้ไหม

  • น่าสนใจและเชื่อมโยงไปยังงานวิจัยชั้นเยี่ยมหลายชิ้น

    • อยากให้มีการเปรียบเทียบกับงานของ OpenMP
    • Rayon มีชื่อเสียงว่าช้ากว่าอยู่นิดหน่อย

  • cooperative scheduling เป็นรากฐานของหลายแพตเทิร์นที่มีเมตริกยอดเยี่ยม

  • ยอดเยี่ยม

  • ดู README เกี่ยวกับ benchmark เพิ่มเติมได้ที่: