Energy Aware Algorithm Design via Probabilistic Computing: From Algorithms and Models to Moore's Law and Novel (Semiconductor)Devices

摘要

With their ever increasing proliferation, concerns of power (or energy) consumption have become significant in the context of the design and as well as the use of computing systems. While devices, computer architecture and the layers of software that reside and execute at higher levels of abstraction (such as operating systems, run-time, compilers and programming languages) all afford opportunities for being energy-aware, the most fundamental limits are truly rooted in the physics of energy consumption - specifically in thermodynamics. Based on this premise, this paper embodies the innovation of models of computing for energy-aware algorithm design and analysis, culminating in establishing, for the first time, the following central thesis of this work: the computational technique referred to as randomization yielding probabilistic algorithms, now ubiquitous to the mathematical theory of algorithm design and analysis, when interpreted as a physical phenomenon through classical statistical thermodynamics with such pioneers as Maxwell, Boltzmann and Gibbs at the helm, leads to energy savings that are proportional to the probability p with which each primitive com- putational step is guaranteed to be correct (or equivalently to the probability of error of (1 — p)).