Bend - ภาษาไฮเลเวลที่รันบน GPU (ใช้ HVM2)

 (github.com/HigherOrderCO)
1 คะแนน โดย GN⁺ 2024-05-18 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • Bend เป็นภาษาโปรแกรมมิงแบบขนานระดับสูงที่มุ่งรวมความสามารถในการแสดงออกแบบ Python·Haskell เข้ากับการรันแบบขนานขนาดใหญ่สไตล์ CUDA และทำงานบนรันไทม์ HVM2
  • รองรับฟังก์ชันลำดับสูงที่มี closure, การจัดสรรอ็อบเจ็กต์ที่รวดเร็ว, recursion แบบไม่จำกัด และ continuation ขณะเดียวกันก็รันบนฮาร์ดแวร์แบบขนานอย่าง GPU ได้โดยไม่ต้องมี สัญกรณ์การทำ parallelization แบบชัดเจน เช่น การสร้าง thread, lock, mutex หรือ atomic
  • เป้าหมายการออกแบบปัจจุบันคือประสิทธิภาพที่ขยายตามจำนวนคอร์ โดยรองรับ thread พร้อมกันมากกว่า 10,000 ตัว แต่เวอร์ชันปัจจุบันอาจมีประสิทธิภาพแบบ single-core ต่ำ และกำลังปรับปรุงการสร้างโค้ดกับการทำ optimization อยู่
  • วิธีรันแบ่งเป็น bend run-rs, bend run-c, bend run-cu และโค้ดที่ parallelize ได้สามารถรันแบบขนานบน C interpreter หรือ CUDA interpreter ได้เพียงเปลี่ยนคำสั่งรัน
  • การรองรับ Windows ยังอยู่ระหว่างดำเนินการ จึงมี WSL2 เป็นทางเลือก และการรันบน GPU ปัจจุบัน รองรับเฉพาะ NVIDIA GPU

โมเดลการเขียนโปรแกรมที่ Bend มุ่งหวัง

  • Bend เป็นภาษาโปรแกรมมิงที่รันบนฮาร์ดแวร์แบบขนานขนาดใหญ่ ขณะยังคงประสบการณ์ใช้งานของภาษาไฮเลเวลไว้
  • ให้ฟีเจอร์ของภาษาที่มีพลังในการแสดงออกอย่าง Python และ Haskell
    • การจัดสรรอ็อบเจ็กต์ที่รวดเร็ว
    • ฟังก์ชันลำดับสูงที่มี closure
    • recursion แบบไม่จำกัด
    • continuation
  • รันบน ฮาร์ดแวร์แบบขนานขนาดใหญ่ อย่าง GPU คล้าย CUDA และมุ่งให้ได้การเร่งความเร็วเกือบเชิงเส้นตามจำนวนคอร์
  • ไม่จำเป็นต้องเขียนสิ่งต่อไปนี้เองเพื่อให้รันแบบขนาน
    • การสร้าง thread
    • lock
    • mutex
    • atomic
  • รันไทม์ใช้ HVM2

ข้อจำกัดและข้อควรระวังในปัจจุบัน

  • Bend โฟกัสที่การขยายประสิทธิภาพตามจำนวนคอร์ และถูกออกแบบให้รองรับ thread พร้อมกันมากกว่า 10,000 ตัว
  • เวอร์ชันปัจจุบันอาจมี ประสิทธิภาพแบบ single-core ต่ำ
  • คาดว่าประสิทธิภาพจะดีขึ้นเมื่อเทคนิคการสร้างโค้ดและการทำ optimization พัฒนาไป
  • การรองรับ Windows ยังอยู่ระหว่างดำเนินการ และสามารถใช้ WSL2 เป็นทางเลือกได้
  • การรองรับ GPU ปัจจุบัน รองรับเฉพาะ NVIDIA GPU

