Parallel Systems · บทที่ 1 จาก 9

Why Parallel Systems?

ก่อนเรียนเทคนิคใด ๆ ต้องเข้าใจก่อนว่าทำไมเราถึงยอมแลกความซับซ้อนมหาศาลของการเขียนโปรแกรมขนาน เพื่อแลกกับความเร็ว — และปัญหา "ใหญ่แค่ไหนถึงเรียกว่าใหญ่" เปลี่ยนไปมากแค่ไหนในรอบ 20 ปีที่ผ่านมา

📚

สังเคราะห์และจัดโครงสร้างใหม่จากเอกสารประกอบวิชา 2110732 Parallel Computing และ 2110414 Large Scale Computing Systems (Veera Muangsin, Natawut Nupairoj — ราว พ.ศ. 2551–2557 / ค.ศ. 2008–2014) โดยจัดบทใหม่ทั้งหมดและเสริมเนื้อหาให้ทันสมัยถึงปี 2026 — ทุกหัวข้อจะมีกล่อง "แล้ว vs ตอนนี้" เทียบของเดิมกับพัฒนาการที่เกิดขึ้นหลังจากนั้น

1Parallel System คืออะไร

นิยาม

"กลุ่มของหน่วยประมวลผลที่สื่อสารและร่วมมือกันเพื่อแก้ปัญหาขนาดใหญ่ให้เร็วขึ้น" — หัวใจคือ "Two heads are better than one" แบ่งงานเดียวกันให้หลายหน่วยประมวลผลช่วยกันทำพร้อมกัน แทนที่จะทำทีละขั้นตอนบนหน่วยประมวลผลเดียว

Parallel เทียบกับ Distributed — สับสนกันบ่อย แต่ตอบคำถามคนละข้อ

มิติ	Parallel Computing	Distributed Computing
เป้าหมายหลัก	ทำงานเดียวให้เร็วขึ้น โดยแบ่งงานนั้นออกเป็นส่วนย่อยที่ทำพร้อมกัน	ทำให้ทรัพยากรที่กระจายตัวทางภูมิศาสตร์ทำงานร่วมกันได้ — เป้าหมายอาจเป็นความพร้อมใช้งาน การแชร์ทรัพยากร ไม่จำเป็นต้องเน้นความเร็วของงานเดียว
ความคับคั่งของการเชื่อมต่อ (coupling)	มักเชื่อมกันแน่น (tightly coupled) latency ต่ำ เพราะต้องแลกเปลี่ยนข้อมูลกันถี่ระหว่างคำนวณ	มักเชื่อมกันหลวม (loosely coupled) ทนต่อ latency สูงและการเชื่อมต่อไม่เสถียรได้มากกว่า
ขอบเขต	มักอยู่ในเครื่องเดียวหรือคลัสเตอร์เดียวกัน	มักกระจายข้ามองค์กร ข้ามศูนย์ข้อมูล หรือข้ามอินเทอร์เน็ต

ในทางปฏิบัติเส้นแบ่งไม่ชัดเจน

ระบบยุคปัจจุบันจำนวนมากเป็นทั้งสองอย่างพร้อมกัน เช่น การเทรนโมเดล AI ขนาดใหญ่ใช้ GPU หลายพันตัวทำงานขนานกันภายในงานเดียว ในขณะที่ GPU เหล่านั้นก็กระจายอยู่คนละเครื่องคนละ rack ในดาต้าเซ็นเตอร์ — วิชานี้ครอบคลุมทั้งสองมุม โดยเริ่มจากมุม parallel (บทที่ 1-6) แล้วขยายไปสู่มุม large-scale/distributed (บทที่ 7-9)

2ปัญหาที่ใหญ่พอจะต้อง "ขนาน" — แล้วเทียบกับตอนนี้

เอกสารต้นฉบับยกตัวอย่าง "Grand Challenge Problems" และซูเปอร์คอมพิวเตอร์ยุคต้นทศวรรษ 2000 ไว้เป็นแรงจูงใจ ตัวเลขเหล่านั้นล้าสมัยไปมากแล้ว แต่คำถามพื้นฐาน "ทำไมเครื่องเดียวไม่พอ" ยังคงเหมือนเดิมทุกประการ

แล้ว · ต้นทศวรรษ 2000

ตอนนี้ · 2026

Earth Simulator (ญี่ปุ่น) — ผู้นำ Top500 ปี 2002 ด้วยความเร็ว 35.86 TFLOPS (3.586×10¹³ FLOPS) ใช้โปรเซสเซอร์แบบ vector หลายพันตัว ถือเป็น "อภิมหาซูเปอร์คอมพิวเตอร์" ของยุคนั้น

