Explore

สรุป Energy-aware Scheduling of Workflow Applications Towards Schedule Length Optimization in Heterogeneous Distributed Embedded Systems

1 Introduction

1. บทนำ (Introduction) กล่าวถึงอะไร?

บทความนี้กล่าวถึงปัญหา “การจัดตารางงาน” (scheduling) สำหรับระบบฝังตัว (embedded systems) ที่มีโปรเซสเซอร์หลากหลายชนิด (“heterogeneous distributed embedded systems”)

ระบบเหล่านี้ถูกนำไปใช้ในโลกจริง เช่น รถยนต์อัจฉริยะ เครือข่าย IoT เซนเซอร์ หุ่นยนต์ ฯลฯ ซึ่งมักทำงานกับแบตเตอรี่ที่มีพลังงานจำกัดมาก

2. ปัญหาหลักที่เน้นในบทนำ

ระบบแบบ embedded เหล่านี้ต้องรันงาน (workflow) ที่มีลำดับและ dependency ซับซ้อน (คิดแบบภาพรวมงานใหญ่ที่ต้องแบ่งย่อย-ต่อกันเป็น network หรือ workflow)

งานแต่ละงาน (task) ต้องรันบน processor ที่ต่างกันไป ซึ่งแต่ละตัวมีประสิทธิภาพและการใช้พลังงานต่างกัน

“ข้อจำกัดด้านพลังงาน” (energy constraint) ที่สำคัญ เช่น แบตเตอรี่มีจำกัด ถ้าใช้งานเกิน จะเกิด error หรือ shutdown

งานต้องเสร็จ “เร็วที่สุด” โดยไม่ใช้พลังงานเกินขอบเขต (optimize schedule length + energy aware)

3. ความท้าทายและการตั้งโจทย์

การแก้โจทย์นี้ยากมาก (NP-hard) เพราะต้องคิดพร้อมกันหลายมิติ: เวลาจบงาน ลำดับ dependency ความต่าง hardware ข้อจำกัดแบตฯ ฯลฯ

วิธีแบบ evolutionary (เช่น GA, PSO) แม้จะดี แต่อาจช้าเกินไปถ้า workflow ซับซ้อนหรือใหญ่มาก

จำเป็นต้องมีวิธี heuristic (สูตรลัดที่เร็ว+มีเหตุผล) ที่แก้ไขปัญหาได้ practical จริงในงานขนาดใหญ่

4. ทางแก้/เป้าหมายของ paper

Paper นี้เสนออัลกอริทึ่มใหม่ เป็นแบบ “three-stage list-based scheduling” เน้นประหยัดพลังงานและลดเวลาเสร็จ workflow

(1) จัดลำดับความสำคัญแต่ละ task (task prioritization)

(2) แจกแจงโควต้าพลังงานแต่ละงานแบบยุติธรรม

(3) กระจายงานเลือก processor+frequency ที่ดีที่สุดและไม่เกิน power limit

วิธีนี้ทดลองกับทั้ง workflow จำลองและ workflow จริง (เช่น งาน data science) แล้วเปรียบเทียบกับอัลกอริทึ่มอื่น

5. จุดที่ “น่าสนใจ” ใน introduction

Paper นี้ไม่ใช่แค่ optimize เวลาจบงาน แต่ optimize พร้อมข้อจำกัดพลังงานอย่างจริงจัง (energy-aware scheduling)

โฟกัสประเด็น “real-world” ที่อัลกอริทึ่มเดิมทำไม่ได้ เช่น งานขนาดใหญ่ พลังงาน strict และ processors ต่างชนิด

จุดเด่นคือ heuristic ของ paper จัดลำดับ task+energy ได้ฉลาด ทำให้ทั้งประหยัดแบตฯ และใช้งานคุ้มเวลา

2 Related Work

1. เนื้อหาโดยรวมของ Section นี้คืออะไร?

