Abstract
Traditional offline scheduling for Multi-Processor Systems-on-Chip (MPSoCs) often relies on pessimistic worst-case execution times, leading to significant energy waste. This paper bridges the gap between theoretical scheduling bounds and practical implementation by evaluating algorithms designed for runtime energy optimization. The study focuses on Directed Acyclic Graphs (DAGs) and utilizes Dynamic Voltage and Frequency Scaling (DVFS) to minimize energy consumption. Results indicate that specialized solvers for Series-Parallel Graphs and approximation algorithms can provide near-optimal energy efficiency within the strict timing constraints of real-time execution.
1. Introduction
In embedded systems design, static scheduling is a common but often inefficient practice. Because offline schedules must account for worst-case execution times (WCET), processors frequently remain idle or run at higher-than-necessary frequencies when tasks complete early. To address this, runtime scheduling leverages actual execution data to adjust processor speeds dynamically. However, the computational overhead of these optimizations must be minimal; if the time spent calculating an optimal schedule exceeds the energy saved, the approach becomes counterproductive. This research investigates whether "theory-sound" algorithms can operate within the 1–10ms window required for practical runtime application.
2. Problem Definition and Taxonomy
The researchers model applications as Directed Acyclic Graphs (DAGs), where nodes represent tasks and edges represent dependencies. Energy optimization is achieved through Dynamic Voltage and Frequency Scaling (DVFS), which slows down processors during periods of "slack" to reduce power consumption.
The problem is categorized into two primary domains:
- SpeedScaling: The mapping of tasks to specific processor cores is predetermined. The algorithm's role is solely to determine the optimal execution speed for each task.
- Speeds & Scheduling: The algorithm must simultaneously decide task-to-core mapping and the corresponding execution speeds.
Furthermore, the study distinguishes between Continuous speeds (a theoretical ideal where any frequency is possible) and Discrete speeds (reflecting real-world hardware with fixed frequency steps).
3. Methodology and Algorithms
The authors evaluated several algorithmic approaches to determine their suitability for runtime use:
- CVX-speed: A convex programming approach used to find optimal solutions for continuous speed scaling.
- SPG-speed: A specialized, linear-time algorithm designed for Series-Parallel Graphs (SPGs). Since many real-world applications exhibit SPG structures, this algorithm offers a high-efficiency alternative to general solvers.
- ILP-D-speed/sched: An Integer Linear Programming (ILP) approach for optimal discrete speed scaling. While mathematically precise, ILP is traditionally viewed as too slow for runtime use.
- APX-D-speed/sched: Approximation algorithms designed to provide results within a guaranteed factor of the optimum while maintaining low computational complexity.
4. Experimental Evaluation
The algorithms were tested using two distinct datasets:
- E3S (Embedded System Synthesis Benchmarks Suite): Small-scale, realistic graphs (approx. 10 tasks) representing typical embedded workloads.
- GENOME (Pegasus library): Large-scale synthetic graphs (50 to 1,000 tasks) used to evaluate the scalability of the algorithms.
Simulations were conducted on a homogeneous MPSoC environment featuring 20 discrete speed levels.
5. Key Findings
5.1 Computational Efficiency
The specialized SPG-speed algorithm demonstrated exceptional performance, processing graphs with 1,000 tasks in less than 1ms. In comparison, the general CVX-speed solver required approximately 60ms, which may exceed the timing requirements of high-speed real-time systems. While ILP solvers remained under 200ms for the tested datasets, they were still significantly outperformed by approximation methods.
5.2 Theory vs. Practical Constraints
A notable finding involved the APX-D-sched approximation algorithm. Its theoretical guarantee requires that the optimal solution uses speeds no higher than half the maximum frequency. In the E3S benchmarks, where deadlines are tight, this assumption was frequently violated, causing the algorithm to fail even when valid schedules existed.
5.3 Energy Trade-offs
The transition from continuous to discrete speeds introduces an energy penalty, particularly in scenarios with loose deadlines. Because hardware is limited to specific frequency steps, the system is often forced to run at a higher speed than the theoretical continuous optimum. However, the APX-D-speed approximation remained within a few percentage points of the ILP optimum while running two orders of magnitude faster, highlighting its utility for runtime systems.
6. Conclusion and Future Work
The study confirms that runtime energy optimization for DAGs is feasible, provided the algorithms exploit graph structures (like SPGs) or utilize efficient approximations. While the current research focuses on homogeneous MPSoCs, future work must address the complexities of heterogeneous architectures (e.g., ARM big.LITTLE) and the energy costs associated with inter-core communication. Integrating these algorithms into comprehensive resource management frameworks remains a critical next step for many-core system design.
Summary updated