Explore

สรุป Energy-Aware Task Mapping and Scheduling for Reliable Embedded Computing Systems

1 Introduction

1. การเติบโตของ MPSoCs และปัญหาใหม่

ปัจจุบันแอปพลิเคชัน (โดยเฉพาะมัลติมีเดีย) ต้องการประสิทธิภาพสูงขึ้น จึงมีการรวมหน่วยประมวลผลหลายตัวไว้ในชิปเดียวเรียกว่า Multiprocessor Systems-on-Chip (MPSoC) ซึ่งสื่อสารกันผ่าน Network-on-Chip (NoC).

ระบบ MPSoC สมัยใหม่มักใช้ หน่วยประมวลผลที่หลากหลาย (เช่น GPP, DSP, ASIC ฯลฯ) เพื่อประหยัดพื้นที่และพลังงาน รวมถึงรองรับการปรับแรงดันไฟฟ้า-ความถี่ (DVFS) เพื่อช่วยลดการใช้พลังงาน.

2. ความท้าทายเรื่องความทนทานและความผิดพลาดของฮาร์ดแวร์

การลดขนาดทรานซิสเตอร์และการเพิ่มความถี่ ทำให้โอกาสเกิดข้อผิดพลาดทั้งชั่วคราวและถาวรเพิ่มขึ้นใน MPSoC

ถ้าฮาร์ดแวร์บางส่วนเสียหายถาวร (permanent fault) แอปพลิเคชันต้องจัดการให้ระบบยังคงทำงานได้ โดยอาจยอมรับ "การลดลงของประสิทธิภาพ" (degradation) ในบางระดับ

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

3. การจัดสรรงานและพลังงาน

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

หากแกนรับงานใหม่เพิ่มขึ้น อาจต้องปรับแรงดัน/ความถี่สูงขึ้นเพื่อให้ยังรักษาความเร็วการทำงาน (throughput) ตามที่ต้องการ นั่นทำให้ปัญหาการ "จัดสรรงาน-พลังงาน-ความทนทาน" เป็นหัวข้อวิจัยสำคัญ

4. ขอบเขตของงานวิจัยนี้

งานนี้เน้นแก้ปัญหา: จะกระจายงานแอปฯ ไปยังแกนต่างๆ ของ MPSoC อย่างไร ให้ใช้พลังงานน้อยที่สุด ขณะที่ยังมั่นใจว่าแอปฯ ทำงานเร็วพอ (throughput) ในทุกกรณีที่แกนเสียได้

สมมุติว่า MPSoC และโครงร่างฮาร์ดแวร์ (floorplan) กำหนดมาแล้ว งานวิจัยนี้เน้นข้อผิดพลาดชนิดถาวรเป็นหลัก

เป็นงานแรกที่พยายาม จัดสรรงานโดยคิดรวม throughput, พลังงานคำนวณ, พลังงานสื่อสาร สำหรับกรณีที่มีความผิดพลาดแบบ reactive fault tolerance ในระบบ heterogeneous MPSoC

5. จุดเด่น/นวัตกรรมของงานนี้

เสนอวิธี จัดสรรและกำหนดงาน โดยมองทั้งพลังงานคำนวณและพลังงานการสื่อสาร ระหว่างแกน โดยยังคง throughput ตามต้องการ

เสนอเทคนิคการ schedule เพื่อลด overhead ในการสร้างและจัดเก็บ schedule ที่ runtime

เสนอ heuristic ลดเวลาสำรวจ design space (การเลือกชุดการจัดสรรแบบต่างๆ)

เสนอการจัดสรรงานที่คำนึงถึง floorplan ของฮาร์ดแวร์

2. Related Work

1. งานวิจัยด้าน Energy Optimization

มีงานเด่นในเรื่องการจัดสรรงานเพื่อลดพลังงานบน MPSoC แบบ embedded เช่น:

Singh et al. และ Mandelli et al.: เน้นจัดสรรงานให้เหมาะกับการสื่อสาร ใช้ heuristic เพื่อประหยัดพลังงานการสื่อสาร แต่ ไม่ได้คำนึงถึงพลังงานจากการคำนวณ (computation energy).

Goh et al. และ Schranzhofer et al.: เสนอเทคนิคลดพลังงานโดยปรับค่าไฟ/ความถี่ (DVFS) แต่ไม่ได้คิดถึงการจัดวางแกน/โครงร่างฮาร์ดแวร์ (floorplanning) และการสื่อสารระหว่างงาน.