Section นี้รีวิวงานวิจัยที่เกี่ยวข้องกับ “การจัดตารางงานประหยัดพลังงานในระบบ distributed embedded ที่มี processor หลายชนิด”

ผู้วิจัยแบ่งกลุ่มงานเด่น ๆ ออกเป็น 4 ประเภทใหญ่ พร้อมเปรียบเทียบข้อดี-ข้อเสียของแต่ละประเภท

⁠

2. ประเภท และจุดน่าสนใจของงานแต่ละกลุ่ม

กลุ่ม 1: DVFS-enabled energy-efficient scheduling

DVFS (Dynamic Voltage and Frequency Scaling) ช่วยปรับความถี่-แรงดันของ processor ตาม workload เพื่อประหยัดพลังงาน

เช่น HEFT, EHEFT ฯลฯ ใช้แนวคิด reclaim slack time/workload ผ่าน DVFS

ข้อเสีย: ต้องมี hardware support เฉพาะ, บางอัลกอริทึ่ม reclaim slack ได้ไม่สมบูรณ์ในระบบ multi-processor ที่ซับซ้อน

กลุ่ม 2: Non-DVFS-based scheduling

สำหรับ hardware ที่ไม่รองรับ DVFS ต้องวางเวลา/energy แยกให้ processor แต่ละตัว

มีวิธีเช่น assign deadline partitioning หรือ energy budget ให้แต่ละงาน

แต่ระบบจะประหยัดพลังงานสู้แบบ DVFS ไม่ได้, และซับซ้อนถ้า processor ต่างกันมาก

กลุ่ม 3: Multi-objective optimization-based scheduling

บางงาน optimize ทั้งเวลา (makespan) และพลังงานพร้อมกัน เช่นใช้ Genetic Algorithm (GA), Pareto approaches

เช่น MOHEFT ใช้ชุดคำตอบ Pareto เพื่อ trade-off ระหว่าง schedule length กับ energy

ข้อดี: เลือกคำตอบคล่องตัวหลายแบบ, cover demand/workload ที่หลากหลาย

ข้อเสีย: computational cost สูง (ใช้เวลามากถ้างานใหญ่หรือ workflow ซับซ้อน)

กลุ่ม 4: Energy pre-assignment policy-based scheduling

เน้นการแจกแจง quota พลังงานให้ task แต่ละตัวก่อน scheduling จริง

มีทั้งแบบ pessimistic, average, weight-based, ratio-based ฯลฯ

ข้อจำกัด: วิธีเก่าส่วนมากไม่คำนึงถึงสมดุลระหว่างงานสำคัญ/งานทั่วไป หรือ ignore เรื่องความต่าง processor

งานวิจัยนี้จึงเสนอวิธีแจกแจง energy ล่วงหน้าโดย ranking processor “favourite” และ level priority ของแต่ละงาน เพื่อแก้ข้อเสีย

⁠

3. ข้อสรุปของผู้วิจัย

งานเดิม ๆ หลายชิ้นโฟกัสเรื่อง “เวลา” หรือ “พลังงาน” เดี่ยว ๆ แต่ไม่รวม constraints หลายตัวพร้อมกัน

งานส่วนมากใช้ metaheuristic ซึ่งดีแต่ช้า, พลังงานอาจเกินข้อจำกัดจริง, และใช้ไม่ได้กับ workflow ขนาดใหญ่

paper นี้นำเสนอ “heuristic ที่ฉลาดขึ้น” ซึ่งคิดพร้อมกันทั้งเวลา/พลังงาน และสมดุลงานสำคัญ รวมถึงปรับแต่งกับ hardware ได้ตรงกับ embedded systems จริง

3 Models and problem formulation

3.1 Workflow model

อธิบายว่าการจัดตารางงานสำหรับระบบ distributed embedded ต้องดู “workflow” ที่ประกอบด้วยงานย่อย (tasks) หลายตัว ที่มีลำดับ-ความสัมพันธ์กัน (dependency)

