¿Existe una máquina abstracta que pueda capturar el consumo de energía?

13

Cuando se informa la complejidad algorítmica de un algoritmo, se supone que los cálculos subyacentes se realizan en alguna máquina abstracta (por ejemplo, RAM) que se aproxima a una CPU moderna. Dichos modelos nos permiten informar la complejidad de algoritmos en el tiempo y el espacio. Ahora, con la propagación de GPGPU , uno se pregunta si hay modelos bien conocidos en los que también se puede tener en cuenta el consumo de energía.

Se sabe que las GPU consumen una cantidad considerable de energía y ciertas instrucciones se dividen en diferentes categorías de consumo de energía en función de su complejidad y ubicación en el sofisticado chip. Por lo tanto, las instrucciones, desde una perspectiva visual, no tienen un costo unitario (o incluso fijo). Una extensión trivial sería asignar pesos al costo de operación, pero estoy buscando un modelo poderoso donde una operación / instrucción pueda costar unidades de energía no constantes , por ejemplo, cantidad polinómica (o incluso más compleja, por ejemplo: función del tiempo transcurrido desde el inicio del algoritmo; o teniendo en cuenta la probabilidad de falla del sistema de enfriamiento, que calentará los chips y ralentizará la frecuencia del reloj, etc.)

¿Existen modelos en los que se puedan incorporar costos y fallas no triviales?

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

¿Tiene alguna razón para creer que la cantidad de energía que cuesta cualquier operación elemental está sujeta a cambios (complejos)? Si está interesado, conozco un trabajo que analiza el consumo de energía con herramientas teóricas.

Raphael

8

Todavía no existe un modelo establecido, pero esta es un área de investigación activa en este momento. Uno de los expertos en algoritmos es Kirk Pruhs. Sus documentos tienen más información, y también puede navegar por esta presentación .

Suresh
fuente

No estoy de acuerdo con el hecho de que todavía no existe un modelo establecido: la mayoría de los documentos coinciden en un modelo físico complicado, simplemente se centran en diferentes partes de este modelo físico. Para las instancias, Kirk se centra en la energía dinámica.

Gopi

Supongo que quiero decir que no hay un modelo de costo computacional establecido.

Suresh

7

Modelos para consumo de energía.

El escalado de velocidad es uno de los modelos más utilizados (recientemente) cuando se considera el consumo de energía. Consiste en modificar la tensión de alimentación. Al reducir el voltaje de suministro o la frecuencia del reloj del procesador, es posible lograr reducciones importantes en el consumo de energía; velocidades más rápidas permiten una ejecución más rápida, pero también conducen a un consumo de energía mucho más alto (supra-lineal).

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

Sin embargo, el escalado de velocidad no es la única energía considerada. Es lo que se llama la energía dinámica . La energía estática es la potencia que se debe a que el procesador está "encendido". Es posible deshacerse de esta energía estática apagando el procesador durante el tiempo de inactividad. Sin embargo tiene un costo. Se ha trabajado mucho en este tema, que está muy cerca del problema del alquiler de esquís .

Por lo general, el consumo de energía es la suma del consumo de energía estático y dinámico multiplicado por el tiempo de ejecución. Sin embargo, la mayoría de los trabajos se centran en cualquiera de estos problemas.

Introducir fallas en este modelo

Creo que esta es la parte más sorprendente del modelo de escalado de velocidad. Por lo general, uno pensaría que cuanto más rápido ejecute una tarea, es más probable que falle la ejecución. Por el contrario, se demostró que reducir la velocidad de un procesador aumenta el número de tasas de fallas transitorias del sistema; La probabilidad de fallas aumenta exponencialmente, y esta probabilidad no puede ser descuidada en la computación a gran escala.

$\lambda$

λ (f) = λ_{0} e^{d \frac{f m a x - f}{f m a x - f m i 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}}$

Esta es una referencia propia, así que no sé si se aprecia aquí, sin embargo, si está interesado, puede encontrar más información en este documento sobre la parte dinámica del consumo de energía.

Gopi
fuente

3

Ha habido intentos de analizar el consumo de energía de los algoritmos en teoría (utilizando los costos de la vida real por operación, por supuesto); ver por ejemplo [1]. Si bien los resultados son lo suficientemente sorprendentes, el algoritmo más rápido no siempre es el que usa menos energía, quedan algunos obstáculos.

En particular, las plataformas modernas desactivan ciertas funciones para que los costos de energía de operación aumenten cuando se vuelven a encender. Si bien en principio es posible incorporarlo en un análisis riguroso, se vuelve técnicamente (¿demasiado?) Difícil. Además, el efecto de las pérdidas de caché en el consumo total de energía no se ha estudiado bien.

Parece que grandes diferencias entre plataformas se oponen a análisis rigurosos que (por una vez) no pueden ignorar detalles específicos porque los modelos generales (es decir, antes de conectar constantes / funciones concretas) tienen un significado limitado.

Hannah Bayer y Markus E. Nebel: Evaluación de algoritmos según su consumo de energía , computabilidad en Europa, 2009

Rafael
fuente

¿Existe una máquina abstracta que pueda capturar el consumo de energía?

Respuestas: