Types of Parallelism

1สามประเภทของพารัลเลลิซึม

2ตัวอย่างเปรียบเทียบ: งานสวน

เอกสารต้นฉบับใช้อุปมาการดูแลสวน (ตัดหญ้า Mow, เล็มขอบ Edge, กำจัดวัชพืช Weed, รดน้ำ/เปิดสปริงเกลอร์) เพื่อแยกความต่างของ 3 ประเภทให้เห็นภาพชัดเจน

3Data Dependence Graph: เครื่องมือหาว่าอะไรขนานได้

4แนวคิดทั้งสามปรากฏในเครื่องมือปัจจุบันอย่างไร

5Data Parallelism: สูตรเดียวกัน ข้อมูลคนละส่วน

Data parallelism เหมาะเมื่อข้อมูลจำนวนมากผ่าน operation ชุดเดียวกันหรือคล้ายกัน เช่น ปรับสีทุก pixel คูณ matrix แต่ละ block หรือคำนวณ gradient จากแต่ละตัวอย่าง ข้อมูลถูกแบ่งเป็น partition แล้ว worker ทำงานชนิดเดียวกันบนส่วนของตน

รูปแบบย่อยที่พบบ่อย

• Map — แปลงแต่ละ element อย่างอิสระ
• Stencil — คำนวณ element จากเพื่อนบ้าน เช่น convolution หรือ simulation grid
• Reduction — รวมหลายค่าเป็นค่าหนึ่ง เช่น sum, max หรือ histogram
• Scan — สร้างผลสะสมทุกตำแหน่ง เช่น prefix sum
• Scatter/Gather — กระจายข้อมูลไปยังตำแหน่งหรือรวบรวมจากตำแหน่งที่ระบุ

คำว่า data-parallel ไม่ได้แปลว่าไม่มี dependency Reduction และ scan ต้องออกแบบ tree structure ส่วน stencil ต้องแลก halo หรือ boundary ระหว่าง partition สิ่งที่เหมือนกันคือเราจัดงานโดยเริ่มจากการแบ่ง data domain

6Functional หรือ Task Parallelism: งานคนละอย่างทำพร้อมกัน

Functional parallelism แยกตามกิจกรรม เช่น task หนึ่งอ่านไฟล์ task หนึ่งถอดรหัส และอีก task วิเคราะห์ข้อมูล เหมาะเมื่อระบบมีงานหลายชนิดที่เป็นอิสระหรือคาบเกี่ยวกันได้

ระบบจริงมักผสมกัน เช่น pipeline หนึ่ง stage ทำ inference บน GPU แบบ data-parallel ขณะที่อีก stage ทำ preprocessing บน CPU แบบ task-parallel การจัดประเภทมีไว้ช่วยคิด ไม่ใช่บังคับให้ระบบอยู่ได้เพียงช่องเดียว

7Pipeline Parallelism: หลายขั้นตอนทำงานคนละชิ้นพร้อมกัน

Pipeline แบ่งงานเป็น stages งานชิ้นแรกเดินจาก stage 1 ไป 2 ไป 3 ขณะ stage 2 ทำชิ้นแรก stage 1 เริ่มชิ้นที่สองได้ เมื่อ pipeline เต็ม throughput ขึ้นกับ stage ที่ช้าที่สุด

8Latency, Throughput และจำนวนงานที่ค้างอยู่ใน Pipeline

Pipeline เพิ่ม throughput โดยให้หลายชิ้นอยู่ในระบบพร้อมกัน แต่ latency ของชิ้นหนึ่งยังรวมเวลาผ่านทุก stage และอาจเพิ่มจาก queue ถ้าส่งงานเร็วกว่าคอขวดรับได้ Queue จะโตจนใช้ memory หมดหรือ deadline หลุด

Backpressure ให้ downstream แจ้ง upstream ให้ชะลอเมื่อรับไม่ทัน เปรียบเหมือนร้านอาหารหยุดรับบัตรคิวชั่วคราวเมื่อครัวเต็ม ถ้าปล่อยให้รับ order ไม่จำกัด ตัวเลขหน้าเคาน์เตอร์อาจดูว่ารับงานได้เร็ว แต่ลูกค้ารออาหารนานขึ้นเรื่อย ๆ

9Dependency มีหลายชนิด

การแยก true dependency ออกจาก name/resource dependency สำคัญ เพราะสองแบบหลังอาจหายได้เมื่อออกแบบ storage หรือ schedule ใหม่ หากเห็นการรอแล้วสรุปว่า algorithm ขนานไม่ได้ เราอาจยอมแพ้เร็วเกินไป

10Loop-Carried Dependency: อุปสรรคของ Parallel Loop

Iteration ของ loop จะขนานได้เมื่อ iteration i ไม่ต้องใช้ผลที่ iteration ก่อนหน้ากำลังสร้าง ตัวอย่าง y[i]=x[i]*2 independent แต่ a[i]=a[i-1]+x[i] มี dependency ต่อเนื่อง

อย่างไรก็ตาม prefix sum ที่ดูเป็นสายยาวสามารถเปลี่ยน algorithm เป็น tree-based scan ได้ ใช้หลายรอบแต่เปิด parallelism มากขึ้น นี่เป็นตัวอย่างว่าความขนานไม่ได้เป็นเพียงคุณสมบัติของ “ปัญหา” แต่ขึ้นกับ algorithm ที่เลือกแทนปัญหานั้นด้วย

11Data Dependence Graph จากรูปวาดสู่การวัด

ใน DAG แต่ละ node คือ task และ edge คือเงื่อนไขว่าปลายทางเริ่มได้หลังต้นทางเสร็จ จากกราฟเดียวกันเราหาได้ทั้ง work, critical path และระดับ parallelism ที่มีในแต่ละช่วง

• Work (T₁) — ผลรวมเวลาของทุก node
• Span (T∞) — ผลรวมเวลาบนเส้นทางยาวที่สุด
• Average parallelism — T₁/T∞ เป็นขอบเขตว่ามีงานพร้อมกันเฉลี่ยมากเพียงใด
• Ready set — node ที่ dependency ครบและ schedule ได้ในขณะนั้น

12Granularity: Task ใหญ่จัดกับเล็กจัดต่างก็มีปัญหา

Coarse-grained task มีงานต่อชิ้นมาก ต้นทุน schedule และ communication ต่ำเมื่อเทียบกับ computation แต่แบ่งโหลดได้หยาบ Fine-grained task เปิด concurrency และ balance ได้ดี แต่ runtime ต้องจัดการ task จำนวนมาก

ค่าที่เหมาะขึ้นกับ architecture ด้วย Task 10 microseconds อาจเหมาะกับ thread pool ในเครื่อง แต่เล็กเกินไปสำหรับการส่งผ่าน network ไป cluster worker

13Regular กับ Irregular Parallelism

งาน regular มีรูปแบบข้อมูลและเวลาต่อ task คาดเดาได้ เช่น dense matrix หรือ image convolution จัด partition แบบ static และใช้ SIMD/GPU ได้ดี งาน irregular เช่น graph traversal, sparse matrix หรือ branch-and-bound มี degree, memory access และขนาด subtree ต่างกัน ต้องใช้ dynamic scheduling มากขึ้น

Irregular ไม่ได้แปลว่าขนานไม่ได้ แต่ locality และ balance เป็นปัญหาหลัก เครื่องมืออย่าง work stealing, graph partitioning และ asynchronous traversal จึงมีบทบาทมาก

14Reduction: หลายคำตอบย่อยรวมเป็นคำตอบเดียว

การรวมผลแบบลำดับมี critical path O(n) แต่ tree reduction รวมเป็นคู่ ๆ ได้ O(log n) stages หาก operation associative เช่นผลรวมจำนวนเต็มในทางคณิตศาสตร์

เทคนิคอย่าง pairwise summation หรือ compensated summation ช่วยความแม่นยำ แต่เพิ่ม work การออกแบบต้องเลือกระหว่าง speed, accuracy และ deterministic result ตามบริบท

15Scatter, Gather และ All-to-All: รูปแบบการสื่อสารก็เป็นส่วนของ Algorithm