Frontier (Oak Ridge National Lab, สหรัฐฯ) และ El Capitan คือซูเปอร์คอมพิวเตอร์ระดับ exascale ทะลุ 1 EFLOPS (10¹⁸ FLOPS) — เร็วกว่า Earth Simulator ประมาณ 30,000 เท่า ในเวลาไม่ถึง 25 ปี ขับเคลื่อนด้วย GPU เป็นหลัก ไม่ใช่ vector processor แบบเดิม

แล้ว · โจทย์ที่ "ใหญ่เกินเครื่องเดียว"

ตอนนี้ · โจทย์ที่ใหญ่กว่าเดิมอีกหลายขั้น

Computational Chemistry, Aerodynamic Design, Human Vision Simulation — ต้องการ 100 TFLOPS ถึงระดับ EFLOPS (ซึ่งตอนนั้นยังเป็นเป้าหมายในอนาคต)

การเทรน Large Language Model (เช่นโมเดลระดับ GPT) ใช้พลังประมวลผลระดับหลายพัน petaFLOP-days บน GPU cluster หลายหมื่นตัว — เป็นโจทย์ที่ "ใหญ่เกินเครื่องเดียว" ในระดับที่ยุค 2000 จินตนาการไม่ถึง

สิ่งที่ไม่เปลี่ยน

ไม่ว่าจะปี 2002 หรือ 2026 คำตอบของ "ทำไมต้องขนาน" เหมือนเดิมเป๊ะ: มีขีดจำกัดทางฟิสิกส์ว่าซีพียูตัวเดียวเร็วได้แค่ไหน (ดูหัวข้อ 4) และเมื่อโจทย์ใหญ่กว่าขีดจำกัดนั้น ทางเดียวที่จะเร็วขึ้นต่อคือเพิ่มจำนวนหน่วยประมวลผลที่ทำงานพร้อมกัน — สิ่งที่เปลี่ยนคือ "หน่วยประมวลผล" นั้นเปลี่ยนจาก vector processor เฉพาะทางราคาแพง มาเป็น GPU consumer-grade ราคาถูกกว่ามากที่ผลิตจำนวนมาก

3โจทย์ 4 ข้อที่ต้องตอบก่อนออกแบบระบบขนานใด ๆ

เอกสารต้นฉบับตั้งคำถามเหล่านี้ไว้ในหัวข้อ "Problem & Algorithm" และ "Architecture" — ยังคงเป็นกรอบคิดที่ใช้ได้เสมอ ไม่ว่าจะออกแบบระบบขนานแบบไหนก็ตาม

คำถาม	ความหมาย
แบ่งปัญหาอย่างไร (Partition)	งานเดิมแบ่งเป็นส่วนย่อยที่ทำพร้อมกันได้อย่างไร — แบ่งตามข้อมูล (data) หรือแบ่งตามหน้าที่ (function)?
จัดการหน่วยประมวลผลกี่ตัว (Scale)	1, 2, 4, 64, หรือ 1024 หน่วยประมวลผล? จำนวนที่มากขึ้นไม่ได้แปลว่าเร็วขึ้นเสมอไป (ดู Amdahl's Law ในบทที่ 6)
เชื่อมต่อกันอย่างไร (Interconnect)	Bus, ring, mesh, หรือเครือข่ายแบบอื่น — โครงสร้างการเชื่อมต่อกำหนดว่าการสื่อสารระหว่างหน่วยประมวลผลจะเร็วหรือช้าแค่ไหน
แลกเปลี่ยนข้อมูลอย่างไร (Memory model)	Memory ใช้ร่วมกัน (shared) หรือแยกกันคนละส่วน (distributed)? ดิสก์เก็บข้อมูลรวมศูนย์หรือกระจาย?

"Unlisted Monster": Overhead

เอกสารต้นฉบับเตือนไว้ตรง ๆ ว่ามีต้นทุนแฝงที่มักถูกมองข้าม — การประสานงาน (coordination), การสื่อสาร (communication), และการซิงโครไนซ์ (synchronization) ระหว่างหน่วยประมวลผลล้วนกินเวลาที่ไม่ได้ทำงานจริง (useful work) เลย ยิ่งแบ่งงานละเอียดขึ้นและมีหน่วยประมวลผลมากขึ้น overhead นี้ยิ่งมีสัดส่วนสูงขึ้นตาม — เป็นรากฐานของ Amdahl's Law และ parallel overhead ที่จะอธิบายละเอียดในบทที่ 6

4ทำไมซีพียูตัวเดียวไปต่อไม่ได้: กำแพงพลังงาน (Power Wall)

สิ่งที่เอกสารต้นฉบับยังไม่ได้พูดถึง (เพราะเกิดขึ้นทีหลัง)

ราวปี 2004-2005 อุตสาหกรรมซีพียูเจอกำแพงพลังงาน (power wall) — การเพิ่มความเร็วสัญญาณนาฬิกา (clock speed) ต่อไปเรื่อย ๆ ทำให้ซีพียูร้อนและกินไฟเกินกว่าจะระบายความร้อนได้จริงในเชิงพาณิชย์ ผลคือ single-core clock speed หยุดโตอย่างรวดเร็วแบบที่เคยเป็นมาตลอดยุค 1990

ทางออกของอุตสาหกรรม

แทนที่จะไล่เพิ่มความเร็วซีพียูตัวเดียว (ซึ่งเข้าใกล้ขีดจำกัดทางฟิสิกส์) อุตสาหกรรมหันมาเพิ่มจำนวนแกนประมวลผล (core) ต่อชิปแทน

"Free lunch is over" — Herb Sutter (2005)

โปรแกรมที่เคยเร็วขึ้นอัตโนมัติทุกครั้งที่ซีพียูรุ่นใหม่ออก (เพราะ clock speed สูงขึ้น) จะไม่เร็วขึ้นอีกต่อไปหากไม่เขียนโค้ดให้รองรับการทำงานแบบขนานเอง — นี่คือจุดเปลี่ยนสำคัญที่ทำให้ "การเขียนโปรแกรมขนาน" ย้ายจากศาสตร์เฉพาะทางของซูเปอร์คอมพิวเตอร์ มาเป็นทักษะพื้นฐานที่โปรแกรมเมอร์ทั่วไปต้องมี เพราะแม้แต่มือถือและแล็ปท็อปทั่วไปก็เป็น multicore ทั้งหมดแล้ว

คำถามซ้อมสอบ

อธิบายความแตกต่างระหว่าง parallel computing กับ distributed computing โดยยกตัวอย่างระบบที่เป็นทั้งสองอย่างพร้อมกัน
อธิบายว่าเหตุใดตัวเลข FLOPS ของซูเปอร์คอมพิวเตอร์ในอดีตกับปัจจุบันจึงต่างกันมหาศาล และสิ่งใดที่ยัง "ไม่เปลี่ยน" ในเหตุผลที่ต้องใช้ระบบขนาน
อธิบาย 4 คำถามพื้นฐานที่ต้องตอบก่อนออกแบบระบบขนาน พร้อมยกตัวอย่างของตัวเอง
อธิบายว่า overhead จากการประสานงานและสื่อสารระหว่างหน่วยประมวลผลส่งผลต่อความคุ้มค่าของการเพิ่มจำนวนหน่วยประมวลผลอย่างไร
อธิบาย power wall และผลกระทบที่มีต่อทิศทางการออกแบบซีพียูตั้งแต่กลางทศวรรษ 2000 เป็นต้นมา

5Concurrency, Parallelism และ Distribution: คล้ายกันตรงที่มีหลายงาน แต่ไม่ใช่เรื่องเดียวกัน

คำสามคำนี้มักปรากฏพร้อมกันจนดูเหมือนใช้แทนกันได้ ความจริงแล้วแต่ละคำกำลังตอบคำถามคนละระดับ การแยกให้ชัดช่วยให้เราเลือกทั้ง algorithm และเครื่องมือได้ถูกตั้งแต่ต้น

แนวคิด	คำถามหลัก	ตัวอย่าง
Concurrency	จะจัดการหลายงานที่คาบเกี่ยวกันอย่างไร แม้อาจไม่ได้ทำพร้อมกันจริง	ระบบปฏิบัติการสลับ CPU ให้หลาย process
Parallelism	จะทำงานหลายส่วนพร้อมกันจริงเพื่อให้เสร็จเร็วขึ้นได้อย่างไร	แบ่ง matrix ให้หลาย core คำนวณพร้อมกัน
Distribution	หลายเครื่องที่ไม่มีหน่วยความจำร่วมจะประสานงานและทนต่อ partial failure อย่างไร	ฐานข้อมูลหลายศูนย์ข้อมูลที่ replica อาจขาดการติดต่อกัน

ภาพเปรียบเทียบ

พ่อครัวคนเดียวทำแกงและทอดไข่สลับกันคือ concurrency พ่อครัวสองคนทำคนละอย่างพร้อมกันคือ parallelism ส่วนครัวสองสาขาที่ต้องส่งวัตถุดิบและยืนยันรายการสั่งซื้อผ่านโทรศัพท์คือ distribution งานทั้งหมดอาจเกิดพร้อมกัน แต่ข้อจำกัดที่ต้องแก้ไม่เหมือนกัน

โปรแกรมหนึ่งอาจ concurrent แต่ไม่ parallel เช่น event loop บน core เดียว หรือ parallel แต่ไม่ distributed เช่น vector instruction ภายใน CPU และอาจเป็นทั้งสองอย่าง เช่น Spark job ที่ใช้หลาย core บนหลายเครื่อง วิชานี้เริ่มจากมุม performance แต่จะค่อย ๆ เชื่อมไปยัง distribution เมื่อขยายออกนอกเครื่องเดียว

6เหตุผลที่ต้องขนานมีมากกว่า “อยากให้เร็วขึ้น”

ลดเวลาให้ได้คำตอบ

งานพยากรณ์อากาศ วิเคราะห์ genome หรือฝึกโมเดลอาจมี deadline ถ้าคำตอบมาหลังเหตุการณ์ผ่านไปแล้ว ต่อให้ถูกต้องก็มีค่าน้อยลง

แก้ปัญหาที่ใหญ่ขึ้น

เมื่อมีทรัพยากรเพิ่ม เราอาจไม่ลดเวลา แต่เพิ่ม resolution, จำนวนตัวแปร หรือจำนวน scenario ให้ผลลัพธ์ละเอียดขึ้น

รองรับงานจำนวนมาก

บริการออนไลน์อาจไม่ได้ทำ request เดียวให้เร็วขึ้น แต่ต้องประมวลผลหลาย request พร้อมกันเพื่อเพิ่ม throughput

ทำงานภายในงบพลังงาน

หลาย core ที่ความถี่ปานกลางอาจให้ throughput ต่อวัตต์ดีกว่า core เดียวที่ดันความถี่สูงมาก เพราะกำลังไฟเพิ่มเร็วกว่า performance

เหตุผลเหล่านี้นำไปสู่ metric ต่างกัน งาน simulation สนใจ time-to-solution บริการเว็บสนใจ throughput กับ tail latency ส่วนอุปกรณ์พกพาสนใจ energy per task การพูดว่า “เร็วขึ้น” โดยไม่บอก metric จึงยังไม่พอสำหรับการออกแบบ

7จาก Frequency Scaling สู่ Multicore

ช่วงหนึ่งผู้พัฒนาโปรแกรมได้รับ performance เพิ่มแทบอัตโนมัติจาก CPU รุ่นใหม่ Clock สูงขึ้น transistor เล็กลง และโปรแกรมเดิมมักเร็วขึ้นโดยไม่ต้องเปลี่ยนโครงสร้างมาก แต่แนวโน้มนี้ชนข้อจำกัดด้านพลังงาน ความร้อน และความซับซ้อนของการดึง Instruction-Level Parallelism

กำลังไฟแบบไดนามิกมักอธิบายโดยประมาณได้ด้วยความสัมพันธ์ต่อไปนี้

Dynamic power

P ≈ α · C · V² · f

เมื่อ α คือ activity factor, C คือ capacitance, V คือ voltage และ f คือความถี่ การเพิ่มความถี่มักต้องเพิ่มแรงดันด้วย จึงทำให้พลังงานและความร้อนเพิ่มเร็วกว่าความถี่เพียงเส้นตรง

เมื่อดัน core เดียวต่อได้ยาก ผู้ผลิตจึงใช้ transistor ที่เพิ่มขึ้นสร้างหลาย core แทน นี่เป็นการย้ายภาระจากผู้ออกแบบ CPU มาสู่ผู้เขียนโปรแกรมบางส่วน จากเดิมโปรแกรมเร็วขึ้นเมื่อซื้อเครื่องใหม่ กลายเป็นต้องเปิดเผย parallelism ให้ฮาร์ดแวร์ใช้ได้

Multicore ไม่ได้คูณความเร็วให้อัตโนมัติ

ถ้าโปรแกรมมี thread เดียว core ที่เหลืออาจช่วยงานระบบ แต่ไม่ได้ทำ critical path ของโปรแกรมให้สั้นลง การมีแปดเลนบนถนนไม่ช่วยรถคันเดียวที่ยังวิ่งอยู่เลนเดิม

8Memory Wall: CPU วิ่งเร็ว แต่ต้องหยุดรอข้อมูล

การคำนวณไม่ได้ใช้เวลาเฉพาะตอนบวกหรือคูณ CPU ต้องอ่าน instruction และข้อมูลจาก memory hierarchy ด้วย Register เร็วมาก cache ช้าลงเล็กน้อย ส่วน DRAM อาจช้ากว่าหลายสิบถึงหลายร้อย cycle หากข้อมูลไม่อยู่ใกล้ core หน่วยคำนวณจึงว่างทั้งที่งานยังไม่เสร็จ

เหมือนช่างประกอบรถ

ช่างมีมือเร็วขึ้นสิบเท่าไม่มีประโยชน์ ถ้าอะไหล่อยู่โกดังอีกฝั่งเมือง Cache คือชั้นวางอะไหล่ข้างโต๊ะ ส่วน locality คือการจัดอะไหล่ที่ต้องใช้ต่อเนื่องให้อยู่ใกล้มือ การเพิ่มช่างโดยไม่จัดระบบส่งของอาจทำให้ทุกคนยืนรอรถขนส่งพร้อมกัน

นี่อธิบายว่าทำไมงานปี 2002 จึงเกิด Superlinear Speedup ได้ เมื่อแบ่งตาราง Dynamic Programming ให้ CPU แต่ละตัว working set ย่อยอาจพอดีกับ cache มากขึ้น จำนวน cache miss ลดลงอย่างมหาศาล เราจึงไม่ได้เพียงหาร arithmetic work ด้วยแปด แต่ยังกำจัดเวลารอ memory บางส่วนที่ baseline เดิมต้องจ่าย

Locality สองแบบ

Temporal locality — ข้อมูลที่เพิ่งใช้มีแนวโน้มถูกใช้อีก ควรเก็บไว้ใกล้ CPU
Spatial locality — ถ้าใช้ตำแหน่งหนึ่ง มีแนวโน้มใช้ตำแหน่งข้างเคียง จึงอ่านเป็น cache line ครั้งละหลาย byte

Parallel algorithm ที่ดีต้องดูทั้งปริมาณ work และเส้นทางข้อมูล เพราะในเครื่องสมัยใหม่ บางครั้งการคำนวณเพิ่มเล็กน้อยเพื่อหลีกเลี่ยงการย้ายข้อมูลกลับคุ้มกว่า

9Dark Silicon และเหตุผลที่มีวงจรแต่เปิดพร้อมกันไม่ได้ทั้งหมด

จำนวน transistor ยังเพิ่มได้ต่อเนื่องช่วงหนึ่ง แต่ power budget ไม่ยอมให้ทุกส่วนทำงานเต็มกำลังพร้อมกัน แนวคิด dark silicon อธิบายว่าชิปอาจมีวงจรหลายชนิด แต่ต้องปิดหรือจำกัดความถี่บางส่วนเพื่อควบคุมความร้อน

ผลที่ตามมาคือสถาปัตยกรรมเริ่มมีหน่วยเฉพาะงาน เช่น GPU, tensor accelerator, video codec และ cryptographic engine แทนการใช้ general-purpose core แก้ทุกอย่าง หน่วยเฉพาะทางทำงานบางชนิดได้มีประสิทธิภาพต่อวัตต์สูงกว่า แต่แลกกับความยืดหยุ่นและความยากในการเขียนโปรแกรม

มุมมองที่เปลี่ยนไป

อดีตถามว่า “จะทำ CPU ให้เร็วขึ้นอย่างไร” ปัจจุบันถามเพิ่มว่า “ควรเปิดส่วนใดของชิป สำหรับงานชนิดใด และย้ายข้อมูลไปหามันคุ้มหรือไม่” Parallel Systems จึงเกี่ยวข้องกับ resource orchestration ภายในชิปพอ ๆ กับจำนวน core

10Strong Scaling กับ Weak Scaling

คำว่า scale มีสองความหมายซึ่งให้ผลต่างกันมาก

รูปแบบ	สิ่งที่คงที่	คำถาม	ตัวอย่าง
Strong scaling	ขนาดโจทย์รวม	เพิ่ม processor แล้วงานเดิมเสร็จเร็วขึ้นเท่าใด	Simulation เดิมจาก 8 ชั่วโมงเหลือ 1 ชั่วโมง
Weak scaling	งานต่อ processor	เพิ่มโจทย์และ processor พร้อมกันแล้วเวลาคงเดิมได้หรือไม่	เพิ่มความละเอียดของภาพตามจำนวน GPU

Strong scaling ชนส่วน sequential และ overhead เร็ว เพราะเมื่อแบ่งงานเล็กลง communication มีสัดส่วนมากขึ้น Weak scaling อาจดูดีแม้เวลาของโจทย์เดิมไม่ได้ลดมาก แต่แสดงว่าเรารับปัญหาที่ใหญ่ขึ้นได้ การรายงาน scalability จึงต้องบอกว่าทดสอบแบบใด

11Decomposition: แบ่งงานอย่างไรจึงมีโอกาสเร็วขึ้น

Domain decomposition

แบ่งพื้นที่ข้อมูล เช่น แบ่งภาพเป็น tile แบ่ง matrix เป็น block หรือแบ่งช่วง genome ให้ worker แต่ละตัว วิธีนี้เหมาะเมื่อ operation บนข้อมูลแต่ละส่วนคล้ายกัน แต่ต้องจัดการข้อมูลบริเวณขอบ

Functional decomposition

แบ่งตามหน้าที่ เช่น รับข้อมูล → แปลงข้อมูล → วิเคราะห์ → บันทึก แต่ละ stage ทำงานต่างกันและอาจต่อเป็น pipeline เหมาะกับ stream หรือระบบที่ throughput สำคัญ

Recursive decomposition

แตกโจทย์เป็นโจทย์ย่อยซ้ำ ๆ เช่น merge sort, quicksort หรือ tree search เหมาะกับ task runtime ที่สร้างและขโมยงานได้แบบ dynamic

แบ่งละเอียดเกินไปก็ช้า

Task เล็กช่วยกระจายโหลด แต่ถ้าเล็กกว่าต้นทุนสร้าง task, schedule, synchronize และส่งข้อมูล ระบบใช้เวลาจัดการงานมากกว่าทำงานจริง Granularity จึงเป็นตัวแปรออกแบบ ไม่ใช่รายละเอียดของ runtime

12Dependency และ Critical Path

งานทั้งหมดหรือ work บอกว่าถ้าทำทีละขั้นต้องใช้ความพยายามเท่าใด ส่วน span หรือ critical path บอกสายงานที่ยาวที่สุดซึ่งหลีกเลี่ยงการรอไม่ได้ ต่อให้มี processor ไม่จำกัด เวลาก็สั้นกว่า span ไม่ได้

ขอบเขตเบื้องต้น

Tₚ ≥ max(T₁ / p, T∞)

เมื่อ T₁ คือ work บน processor เดียว, p คือจำนวน processor และ T∞ คือ critical path ขอบเขตนี้บอกทั้งข้อจำกัดจากปริมาณงานและข้อจำกัดจาก dependency

การต้มอาหาร

หั่นผักหลายชนิดทำพร้อมกันได้ แต่ต้องรอน้ำเดือดก่อนใส่เส้น และต้องต้มเส้นก่อนจัดจาน ต่อให้มีผู้ช่วยหนึ่งร้อยคน ลำดับน้ำเดือด → ต้มเส้น → จัดจานยังเป็น critical path ที่ย่นด้วยคนเพิ่มไม่ได้

13Load Balance: ทุกคนมีงาน ไม่ได้แปลว่าทุกคนเสร็จพร้อมกัน

เวลารวมของงานขนานมักถูกกำหนดโดย worker ที่ช้าที่สุด หากแบ่งข้อมูลเท่ากันแต่ความยากไม่เท่ากัน บาง worker อาจว่างรออีกตัว เช่น การแบ่ง graph ตามจำนวน vertex ไม่ได้แปลว่าจำนวน edge เท่ากัน

วิธี	ข้อดี	ข้อจำกัด
Static partitioning	ต้นทุนต่ำ ตำแหน่งข้อมูลคาดเดาได้	ไม่เหมาะเมื่อเวลาของ task ต่างกันมาก
Dynamic scheduling	แจกงานเพิ่มให้ worker ที่ว่าง	มี queue contention และ scheduling overhead
Work stealing	Worker ที่ว่างขโมยงานจาก worker อื่น กระจายคอขวด	Locality อาจเสียและพฤติกรรมซับซ้อนขึ้น

การทำ load balance จึงต้องแลกกับ locality บางครั้งปล่อยให้ worker หนึ่งมีงานมากกว่าเล็กน้อยแต่ข้อมูลอยู่ใน cache ยังเร็วกว่าย้าย task ไปอีก core แล้วต้องอ่านข้อมูลใหม่ทั้งหมด

14Overhead ที่กิน Speedup

Task creation — การสร้าง thread, process หรือ kernel มีต้นทุน
Communication — ย้ายข้อมูลระหว่าง core, socket, GPU หรือเครื่อง
Synchronization — barrier, lock และ atomic operation ทำให้บางส่วนรอ
Contention — หลาย worker แย่ง cache line, memory channel, network หรือ storage
Redundant work — บาง algorithm คำนวณซ้ำเพื่อหลีกเลี่ยงการสื่อสาร
Imbalance — processor เร็วเท่ากันแต่ได้งานไม่เท่ากัน
Startup and teardown — เตรียม environment, distribute data และรวบรวมผล

สูตร speedup ที่ดีจึงไม่ใช่เพียงหาร work ด้วย p แต่ต้องรวม overhead ซึ่งมักโตตามจำนวน processor เมื่อ p มากพอ การเพิ่มทรัพยากรจึงอาจทำให้ช้าลงได้

15Amdahl's Law: ส่วนเล็กที่ไม่ขนานอาจกลายเป็นเพดานใหญ่

ถ้าสัดส่วน f ของโปรแกรมทำงานขนานได้ และส่วน 1−f ต้องทำลำดับ เวลาที่คาดหวังเมื่อใช้ p processors เขียนได้โดยประมาณดังนี้

Amdahl's Law

S(p) = 1 / ((1 − f) + f/p)

เมื่อ p เพิ่มเข้าใกล้อนันต์ ส่วน f/p ลดลงเกือบศูนย์ แต่ส่วน 1−f ยังอยู่ ถ้ามี sequential 5% speedup สูงสุดจึงไม่เกิน 20 เท่า

Amdahl ไม่ได้บอกว่า parallelism หมดหวัง แต่บังคับให้เราหาส่วนที่กลายเป็น serial bottleneck หลัง optimize แล้ว บางครั้งการเพิ่ม processor ไม่คุ้มเท่าการออกแบบ algorithm ใหม่เพื่อลด critical section หรือ communication

16เมื่อใดไม่ควรทำ Parallel

งานเล็กกว่า overhead ของการแบ่งและรวมผล
Dependency เป็นสายยาวและแทบไม่มี independent work
ข้อมูลต้องแก้ shared state จุดเดียวตลอดเวลา
ระบบถูกจำกัดด้วย I/O ภายนอกที่เพิ่ม bandwidth ไม่ได้
ความซับซ้อนในการทดสอบและ debug แพงกว่าประโยชน์ทางเวลา
ความต้องการจริงคือเพิ่ม throughput ของหลาย request ไม่ใช่ลด latency ของ request เดียว ซึ่งอาจใช้ replication หรือ batching เหมาะกว่า

ความขนานที่ดีที่สุดบางครั้งคือไม่ขนาน

ถ้างานใช้ 20 มิลลิวินาที แต่การส่งขึ้น GPU และดึงผลกลับใช้ 10 มิลลิวินาทีต่อด้าน ต่อให้ kernel ฟรีก็ไม่ได้เร็วขึ้น การเลือกไม่ใช้ทรัพยากรพิเศษในกรณีนี้ไม่ใช่ล้าหลัง แต่เป็นการเข้าใจต้นทุน

17กรณีศึกษา: Dynamic Programming แบบ Wavefront

ตาราง Dynamic Programming ทั่วไปมี dependency จากด้านบน ด้านซ้าย หรือแนวทแยง เซลล์ในแถวเดียวกันจึงอาจทำพร้อมกันไม่ได้ทั้งหมด แต่เซลล์บน anti-diagonal เดียวกันพึ่งข้อมูลจากแนวก่อนหน้าและคำนวณพร้อมกันได้

วาด dependency ของเซลล์ก่อนเขียน parallel loop
จัดกลุ่มเซลล์ที่ไม่มี dependency ต่อกันเป็น wavefront
แบ่ง wavefront เป็น block เพื่อให้ข้อมูลย่อยพอดีกับ cache
ส่งหรือแชร์เฉพาะ boundary ที่ block ถัดไปต้องใช้
ใช้ barrier ระหว่าง wavefront เท่าที่จำเป็น ไม่ synchronize ทุกเซลล์

กรณีนี้แสดงแก่นของทั้งวิชา: algorithm เปิด parallelism ผ่านรูป dependency, architecture กำหนดราคาของข้อมูล และ performance เกิดจากการเลือกระดับ block ที่สมดุลระหว่าง concurrency, cache locality และ synchronization

18การวัดผลเบื้องต้นที่ควรทำทุกครั้ง

ใช้ input เดียวกันและตรวจว่าผลลัพธ์ถูกต้องเท่ากัน
นิยามว่าเวลารวม preprocessing, transfer และ I/O หรือไม่
วัดหลายรอบ รายงานค่ากลางและความแปรปรวน
วัด T(1) ของ parallel implementation ด้วย ไม่เปรียบเฉพาะกับ serial code คนละชุด
เก็บ CPU utilization, cache miss, memory bandwidth และเวลารอ synchronization
ทดลองหลาย input size และหลายจำนวน processor เพื่อเห็นจุดอิ่มตัว

กราฟเส้นเดียวเล่าไม่ครบ

ถ้ารายงานเพียง speedup ที่ p=8 เราไม่เห็นว่าเส้นเริ่มแบนที่ p เท่าใด และไม่รู้ว่าปัญหาเกิดจาก serial fraction, memory bandwidth หรือ imbalance การวัดที่ดีต้องช่วยอธิบาย ไม่ใช่เพียงช่วยโฆษณาผลลัพธ์

19กิจกรรมและแล็บที่แนะนำ

แล็บ 1: หาเพดานของ Parallel Sum

ให้นักศึกษา sum array ด้วย 1, 2, 4 และ 8 threads เปลี่ยนขนาดข้อมูลตั้งแต่เล็กกว่า cache ไปจนใหญ่กว่า DRAM cache หลายเท่า วัด runtime, speedup และ cache miss แล้วอธิบายว่าทำไมกราฟเปลี่ยนรูปตามขนาดข้อมูล

แล็บ 2: Wavefront DP

สร้างตาราง dependency ขนาดเล็กให้เห็นผลด้วยมือ จากนั้น implement แบบ sequential และ block wavefront ทดลองเปลี่ยน block size แล้วหาจุดที่เร็วที่สุด พร้อมอธิบายด้วย locality และ synchronization overhead

แบบฝึกคิด

เลือกงานจริงหนึ่งงาน เช่น resize ภาพ ประมวลผลไฟล์ log หรือค้นหาเส้นทาง แล้วเขียน design note หนึ่งหน้า: decomposition, dependency, shared data, expected bottleneck, metric และเหตุผลว่าทำไม parallelism จึงน่าจะคุ้ม

Checklist ก่อนประกาศว่าจะทำระบบแบบขนาน

ผลลัพธ์ที่ต้องการคือ latency ต่ำลง throughput สูงขึ้น หรือแก้โจทย์ใหญ่ขึ้น
Baseline ใช้ algorithm และ optimization ที่เป็นธรรมแล้วหรือยัง
ส่วนใดของงานเป็น independent work และส่วนใดอยู่บน critical path
ข้อมูลต่อ worker มีขนาดเท่าใด ต้องส่งหรือแชร์บ่อยแค่ไหน
Task หนึ่งใหญ่พอชดเชย scheduling และ synchronization overhead หรือไม่
Load เปลี่ยนตาม input หรือแบ่งแบบ static ได้
ทรัพยากรที่แชร์กัน เช่น memory bandwidth, storage และ network จะอิ่มที่จำนวน worker เท่าใด
เมื่อเพิ่ม processor แล้วจะเก็บหลักฐานอะไรเพื่ออธิบาย speedup หรือ slowdown

Checklist นี้มีไว้ป้องกันการเริ่มจากคำตอบ เช่น “ใช้ GPU” หรือ “ทำบน Spark” ก่อนเข้าใจโจทย์ หากยังตอบไม่ได้ว่า dependency กับ data movement อยู่ตรงไหน การเลือก framework ในตอนนั้นก็ใกล้เคียงกับการเลือกยานพาหนะก่อนรู้ว่าจะเดินทางไปที่ใด

Failure timeline ทางประสิทธิภาพ

สมมติใช้ 1 core ใช้เวลา 100 วินาที, 2 cores เหลือ 55 วินาที, 4 cores เหลือ 34 วินาที, 8 cores เหลือ 31 วินาที และ 16 cores กลับเป็น 38 วินาที กราฟนี้ไม่ได้บอกเพียงว่า “16 cores ไม่ดี” แต่ชวนตั้งสมมติฐานเป็นลำดับ: ช่วงแรก work ถูกแบ่งได้ ช่วง 4–8 cores เริ่มชน memory bandwidth และที่ 16 cores synchronization กับ contention มากกว่างานที่ประหยัดได้

การทดลองถัดไปจึงควรแยกตัวแปร เช่น เพิ่ม input size เพื่อดู granularity, วัด bandwidth, ลดความถี่ barrier หรือ pin threads ไม่ใช่เปลี่ยนทุกอย่างพร้อมกันแล้วสรุปจากกราฟใหม่ การวิเคราะห์ performance ที่ดีคล้ายการ debug: เปลี่ยนหนึ่งสมมติฐานและหา evidence ที่ทำให้มันอยู่หรือออกไป

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

Parallel Systems ไม่ได้เริ่มจากจำนวน core แต่เริ่มจากโครงสร้างของงาน เราต้องรู้ว่า work อยู่ตรงไหน dependency จำกัดอะไร ข้อมูลเคลื่อนที่อย่างไร และ overhead ใดจะโตเมื่อเพิ่ม processor ข้อจำกัดของ frequency scaling, power wall และ memory wall ทำให้ multicore กับ accelerator กลายเป็นสิ่งจำเป็น แต่ไม่ได้ทำให้โปรแกรมเดิมเร็วขึ้นโดยอัตโนมัติ

บทถัดไปจะเปิด CPU ออกมาดูว่า ก่อนโปรแกรมเมอร์สร้าง thread ฮาร์ดแวร์พยายามทำ instruction หลายคำสั่งพร้อมกันอย่างไร ผ่าน pipeline, superscalar และ out-of-order execution การเข้าใจความขนานระดับนี้จะทำให้เราเห็นว่า parallelism ไม่ได้เริ่มเมื่อมีหลาย core แต่มันเริ่มอยู่ภายใน core มานานแล้วครับ