Analyzing and optimizing energy efficiency of algorithms on DVS systems a first step towards algorithmic energy minimization

ABSTRACT

The energy efficiency at the algorithmic level on DVS systems and its analysis and optimization methods are presented. Given a problem the most energy efficient algorithm is not uniquely determined but dependent on multiple factors, including intratask dynamic voltage scaling (IntraDVS) policies, the size of intermediate data structure, and the size of inputs. We show that at the algorithmic level principles behind energy optimization and performance optimization are not identical. We propose a metric for evaluating optimal energy efficiency of static voltage scaling (SVS) and a few new effective IntraDVS policies employing data flow information. Experimental results on sorting algorithms show the existence of several tradeoffs in terms of energy consumption. Transforming algorithms by employing problem specific knowledge and data flow information successfully improves their energy efficiency.

REFERENCES

• 1: Richard Bird, Introduction to Functional Programming, Pearson Education, 1998
• 2: Tohru Ishihara , Hiroto Yasuura, Voltage scheduling problem for dynamically variable voltage processors, Proceedings of the 1998 international symposium on Low power electronics and design, p.197-202, August 10-12, 1998, Monterey, California, United States [doi>10.1145/280756.280894]
• 3: R. Jain, D. Molnar, and Z. Ramzan, "Towards a model of energy complexity for algorithms," In Wireless Communications and Networking Conference, vol. 3, pp. 1884--1890, 2005.
• 4: Ravi Jain , David Molnar , Zulfikar Ramzan, Towards understanding algorithmic factors affecting energy consumption: switching complexity, randomness, and preliminary experiments, Proceedings of the 2005 joint workshop on Foundations of mobile computing, September 02-02, 2005, Cologne, Germany [doi>10.1145/1080810.1080823]
• 5: Alain J. Martin, Towards an energy complexity of computation, Information Processing Letters, v.77 n.2-4, p.181-187, Feb. 1, 2001 [doi>10.1016/S0020-0190(00)00214-3]
• 6: David R. Musser, Introspective sorting and selection algorithms, Software—Practice & Experience, v.27 n.8, p.983-993, Aug. 1997 [doi>10.1002/(SICI)1097-024X(199708)27:8<983::AID-SPE117>3.0.CO;2-#]
• 7: D. Shin and J. Kim, "Optimizing intratask voltage scheduling using profile and data-flow information," IEEE Trans, on Computer-Aided Design of Integrated Circuits and Systems, 26(2):369--385, 2007.
• 8: Vivek Tiwari , Sharad Malik , Andrew Wolfe, Power analysis of embedded software: a first step towards software power minimization, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.384-390, November 06-10, 1994, San Jose, California, United States
• 9: John D. Valois, Introspective sorting and selection revisited, Software—Practice & Experience, v.30 n.6, p.617-638, May 2000 [doi>10.1002/(SICI)1097-024X(200005)30:6<617::AID-SPE311>3.3.CO;2-1]