เทคนิค "slack budgeting" (Hu & Marculescu): กระจายเวลาว่างให้แต่ละงานเพื่อปรับความถี่ลง ลดพลังงาน แต่ไม่มี consideration เรื่อง throughput degradation

ข้อจำกัดร่วม: งานเหล่านี้ ไม่ได้รองรับกรณีแกนเสีย (fault) ทำให้ไม่เหมาะสำหรับการ optimize เรื่องพลังงานร่วมกับ fault tolerance

⁠

2. งานวิจัยด้าน Fault Tolerance

มีการใช้เทคนิค ฮาร์ดแวร์ redundancy มาตั้งแต่เดิม แต่เริ่มมีการใช้วิธี ซอฟต์แวร์ เช่น task migration เพื่อความคุ้มค่าในการจัดการ fault

มี 2 แนวทางหลัก:

Proactive: ป้องกันหรือชะลอการเกิด fault เช่น การจัดการใช้งานให้ไม่หนักเกินไป

Reactive: รับมือเมื่อเกิดแกนเสียแล้ว เช่น task migration, scheduling ใหม่

Reactive fault tolerance แบ่งเป็น 2 แบบ

Runtime: ตัดสินใจ migrate งานเมื่อเกิด fault จริง เช่น Al Faruque et al., Derin et al., Zhang et al. – มักใช้ algorithm ที่คอมพิวต์ง่าย แต่ไม่เสมอไปที่ throughput จะอยู่ในเกณฑ์ที่ต้องการ

Design-time: เตรียมแผนการ mapping/มอบหมายงานไว้ล่วงหน้า (static) สำหรับแต่ละกรณีแกนเสีย เช่น Yang & Orailoglu, Lee et al., Huang et al., Das & Kumar – ทำให้สามารถใช้ algorithm ที่ซับซ้อนใน design-time แลกกับ schedule storage overhead ที่มากขึ้น

งานเช่น Yang & Orailoglu: ใช้เทคนิค "band and band reconfiguration" แบ่งแกนเป็น band หากแกนเสียจะย้ายงานไป band ที่กำหนด ข้อจำกัดคือ throughput ไม่ได้รับประกัน

Huang et al.: ใช้ evolutionary algorithm scheduling slot แบบ reexecution เพื่อลด throughput degradation แต่เมื่อระบบต้องทน fault สูง schedule length จะยาวมาก

Lee et al.: offline mapping, virtual mapping เพื่อช่วย migration ให้ได้ throughput สูงสุด แต่ไม่ได้ optimize migration overhead ทำให้ migration cost เพิ่มขึ้น และ throughput ที่สูงกว่าเป้าหมายอาจเปลือง buffer

Das & Kumar: ลด migration overhead กับ throughput degradation สำหรับ streaming application แต่ไม่ได้ optimize เรื่อง scheduling ทำให้เกิด schedule overhead ใน runtime หรือ storage overhead ใน design-time

ข้อจำกัดร่วม: งานเหล่านี้มักไม่ optimize energy consumption รวมด้วย

⁠

3. งานวิจัยล่าสุดที่ optimize Energy & Fault Tolerance พร้อมกัน

Wei et al.: ใช้ ILP joint optimize energy กับเวลา (execution time) ที่รวม fault tolerance overhead (checkpointing) ไม่เหมาะกับ permanent faults เพราะไม่ได้แก้ปัญหา migration จริง

Huang & Xu: scheduling เพื่อลดพลังงานและยืดอายุ system แต่ไม่ได้ optimize migration overhead, resource management หรือ throughput degradation

Das et al.: minimize communication energy ใน migration แต่ไม่ได้ optimize computation energy และ schedule/mapping storage overhead

Highlight ที่เกี่ยวข้องกับเป้าหมายของ paper นี้:

งานของ Yang & Orailoglu, Huang et al., Lee et al., Das & Kumar มีประเด็นสำคัญเกี่ยวกับการจัดสรรงานและ migration เมื่อเกิด permanent fault ใน MPSoC

Singh et al., Mandelli et al., Schranzhofer et al. เด่นเรื่อง energy-aware mapping ซึ่งตรงกับโจทย์ของ paper นี้