การติดตั้งและวิธีรัน

  • ทั้ง Linux และ Mac ต้องติดตั้ง Rust
  • Bend เวอร์ชัน C ใช้ GCC และ README แนะนำ GCC 12.x หรือต่ำกว่า
  • หากต้องการใช้ CUDA runtime ต้องติดตั้ง CUDA Toolkit 12.x สำหรับ Linux
  • ติดตั้ง HVM2 ด้วย cargo install hvm และติดตั้ง Bend ด้วย cargo install bend-lang
  • คำสั่งรันโปรแกรม Bend แบ่งตามตัวรัน
    • bend run <file.bend>: ใช้ C interpreter เป็นค่าเริ่มต้น, รันแบบขนาน
    • bend run-rs <file.bend>: ใช้ Rust interpreter, รันแบบลำดับ
    • bend run-c <file.bend>: ใช้ C interpreter, รันแบบขนาน
    • bend run-cu <file.bend>: ใช้ CUDA interpreter, รันแบบขนานขนาดใหญ่
  • สามารถใช้ gen-c และ gen-cu เพื่อคอมไพล์เป็นไฟล์ C/CUDA แบบ standalone ได้
  • ตัวสร้างโค้ดยังอยู่ในระยะเริ่มต้น และยังไม่ mature เท่าคอมไพเลอร์อย่าง GCC หรือ GHC
  • ใช้แฟล็ก -s เพื่อตรวจสอบจำนวน reduction, เวลาในการรัน และจำนวน interaction ต่อวินาทีได้

ตัวอย่างการหาผลรวมแบบลำดับและแบบขนาน

  • ตัวอย่างการหาผลรวมใน README เปรียบเทียบโค้ดสองวิธีที่บวกตัวเลขตั้งแต่ start ถึง target
  • เวอร์ชันแบบลำดับ มีโครงสร้างที่บวกค่า start ปัจจุบันเข้ากับผลลัพธ์ของ Sum(start + 1, target)
    • การคำนวณถัดไปพึ่งพาผลรวมก่อนหน้า
    • ไม่สามารถไปขั้นถัดไปได้ก่อนที่การคำนวณปัจจุบันจะจบ จึงทำ parallelization ไม่ได้
    • ตัวอย่างเรียก Sum(1, 1_000_000) และมีคอมเมนต์ว่าอาจล้นค่าสูงสุดของตัวเลขใน Bend
  • เวอร์ชันที่ parallelize ได้ จะแบ่งช่วงออกเป็นครึ่งหนึ่ง แล้วคำนวณผลรวมด้านซ้ายและด้านขวาแบบ recursive
    • การคำนวณ (3 + 4) ไม่พึ่งพาการคำนวณ (1 + 2)
    • การคำนวณทั้งสองสามารถเกิดขึ้นพร้อมกันได้ จึงรันแบบขนานได้
  • ใน Bend หากโค้ดสามารถรันแบบขนานได้ ก็จะรันแบบขนานเพียงเปลี่ยนคำสั่งรัน

ตัวอย่างประสิทธิภาพของ Bitonic Sorter

  • README ยก bitonic sorter ที่ทำด้วย การหมุนต้นไม้แบบ immutable เป็นตัวอย่างความเร็ว
  • อัลกอริทึมนี้เป็นประเภทที่คาดหวังได้ยากว่าจะเร็วบน GPU แต่ Bend ใช้วิธี divide-and-conquer เพื่อรันบนหลาย thread
  • ไม่จำเป็นต้องสร้าง thread หรือจัดการ lock อย่างชัดเจน
  • ผล benchmark มีดังนี้
    • bend run-rs: CPU, Apple M3 Max, 12.15 วินาที
    • bend run-c: CPU, Apple M3 Max, 0.96 วินาที
    • bend run-cu: GPU, NVIDIA RTX 4090, 0.21 วินาที
  • สามารถดูอัลกอริทึมอื่นได้ใน examples folder

