Energy efficient algorithms

This article was due to content flaws on the quality assurance side of the computer science editorial added. This is done in order to bring the quality of the articles from the subject area of ​​computer science to an acceptable level. Help to eliminate the shortcomings in this article and take part in the discussion !  ( + )

motivation

Energy costs are a major expense when using many computer systems. Operators of large server farms consume thousands of gigawatt hours of electrical energy. The resulting heat must be dissipated so that hardware remains at operating temperature and does not suffer any damage. Energy savings lead directly to less heat generation and lower costs.

The availability of electrical energy is limited in mobile systems such as laptops, smartphones and many Bluetooth systems. Batteries have only limited storage capacity, so that energy savings lead to longer service lives of these systems.

history

• The 1961 by Rolf Landauer formulated Landauer's principle provides a theoretical lower limit for the energy consumption of irreversibly operating computers.

• In 1992 the United States Environmental Protection Agency introduced the Energy Star eco-label for energy-saving devices, which has led to the proliferation of standby modes.

• In 2017, the EU limited the energy consumption of connected devices to 3 to 12 watts in standby mode.

techniques

Power-down strategies

Most systems have energy saving or standby modes . The energy consumption is lower in these modes than in the active operating mode. Every system should switch to such a mode when inactive. However, the change to the active operating mode is coupled with additional energy consumption. The question of when a system should switch to energy-saving mode if the length of inactivity is unknown can be solved using online algorithms . OBdA one can describe the problem with a system with two modes as follows.

Systems with two modes

In the active operating mode is the energy consumption . In the energy saving mode is the energy consumption . The energy consumption of changing to the operating mode is . The energy consumption in the energy saving mode can usually be neglected or added to the value . ${\displaystyle 1{\tfrac {Energieeinheit}{Zeiteinheit}}}$ ${\displaystyle 0}$ ${\displaystyle \beta }$ ${\displaystyle \beta }$

A competitive analysis shows that the best deterministic algorithm for the problem always switches to energy-saving mode if the inactivity lasts β time units. In the worst case, this algorithm has twice the energy consumption compared to an optimal algorithm.

The problem can be reduced to the ski rental problem and investigated analogously.

Systems with multiple modes

For systems with several energy saving modes, online algorithms can also be used to reduce energy consumption. Let be the modes of operation of a system with modes. be the energy consumption in mode . The modes are numbered so that applies. is the energy requirement to switch from mode to operating mode . Irani et al. have shown that the power consumption of an optimal offline algorithm for an inactive phase of length is as follows ${\displaystyle m_{1},m_{2},...,m_{l}}$ ${\displaystyle l}$ ${\displaystyle r_{i}}$ ${\displaystyle m_{i}}$ ${\displaystyle r_{1}>r_{2}>...>r_{l}}$ ${\displaystyle \beta _{i}}$ ${\displaystyle m_{i}}$ ${\displaystyle m_{1}}$ ${\displaystyle T}$

• ${\displaystyle OPT(T)={\underset {1\leq i\leq l}{\min }}(r_{i}T+\beta _{i})}$

An online algorithm that selects the mode at any time during an inactive phase is 2-competitive. ${\displaystyle t}$ ${\displaystyle M_{OPT}(t)}$

Speed ​​scaling

Current microprocessors can be operated at different speeds. The energy consumption increases with increasing speed. By reducing the speed, energy can be saved, but at the price of lower performance. It is the job of the process scheduler to decide when which process is executed with which processor speed . Depending on the context, there are a number of algorithms with the aim of keeping the energy consumption of the system as low as possible.

Benchmark

JouleSort was proposed in 2007 by Suzanne Rivoire, Mehul A-Shah, Parthasarathy Ranganathan and Christos Kozyrakis as a benchmark for energy-efficient computer systems.

The task is to sort a certain number of 100-byte data with 10-byte keys. The data is loaded and saved on permanent storage media. The total number of data to be sorted is 10 ⁸ (~ 10 GB), 10 ⁹ (~ 100 GB), 10 ¹⁰ (~ 1 TB) and 10 ¹² (~ 100 TB). The winner is the system that has the lowest total energy requirement for sorting.

Due to the large amounts of data, JouleSort concentrates on inputs and outputs on a non-volatile memory when the system is at maximum capacity. This clearly shows the lower energy requirements of flash memories compared to hard drives.

Individual evidence

1. ↑ ^{a b c} JouleSort: A Balanced Energy-Efficiency Benchmark . Retrieved July 25, 2019.
2. ↑ Off mode, standby and networked standby . Retrieved July 25, 2019.
3. ↑ ^{a b c} Energy-Efficient Algorithms . Accessed July 31, 2019.
4. ↑ S. Irani, SK Shukla, RK Gupta: Online strategies for dynamic power management in systems with multiple power-saving states . In: ACM Transaction in Embedded Computing Systems . September 2, pp. 325-346.
5. ↑ Sort Benchmark Home Page . Accessed July 31, 2019.