Algoritmos energéticamente eficientes. Landauer & Bennett.

Desde hace tiempo nos interesamos por el tema que indicamos en el título. Es más hemos contribuido a ello con un modelo de computación paralela (RH Systems, basados en enrutamiento por recorridos hamiltonianos) en el que, utilizando los resultados de la patente entendemos (no hay demostraciones de ningún tipo de momento) que mejora la eficiencia energética de estos sistemas. Un artículo que he encontrado interesante sobre ello.

Título: Energy-Efficient Algorithms

1.El principio teórico de Landauer. 

Expresa que hay un mínimo de energía que se debe de consumir para borrar un bit, el llamado límite de Landauer.

La fórmula precisa es:  kT ln 2, where k is the Boltzmann constant (approximately 1.38×10−23 J/K), T is the temperature of the circuit in kelvins, and ln 2 is the natural logarithm of 2 (approximately 0.69315).

2.Su aplicación a la realidad.

Esta operación de borrado no se puede hacer con menos de esta cantidad de energía, independientemente de las mejoras tecnológicas.

CPU power efficiency (number of computations per kilowatt hour of energy) has doubled every 1.57 years from 1946 to 2009 [KBSW11]. Within the next 15–60 years, however, this trend will hit a fundamental limit in physics, known as Landauer’s Principle [Lan61].

Most CPUs discard many bits of information per clock cycle, as much as one per gate; for example, an AND gate with output 0 or an OR gate with output 1 “forgets” the exact values of its inputs.

Most CPUs discard many bits of information per clock cycle, as much as one per gate; for example, an AND gate with output 0 or an OR gate with output 1 “forgets” the exact values of its inputs. To see how this relates to Landauer’s principle, consider the state-of-the-art 15-core Intel Xeon E7-4890 v2 2.8GHz CPU. In a 4-processor configuration, it achieves 1.2 · 1012 computations per second at 620 watts,1 for a ratio of 7.4·1015 computations per kilowatt hour. At the pessimistic extreme, if every one of the 4.3 · 109 transistors discards a bit, then the product 3.2 · 1025 is only three orders of magnitude greater than Landauer limit. If CPUs continue to double in energy efficiency every 1.57 years, this gap will close in less than 18 years. At the more optimistic extreme, if a 64-bit computation discards only 64 bits (to overwrite one register), the gap will close within 59 years. The truth is probably somewhere in between these extremes.

La así llamada Ley de Moore ya ha llegado prácticamente a su límite, lo cual ha impulsado la tendencia multicore, aunque todavía está sujeta a avances tecnológicos. Y para llegar al límite de Landauer no queda tampoco demasiado tiempo, entre 18 y 59 años.

3. La computacióon reversible ¿ una solución a este límite tecnológico ?. 

Reversible computing. The only way to circumvent the Landauer limit is to do logically reversible computations, whose inputs can be reconstructed from their outputs, using physically adiabatic circuits. According to current knowledge, such computations have no classical fundamental limitations on energy consumption. General-purpose CPUs with adiabatic circuits were constructed by Frank and Knight at MIT [Fra99]. The design of reversible computers is still being actively studied, with papers on designs for adders [NTR11], multipliers [NTR10], ALUs [MR11], clocks [SAI+13], and processors [TAG12] being published within the last five years. AMD’s CPUs since Oct. 2012 (Piledriver) use “resonant clock mesh technology” (essentially, an adiabatic clock circuit) to reduce overall energy consumption by 24% [Cyc12]. Thus the ideas from reversible computing are already creating energy savings today. But what can be done by reversible computation? Reversible computation is an old idea, with reversible Turing machines being proved universal by Lecerf in 1963 [Lec63] and ten years later by Bennett [Ben73]. Early complexity results showed that any computation can be made reversible, but with a quadratic space overhead [Ben89] or an exponential time overhead [LMT97,Wil00], in particular models of computation. More recent results give a trade-off with subquadratic space and subexponential time [BTV01]. These general transforms are too expensive; in particular, in a bounded-space system, consuming extra space to make computations reversible is just delaying the inevitable destruction of bits.

Había oído hablar de la computación reversible, su universalidad, pero sabía que fuese tan costosa en términos de espacio y tiempo. Muy interesante.

5. Los resultados del artículo.

This paper is the first to perform a thorough algorithmic study of partially reversible computing, and to analyze realistic time/space/energy trade-offs. We define the (Landauer/irreversibility) energy cost, and use it to explore reversible computing in a novel manner. Although there are many other sources of energy inefficiency in a computer we believe the Landauer energy cost is a fundamental and useful measure. A key perspective shift from most of the reversible computing literature (except [LV96]) is that we allow algorithms to destroy bits, and measure the number of destroyed bits as the energy cost. This approach enables the unification of classic time/space measures with a new energy measure. In particular, it enables us to require algorithms to properly clean up all additional space by the end of their execution, and data structures to be properly charged for their total space allocation.

Lo cierto es que la energía no se consume solo borrando  bits. Dicho esto la diferencia entre un algoritmo que utilice backtracking y uno que encuentre de manera más directa la solución es precisamente que el que utiliza backtraking tiene que borrar muchos más bits a lo largo de su computación. ¿ O interesa almacenar las vías muertas ?.

These models open up an entire research field, which we call energy-efficient algorithms, to find the minimum energy required to solve a desired computational problem within given time and space bounds. We launch this field with several initial results about classic algorithmic problems, first analyzing the energy cost of existing algorithms, and then modifying or designing new algorithms to reduce the energy cost without significantly increasing the time and space costs. Table 2 summarizes these results.

En fin lo dejamos aquí. El lector interesado puede leer el artículo completo en el enlace del principio.

Nota. Hemos seleccionado los dos nombres del título más que nada por adornarlo. Se trata de dos de los investigadores (los dos trabajaron en IBM) principales en este campo. No nos olvidamos de Yves Lecerf. El caso es que tras una primera prometedora publicación sobre computabilidad de máquinas reversibles (en la que demuestra la universalidad de la computación clásica reversible), dejó este tipo de investigaciones. Bennett publicó más tarde este mismo resultado y además estudió el tema desde el punto de vista de complejidad computacional. Realmente no conocía a Lecerf, investigador de curiosa carrera. Fin de nota. 

Terms and conditions: 1. Any commenter of this blog agrees to transfer the copy right of his comments to the blogger. 2. RSS readers and / or aggregators that captures the content of this blog (posts or comments) are forbidden. These actions will be subject to the DMCA notice-and-takedown rules and will be legally pursued by the proprietor of the blog.

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s


A %d blogueros les gusta esto: