Parallelism Inside a CPU

1Pipelining: สายพานการผลิตคำสั่ง

             1   2   3   4   5   6   7   8   9
Inst 1       F   D   O   E   S
Inst 2           F   D   O   E   S
Inst 3               F   D   O   E   S
Inst 4                   F   D   O   E   S

2Hazard: สิ่งที่ทำให้ Pipeline สะดุด

3Superscalar: ก้าวข้าม "หนึ่งคำสั่งต่อหนึ่งรอบสัญญาณนาฬิกา"

Multimedia Extension: MMX, 3DNow! — บทเรียนประวัติศาสตร์

4ข้อจำกัดของ ILP ในเครื่องปัจจุบัน และต้นทุนที่เอกสารเดิมยังไม่กล่าวถึง

5หนึ่งคำสั่งไม่ได้เกิดขึ้นในหนึ่งจังหวะ

เวลาเราอ่าน assembly หนึ่งบรรทัด ดูเหมือน CPU หยิบคำสั่งมาทำแล้วจบ ความจริงคำสั่งต้องผ่านหลายขั้น เช่น fetch, decode, อ่าน operand, execute, เข้าถึง memory และเขียนผลกลับ หากรอให้คำสั่งหนึ่งผ่านครบทุกขั้นก่อนเริ่มคำสั่งถัดไป วงจรแต่ละส่วนจะว่างอยู่มาก

6Latency กับ Throughput ของ Pipeline

Pipeline ลึกขึ้นแบ่งงานแต่ละ stage ให้สั้น จึงอาจเพิ่ม clock frequency และรับคำสั่งใหม่ได้ถี่ขึ้น แต่คำสั่งหนึ่งต้องผ่าน stage มากขึ้น และเมื่อ branch ผิดต้องทิ้งงานใน pipeline มากกว่าเดิม จึงไม่มีเหตุผลว่าลึกที่สุดจะดีที่สุดเสมอ

คำว่า one instruction per cycle จึงหมายถึง throughput ในสภาวะต่อเนื่อง ไม่ได้หมายความว่าคำสั่งแต่ละตัวใช้เวลาเพียง cycle เดียว ความต่างนี้สำคัญมากเมื่อวิเคราะห์ latency chain

7Data Hazard: เมื่อคำสั่งหลังต้องรอผลคำสั่งก่อน

Forwarding ส่งผลจาก execution unit ไปยังคำสั่งถัดไปโดยไม่รอเขียนกลับ register file ลด stall ของ RAW บางชนิด แต่ load-use dependency มักยังต้องรอ เพราะข้อมูลจาก cache มาถึงช้ากว่า ALU result

8Control Hazard และ Branch Prediction

เมื่อพบ branch CPU ยังไม่รู้ instruction ถัดไปจนคำนวณเงื่อนไขเสร็จ หากหยุดรอทุกครั้ง throughput จะตกมาก CPU จึงทายเส้นทางและ fetch ต่อแบบ speculative หากทายถูกงานที่ทำล่วงหน้าใช้ได้ หากผิดต้อง flush และเริ่มใหม่จากเส้นทางจริง

ตัวทำนายไม่ได้เดาสุ่ม

• ใช้ประวัติของ branch เดิมว่าครั้งก่อน taken หรือไม่
• ใช้รูปแบบหลายบิตเพื่อไม่เปลี่ยนใจจากเหตุการณ์ผิดปกติครั้งเดียว
• ใช้ global history จับความสัมพันธ์ระหว่าง branch หลายจุด
• ใช้ branch target buffer จำปลายทางเพื่อเริ่ม fetch ได้เร็ว
• ใช้ return-address stack สำหรับการกลับจาก function

Branch ที่คาดเดาได้ เช่น loop ที่วนซ้ำจำนวนมาก มักมี accuracy สูง ส่วนข้อมูลสุ่มที่เลือกเส้นทางคนละครึ่งคาดยาก การเรียงข้อมูลหรือใช้ branchless transformation บางครั้งจึงช่วยได้ แต่ต้องวัด เพราะคำสั่งเพิ่มและ vectorization อาจเปลี่ยน trade-off

9Superscalar: ออกคำสั่งได้มากกว่าหนึ่งคำสั่งต่อ Cycle

Pipeline แบบ scalar รับคำสั่งใหม่ได้หนึ่งคำสั่งต่อ cycle ส่วน superscalar CPU มีหลาย execution units และพยายาม issue หลายคำสั่งใน cycle เดียว ถ้าคำสั่งเหล่านั้น independent และ operand พร้อม

ความกว้างของ frontend, จำนวน decoder, reservation station, execution port และ bandwidth การเขียนผลล้วนเป็นข้อจำกัด การบอกว่า CPU เป็น 4-wide จึงไม่ได้แปลว่าทุกโปรแกรมได้ 4 instructions per cycle หากโค้ดมี dependency chain หรือ cache miss ยาว execution units ก็ยังว่าง

10Out-of-Order Execution: เปลี่ยนลำดับทำ แต่ไม่เปลี่ยนความหมาย

ถ้าคำสั่งหนึ่งรอข้อมูลจาก memory คำสั่งถัดไปที่ไม่เกี่ยวข้องอาจทำก่อนได้ CPU จึง decode ตามลำดับ แต่ schedule execution ตามความพร้อม แล้ว commit ผลกลับตามลำดับโปรแกรมเพื่อรักษา precise state

1. Fetch/Decode รับ instruction ตามเส้นทางที่คาดไว้
2. Rename เปลี่ยน architectural register เป็น physical register เพื่อตัด WAR/WAW false dependency
3. Dispatch ส่ง instruction เข้า scheduler หรือ reservation station
4. Issue/Execute เลือกคำสั่งที่ operand พร้อมไปยัง execution unit
5. Retire ยืนยันผลตามลำดับผ่าน reorder buffer

Register renaming เปรียบเหมือนนักศึกษาสองคนมีชื่อเล่น “เอ” เหมือนกัน ระบบจึงออกหมายเลขประจำตัวใหม่ให้ ไม่ต้องบังคับให้ทั้งสองทำงานต่อคิวเพียงเพราะชื่อชนกัน ส่วน RAW เป็นความสัมพันธ์จริงที่เปลี่ยนชื่อแล้วก็ยังต้องรอ

11Reorder Buffer และ Precise Exception

เมื่อ execution เกิดนอกลำดับ หากคำสั่งเก่าพบ exception CPU ต้องทำให้ระบบดูเหมือนคำสั่งก่อนหน้าสำเร็จแล้ว ส่วนคำสั่งนั้นและคำสั่งหลังยังไม่เกิด Reorder Buffer เก็บผลชั่วคราวและ retire ตามลำดับ จึงย้อน speculative work ที่ยังไม่ commit ได้

กลไกนี้ทำให้ฮาร์ดแวร์ภายในซับซ้อน แต่ software ยังเห็น sequential semantics ตาม Instruction Set Architecture เป็นตัวอย่างของ abstraction ที่ซ่อน parallel execution ไว้ใต้โปรแกรมแบบลำดับ

12Speculation: ทำงานก่อนรู้ว่าจำเป็นหรือไม่

Branch prediction บอกเส้นทางที่น่าจะถูก CPU จึง execute instruction ต่อไปแบบ speculative ผลยังไม่เปิดเผยเชิงสถาปัตยกรรมจนกว่าจะยืนยันเส้นทาง หากทายผิดจึงทิ้งผลได้

แต่ผลข้างเคียงระดับ microarchitecture เช่น cache line ที่ถูกโหลด อาจยังคงอยู่ นี่เป็นรากของช่องโหว่อย่าง Spectre ซึ่งผู้โจมตีชักนำให้ speculative execution แตะข้อมูลลับ แล้วอ่านร่องรอยผ่าน timing แม้ผล instruction ถูกยกเลิกแล้ว

13Spectre กับ Meltdown ต่างกันตรงไหน

รายละเอียด variant มีมากและเปลี่ยนตาม microarchitecture ประเด็นในวิชานี้คือ optimization ที่ซ่อนอยู่ไม่ใช่ของฟรี มันสร้าง state, timing และช่องทางสังเกตใหม่ซึ่ง software security model เดิมอาจไม่ครอบคลุม

14SIMD และ Vectorization: หนึ่งคำสั่งกับข้อมูลหลายตัว

ILP ทำหลาย instruction อิสระพร้อมกัน ส่วน SIMD ใช้ instruction เดียวทำ operation เดียวกับข้อมูลหลาย element เช่น บวกเลข 8 ค่าใน vector register พร้อมกัน เหมาะกับ loop ที่แต่ละ iteration เป็นอิสระและ control flow คล้ายกัน

// scalar concept
for (i = 0; i < n; i++) c[i] = a[i] + b[i];

// vector concept: โหลด a,b หลายค่าต่อครั้ง แล้วบวกเป็นชุด

Compiler อาจ auto-vectorize ได้เมื่อพิสูจน์ว่าไม่มี alias หรือ loop-carried dependency หาก pointer อาจชี้ทับกัน หรือมี branch ซับซ้อน compiler อาจระวังจนไม่ vectorize Programmer จึงควรอ่าน optimization report และวัดผล ไม่ใช่เดาจาก syntax

15SIMD, SIMT และ GPU

GPU ใช้แนวคิดคล้าย SIMD แต่จัดโปรแกรมเป็น threads จำนวนมากภายใต้โมเดล SIMT Threads ใน warp หรือ wavefront เดิน instruction เดียวกัน ถ้า branch ไปคนละทางต้อง execute แยกเส้นทางและ mask threads บางส่วน เรียกว่า divergence

16SMT: ใช้หลาย Thread เติมช่องว่างของ Core

Simultaneous Multithreading เช่น Intel Hyper-Threading ให้ hardware thread หลายตัวแชร์ execution resources ของ core เดียว เมื่อ thread หนึ่งรอ cache miss อีก thread อาจใช้ execution slot ที่ว่าง ช่วย utilization แต่ไม่ได้เพิ่ม ALU, cache หรือ memory bandwidth เป็นสองเท่า

งานที่ใช้ resource คนละชนิดอาจอยู่ร่วมกันได้ดี ส่วนสอง thread ที่แย่ง execution port หรือ memory bandwidth เดียวกันอาจแทบไม่เร็วขึ้น และอาจช้าลงจาก contention ดังนั้น logical CPU ไม่ควรถูกนับเท่ากับ physical core โดยไม่วัด workload จริง

17Memory-Level Parallelism

Out-of-order core สามารถมี cache miss หลายรายการ outstanding พร้อมกัน เพื่อซ้อน latency ของ memory access หาก access independent กัน แต่ dependency chain แบบ pointer chasing เช่น linked list ทำให้ request ถัดไปเริ่มไม่ได้จนค่าปัจจุบันกลับมา จึงใช้ bandwidth ไม่เต็มแม้ memory system รองรับมาก

18Compiler ช่วยดึง ILP อย่างไร

• Instruction scheduling จัดคำสั่งให้มี independent work คั่น latency
• Loop unrolling เปิด iteration หลายชุดให้ CPU เห็นพร้อมกัน ลด branch overhead
• Vectorization รวม scalar operations เป็น SIMD instruction
• Inlining ลด call overhead และเปิดโอกาส optimize ข้าม function
• Alias analysis พิสูจน์ว่า memory reference ไม่ทับกันเพื่อ reorder ได้

Optimization อาจเพิ่ม code size จน instruction cache แย่ลง หรือ unroll มากจนใช้ register เกินและเกิด spill การเปิด optimization สูงสุดจึงไม่รับประกันว่าจะดีที่สุดทุกโปรแกรม

19อ่าน Performance Counter ให้ฮาร์ดแวร์เล่าเรื่อง

เวลาอย่างเดียวบอกว่าโปรแกรมช้า แต่ไม่บอกว่าช้าเพราะอะไร Hardware counter ช่วยวัด cycles, instructions retired, branch miss, cache miss, stalled cycles และ memory bandwidth

20กรณีศึกษา: ผลรวมสะสมที่ขนานยากกว่าผลรวมธรรมดา

การ sum array ธรรมดาแบ่งช่วงให้หลาย accumulator แล้วรวมท้ายได้ แต่ prefix sum ต้องให้ผลตำแหน่ง i รวมค่าก่อนหน้าทั้งหมด ดูเหมือนเป็น dependency chain ยาว หากเปลี่ยน algorithm เป็น tree-based scan เราสามารถทำ upsweep และ downsweep เป็นรอบ ๆ เปิด parallelism โดยเพิ่มโครงสร้างการคำนวณ

ตัวอย่างนี้ชี้ว่าฮาร์ดแวร์ดึง ILP จากโปรแกรมได้เพียงขอบเขตหนึ่ง หาก dependency อยู่ใน algorithm จริง ต้องเปลี่ยน algorithm ไม่ใช่หวังให้ out-of-order execution แก้แทนทั้งหมด

21แล็บที่แนะนำ

Checklist เวลาโค้ดบน CPU ช้ากว่าที่คาด

การ optimize ควรเริ่มจาก bottleneck ที่มีหลักฐาน หาก branch miss ต่ำ การเขียน branchless code อาจเพิ่ม instruction โดยไม่ช่วย หาก memory bandwidth อิ่ม การ unroll เพิ่มก็เพียงทำให้หลายคำสั่งมารอ memory พร้อมกันมากขึ้น

จาก ILP ไปสู่ Thread-Level Parallelism

เมื่อ dependency และ instruction window จำกัดงานที่ core หนึ่งมองเห็น CPU ไม่สามารถดึง ILP เพิ่มได้ไม่สิ้นสุด การมีหลาย cores จึงเปิด instruction streams คนละสายให้ทำงานพร้อมกัน แต่แลกกับโจทย์ใหม่ ได้แก่การแบ่งข้อมูล cache coherence, synchronization และ load balance สิ่งที่ฮาร์ดแวร์เคยซ่อนให้ภายใน core จะเริ่มต้องปรากฏในโครงโปรแกรมมากขึ้น

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

ภายใน CPU หนึ่ง core มี parallelism หลายชั้น ทั้ง pipelining, superscalar issue, out-of-order execution, speculation, SIMD, SMT และ memory-level parallelism ฮาร์ดแวร์พยายามทำให้โปรแกรมแบบลำดับดูเหมือนทำทีละคำสั่ง ทั้งที่ภายในมีคำสั่งจำนวนมากกำลังเดินทางพร้อมกัน

แต่ฮาร์ดแวร์สร้าง parallelism จากอากาศไม่ได้ Dependency, branch ที่คาดยาก และ memory latency ยังเป็นเพดาน บทถัดไปจึงถอยออกมาจากวงจร CPU แล้วจัดหมวดว่า parallelism ในระดับ algorithm มีรูปแบบใดบ้าง เราจะได้เลือกว่าจะกระจายข้อมูล แยกหน้าที่ หรือต่อเป็น pipeline ก่อนตัดสินใจใช้เครื่องมือครับ