ใช้โมเดล DAG (กราฟแบบมีทิศและไม่มีวนกลับ) เพื่อแทน structure และ flow ข้อมูล งานต้น (entry task) งานสุดท้าย (exit task) และการส่งข้อมูลระหว่างงาน

processor ในระบบมีหลายแบบ (heterogeneous) งานแต่ละตัวอาจรันบน processor ที่ไม่เหมือนกัน ซึ่งแต่ละตัวมีความเร็วและ bandwidth ต่างกัน

เวลาส่งข้อมูลระหว่างงานขึ้นกับว่าอยู่ processor เดียวกันหรือไม่ ถ้าคนละ processor จะเสียเวลาเพิ่มเติม

3.2 Energy consumption model

อธิบายว่าในระบบฝังตัวแบบ distributed ข้อจำกัดสำคัญคือแบตเตอรี่หรือพลังงานในแต่ละ processor

โมเดลนี้แยกพลังงานออกเป็น static (กินตลอดเวลาทั้ง idle/active) และ dynamic (เพิ่มตาม workload และความถี่ที่ใช้งาน)

processor แต่ละตัวปรับความถี่ได้ (DVFS) ส่งผลต่อทั้งเวลารันงานและพลังงานที่ใช้

งานแต่ละตัวเวลาถูกจัดสรรไป processor ตัวไหนและใช้ความถี่เท่าไหร่ จะกินพลังงานต่างกัน

มีการกำหนด “minimum” กับ “maximum” energy สำหรับแต่ละงาน (แล้วแต่ processor/frequency ที่เลือก)

รวมพลังงานขั้นต่ำและสูงสุดทั้งหมดใน workflow เพื่อใช้เป็นกรอบในการจัดตารางงานไม่ให้เกิน limit ที่ตั้งไว้

3.3 Problem formulation

รวบรวมข้อจำกัดสำคัญที่ต้องตามในการจัดตารางงาน:

งานแต่ละตัวต้องถูก assign ให้ processor เดียว ไม่ซ้ำซ้อน

ต้องตาม dependency ของงาน (ถ้างานหนึ่งต้องต่ออีกงาน งานแรกต้องเสร็จก่อน)

งานรันต้องไม่ถูกแทรกคาบเกี่ยว (non-preemptive)

พลังงานรวมที่ workflow ใช้ทั้งหมดต้องไม่เกินที่กำหนด

ข้อจำกัดเหล่านี้ถูกนำมาใช้เป็นเงื่อนไขร่วมในโมเดลคำนวณหาตารางงานที่เหมาะสม

วัตถุประสงค์หลักคือหาแผนที่ “ทั้ง workflow เสร็จเร็วที่สุด” (schedule length น้อยสุด) แต่ยังไม่ละเมิด energy limit หรือข้อจำกัดอื่น ๆ

⁠

จุดน่าสนใจใน section นี้

Paper วางโมเดลแบบ “ครบมิติ” สำหรับงาน workflow จริงใน distributed embedded systems โดยคิดทั้งเรื่อง dependency ความต่าง hardware และข้อจำกัดพลังงาน

ทำให้สามารถนำไปต่อยอดวางแผนจัดงานแบบอัตโนมัติได้กับ hardware จริง แม้จะ complex มาก

เป็นพื้นฐานให้ heuristic อัลกอริทึ่มใน section ถัดไปใช้งานได้ตรงตามโจทย์ของอุตสาหกรรม

4 The proposed list-based approach

ภาพรวม Section 4

เป็นหัวใจของ paper ที่นำเสนอเทคนิคใหม่ในการจัดตารางงาน (scheduling) แบบ energy-aware สำหรับ workflow บนระบบที่ใช้ processor หลายชนิด

เทคนิคจะทำงานทีละ 3 ขั้น (Stage) คือ: จัดลำดับงาน/ความสำคัญ, กระจายพลังงานล่วงหน้า, และจัดงานลง processor+frequency ที่เหมาะสม

⁠

4.1 Task prioritization stage

ในขั้นแรกนี้จะ “จัดลำดับความสำคัญ” (priority) ของแต่ละงาน เพื่อช่วยให้การเลือกงานไปลง processor มีประสิทธิภาพสูงสุด

พิจารณา 2 ปัจจัยหลัก:

งานที่สำคัญในการ progress ทั้ง workflow (ดูว่าเส้นทางยาวสุดใน DAG คือสายไหน)

งานไหนรันแล้วใช้งาน processor/ฟีเจอร์ที่มั่นคงหรือแตกต่างมาก (ดูความเสถียรของเวลารันแต่ละ processor)

ใช้ข้อมูลพิเศษดู “เส้นทางงานยาวสุด” จาก entry หรือจากงานไป exit เพื่อประเมินว่าถ้าชะลอจะกระทบ workflow มากแค่ไหน

เลือกจัดลิสต์งานตามคะแนนสำคัญ (งานไหนเสร็จช้าทั้งระบบจะพัง), งานที่เป็น bottleneck จะถูก prioritize ก่อน

⁠

4.2 Energy pre-assignment stage

เมื่อได้ลิสต์งานแล้ว จะ “กระจายโควต้าพลังงาน” ให้แต่ละงานล่วงหน้า ก่อนจัดตารางงานจริง

การแจกพลังงาน “ไม่ใช่เท่า ๆ กัน” แต่ดูรอบด้าน:

ระดับความสำคัญของงาน

งานที่เสี่ยงเป็น bottleneck หรือใช้พลังงานมากจริงๆ จะได้โควต้ามากกว่า

ใช้ประวัติการใช้งาน processor/งานจริง เพื่อแบ่งส่วน slack (พลังงานเหลือ) เช่น งานที่ critical กิน energy ได้เยอะกว่าเพื่อความปลอดภัย

ทำให้แต่ละงาน “มีสิทธิ์ใช้พลังงาน” ตามน้ำหนักที่ควรเป็น ไม่ใช่แบ่งเฉลี่ยแบบโง่ ๆ

⁠

4.3 Task allocation stage

ขั้นสุดท้าย: เอาลิสต์งานที่จัดลำดับมา ลง processor จริง โดยเลือก processor และความถี่ที่เหมาะสุดในแต่ละกรณี

พิจารณาให้ “งานเสร็จเร็วที่สุด” (โดยดูว่า processor นี้ว่างเมื่อไหร่, ส่งข้อมูลข้าม processor จะ delay ไหม)

processor ที่มีความสามารถรันงานเร็วและใช้พลังงานตามโควต้าจะถูกเลือกก่อน

ทุกการตัดสินใจจะต้องไม่ให้พลังงาน collapse เกิน limit ที่ตั้งไว้

ขั้นตอนนี้ทำแบบวนลูป: เอางานลำดับต้นสุดในลิสต์มาวางลง processor, อัพเดตเวลารันจริง, repeat ไปจนครบทุกงาน

⁠

จุดเด่น & น่าสนใจ

การจัดลำดับงานแบบนี้ “ฉลาดกว่า” เพราะตัดสินแบบรวมทุกรายละเอียด ไม่ใช่มองแค่ deadline หรือ estimation ง่ายๆ

การกระจายพลังงานแบบ stretch ทำให้ workflow ทั้งระบบ “มั่นคง” ไม่ติดคอขวดเพราะบางงานไม่ได้พลังงานพอ

การเลือก processor/ความถี่ไม่ใช่แค่ fastest แต่คำนึงถึงเสถียรภาพและข้อจำกัดจริงทั้งเวลาและแบต

Framework นี้เหมาะกับระบบ embedded ที่ต้องการ reliable scheduling & energy saving แบบที่ metaheuristic เดิม ๆ ทำไม่ค่อยไหว

⁠

