We initiate the theoretical investigation of energy-efficient circuit design. We assume that the circuit design specifies the circuit layout as well as the supply voltages for the gates. To obtain maximum energy efficiency, the circuit design must balance the conflicting demands of minimizing the energy used per gate, and minimizing the number of gates in the circuit; If the energy supplied to the gates is small, then functional failures are likely, necessitating a circuit layout that is more fault-tolerant, and thus that has more gates.
By leveraging previous work on fault-tolerant circuit design, we show general upper and lower bounds on the amount of energy required by a circuit to compute a given relation. We show that some circuits would be asymptotically more energy-efficient if heterogeneous supply voltages were allowed, and show that for some circuits the most energy-efficient supply voltages are homogeneous over all gates. Additionally, we show hardness and approximation results for the problem of finding the minimum energy required by a fixed circuit to compute a relation.
Joint work with Antonios Antoniadis, Neal Barcelo, Kirk Pruhs, and Michele Scquizzato
Below are some of the references for this talk:
Energy-Efficient Circuit Design
A. Antoniadis, N. Barcelo, M. Nugent, K. Pruhs, M. Scquizzato
Innovations in Theoretical Computer Science, 2014
Lower bounds for the complexity of reliable boolean circuits with noisy gates.
P. Gács and A. Gál.
IEEE Transactions on Information Theory, 1994.
Lower bound for the redundancy of self-correcting arrangements of unreliable functional elements.
R. L. Dobrushin and S. I. Ortyukov.
Problems of Information Transmission, 1977.
Upper bound for the redundancy of self-correcting arrangements of unreliable functional elements.
R. L. Dobrushin and S. I. Ortyukov.
Problems of Information Transmission, 1977.
On networks of noisy gates.
N. Pippenger.
IEEE Symposium on Foundations of Computer Science, 1985