PaperlayerView exact revision on arXiv

Source-linked AI summary

Some Observations on Optimal Frequency Selection in DVFS-based Energy Consumption Minimization

Nikzad Babaii Rizvandi, Javid Taheri, Albert Y. Zomaya

arXiv:1201.1695v1cs.DCcs.PF

TL;DR

The paper addresses energy minimization in parallel and distributed systems where conventional DVFS slack reclamation typically uses one discrete frequency per task. It formulates multi-frequency slack reclamation, proves that at most two frequencies suffice for discrete processors, and reports superior MVFS-DVFS performance across random and real application task graphs.

  • Problem

    Existing DVFS slack-reclamation methods generally use one discrete frequency per task, potentially underutilizing slack and wasting energy in parallel and distributed systems.

  • Method

    MVFS-DVFS formulates slack reclamation with combinations of processor frequencies and uses at most two voltage-frequency settings for discrete processors.

  • Results

    Simulation results from 3000 randomly generated and 600 real application task graphs show MVFS-DVFS outperforming other techniques, although success depends on available task slack.

  • Takeaways & Limitations

    For convex processor power functions, the optimal discrete solution uses two adjacent voltage-frequencies, providing a basis for efficient slack reclamation.

  • Takeaways & Limitations

    MVFS-DVFS experiments consider tasks whose durations are at least 100 times longer than frequency-transition times, allowing transition overhead to be neglected.

Abstract

from arXiv · show

In recent years, the issue of energy consumption in parallel and distributed computing systems has attracted a great deal of attention. In response to this, many energy-aware scheduling algorithms have been developed primarily using the dynamic voltage-frequency scaling (DVFS) capability which has been incorporated into recent commodity processors. Majority of these algorithms involve two passes: schedule generation and slack reclamation. The former pass involves the redistribution of tasks among DVFS-enabled processors based on a given cost function that includes makespan and energy consumption; and, while the latter pass is typically achieved by executing individual tasks with slacks at a lower processor frequency. In this paper, a new slack reclamation algorithm is proposed by approaching the energy reduction problem from a different angle. Firstly, the problem of task slack reclamation by using combinations of processors' frequencies is formulated. Secondly, several proofs are provided to show that (1) if the working frequency set of processor is assumed to be continues, the optimal energy will be always achieved by using only one frequency, (2) for real processors with a discrete set of working frequencies, the optimal energy is always achieved by using at most two frequencies, and (3) these two frequencies are adjacent/neighbouring when processor energy consumption is a convex function of frequency. Thirdly, a novel algorithm to find the best combination of frequencies to result the optimal energy is presented. The presented algorithm has been evaluated based on results obtained from experiments with three different sets of task graphs: 3000 randomly generated task graphs, and 600 task graphs for two popular applications (Gauss-Jordan and LU decomposition). The results show the superiority of the proposed algorithm in comparison with other techniques.

1. INTRODUCTION

Energy-aware HPC scheduling uses DVFS to reduce consumption, but conventional slack reclamation often wastes available slack by restricting each task to one discrete frequency. The paper proposes MVFS-DVFS, which combines frequencies during slack reclamation.

  • 1. INTRODUCTION: High-performance computing systems face substantial energy demands, including reported consumptions of 12 MW/h for the Earth Simulator and 100 MW/h for Petaflop.Cooling-system energy can further increase total consumption.
  • 1. INTRODUCTION: DVFS-based scheduling generally either jointly optimizes task placement, makespan, and energy or reclaims slack after an energy-agnostic schedule.The second approach applies an independent DVFS technique to tasks’ generated slack times.
  • 1. INTRODUCTION: Existing slack-reclamation methods usually assign each task one discrete frequency, which can leave slack underused and waste processor and device energy.The paper identifies limited exploration of slack-reclamation opportunities as a second major limitation.
  • 1. INTRODUCTION: MVFS-DVFS reclaims generated slack by executing tasks with a linear combination of multiple voltage-frequency settings.The supplied passage introduces the approach but truncates the full description of its frequency combination.

2. RELATED WORK

Prior work applies DVFS to energy-aware scheduling across embedded and high-performance systems, but many methods target smaller or shared-memory systems rather than clusters. RDVFS and MMF-DVFS are identified as the closest comparison methods for this work.

  • 2. RELATED WORK: Energy-aware scheduling methods are commonly categorized as static offline or dynamic online approaches, based on whether task timing information is provided or estimated before execution.The passage introduces this categorization for real-time embedded systems.
  • 2. RELATED WORK: Many existing methods cannot directly reduce energy in clusters because they target systems with few processors or shared memories and often assume independent tasks.The cited passage contrasts these assumptions with cluster-oriented needs.
  • 2. RELATED WORK: Related studies address precedence-constrained jobs, energy scalability, dependency-aware slack, profiling-based optimization, and just-in-time DVFS for MPI programs.These approaches cover both scheduling trade-offs and processor voltage-frequency selection.
  • 2. RELATED WORK: RDVFS and MMF-DVFS are presented as the most efficient closely related algorithms and are selected as comparison baselines.MMF-DVFS uses a linear combination of the processor’s highest and lowest frequencies, while RDVFS selects a suitable low-frequency setting.

3. PRELIMINARIES

