Explore

OSเนื้อหาสำหรับ Presentation

Title: Architecture-aware, Constraint-first, Energy-smart Scheduling

⁠

เนื้อหาโอ⁠

⁠

The Core Problem

การจัดตารางงาน (Scheduling) บน “ระบบฝังตัวแบบกระจาย” (Heterogeneous Distributed Embedded Systems)

โดยแต่ลตัวจะมีลักษณจำเฉพาะดังนี้

Heterogeneous: ระบบนี้มีหน่วยประมวลผล(Core) หลายตัว และแต่ละตัวอาจไม่เหมือนกัน (เช่น บางตัวแรงแต่กินไฟ บางตัวประหยัดไฟแต่ช้า)

DVFS(Dynamic Voltage and Frequency Scaling): แต่ละ Core สามารถปรับความเร็ว(ความถี่) และแรงดันไฟได้ ยิ่งวิ่งเร็ว ก็ยิ่งกินพลังงานมาก

NoC (Network-on-Chip): Core ต่างๆ สื่อสารกันผ่านเครือข่ายบนชิป การส่งข้อมูลข้าม Core ที่อยู่ไกลกัน (มีหลาย "hop" หรือหลายจุดพัก) จะยิ่งใช้พลังงานสื่อสารสูงขึ้น

ปัญหาคือ: เราจะ "จัดสรร" (Mapping) งานไหนไปลง Core ไหน และ "จัดลำดับ" (Scheduling) ให้ทำงานเมื่อไหร่ (ด้วยความถี่เท่าไหร่) เพื่อให้บรรลุเป้าหมาย อย่างที่มักจะขัดแย้งกัน:

ประหยัดพลังงาน (Energy Consumption)

รักษาคุณภาพบริการ (QoS) หรือจำตามข้อจำกัด

1. Architecture-aware

นี่คือรากฐานที่สำคัญที่สุด แนวคิดคือ "อย่าจัดตารางงานแบบสุ่มสี่สุ่มห้า" แต่ต้องเข้าใจ "แผนผัง" (Floorplan) ของฮาร์ดแวร์จริง

ทำไมสำคัญ: พลังงานที่ใช้ในการ "สื่อสาร" (Communication Energy) อาจสูงมาก ถ้านำงาน 2 งานที่ต้องคุยกันบ่อยๆ ไปวางไว้คนละมุมของชิป (เช่น Core 0 กับ Core 8) ข้อมูลต้องวิ่งผ่าน NoC หลาย hop ทำให้สิ้นเปลืองพลังงานมหาศาล

หลักการ: ตอนที่จัดสรรงาน (Mapping) ต้องพยายามวางงานที่สื่อสารกันหนักๆ ให้อยู่ "ใกล้กัน" บน NoC เพื่อลดจำนวน hop และลดพลังงานสื่อสาร

2. Constraint-first

นี่คือจุดที่งานวิจัย 2 ฉบับถูกนำมาใช้ โดยแบ่ง "โลก" ออกเป็น 2 แบบ ตามข้อจำกัดที่สำคัญที่สุด

โลกที่ 1: "ห้ามประสิทธิภาพตก" (Throughput-first) → ใช้วิธี TConEMin (2014)

โจทย์: ไม่ว่าอะไรจะเกิดขึ้น แม้ว่า Core จะพัง (Fault-tolerant) ระบบต้องยังทำงานได้เร็วตามเป้า (รักษา Throughput)

ข้อจำกัด (Constraint): Throughput (ประสิทธิภาพ)

เป้าหมาย (Optimize): ใช้ พลังงานรวม (ทั้งคำนวณและสื่อสาร) ให้น้อยที่สุด

กลไกของ TConEMin:

Design-time (ตอนออกแบบ): เราจะคำนวณล่วงหน้าเลยว่า ถ้า Core 1 พัง, ถ้า Core 2 พัง, หรือถ้า Core 1 กับ 3 พัง (ฯลฯ) แผนการจัดสรรงาน (Mapping) ที่ดีที่สุด (ที่ยังรักษา Throughput ได้ และประหยัดพลังงานที่สุด) คืออะไร แล้วบันทึกแผนเหล่านี้เก็บไว้

Run-time (ตอนทำงานจริง): ถ้ามี Core พังจริง ระบบจะไปดึงแผนที่เตรียมไว้สำหรับกรณีนั้นๆ ออกมาใช้ แล้วย้ายงาน (Task Migration) ทันที

Heuristic (วิธีอันชาญฉลาด): ตอนที่ค่อยๆ ปรับแผนเพื่อลดพลังงาน (ในขั้นตอน Design-time) มันจะใช้เทคนิคที่เรียกว่า "Gradient move" อการลองย้ายงาน/เปลี่ยนความถี่ แล้วดูว่า "คุ้มไหม" โดยวัดจากค่า G = {E_{old}-E_{new}/{T_{new}-T_{old} (คือเลือกการย้ายที่ "ลดพลังงานได้เยอะ แต่กระทบเวลาน้อยที่สุด" ก่อน) (สูตรจาก Algo 3)

หัวใจของ TConEMin (Self-timed scheduling):

Self-timed scheduling: ปกติการจัดตารางงานต้องเก็บ "เวลาเป๊ะๆ" (เช่น Task A เริ่มที่ 5ms, Task B เริ่มที่ 10ms) ซึ่งเปลืองที่เก็บและวุ่นวายมาก

วิธีนี้บอกว่า "ไม่ต้องเก็บเวลาเป๊ะ" ให้เก็บแค่ "ลำดับ" (Order) (เช่น บน Core 1 ให้ทำ Task A → C → B) เมื่อ A ทำเสร็จ ก็แค่ส่งสัญญาณบอก C ให้เริ่มต่อ

ผลลัพธ์: งานวิจัยนี้พบว่าวิธีนี้ช่วย ลดเวลาสร้างตารางตอน Run-time ลง 95% และลดพื้นที่เก็บตารางลง 92% ทำให้ใช้งานได้จริง

โลกที่ 2: "ห้ามใช้พลังงานเกินงบ" (Energy-budget-first) → ใช้วิธี ESMM (2025)

โจทย์: ระบบนี้ (เช่น อุปกรณ์ที่ใช้แบตเตอรี่) มี "งบพลังงาน" (Energy Budget) ที่จำกัดมากสำหรับงานทั้งชุดนี้

ข้อจำกัด (Constraint): พลังงานรวม (Total Energy)

เป้าหมาย (Optimize): ทำงานทั้งหมดให้ เสร็จเร็วที่สุด (Minimize Schedule Length หรือ Makespan)

กลไก 3 ขั้นตอนของ ESMM (List-based):

Design-time (ตอนออกแบบ): เราจะคำนวณล่วงหน้าเลย6ว่า ถ้า Core 1 พัง, ถ้า Core 2 พัง, หรือถ้า Core 1 กับ 3 พัง (ฯลฯ) แผนการจัดสรรงาน(Mapping)ที่ดีที่สุด (ที่ยังรักษา Throughput ได้ และประหยัดพลังงานที่สุด) คืออะไร แล้วบันทึกแผนเหล่านี้เก็บไว้

แบ่งงบพลังงาน (Energy Pre-assignment): นี่คือขั้นตอนสำคัญที่สุด คือการ "ซอยงบ" พลังงานก้อนใหญ่ ให้เป็นงบย่อยๆ สำหรับแต่ละ Task วิธีนี้จะแบ่งงบอย่างยุติธรรม (Fair) ไม่เหมือนวิธีเก่าๆ ที่อาจลำเอียงให้ Task แรกๆ ใช้พลังงานจนหมด จน Task หลังๆ ไม่มีพลังงานเหลือ ต้องวิ่งช้าๆ

เลือกโปรเซสเซอร์และความถี่ (Allocation): เมื่อถึงคิว Task ไหน ก็ดูว่ามี Core + ความถี่ (P-f pair) ไหนบ้าง ที่ทำให้ Task นี้เสร็จเร็วที่สุด (EFT - Earliest Finish Time) โดยที่ใช้พลังงานไม่เกินงบย่อยที่แบ่งไว้ให้

ผลลัพธ์ของ ESMM: เมื่อเทียบกับวิธีมาตรฐานอื่นๆ (เช่น HEFT)

HEFT: เป็นวิธีที่นิยมมาก มักจะทำให้งานเสร็จเร็ว (Schedule Length สั้น) แต่ "ไม่สนใจงบพลังงาน" และมักจะ "กินพลังงานเกินงบ" (Infeasible)

ESMM: สร้างตารางงานที่ "สั้น" (อาจไม่สั้นเท่า HEFT) แต่ "อยู่ในงบพลังงานเสมอ" (Feasible) ซึ่งในโลกความจริง "การอยู่ในงบ" สำคัญกว่า

3. Energy-smart

นี่คือการสรุปว่า "ความฉลาด" ของทั้งสองงานคืออะไร:

TConEMin: ฉลาดโดยการใช้ "Gradient move" เพื่อหาจุดที่คุ้มค่าที่สุดในการลดพลังงาน หลังจากที่มั่นใจแล้วว่า Throughput ผ่านแน่ๆ

ESMM: ฉลาดโดยการ "แบ่งงบพลังงานย่อย" (Pre-assignment) ซึ่งเป็นกุญแจที่ทำให้มั่นใจว่า "ไม่ทะลุงบ" แล้วค่อยไปหาวิธีที่เร็วที่สุดภายใต้งบนั้น

Conclusion

โครงสไลด์ที่แนะนำ

Title: Architecture-aware, Constraint-first, Energy-smart Scheduling

Motivation: ทำไมต้องคำนึงทั้งสถาปัตย์/ข้อจำกัด/พลังงาน

Problem model: DAG/SDF, Heterogeneous HW, NoC/Comm energy

Architecture-aware 101: ทำไม “ระยะทาง/ลิงก์” ทำให้พลังสื่อสารพุ่ง

Constraint-first แยก 2 โลก: Throughput-first vs Energy-budget-first

TConEMin—Design-time→Run-time flow (fault scenarios, encode/decode)

TConEMin—Heuristics/Gradient & Self-timed (ทำไมลด 95%/92%)

TConEMin—ผลลัพธ์ภาพรวม (22%, 30%, ฯลฯ)

ESMM—สามขั้นตอน (prioritize, pre-assign, pick P×f)

ESMM—เทียบวิธีดัง/ผลลัพธ์ (NSL −16.7%, ADR −7.6%, HEFT เกินงบ)

Unified playbook (จะเลือกแนวไหนในโปรเจ็กต์จริง)

Scalability & Practical tips (fault explosion → ใช้ heuristic; self-timed)

Implementation checklist

Summary / Takeaways

Want to print your doc?
This is not the way.

Try clicking the ··· in the right corner or using a keyboard shortcut (

CtrlP

) instead.