Existe uma máquina abstrata que pode capturar o consumo de energia?

13

Ao relatar a complexidade algorítmica de um algoritmo, assume-se que os cálculos subjacentes são executados em alguma máquina abstrata (por exemplo, RAM) que se aproxima de uma CPU moderna. Tais modelos nos permitem relatar a complexidade de algoritmos no tempo e no espaço. Agora, com a expansão das GPGPUs , questiona-se se existem modelos bem conhecidos nos quais também é possível levar em consideração o consumo de energia.

As GPUs são conhecidas por consumir uma quantidade considerável de energia e certas instruções se enquadram em diferentes categorias de consumo de energia com base em sua complexidade e localização no sofisticado chip. Portanto, as instruções, do ponto de vista energético, não têm custo unitário (ou mesmo fixo). Uma extensão trivial seria atribuir pesos ao custo da operação, mas estou procurando um modelo poderoso em que uma operação / instrução possa custar unidades de energia não constantes , por exemplo, quantidade polinomial (ou ainda mais complexa, por exemplo: função do tempo decorrido desde o início) do algoritmo; ou levando em consideração a probabilidade de falha do sistema de refrigeração, o que aquecerá os chips e diminuirá a freqüência do relógio, etc.)

Existem modelos onde custos e falhas não triviais podem ser incorporados?

complexity-theory computer-architecture power-consumption machine-models Gopi
fonte

Você tem motivos para acreditar que a quantidade de energia que qualquer custo elementar de operação está sujeita a alterações (complexas)? Se você estiver interessado, conheço um trabalho que analisa o consumo de energia com ferramentas teóricas.

Raphael

8

Ainda não existe um modelo estabelecido, mas essa é uma área de pesquisa ativa no momento. Um dos especialistas no lado dos algoritmos é Kirk Pruhs. Seus documentos têm mais informações e você também pode navegar nesta apresentação .

Suresh
fonte

Eu discordo do fato de que ainda não existe um modelo estabelecido: a maioria dos artigos concorda com um modelo físico complicado, eles simplesmente se concentram em diferentes partes desse modelo físico. Kirk se concentra na energia dinâmica.

Gopi

Acho que quero dizer que não existe um modelo de custo computacional estabelecido.

Suresh

7

Modelos para consumo de energia

A escala de velocidade é um dos modelos mais utilizados (recentemente) ao considerar o consumo de energia. Consiste em modificar a tensão de alimentação. Ao diminuir a tensão de alimentação ou a freqüência do clock do processador, é possível obter reduções importantes no consumo de energia; velocidades mais rápidas permitem uma execução mais rápida, mas também levam a um consumo de energia (supra-linear) muito maior.

$s$ $s^3$ $s^3 \times d$ $d$

No entanto, a redução de velocidade não é a única energia considerada. É o que é chamado de energia dinâmica . A energia estática é a energia que é devida ao fato de o processador estar "ligado". É possível se livrar dessa energia estática , desligando o processador durante o tempo ocioso. No entanto, tem um custo. Muito trabalho foi feito sobre esse assunto, muito próximo do problema do aluguel de esquis .

Normalmente, o consumo de energia é a soma do consumo de energia estática e dinâmica vezes o tempo de execução. No entanto, a maioria dos trabalhos se concentra em um desses problemas.

Introduzindo falhas neste modelo

Eu acho que essa é a parte mais surpreendente do modelo de escala de velocidade. Geralmente, alguém poderia pensar que quanto mais rápido você executar uma tarefa, maior a probabilidade de falhar na execução. Pelo contrário, foi demonstrado que reduzir a velocidade de um processador aumenta o número de taxas de falhas transitórias do sistema; a probabilidade de falhas aumenta exponencialmente, e essa probabilidade não pode ser negligenciada na computação em larga escala.

$\lambda$

λ (f) = λ_{0 0} e^{d \frac{f m uma x - f}{f m uma x - f m Eu n}},

$\lambda(f)=\lambda_0 e^{d\frac{fmax-f}{fmax-fmin}},$

f

$f$

[f m i n, f m a x]

$[fmin,fmax]$

λ_{0}

$\lambda_0$

d

$d$

w

$w$

f

$f$

R (f) = e^{- λ (f) \times \frac{w}{f}}

$R(f)=e^{-\lambda(f)\times\frac{w}{f}}$

Isso é auto-referência, então não sei se é apreciado aqui; no entanto, se você estiver interessado, poderá encontrar mais informações neste documento sobre a parte dinâmica do consumo de energia.

Gopi
fonte

3

Houve tentativas de analisar o consumo de energia de algoritmos em teoria (usando os custos da vida real por operação, é claro); veja, por exemplo, [1]. Embora os resultados sejam surpreendentes o suficiente - o algoritmo mais rápido nem sempre é o que utiliza menos energia - alguns obstáculos permanecem.

Em particular, as plataformas modernas desativam certos recursos, de modo que o custo da energia da operação aumenta quando eles são ligados novamente. Embora, em princípio, seja possível incorporar uma análise rigorosa, torna-se tecnicamente (também?) Difícil. Além disso, o efeito de perdas de cache no consumo total de energia não foi bem estudado.

Parece que enormes diferenças entre plataformas se opõem a análises rigorosas que não podem (por uma vez) ignorar detalhes específicos, porque os modelos gerais (isto é, antes de conectar constantes / funções concretas) têm significado limitado.

Hannah Bayer e Markus E. Nebel: Avaliando algoritmos de acordo com seu consumo de energia , computabilidade na Europa, 2009

Rafael
fonte

Existe uma máquina abstrata que pode capturar o consumo de energia?

Respostas: