Energy-Constrained Scheduling

Unlike traditional schedulers that treat CPU time or memory as the primary resource, energy-constrained schedulers treat joules or watt-hours as the fundamental, depletable resource to be allocated. The scheduler's objective function is explicitly defined to maximize task completion within a hard energy budget. This requires continuous monitoring of the system's state of charge and predictive models of task energy consumption.

Effective scheduling depends on accurate forecasts of energy consumption for pending tasks. This involves:

• Static profiling: Measuring the average energy cost of each task type (e.g., sensor read, inference, radio TX) offline.
• Runtime adaptation: Adjusting models based on dynamic factors like supply voltage, chip temperature, and input data complexity.
• The scheduler uses these models to create a feasible schedule—a sequence of tasks that does not exceed the available energy budget.

The scheduler must have intimate knowledge of and control over the device's power management features. It coordinates task execution with:

• Sleep states (C-states): Strategically placing the CPU/accelerator into deep sleep between tasks.
• Dynamic Voltage and Frequency Scaling (DVFS): Selecting the most energy-efficient operating point for each task's deadline.
• Power gating: Instructing the system to completely shut down unused peripherals or cores. This turns passive hardware features into active scheduling knobs.

The scheduler navigates the inherent tension between task performance and energy savings. Key trade-off decisions include:

• Task dropping: Selectively skipping non-critical tasks when energy is critically low.
• Accuracy scaling: Instructing ML models to use a more energy-efficient (but less accurate) precision mode or early exit.
• Deadline relaxation: Negotiating with the application to extend a task's deadline, allowing the use of a slower, more efficient CPU frequency.

To minimize scheduling overhead (which itself consumes energy), these schedulers are often:

• Event-driven: Activated by external triggers like a sensor interrupt or a timer, rather than running a continuous scheduling loop.
• Non-preemptive: Once a task starts, it runs to completion to avoid the energy cost of context switches and to allow the system to enter a deep sleep state predictably.
• This leads to designs that are more finite state machine than general-purpose OS scheduler.

The ultimate goal is not merely to finish tasks, but to maximize the system's utility—a measure of application benefit—per unit of energy consumed. This is formalized in optimization problems like:

• Maximizing completed task value before battery exhaustion.
• Achieving energy-neutral operation in harvesting systems.
• Minimizing the Energy-Delay Product (EDP) for latency-sensitive tasks. The scheduler's policy is the solution to this constrained optimization problem.

The fundamental problem is to schedule a set of computational tasks (e.g., sensor sampling, inference, radio transmission) with varying energy costs and deadlines on a device with a limited energy budget. The goal is to find a feasible schedule that maximizes a utility function, such as the number of tasks completed or total system uptime, before the battery is exhausted. This often involves:

• Task Characterization: Profiling the energy consumption of each software routine.
• Budget Allocation: Dynamically partitioning the total energy budget across the device's operational lifetime.
• Feasibility Checking: Determining if a set of tasks can be completed given the remaining energy and time.

Effective scheduling does not work in isolation; it directly controls underlying hardware power states. It co-optimizes with:

• Dynamic Voltage and Frequency Scaling (DVFS): The scheduler selects optimal voltage/frequency pairs for each task to trade performance for energy savings.
• Power Gating & Sleep States: It determines when to power down entire subsystems (e.g., a vision sensor or ML accelerator) between active periods.
• Wake-on-Event Triggers: Schedules are often event-driven, waking the main processor only when a sensor in the always-on (AON) domain detects meaningful activity.

Different policies optimize for different objectives under energy constraints:

• Earliest Deadline First (EDF) with Energy: Prioritizes tasks with the closest deadlines, but only if sufficient energy exists to complete them.
• Maximum Utility per Joule: Selects the sequence of tasks that delivers the highest system value (e.g., accuracy of inference) for the energy expended.
• Energy-Aware Rate Monotonic (RM): A fixed-priority policy for periodic tasks where priority is assigned based on period, but low-energy modes are used during slack time.
• Battery-Aware Scheduling: Accounts for non-linear battery characteristics, like rate capacity effect, scheduling high-power tasks when the battery state-of-charge is high to improve efficiency.

Scheduling must account for the unique behavior of machine learning workloads on microcontrollers:

