Towards understanding algorithmic factors affecting energy consumption

摘要

Mobile devices consider energy to be a limiting resource. Over the past decade significant research has gone into how one can reduce energy consumption at the hardware level, network protocol level, operating system level, and compiler level. In almost all algorithm analysis, a single resource such as time or communication is often taken as a proxy for energy. We address this problem by defining an algorithmic model for energy, designing algorithm variants that reduce energy cost in this model, and then performing preliminary experiments to test the model.Our starting point is an algorithmic energy model inspired by work from the compilers community [26]. Augmenting and simplifying this model motivates the need to consider an algorithm's "switching" complexity; this measure captures the extent to which one switches between different functional units during execution. We carry out preliminary experiments on the Itsy pocket computer, which contains a StrongARM SA-1100 processor running Linux, to compare "high-switch" versions of bubble sort and other algorithms to optimized "low-switch" versions. Our preliminary results show that switching does not appear to affect energy consumption at the algorithmic level.We then look at a factor that does not appear to have been studied, namely the cost of generating (pseudo)random bits. Derandomization is a goal in cryptography and complexity theory. To our knowledge the energy cost of randomness itself has not been studied. Nonetheless, many mobile protocols and algorithms might utilize randomness, for example to handle contention resolution, generate cryptographic keys, or to accomplish efficient sorting. We consider three common mechanisms for generating randomness: the standard C library random number generator, and the Linux /dev/random, and /dev/urandom generators. We perform tests that compare the energy consumed by these generators compared to thecost of performing basic arithmetic instructions. We use Quicksort as an example of a classic basic application-level algorithm to understand the energy cost of randomness, and compare the energy consumed by randomized Quicksort to standard Quicksort. Our preliminary results show that generating randomness does in fact incur a significant energy cost, and /dev/random is the most expensive of the three mechanisms.We conclude that understanding energy consumption at the algorithmic level is an important but overlooked area of investigation, and discuss the implications of our results. We end with directions for for further work.