เอกสารอ้างอิง

  • เทคโนโลยีพื้นฐานของ Bend ดูได้ใน HVM2 paper
  • เอกสารทางการยังอยู่ระหว่างจัดทำ และคำอธิบายที่ลึกขึ้นอยู่ใน GUIDE.md
  • ดูรายการฟีเจอร์ได้ใน FEATURES.md
  • Bend พัฒนาโดย HigherOrderCO

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

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

 
GN⁺ 2024-05-18
ความคิดเห็นบน Hacker News

  • ลองย้ายตัวอย่าง sum ไปเป็น Python ล้วน แล้วพบว่าใช้เวลา 4.478 วินาทีบน pypy3 แบบเธรดเดียว และ 1 นาที 42.148 วินาทีบน Python 3.12
    ในทางกลับกัน เวอร์ชัน Bend แบบเธรดเดียวบนโน้ตบุ๊กของฉันรันมา 42 นาทีแล้ว ใช้หน่วยความจำ 6GB และยังไม่จบ สภาพแวดล้อมคือ 12th Gen Intel(R) Core(TM) i7-1270P, Ubuntu 24.04
    ถ้าตัวอย่างที่ง่ายมากยังช้าขนาดนี้ ก็ยากจะคาดหวังกับงานที่ซับซ้อนกว่า และก็สงสัยว่าได้มีการทดสอบหรือพัฒนาบนสภาพแวดล้อมอื่นนอกเหนือจาก Mac/aarch64 หรือไม่ ไว้จะลองรันใหม่ด้วยอาร์กิวเมนต์ -s ทีหลัง

    • การที่รันนาน 42 นาทีมีโอกาสสูงว่าเป็น บั๊ก ตอนนี้ยังไม่ได้ทดสอบมากนักบนสภาพแวดล้อมอื่นนอกจาก M3 Max และเราก็ทราบอยู่แล้วว่าบน CPU ที่ไม่ใช่ของ Apple จะช้ากว่า 2 เท่า จึงมีแผนจะปรับปรุง
      ในตัวอย่าง sum นั้น Bend เสียเปรียบมากเพราะต้องจัดสรร IC node 2 ตัวทุกครั้งที่มีการคำนวณตัวเลข แต่ Python ไม่เป็นแบบนั้น เราวางแผนจะหลีกเลี่ยงจุดนี้ได้เหมือน HVM1 ในเร็ว ๆ นี้ แต่ใน HVM2 ยังไม่ได้ทำ
      งานส่วนใหญ่ของ Bend ถูกใช้ไปกับการทำให้ ตัวประเมินผลแบบขนาน ทำงานได้อย่างถูกต้อง และการรัน closure กับ recursion แบบไม่จำกัดบน GPU เป็นเรื่องยากมาก เราเพิ่งจัดการส่วนนั้นเสร็จ จึงแทบยังไม่ได้ลงแรงกับการปรับแต่งระดับจุลภาค และการสร้างโค้ดของ HVM2 ก็ยังแย่มาก
      ถ้าเทียบกับกรณีอย่างตัวอย่าง Bitonic Sort ที่ทั้งสองฝั่งมีปริมาณการจัดสรรเท่ากัน ก็น่าจะเห็นประสิทธิภาพจริงได้ยุติธรรมกว่า HVM1 บนคอร์เดียวช้ากว่า GHC ราว 3 เท่า และคิดว่า HVM2 ก็น่าจะไปถึงระดับนั้นได้ในไม่ช้า
      เข้าใจได้ว่าคำพูดแบบ “ตอนนี้ยังแย่แต่จะดีขึ้น” อาจทำให้คนหมดอารมณ์ร่วม แต่ตอนนี้ฐานหลักพร้อมแล้ว การปรับแต่งระดับจุลภาคเป็นส่วนที่ง่ายที่สุด และเราเชื่อว่าประสิทธิภาพจะดีขึ้นมากจากตรงนี้
    • ฉันไม่ได้มีส่วนได้ส่วนเสียอะไรกับข้อถกเถียงนี้ แต่ recursion เป็นการทดสอบประสิทธิภาพของคอมไพเลอร์/อินเทอร์พรีเตอร์ในการสร้างและทำลาย call stack มากกว่าจะเป็นการทดสอบประสิทธิภาพการคำนวณ
      ภาษานี้มุ่งเป้าไปที่แอปพลิเคชัน GPU ที่มีงานคำนวณหนัก และยังอยู่ในระยะเริ่มต้น recursion ไม่ใช่แอปพลิเคชันเป้าหมาย จึงมองว่าไม่ใช่เบนช์มาร์กที่เหมาะนัก
    • คำว่า เธรด บน GPU กับ CPU หมายถึงคนละอย่างกัน และบน GPU มันใกล้เคียงกับ SIMD lane มากกว่า
      คล้ายกับที่ ISPC สามารถคอมไพล์ให้แต่ละเธรดของ CPU เรียกฟังก์ชัน 32 ครั้งพร้อมกันได้ ตัวอย่างเช่น บน AVX512 ถ้าใช้ข้อมูล 16 บิต ก็อาจเกิดการทำงานพร้อมกัน 2048 ชุดจาก 32 คอร์ × 2 SMT threads ต่อคอร์ × 32 ชุดการทำงานจากคอมไพเลอร์
    • Python นั้นอ่อนมากในเรื่อง recursion ซึ่งเป็นหนึ่งในเหตุผลที่มันไม่เหมาะกับการเขียนโปรแกรมเชิงฟังก์ชัน ดังนั้นนี่อาจไม่ใช่เบนช์มาร์กที่ยุติธรรม
      ถ้าเขียนแบบเป็นสไตล์ Python จริง ๆ ก็คงใช้ลูปและสถานะที่แก้ไขได้
    • ไม่เข้าใจว่าทำไมต้องมี +0 มันไม่ใช่แค่การคำนวณที่ไม่ทำอะไรเลยหรือ?

  • มีปฏิกิริยาเชิงลบในเธรดนี้เยอะ แต่แค่ทำมาได้ถึงขั้นนี้ก็อยากส่ง kudos ให้ผู้เขียนแล้ว
    โปรเจกต์คล้าย ๆ กันที่ฉันรู้จักมีแค่ Futhark แต่ไวยากรณ์แบบ Haskell อาจค่อนข้างเข้าใจยากสำหรับนักพัฒนาทั่วไปที่คุ้นกับ C/C++/Python/JS/Java ฯลฯ
    สิ่งที่น่าเสียดายที่สุดคือ ไม่เหมือน Futhark ที่รองรับเป้าหมายได้ทั้ง OpenCL, CUDA, ISPC, HIP, CPU คอร์เดียว และ CPU หลายคอร์ อันนี้ดูเหมือนจะมุ่งแค่ CUDA หรือมัลติคอร์เท่านั้น ส่วนปัญหาเรื่องประสิทธิภาพที่คนอื่นพูดถึง ฉันคิดว่าแก้ได้แน่นอน

    • ILGPU ก็น่าลองดูเหมือนกัน มีมานานแล้วและค่อนข้างดี แต่น่าเสียดายที่ไม่ค่อยเป็นที่รู้จัก
      ตัวอย่างสั้น ๆ: https://github.com/m4rs-mt/ILGPU/blob/master/Samples/SimpleM...
      และยังรองรับฟีเจอร์ขั้นสูงอย่าง inline PTX assembly: https://github.com/m4rs-mt/ILGPU/blob/master/Samples/InlineP...
    • Chapel ก็ถูกใช้อยู่พอสมควรในงานคอมพิวเตอร์สมรรถนะสูง
      NVIDIA เองก็สนับสนุนภาษาแปลงสาย Haskell, .NET, Java, Julia บน CUDA และยังมี Python JIT รวมถึงกำลังร่วมมือกับฝั่ง Mojo ด้วย
    • ParaSail ก็เป็นภาษาอีกตัวที่เดินไปในทิศทางคล้ายกัน: https://github.com/parasail-lang/parasail
      มันถูกสร้างโดย Tucker Taft ซึ่งทำงานเป็นผู้ออกแบบ Ada มาตั้งแต่ปี 1995 และฟีเจอร์ด้านขนานบางส่วนของ ParaSail ก็ถูกนำเข้าไปใน Ada 2022 แล้ว

  • OP มักเอาของที่เจ๋งที่สุดใน HN ช่วงหลัง ๆ มาลง แต่ก็น่าเสียดายที่อันนี้ดูชัดว่าเป็น เวอร์ชันเริ่มต้น และกลับได้รับแต่คำวิจารณ์ยาว ๆ

    • HN ค่อนข้างเป็นชุมชนของคนที่อยากโพสต์สิ่งใหม่หรือสิ่งที่มีความคิดสร้างสรรค์ ถ้าใครอยากชื่นชม ก็มักจะกดโหวตให้คอมเมนต์ที่มีอยู่แล้ว มากกว่าจะเขียนคอมเมนต์ใหม่ว่า “เจ๋งดี” อีกอัน
      ในทางกลับกัน คำวิจารณ์มีวิธีพูดให้ถูกได้จำกัด แต่มีวิธีพูดให้ผิดได้มากมาย จึงแตกแขนงได้ไม่รู้จบ ผลคือคอมเมนต์เชิงบวกมีแค่ไม่กี่อัน ส่วนใหญ่จึงดูเหมือนเป็นคำวิจารณ์หรือ “น่าจะทำสิ่งนี้ด้วย” มากกว่า นี่ไม่ใช่ความผิดของใครคนใดคนหนึ่ง แต่เป็นเพราะวัฒนธรรมของคนสายเทคทุกวันนี้โน้มเอียงไปทางนั้น
    • ถ้าเป็นโปรเจกต์ของฉันเอง ฉันคงรู้สึกขอบคุณมากที่มีคนวิจารณ์ เพราะแบบนั้นถึงจะเติบโตได้
      ถ้าผู้คนเอาแต่ซ่อนความจริงอันโหดร้ายไว้หลังเสียงปรบมือ โลกก็คงพังทลาย
    • มันได้ 905 โหวต แล้ว ดังนั้นก็นับว่าได้รับการตอบรับเชิงบวกมากพอสมควรแล้ว
      คำวิจารณ์เองก็หมายถึงผู้คนสนใจไอเดียและแนวทางนี้มากพอจะเข้ามามีส่วนร่วม ซึ่งบ่อยครั้งก็เป็นสัญญาณเชิงบวก
    • การไม่วิจารณ์โปรเจกต์ใหม่ ๆ ที่ทะเยอทะยานก็เป็นบรรทัดฐานทางสังคมที่ดี เพราะความพยายามแบบนั้นควรได้รับการสนับสนุนและไม่ควรถูกบั่นทอน
      แต่การวิจารณ์โปรเจกต์ที่ทำให้เข้าใจผิด หรือมีข้ออ้างที่หลักฐานไม่พอ หรือเป็นเท็จ ก็เป็นบรรทัดฐานทางสังคมที่ดีเช่นกัน เพราะมันช่วยลดคำกล่าวอ้างแบบนั้นลง
    • สิ่งที่เจ๋งที่สุดมักเป็นสิ่งที่เข้าใจยากที่สุด
      และสิ่งที่เข้าใจยากก็มักถูกมองว่าเป็นภัยคุกคาม คำวิจารณ์จึงเป็นปฏิกิริยาต่อภัยคุกคามที่พบได้บ่อย และยังเป็นรูปแบบการตอบสนองที่ใช้ความเข้าใจน้อยที่สุดด้วย

  • หน้าเว็บไซต์ทำออกมาได้ดีมาก เห็นชัดเจนทันทีว่ากำลังทำอะไร
    คนที่ทำงานกับ “combinator” มักอยากใช้ศัพท์เฉพาะชวนหวาดกลัวเต็มไปหมด แต่ OP แสดงให้เห็น ไอเดียที่เรียบง่าย เบื้องหลังเครื่องมือนี้จริง ๆ ชอบตรงที่มันตรงข้ามกับแนวทางแบบวิชาการที่โชว์รายละเอียดจนสุดแต่กลับไม่บอกว่าจริง ๆ แล้วเกิดอะไรขึ้น อยากเห็นวิธีแบบนี้มากขึ้น

  • ในทางทฤษฎีมันเจ๋งและก็เข้าใจคุณค่าที่เสนอมา แต่พูดตามตรงยังไม่คิดว่านี่จะกลายเป็น เครื่องมือที่มีความเกี่ยวข้องในทางปฏิบัติ ได้
    นี่คือโน้ตหลังจากความประทับใจแรกและการไล่อ่าน paper แบบคร่าว ๆ รู้ว่าเป็นซอฟต์แวร์ระยะเริ่มต้นมาก
    Bend ดูเหมือน DSL ที่มีข้อจำกัดสูงมาก ไม่มี FFI ไม่มีทางโต้ตอบกับ primitive buffer และฟอร์แมตเลขทศนิยม 24 บิตก็ดูแปลก
    มีเหตุผลที่ IC ไม่ได้เป็นกระแสหลัก ประสิทธิภาพมีแนวโน้มสูงว่าจะยังแย่มากต่อไป และการเดินกราฟก็ไม่ค่อยเข้ากับฮาร์ดแวร์
    สมมติฐานเรื่อง optimal reduction ใช้ได้ แต่สุดท้ายก็ยังต้องเขียน kernel ในรูปแบบที่ขนานได้ นั่นคือไม่มี data dependency และต้องคิดเรื่องการใช้ recursion ด้วย
    ไม่มีตัวอย่างจริงจังที่เปรียบเทียบโปรแกรม OMP/CUDA กับโค้ด Bend/HVM ที่เทียบเท่ากันโดยตรง จึงประเมินได้ยากว่าความซับซ้อนของการ implement ลดลงแค่ไหน และประสิทธิภาพได้ประมาณไหน
    ในโลกของ high-performance parallel computing จริง ๆ โครงสร้างแบบต้นไม้แทบไม่มี และ array คือราชา ทั้งหมดนี้มาจากธรรมชาติทางกายภาพของการทำงานของหน่วยความจำในระดับฮาร์ดแวร์ สิ่งที่เวิร์กที่สุดกับบัฟเฟอร์หน่วยความจำต่อเนื่องแบบเปลี่ยนค่าได้ก็คือ loop ถ้า HVM ทำสิ่งนี้ได้ค่อยน่าติดตาม
    ตอนนี้มันดูเหมือนภาษาที่ยังไม่สุกดี วาง abstraction ขนาดมหึมาทับบนฮาร์ดแวร์ เกือบจะแยกขาดจากข้อมูลภายนอกโดยสมบูรณ์ และช้ามาก อีกทั้งยังใช้ความสามารถอย่าง multi-level cache, tensor core, SIMD, atomic operation ไม่ได้ด้วย
    ถ้าฟังดูแรงไปก็ขอโทษ แต่ยังมองว่าการ implement ทางเทคนิคและพื้นฐานทางทฤษฎีน่าสนใจมาก ๆ แค่ยังไม่เชื่อเรื่องประโยชน์ใช้สอยในโลกจริง ณ ตอนนี้

    • ขอบคุณสำหรับฟีดแบ็ก ขอแก้บางจุดนะ เราใช้ multi-level cache อยู่แล้ว และถ้าใช้อย่างถูกต้องก็ทำประสิทธิภาพได้สูงขึ้น 5 เท่า
      FFI ทำเสร็จแล้วแต่ยังไม่เปิดเผย เพราะอยากปล่อยพร้อมกับการเรนเดอร์กราฟิก ซึ่งคิดว่าน่าจะเจ๋งมาก
      Haskell/GHC ก็ใช้กราฟกับต้นไม้เหมือนกัน แต่คงไม่มีใครบอกว่าไม่ใช้งานจริง แม้จะจริงที่ array คือราชา แต่อัลกอริทึมสมัยใหม่จำนวนมากที่ไม่ค่อยเข้ากับ array เช่น compiler, type checker, solver ก็ถูก implement ด้วย Haskell
      เหตุผลหลักที่ IC ไม่เร็วก็เพราะยังไม่มีใครทำงาน optimize ระดับล่างบนมันอย่างจริงจัง implementation เดิม ๆ ล้วนไม่มีประสิทธิภาพอย่างมาก และงานของผมเองก็ใช้เวลาไปกับการทำให้มัน รันได้ถูกต้อง บน GPU เป็นหลักจนถึงตอนนี้
      เช่นเดียวกับที่ตอนนี้ยังไม่มี loop วิธีแก้ก็คือแค่เพิ่ม loop เข้าไป ถ้าคิดว่ามีนี่เป็นข้อจำกัดโดยเนื้อแท้ คุณอาจต้องแปลกใจ
      ในที่สุด HVM2 ก็กลายเป็นอัลกอริทึมที่ถูกต้องและขยายขนาดได้แล้ว และตอนนี้ก็ถึงเวลาจะ optimize ประสิทธิภาพระดับล่างจริง ๆ
    • เรื่องข้อ 5 นั้น ต้นไม้แม้จะต่างจาก implementation แบบวิทยาการคอมพิวเตอร์ทั่วไป แต่ก็ถูกใช้ค่อนข้างแพร่หลาย
      ในอัลกอริทึม Fast Multipole หรือ Barnes-Hut มีการใช้ลำดับ Morton หรือ H-index เพื่อลดการคำนวณเป็นคู่ ๆ แบบ O(n²) ลงเป็น O(n) และ O(n log n) ตามลำดับ Barnes-Hut พบได้บ่อยกว่าในฟิสิกส์ดาราศาสตร์ ส่วน Fast Multipole มักเห็นบ่อยกว่าใน molecular dynamics ทางเคมี

  • เมื่อ 10 ปีก่อนผมเคยเรียนวิชาว่าด้วยอัลกอริทึมขนานของ CMU คือ 15-210 เขาอธิบายว่าเมื่อกฎของมัวร์ชนข้อจำกัด ความขนานจะกลายเป็นอนาคตของการคำนวณ และผมก็ถูกโน้มน้าวจนอยากลองเล่นดู
    แต่ตัวเลือกสำหรับการเขียนโปรแกรมขนานแบบทั่วไปมีไม่มาก แม้แต่ SML ที่ใช้ในคลาสก็ยังไม่ขนาน และช่วงท้ายมีส่วนที่ใช้ extension กับ CUDA อยู่ แต่เท่าที่จำได้มันมีข้อจำกัดมาก
    หลังจากนั้นก็ได้ลอง multithreading บ้างเพราะ Rust และได้ทำงานสร้างสรรค์กับ shader บ้างเพราะ Shadertoy แต่ภาษา parallel แบบ general-purpose บน GPU นี่ทำให้อยากลองเองมากจริง ๆ

    • เดี๋ยวนี้ 210 เป็น แบบขนาน จริง ๆ แล้ว ถ้าใช้ MaPLe(https://github.com/MPLLang/mpl) ก็สามารถรันโค้ดสไตล์ 210 ได้ และยังได้ประสิทธิภาพที่แข่งขันกับ C/C++ ได้ด้วย
      ถ้าคุณชอบ 210 คุณอาจชอบ https://futhark-lang.org/ ด้วย เป็นภาษาในตระกูล ML คอมไพล์ลง GPU ได้และประสิทธิภาพก็ดี
    • กระแสที่เครื่องกำลังไปทาง มัลติคอร์ ก็เป็นหนึ่งในเหตุผลที่ผมตัดสินใจเรียน Elixir

  • ไอเดียเจ๋งมาก แต่ถ้าผมไม่ได้พลาดอะไรไป มันดูเหมือนจะ ช้ามาก
    ผมเขียน loop ง่าย ๆ ใน C++ ที่บวกเลขตั้งแต่ 0 ถึง 2³⁰ แล้วพบว่าแบบ single-thread ไม่ optimize ใช้เวลา 1.7 วินาทีบนโน้ตบุ๊กของผม ซึ่งใกล้เคียงกับประสิทธิภาพของ Bend บน RTX 4090 ถ้าใส่ -O3 loop จะถูกเวกเตอร์ไรซ์และรันเสร็จในเวลาไม่ถึง 80ms

    • ตอนนี้ Bend ยังไม่มี tail-call optimization มันเลยกำลังจัดสรรสแตกความยาว 1 พันล้านอยู่ ขณะที่ C แค่วน loop เฉย ๆ
      ถ้าเทียบกับโปรแกรม C ที่มีการจัดสรรจริง ๆ เป็นไปได้ว่า Bend จะเร็วกว่าแม้ใช้เพียงไม่กี่เธรด
      การสร้างโค้ดของ Bend ยังแย่มากในตอนนี้ แต่ก็เป็นของที่เก็บได้ไม่ยาก งานส่วนใหญ่ถูกใช้ไปกับการทำ evaluator แบบขนานที่ยากมากให้ ทำงานได้ถูกต้อง
      ฟังดูเหมือน “เชื่อผมก่อน” ก็จริง แต่เมื่อเริ่มทำ procedure compilation, การสร้าง loop ฯลฯ แล้ว ประสิทธิภาพแบบ single-thread จะดีขึ้นมาก แค่ยังไม่ได้ทำเท่านั้น
      บางทีก็คิดว่าอาจควรรออีกหน่อยก่อนเอาขึ้นจริง
    • ควรเช็กด้วย objdump ว่า loop ถูกเวกเตอร์ไรซ์จริงหรือว่า compiler optimize ทิ้งไปทั้งดุ้น
      loop นั้นทำให้เกิด signed integer overflow ซึ่งใน C++ ถือเป็น undefined behavior compiler จึงสามารถให้ผลลัพธ์อะไรก็ได้อย่างถูกกฎหมาย
      ถ้าอยากเลี่ยงก็ควรประกาศ sum เป็น unsigned การล้นของจำนวนเต็มแบบ unsigned ถูกนิยามไว้อย่างชัดเจน และการ optimize ก็ยังเกิดขึ้นได้ แต่至少ก็รับประกันความถูกต้อง
    • ถ้าคอมไพล์ด้วย clang ที่ -O3 loop จะถูกลบออกไปทั้งหมด: https://godbolt.org/z/M1rMY6qM9
      แบบนี้คงไม่ใช่การเปรียบเทียบที่ยุติธรรมนัก
    • ประเด็นสำคัญน่าจะอยู่ที่ Bend เป็นสิ่งที่ ระดับสูงกว่า C++ มาก
      แน่นอนว่าผมเองก็อาจพลาดประเด็นสำคัญไปเหมือนกัน

  • อยากแสดงความยินดีกับผู้เขียน เป็นงานที่ยอดเยี่ยมจริง ๆ
    การสร้าง automatic parallelization ที่ถูกต้องไม่ใช่เรื่องง่ายเลย และคุณมีสิทธิ์ภูมิใจกับมันมาก ๆ รอดูว่าต่อไปโปรเจกต์นี้จะพัฒนาไปอย่างไร

  • ไม่เข้าใจว่าทำไมถึงมีปฏิกิริยาเชิงลบเยอะขนาดนี้ ดูเหมือนฝูงชนที่กำลังเดือดดาลคอยขุดหาช่องโหว่ใน README และทำตัวเหมือนบอตที่พยายามบิดบริบทกับเจตนาของโพสต์
    ใช้เวลาอ่านให้เข้าใจไม่ถึง 2 นาที แต่กลับเถียงกันเป็นชั่วโมง ๆ นี่ทั้งไม่รู้จริงและโหดร้าย OP มาได้ไกลขนาดนี้ในฐานะโปรเจกต์คนเดียว ดังนั้นหวังว่าจะเดินหน้าต่อไป

  • ผมสงสัยว่า HVM2 คอมไพล์ interaction nets ไปเป็นอย่างเช่น SPIR-V หรือว่าเป็น อินเทอร์พรีเตอร์ ที่รันบน GPU แบบเดียวกับ HVM ดั้งเดิม
    ก่อนหน้านี้ผมเคยลองคอมไพล์ interaction nets ไปเป็น C โดยลดรูปโปรแกรมให้มากที่สุดเท่าที่ทำได้ แต่ไม่ลดรูปอินพุต แล้วจัดการมันเหมือนเป็นการทำ whole-program optimization การเล็งไปที่ภาษา shader ก็ดูเหมือนจะไม่ยากมากนัก
    ดูจากรีโพซิทอรีแล้ว เหมือนว่าจะมีภาษา IR ระดับล่างสำหรับระบุ HVM2 nets และมีคอมไพเลอร์ที่ไปยัง C/CUDA: https://github.com/HigherOrderCO/HVM
    แต่พอกลับไปดูอีกที HVM2 CUDA runtime ก็ดูเหมือนเป็นอินเทอร์พรีเตอร์ที่ไล่เดินกราฟในหน่วยความจำแล้วใช้การลดรูป: https://github.com/HigherOrderCO/HVM/blob/5de3e7ed8f1fcee6f2...
    สิ่งที่ผมพูดถึงคือการไล่ interaction nets เพื่อกู้คืนเทอมที่ใกล้เคียงกับ lambda calculus แล้วค่อยลดระดับเป็น C ทีละชิ้นเล็ก ๆ เพื่อลด runtime overhead ให้ต่ำที่สุด
    แรงจูงใจแบบตรงไปตรงมาคือ ด้วย Bend มันยากที่จะเอาชนะ GPU kernel ที่เขียนด้วยมือในงานอย่าง ML workload ตามทฤษฎีแล้ว HVM อาจทำหน้าที่เป็นกาวสำหรับเชื่อม computation kernels และทำให้ลำดับการทำงานขนานกันได้ แต่ถ้าจะทำแบบนั้นก็ต้องมี FFI ที่ดี
    interaction nets แปลข้ามขอบเขต FFI ได้ยาก แต่ถ้าใส่โหนด computation kernel ของ FFI ไว้ใน interaction network แล้วคอมไพล์ net ไปเป็น C ก็อาจกู้คืน FFI ที่สมเหตุสมผลได้โดยไม่มี translation overhead
    อีกทางเลือกหนึ่งคือทำ HVM เป็นฮาร์ดแวร์ ซึ่งผมก็กำลังลองเล่นกับมันอยู่บ้างบน FPGA ที่เหลือใช้อยู่

    • มันเป็นทั้งอินเทอร์พรีเตอร์ที่รันบน GPU และเป็น คอมไพเลอร์ ที่ไปยัง native C และ CUDA
      ไม่ได้เล็ง SPIR-V โดยตรง แต่ก็ตั้งใจจะรองรับ
      C compiler ให้ความเร็วเพิ่มขึ้นตามที่คาดไว้ คือ 3~4 เท่า และเดี๋ยวจะมากกว่านั้นอีก แต่ CUDA runtime ยังไม่ได้ความเร็วเพิ่มขึ้นมากเมื่อเทียบกับเวอร์ชันที่ไม่คอมไพล์
      คิดว่าสาเหตุมาจาก warp divergence ในโปรซีเยอร์ที่ยังไม่คอมไพล์ เราสามารถรวมทุก function call เข้าเป็นตัวขยายฟังก์ชันแบบอินเทอร์พรีเตอร์ “อเนกประสงค์” ตัวเดียวได้ และทำให้ warp threads ลดรูปได้โดยไม่ต้องแตกแขนง ต่อจากนี้ตั้งใจจะศึกษาเรื่องนี้ให้ลึกขึ้น