14
$\begingroup$

When reporting algorithmic complexity of an algorithm, one assumes the underlying computations are performed on some abstract machine (e.g. RAM) that approximates a modern CPU. Such models allow us to report time and space complexity of algorithms. Now, with the spread out of GPGPUs, one wonders whether there are well known models where one can take into account power consumption as well.

GPUs are well known to consume considerable amount of power and certain instructions fall into different categories of power consumption based on their complexity and location on the sophisticated chip. Hence instructions, from an energy of view, are not of unit (or even fixed) cost. A trivial extension would be assigning weights to operation cost, but I'm looking for a powerful model where an operation/instruction might cost non-constant units of energy, e.g. polynomial amount (or even more complex e.g.: function of time elapsed since start of the algorithm; or taking into account probability of failure of cooling system, which will heat up the chips, and slow down the clock frequency etc.)

Are there such models where non-trivial costs and faults can be incorporated?

Improve this question
$\endgroup$
1
  • $\begingroup$ Do you have reason to believe that the amount of energy any elementary operation costs is subject to (complex) change? If you are interested, I know about a work that analyses energy consumption with theoretical tools. $\endgroup$
    – Raphael ♦
    Mar 13, 2012 at 1:16

3 Answers 3

Reset to default
8
$\begingroup$

There isn't an established model yet, but this is an area of active research right now. One of the experts on the algorithms side of things is Kirk Pruhs. His papers have more information, and you can also browse this presentation.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I disagree with the fact that there isn't an established model yet: most of the papers agree on a complicated physical model, they simply focus on different part of this physical model. For insctances Kirk focuses on the dynamical energy. $\endgroup$
    – Gopi
    Mar 13, 2012 at 18:35
  • $\begingroup$ I guess I mean there isn't an established computational cost model. $\endgroup$
    – Suresh
    Mar 13, 2012 at 18:39
7
$\begingroup$

Models for energy consumption

Speed scaling is one of the most used model (recently) when considering energy consumption. It consists in modifying the supply voltage. By lowering supply voltage, or processor clock frequency, it is possible to achieve important reductions in power consumption; faster speeds allow for a faster execution, but they also lead to a much higher (supra-linear) power consumption.

More precisely, a processor running at speed $s$ dissipates $s^3$ watts per unit of time, hence it consumes $s^3 \times d$ joules when operated during $d$ units of time.

However speed scaling is not the only energy considered. It is what is called the dynamic energy. The static energy is the power that is due to the processor being 'on'. It is possible to get rid of this static power by shutting down the processor during idle time. However it has a cost. There has been a lot of work done on this subject which is very close to the ski rental problem.

Usually the energy consumption is the sum of the static and dynamic power consumption times the execution time. However, most paper focus on either one of these problems.

Introducing faults in this model

I think this is the most surprising part of the speed-scaling model. Usually one would think that the faster you execute a task, the more likely you are to fail the execution. On the contrary, it was shown that reducing the speed of a processor increases the number of transient fault rates of the system; the probability of failures increases exponentially, and this probability cannot be neglected in large-scale computing.

Intuitively, there is the fact that the more time you spend on a task the more chances you have to fail during the execution of that task. However there is more than that: Shatz and Wang in this, stated that the fault-model followed a Poisson distribution. The parameter $\lambda$ of the Poisson distribution is then:\ $$ \lambda(f)=\lambda_0 e^{d\frac{fmax-f}{fmax-fmin}}, $$ where $f$ is the processing speed comprised in $[fmin,fmax]$, and $\lambda_0$ and $d$ are constant dependent on the systyem. If you consider a task of weight $w$, executed at speed $f$, the reliability of the execution for that task is $R(f)=e^{-\lambda(f)\times\frac{w}{f}}$.

This is self reference so I do not know if it is appreciated here, however if you are interested, you can find more information in this paper on the dynamic part of the energy consumption.

Improve this answer
$\endgroup$
3
$\begingroup$

There have been attempts to analyse energy consumption of algorithms in theory (using real-life costs per operation, of course); see e.g. [1]. While the results are surprising enough---the fastest algorithm is not always the one using the least energy---some obstacles remain.

In particular, modern platforms switch off certain features so that operation energy cost spikes when they are turned on again. While in principle possible to incorporate in rigorous analysis, it becomes technically (too?) hard. Also, the effect of cache misses on total energy consumption has not been studied well.

It appears that huge differences between platforms oppose rigorous analyses which can (for once) not ignore specifics because general models (i.e. before plugging in concrete constants/functions) have limited significance.

  1. Hannah Bayer and Markus E. Nebel: Evaluating Algorithms according to their Energy Consumption, Computability in Europe, 2009
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.