The paper models homogeneous DVFS-enabled processors executing dependent tasks represented by DAGs, with each task characterized by available time, frequency-dependent execution, ideal continuous frequency, required clock ticks, and original-schedule duration. Energy combines dynamic execution power with idle power over the available task interval.

  • 3. PRELIMINARIES: The target system contains N homogeneous processors with individual memories, and frequency-switching time is assumed negligible relative to task execution time.The model states that switching takes 30–150 μsec while tasks execute for at least 1 msec.
  • 3. PRELIMINARIES: Applications consist of dependent tasks represented by a directed acyclic graph (DAG).The model assumes the DAG executes on the modeled high-performance computing system.
  • 3. PRELIMINARIES: Each task records available processor time, execution time at a selected frequency, an ideal continuous frequency, required clock ticks, and its original-schedule execution time.Available time includes execution and slack time.
  • 3. PRELIMINARIES: Processors support an ordered discrete set of voltage-frequency pairs, while power is modeled with dynamic CMOS switching and static leakage components.The paper also adopts a general relation among voltage, frequency, and power.
  • 3. PRELIMINARIES: A task’s total energy combines dynamic execution energy over its execution time with idle energy over the remaining available interval.The energy expression uses processor idle power for the non-execution portion.

4. MULTIPLE VOLTAGEFREQUENCY SELECTION FOR DYNAMIC VOLTAGEFREQUENCY SCALING (MVFSDVFS)

MVFS-DVFS formulates task slack reclamation as an energy-minimization problem over combinations of processor voltage-frequencies. Its analysis reduces the optimal solution to at most two frequencies and develops a path toward selecting them.

  • 4.1. Problem Statement: The general problem minimizes task energy while completing K clock ticks within an available time T, using available voltage-frequency pairs.The formulation treats each task’s slack reclamation independently from other DAG tasks.
  • 4.2. Computing the Optimal Solution: The solution method first analyzes a three-frequency task executed in exact time T, expressing energy as a linear function of one frequency’s execution time.The sign of the linear coefficient determines whether that time should be maximized or minimized.
  • 4.2. Computing the Optimal Solution: At most two voltage-frequencies always provide the optimal energy consumption for the simplified task formulation.The result follows regardless of whether the derived energy function increases or decreases with the remaining time variable.
  • 4.2. Computing the Optimal Solution: With a continuous frequency range, one voltage-frequency covering the whole slack time minimizes energy; with discrete frequencies, the optimum uses two frequencies surrounding the ideal frequency.The ideal frequency is defined by f_ideal = K/T.
  • 4.4. Simplified-Multiple Frequency Selection DVFS (SMFS-DVFS): For convex processor energy consumption, two non-adjacent selected frequencies cannot be optimal because inserting an available intermediate frequency reduces total energy.Therefore, the minimizing pair must be adjacent or neighboring.

5. EXPERIMENTAL RESULTS AND DISCUSSION

MVFS-DVFS is evaluated against RDVFS, MMF-DVFS, and optimum continuous frequency across synthetic and real-world task graphs, schedulers, and processor counts. Its energy-saving advantage depends on available task slack, while combining neighboring frequencies addresses limitations of single-frequency reclamation.

  • 5.1 An Example: In the illustrative task, the optimum continuous frequency is 53.84 MHz, but it is not available in the processor’s discrete frequency list.The example compares continuous optimum energy with discrete-frequency reclamation methods.
  • 5.1 An Example: SMFS-DVFS uses two neighboring processor frequencies and achieves energy closer to the continuous optimum than RDVFS in the example.The two frequencies are obtained from RDVFS, and the example reports SMFS-DVFS energy of 28.43 mW.
  • 5.2.2. Task information: 3000 random task graphs vary graph size, scheduling policy, processor count, task distribution, communication costs, and dependencies in the evaluation.The experiments use list scheduling, LPT, and SPT with 2, 4, 8, 16, and 32 processors.
  • 5.3. Results and Discussions: MVFS-DVFS shows superior normalized energy performance compared with other algorithms across the evaluated DAG sets.Table 3 summarizes results for 3600 task graphs represented by Figures 4 and 5.
  • 5.3. Results and Discussions: Gauss-Jordan task graphs are difficult for these algorithms because task relations and communication costs leave no reclaimable slack.Figure 6 illustrates a three-level Gauss-Jordan schedule on three homogeneous processors with communication costs of 10 time units.
  • 5.3. Results and Discussions: Increasing processor count saves more energy for random and LU task graphs because processing accelerates and system slack increases.Scheduling type also affects slack in random task graphs, with greater slack reported for 8 and 16 processors than for 4 and 32.
  • 5.3. Results and Discussions: MVFS-DVFS experiments restrict tasks to durations at least 100 times longer than frequency-transition times.This condition reflects the assumption that transition overhead is relatively small compared with task execution time.

6. Conclusion

The paper presents MVFSDVFS and proves that optimal discrete-frequency energy use requires at most two frequencies, adjacent under convex processor power consumption. Experiments across random and real application task graphs report the least energy in all cases.

  • 6. Conclusion: MVFSDVFS consumes the least energy in all cases compared with other related algorithms.The evaluation used 3000 randomly generated task graphs and 600 real application task graphs.
  • 6. Conclusion: For discrete processor voltage-frequencies, each task achieves optimal energy using at most two voltage-frequencies.
  • 6. Conclusion: When processor power consumption is convex in frequency, the two optimal voltage-frequencies are adjacent.
Loading 1201.1695v1…