• Variable-Cost Inference: The energy of an ML inference can vary with input complexity. Schedulers can leverage early exit networks to allocate less energy for simpler inputs.
• Multi-Model Scheduling: Devices may switch between different compressed models (e.g., a high-accuracy model and a low-power model) based on the available energy budget and task criticality.
• Sensor-Inference Co-scheduling: Tightly couples the scheduling of sensor sampling (e.g., camera wake-up) with the subsequent inference task to minimize the active time of high-power components.

For devices powered by ambient energy (solar, vibration), scheduling becomes predictive and adaptive. The system aims for energy-neutral operation.

• Energy Prediction: Uses models to forecast harvestable energy (e.g., based on time of day for solar).
• Adaptive Duty Cycling: The scheduler dynamically adjusts the device's duty cycle—the ratio of active time to sleep time—based on the current and predicted energy in the storage capacitor or battery.
• Load Matching: Works with Maximum Power Point Tracking (MPPT) circuits to schedule high-energy tasks when the harvesting source is most productive.

The effectiveness of a scheduling strategy is measured against several key metrics:

• System Lifetime: The total operational time until the energy budget is depleted.
• Task Completion Ratio: The percentage of scheduled tasks successfully executed before their deadline.
• Energy-Delay Product (EDP): Evaluates the trade-off between energy consumed and performance (timeliness).
• Inference-per-Watt: A domain-specific metric for ML workloads, measuring computational throughput per unit of energy.
• Energy Profiling: Implemented using energy profiling tools to measure the real-world impact of scheduling decisions on total system power.

A broader class of operating system or runtime algorithms that allocate computational tasks and manage hardware power states to minimize total system energy consumption. While energy-constrained scheduling specifically works with a fixed energy budget, power-aware scheduling aims for general efficiency, often using techniques like:

• Dynamic Voltage and Frequency Scaling (DVFS)
• Heterogeneous core mapping (big.LITTLE architectures)
• Predictive idling to enter low-power states. Its goal is to reduce Joules per task without a hard cap on total available energy.

A system-level strategy that dynamically controls the power states of hardware components (e.g., putting cores, peripherals, or memory into sleep modes) based on workload predictions. DPM provides the hardware control primitives that an energy-constrained scheduler leverages. Key techniques include:

• Power gating (cutting power to idle blocks).
• Clock gating (stopping the clock to unused circuits).
• Managing Sleep States (C-States). The scheduler uses DPM policies to decide when to transition components between these states to stay within the energy budget.

A scheduling algorithm that assigns tasks to specific processor cores or accelerators while modeling the battery's non-ideal characteristics. Unlike a simple energy budget, it considers:

• State of Charge (SoC) and internal resistance.
• Battery recovery effect (voltage rebound during rest).
• Degradation kinetics to maximize total system lifetime. This approach is crucial for energy-constrained scheduling in real deployments, as battery capacity is not a linear, static resource. It informs how the energy budget should be spent over time.

A fundamental power-saving technique where a device (e.g., radio, sensor, or full system) alternates between short active periods and long low-power sleep periods. The duty cycle is the ratio of active time to the total period. Energy-constrained scheduling often governs the duty cycle of different subsystems:

• Determines when a sensor wakes to sample.
• Schedules how long a radio transmits data.
• Balances the duty cycles of concurrent tasks to ensure the weighted sum of their energy consumption does not exceed the budget before mission completion.

A key combined metric (Energy Consumed × Execution Time) used to evaluate the Pareto frontier of the performance-energy trade-off. Energy-constrained scheduling algorithms often use EDP or its variant, Energy-Delay-Squared Product (ED²P), as an optimization objective. It answers: 'What is the most energy-efficient way to complete this set of tasks without violating timing deadlines?' Minimizing EDP typically avoids both wasteful high-power bursts and excessively slow, leakage-dominated execution.

A design goal for energy-harvesting systems where long-term average energy consumption ≤ average energy harvested. Energy-constrained scheduling is the algorithmic engine that makes this possible. The scheduler must:

• Predict or measure harvested energy (e.g., from solar, vibration).
• Allocate this energy to tasks (sensing, computation, communication).
• Maintain an energy buffer to handle periods of low harvest. This enables perpetual operation for IoT devices, with the scheduler dynamically adjusting the quality of service based on available energy.