• Broadcast ส่งข้อมูลหนึ่งชุดไปทุก worker
• Scatter แบ่งข้อมูลจากต้นทางไปคนละส่วน
• Gather รวบรวมผลย่อยกลับจุดเดียว
• All-reduce รวมผลแล้วแจกคำตอบรวมให้ทุกคน
• All-to-all ทุก worker ส่งคนละส่วนให้ทุก worker มักแพงและสร้าง congestion

งาน Machine Learning แบบ data-parallel มักคำนวณ gradient ในแต่ละ accelerator แล้ว all-reduce ผล การเพิ่ม GPU จึงลด compute ต่อ GPU แต่ communication ของ gradient อาจกลายเป็นคอขวด รูป parallelism และ collective communication ต้องออกแบบร่วมกัน

16Synchronization: รอเท่าที่ความหมายจำเป็น

Global barrier เข้าใจง่ายแต่เปลี่ยน straggler หนึ่งตัวให้ทุกคนรอ Dataflow scheduling ปล่อย task ที่ input พร้อมเดินต่อได้ จึงเหมาะกับ DAG ที่แต่ละแขนมีเวลาต่างกัน

17Nested และ Hybrid Parallelism

โปรแกรมสมัยใหม่ใช้ parallelism ซ้อนหลายระดับ เช่น MPI แบ่งงานระหว่างเครื่อง OpenMP แบ่งงานระหว่าง core และ SIMD ทำหลาย element ต่อ instruction หรือ Spark แบ่ง partition ระหว่าง executor ขณะที่ library ภายในใช้ multithreaded BLAS

18Parallelism ใน Deep Learning

ระบบฝึกโมเดลขนาดใหญ่จึงไม่ได้เลือก parallelism แบบเดียว แต่ประกอบหลายมิติให้ตรงกับ memory capacity, bandwidth และ topology ของ cluster

19กรอบเลือกประเภท Parallelism

1. วาดข้อมูลและ dependency ก่อนเลือกเครื่องมือ
2. ถ้า operation ซ้ำบนข้อมูลจำนวนมาก ให้เริ่มพิจารณา data parallelism
3. ถ้ามีงานคนละชนิดที่อิสระ ให้พิจารณา task parallelism
4. ถ้าข้อมูลไหลผ่านหลายขั้นและมีหลายชิ้นต่อเนื่อง ให้พิจารณา pipeline
5. ตรวจ stage/task ที่ช้าที่สุดและ pattern การสื่อสาร
6. ออกแบบ granularity ให้ computation มากพอชดเชย overhead
7. ค่อยเลือก thread, process, GPU, MPI หรือ framework

20กรณีศึกษา: ระบบประมวลผลวิดีโอ

1. วิดีโอหลายไฟล์ประมวลผลพร้อมกันเป็น task parallelism ระดับ job
2. แต่ละไฟล์ผ่าน decode → filter → inference → encode เป็น pipeline
3. Filter แต่ละ frame ใช้ data parallelism บน pixel/GPU
4. Inference หลาย frame รวมเป็น batch เพื่อใช้ accelerator คุ้มขึ้น
5. เขียนผลแยกไฟล์ ลด shared lock และรวม metadata ภายหลัง

คอขวดอาจย้ายตาม configuration ถ้า decode ช้า GPU จะว่าง ถ้า batch ใหญ่ latency ต่อ frame สูงขึ้น ถ้า encode ช้า queue หลัง inference โต การออกแบบจึงต้องวัดทั้ง stage time, utilization, queue และ end-to-end latency

21แล็บและแบบฝึกที่แนะนำ

22สรุปและขั้นตอนถัดไป

Data, task และ pipeline parallelism เป็นสามเลนส์หลักสำหรับมองงาน แต่ระบบจริงผสมกันได้ สิ่งสำคัญกว่าชื่อหมวดคือ dependency, granularity, load balance, communication และ synchronization เพราะสิ่งเหล่านี้กำหนดว่า parallelism ที่เห็นบนกระดาษจะกลายเป็น speedup บนเครื่องจริงหรือไม่

บทถัดไปจะถามต่อว่า เมื่อรู้รูปแบบของงานแล้ว ฮาร์ดแวร์ชนิดใดเหมาะกับมัน Shared memory, distributed memory, vector processor, GPU, cluster และ NUMA ต่างเปิด parallelism และคิดราคาการย้ายข้อมูลคนละแบบครับ