สรุปสั้นสุด: Section 4 นำเสนอวิธีการใหม่ที่ “คิดรอบด้าน” เรื่องการจัดตารางงานแบบประหยัดพลังงาน ด้วยการจัดลำดับงาน (คิดเส้นทาง impact workflow), แจกโควต้าพลังงานฉลาด ๆ, แล้ววางงานลง processor แบบ optimize ทั้งเวลาและ energy constraint เป็น step-by-step ที่ practical ใช้กับระบบจริงได้ทันที

5 Experimental results and discussion

5.1 Performance metrics

ผู้วิจัยกำหนด “ตัวชี้วัดผลลัพธ์” 4 อย่าง เพื่อประเมินทุกอัลกอริทึ่ม:

Schedule Length (SL): เวลาที่ workflow เสร็จงานชิ้นสุดท้าย (อยากได้ต่ำสุด)

Energy Consumption (EC): พลังงานรวมที่ใช้ ต้องไม่เกินข้อจำกัด (limit)

Deviation Ratio: สัดส่วนความคลาดเคลื่อน schedule length ของวิธีนั้นเทียบ optimal/เป้าหมาย (น้อยคือดี)

Normalized SL: เทียบผล SL แบบเปอร์เซ็นต์ สำหรับ workflow ขนาดต่างกัน

⁠

5.2 Experimental Results for Randomly Generated Workflows

วิธีการ: สุ่มสร้าง workflow ขึ้นมาจำนวนมาก ทดสอบกับอัลกอริทึ่มต่างๆ ได้แก่ ESMM (วิธีที่เสนอ), MSLECC, ESECC, ISAECC, TSSA, HEFT, REF, NLMIP

เป้าหมาย: เปรียบเทียบว่าวิธีใด รันงานเสร็จไว (SL ต่ำ), ใช้พลังงานเหมาะสม, ไม่เกินพลังงานที่กำหนด และ deviation ต่ำ

ผลลัพธ์เด่น:

HEFT: SL ต่ำสุด (เร็วสุด) แต่ใช้พลังงานเกิน limit (จึงใช้งานจริงไม่ได้)

ESMM: SL ต่ำเกือบเท่า HEFT (แปลว่าเร็วมาก) แต่ “พลังงานไม่เกิน limit” ทุกครั้ง (ปลอดภัย/feasible)

MSLECC, ESECC, ISAECC, TSSA: ให้ผล SL นานกว่า ESMM, แม้จะอยู่ในกรอบข้อจำกัดทั้งหมด

REF/NLMIP (exact optimal): ได้ผลลัพธ์ดีที่สุดแต่ช้ากว่าและใช้เวลาแก้โจทย์นาน (ไม่เหมาะกับงานจริงมาก)

Deviation: ESMM ลด deviation ได้เฉลี่ย ~7.6% และ SL เฉลี่ยดีกว่า baseline ~16.7%

⁠

5.3 Experimental Results for Real-Life Workflows

วิธีการ: ทดลองกับ workflow จริง เช่น workflow วิทยาการข้อมูล, งานประมวลผล ฯลฯ

เป้าหมาย: ดูว่าวิธี ESMM กับคู่แข่งใช้ได้กับโจทย์จริงไหม และควบคุมพลังงาน+เวลาทั้งระบบได้หรือไม่

ผลลัพธ์เด่น:

ESMM: ยังทำได้ดี รันงานเสร็จเร็วในกรอบข้อจำกัดพลังงาน ใช้งานได้จริงบน workflow จากอุตสาหกรรม

คู่แข่งขัน: วิธีแบบอื่นบางตัว (เช่น HEFT) SL จะเร็วกว่าในบางสถานการณ์ แต่ใช้พลังงานเกิน limit (เสี่ยงแบตหมดก่อนจบงาน)

ภาพรวม: ESMM ดีกว่าชัดเจนในเชิง balance ทั้ง speed กับ energy และสามารถรองรับงานจริง บน embedded hardware ที่ต้องการ reliability

⁠

สรุปเนื้อหา-ผลการทดลองที่เข้าใจง่าย