อย่างไรก็ตาม ทุกงานมีจุดอ่อนคือ ยังไม่ได้ optimize ทุกด้าน (energy, fault, throughput) พร้อมกัน ทำให้ paper นี้มีพื้นที่ในการเสนอแนวทางใหม่ที่ optimize ทั้งหมดร่วมกัน

3 Introduction to Synchronous Dataflow Graphs (SDFGs)

1. SDFG คืออะไร?

Synchronous Dataflow Graphs (SDFGs) คือโมเดลกราฟที่นิยมใช้สำหรับออกแบบและวิเคราะห์แอปพลิเคชันประเภท DSP (Digital Signal Processing) และมัลติมีเดียบน MPSoC

ใน SDFG งานแต่ละชิ้น (task) จะเรียกว่า actor เป็น node ในกราฟ ส่วน edge คือ channel สำหรับส่งข้อมูลระหว่าง actors

Actor จะอ่านข้อมูลจาก input port แล้วประมวลผล และส่งผลลัพธ์ออกทาง output port โดยในแต่ละรอบ (firing) จะใช้และผลิตจำนวน token ที่เท่าเดิมเสมอ (เรียกว่า port rate)

2. วิธีการทำงานของ SDFG

Actor สามารถทำงาน (firing) เมื่อมี token ใน input ครบตามเงื่อนไข และ buffer/พื้นที่ใน output เพียงพอ

edge หรือ channel อาจมี initial tokens (token เริ่มต้น) เพื่อ modeling cyclic dependency และ buffer space

SDFGs สามารถวิเคราะห์ throughput, latency และ buffer requirements ได้ครบถ้วน

3. แนวคิดสำคัญและประโยชน์

SDFG ช่วยคำนวณว่าแอปฯ ทำงานเร็วแค่ไหน (throughput): คำนวณเป็น period คือเวลาที่ใช้ต่อหนึ่งรอบงานในระบบ

ในการวิเคราะห์ throughput จะใช้ repetition vector กำหนดว่าแต่ละ actor ทำงานกี่ครั้งต่อหนึ่งรอบ

สามารถจัดการ buffer ได้โดย modeling edge ที่วนกลับ (back edge) เพื่อกำหนดขนาด buffer ในระบบ

4. การ schedule ที่ใช้กับ SDFG

เทคนิคหลักสำหรับ scheduling SDFGs คือ self-timed execution: กำหนดลำดับและผู้รับผิดชอบงาน (mapping) ที่ดีไว้ล่วงหน้า จากนั้นให้แต่ละ actor firing ตามลำดับที่ออกแบบไว้โดยอาศัย worst-case execution time

การ fire จะเป็นของจริงตามลำดับที่กำหนด ใน runtime actor จะถูกดำเนินการตามลำดับนั้น (self-timed) ต่างจาก schedule แบบ static ตรงที่ self-timed รองรับความผันผวนของเวลาทำงานจริงแต่ละรอบได้ดีกว่า

5. คุณสมบัติและข้อดีของ self-timed scheduling

Self-timed schedule มักจะมี phase ชั่วคราว (transient) ก่อนเข้าสู่ phase ทำงานปกติ (steady-state)

Throughput จะได้จากค่าเฉลี่ยการ firing actor ในช่วง steady-state

ทำให้ระบบ robust และรองรับความเปลี่ยนแปลง runtime ได้ดี

เทคนิคนี้เหมาะกับ streaming application และใช้กับ DAG ได้ด้วย

⁠

ใจความสำคัญ

SDFG เป็นโมเดลกราฟที่เหมาะสำหรับงานที่มีการส่งข้อมูลต่อเนื่องและสัมพันธ์กันบนหลายแกนใน MPSoC

ช่วยให้ออกแบบ/วิเคราะห์การ mapping, scheduling, throughput และ buffer ได้ชัดเจน

Self-timed execution คือหัวใจของการ schedule SDFG ที่ทำให้ระบบมั่นใจได้ว่าทำงานต่อเนื่องแม้เกิด fault และ throughput ถูกควบคุมได้

⁠

4 Problem Formulation

4.1 Architecture Model

ระบบเป้าหมายคือ heterogeneous MPSoC มีหลายแกนประมวลผล (cores) เชื่อมต่อกันด้วยโครงข่าย (เช่น mesh)

แต่ละโซนบน chip อาจมี core ชนิดเหมือนกัน (เช่น DSP, GPP ฯลฯ) และ core แต่ละตัวอาจตั้ง ความถี่ ได้หลายระดับ