ทีมงานรันอัลกอริทึ่มกับ workflow ทั้งแบบสุ่มและงานจริง วัด 4 metrics สำคัญ

ESMM ที่เสนอ “ดีกว่าทุกตัวในแง่ใช้งานจริง” ทั้งเวลาเสร็จ ระบบไม่ล่มเพราะแบตหมด และ deviation ต่ำ

Metaheuristic/Optimal แบบเดิมใช้เวลามาก, บางตัวเร็วแต่กินไฟเกิน limit

วิธีการของ paper คือ “ตรงจุดกับ embedded ยุคใหม่” เพราะ optimize ทั้งเวลาและพลังงานจริง มีความ practical สำหรับงานขนาดใหญ่และ workflow ซับซ้อน

6 Conclusions and future work

สาระสำคัญของ Conclusions:

Paper สรุปว่า...

วิธีการ “three-stage list-based scheduling” ที่เสนอในงานนี้ สามารถแก้ปัญหาการจัดตารางงานแบบประหยัดพลังงาน (energy-aware scheduling) สำหรับระบบฝังตัวที่มี processor หลายชนิดและข้อจำกัดแบตเตอรี่

วิธีนี้ช่วยลดเวลารวม workflow (schedule length) ได้ดีมาก และใช้พลังงานอยู่ในกรอบ limit เสมอ

ได้ผลลัพธ์ใกล้เคียงแบบ optimal solution (NLMIP) แต่คำนวณได้เร็วกว่าและเหมาะกับ “งานขนาดใหญ่จริง”

ข้อดีและจุดเด่น

Model ที่นำเสนอคิดทั้ง 1) ลำดับ dependency งาน, 2) ความหลากหลายของ processor, 3) ข้อจำกัดพลังงาน

สเตจ energy pre-assignment ช่วยกระจายสิทธิ์ใช้พลังงานแต่ละงานอย่างแฟร์ ไม่ให้ bottleneck task ขาด power

จัดอันดับความสำคัญงานแบบใช้ข้อมูลจริง ไม่ใช่ตีค่าประมาณส่งเดชแบบ heuristic ทั่วไป

เหมาะกับงาน embedded system ที่ใช้งานจริง เช่น IoT, data center ฝังตัว, wireless sensor networks

สรุปผลการทดลอง

รันทั้ง workflow จำลองและงานจริง เห็นว่า solution นี้เร็วกว่า metaheuristic แบบ GA/PSO หลายเท่า ในขณะที่ประสิทธิภาพใกล้เคียง optimal

ผลลัพธ์เสถียรและปลอดภัยกับ embedded ที่ห้ามเกินแบตเตอรี่

สามารถต่อยอดใช้กับงานขนาดใหญ่หลากหลาย domain ได้ทันที

แนวทางงานวิจัยในอนาคต (Future Work):

ผู้เขียนเสนอว่าจะต่อยอดวิธีนี้ไปปรับใช้กับงานที่มี “ข้อจำกัดเพิ่มเติม” เช่น real-time deadline, reliability constraint

อาจพัฒนาให้รองรับ hardware ที่แตกต่างกันมากขึ้น และปรับแต่งให้เป็น adaptive scheduling ในระบบที่เปลี่ยนแปลง dynamic (เช่น multi-hop IoT, edge computing)

อาจนำ model นี้ไปปรับใช้กับ framework cloud/distributed system ที่ modern hardware mix มากกว่าเดิม

⁠

สรุปเข้าใจง่าย: ส่วนนี้คือการยืนยันว่า model และอัลกอริทึ่มของ paper สามารถแก้ปัญหา scheduling บน embedded systems ได้ดีจริง ทั้งลดเวลา workflow และใช้พลังงานไม่เกิน มีจุดเด่นเรื่องการกระจายพลังงาน ยุติธรรมและเหมาะสมกับงานจริง ถัดไปจะพัฒนาต่อยอดเพื่อรองรับข้อจำกัดและสถานการณ์ซับซ้อนยิ่งขึ้นในยุค distributed/IoT