จุดสำคัญ: งานนี้พิจารณาตำแหน่ง core บนแผนผัง (floorplan-aware) เพื่อให้ mapping งานมี communication energy ต่ำที่สุด

หาก mapping ไม่พิจารณาตำแหน่ง อาจทำให้ข้อมูลข้ามหลาย hops สิ้นเปลืองพลังงาน

⁠

4.2 Mapping Representation

กำหนดชุดสัญลักษณ์สำหรับจัดสรรงาน:

จำนวน core (narc)

จำนวน actor (napp)

Mapping ของงาน (Mn) จะบอกว่า actor ใดไปอยู่ core ใด ใช้ความถี่เท่าไร

มีตัวแปรระบุเหตุการณ์ที่ core เสีย (fault scenario) เพื่อเตรียม mapping สำรอง

ทุก mapping ถูกบันทึกด้วย ID เฉพาะสำหรับอ้างอิงและสลับ mapping เวลาเกิด fault

⁠

4.3 Computation Energy Modeling of an Application

พลังงานคำนวณ (computation energy) ของระบบคิดจาก:

กำลังไฟฟ้าไดนามิก (dynamic power) ขึ้นกับ activity factor, ความถี่และแรงดันไฟ, ค่าประจุ ฯลฯ

เน้นลด dynamic power เป็นหลัก

การคำนวณพลังงานจะใช้แค่ steady-state phase เป็นหลัก (เนื่องจากทำงานนานกว่า transient phase)

“Computation energy” ใน paper นี้คือพลังงานที่ใช้ในช่วง steady-state ของการทำงานแต่ละครั้ง

⁠

4.4 Communication Energy Modeling of Applications

Communication energy คือพลังงานที่ใช้ส่งข้อมูลระหว่าง core ผ่าน NoC

ถ้าข้อมูลต้องข้ามหลาย hops (เช่นหลาย router หรือ switch) จะใช้พลังงานมากขึ้น

จุดสำคัญคือ mapping "ระหว่าง core" ต้องออกแบบให้ข้อมูลวิ่งผ่าน hops น้อยที่สุดเพื่อลด communication energy

พลังงานต่อบิตแบ่งเป็นส่วนที่ใช้ใน switch กับลิงก์ (สายสื่อสาร)

⁠

4.5 Migration Overhead Modeling of Application

Migration overhead คือพลังงานที่ต้องใช้ย้ายงานจาก core ที่เสียไป (เช่นย้าย state/data/code ไป core อื่น)

ปกติจะมีโมดูลช่วยย้ายงาน (TMM) ระดับระบบ ทำให้ย้ายได้รวดเร็วโดยไม่กระทบงานปกติ

พลังงานการ migration คิดจากขนาดข้อมูลของ actor ที่ถูกย้ายและระยะทาง (จำนวน hops)

ในงานวิจัยนี้ พลังงาน migration ถือว่าน้อยมากเมื่อเทียบกับ computation/communication energy จึงมักละเลยในผลทดลอง

แต่สำหรับระบบที่ต้องการ uptime สูง สามารถนำ migration overhead ไปคิดรวมได้

⁠

ใจความสำคัญ

ปัญหาที่ paper นี้แก้คือ: จะจัดสรรงานแต่ละตัวบน core หลากชนิดใน MPSoC อย่างไรให้ใช้พลังงานคำนวณและพลังงานสื่อสาร “รวมกันน้อยที่สุด” เมื่อมีเหตุการณ์ core เสีย และยังคงให้ throughput ตามเงื่อนไขที่แอปพลิเคชันต้องการ

ทุกส่วน (architecture, mapping, energy model) ถูกกำหนดให้รองรับกรณี core พังถาวร โดยพิจารณาทั้ง mapping สำรอง, พลังงานคำนวณ, พลังงานสื่อสาร และ migration overhead ในแต่ละเหตุการณ์

5 Design Methodology

การออกแบบวิธีจัดสรรงาน/mapping เพื่อให้ MPSoC ทนทานต่อ fault และ ใช้พลังงานต่ำ จะทำ “ล่วงหน้า” (design-time/offline) พร้อมเตรียม mapping สำรองสำหรับแต่ละกรณี fault ที่อาจเกิดขึ้น

เมื่อตรวจพบว่า core ใดเสีย system ก็จะสลับไปใช้ mapping ที่เตรียมไว้สำหรับ fault scenario นั้นทันที

⁠