Swapnoneel Roy
ABSTRACT
Energy consumption has emerged as a first class computing resource for both server systems and personal computing devices. The growing importance of energy has led to rethink in hardware design, hypervisors, operating systems and compilers. Algorithm design is still relatively untouched by the importance of energy and algorithmic complexity models do not capture the energy consumed by an algorithm. In this paper, we propose a new complexity model to account for the energy used by an algorithm. Based on an abstract memory model (which was inspired by the popular DDR3 memory model and is similar to the parallel disk I/O model of Vitter and Shriver), we present a simple energy model that is a (weighted) sum of the time complexity of the algorithm and the number of 'parallel' I/O accesses made by the algorithm. We derive this simple model from a more complicated model that better models the ground truth and present some experimental justification for our model. We believe that the simplicity (and applicability) of this energy model is the main contribution of the paper. We present some sufficient conditions on algorithm behavior that allows us to bound the energy complexity of the algorithm in terms of its time complexity (in the RAM model) and its I/O complexity (in the I/O model). As corollaries, we obtain energy optimal algorithms for sorting (and its special cases like permutation), matrix transpose and (sparse) matrix vector multiplication.
Supplemental Material
Available for Download
to compile: 1. latex itcs101-roy 2. bibtex itcs101-roy 3. latex itcs101-roy 4. latex itcs101-roy 5. dvips latex itcs101-roy 6. ps2pdf latex itcs101-roy.ps Note: I have included the main tex file itcs101-roy.tex here (in addition to submitting it separately).
- Calculating memory system power for DDR3. http://download.micron.com/pdf/technotes/ddr3/TN41_01DDRPower.pdf.Google Scholar
- Data center energy consumption trends. http://www1.eere.energy.gov/femp/program/dc_energy_consumption.html.Google Scholar
- Hardware monitor. http://www.bresink.de/osx/HardwareMonitor.html.Google Scholar
- Joulemeter: Computational energy measurement and optimization. http://research.microsoft.com/en-us/projects/joulemeter/http://research.microsoft.com/en-us/projects/joulemeter/.Google Scholar
- A. Aggarwal and J. Vitter. The input/output complexity of sorting and related problems. In Communications of the ACM. Volume 31, Number 9, 1988. Google ScholarDigital Library
- S. Albers. Energy-efficient algorithms. Commun. ACM, 53:86--96, May 2010. Google ScholarDigital Library
- N. Bansal, T. Kimbrel, and K. Pruhs. Speed scaling to manage energy and temperature. J. ACM, 54(1), 2007. Google ScholarDigital Library
- R. D. Barve, E. F. Grove, and J. S. Vitter. Simple randomized mergesort on parallel disks. Parallel Computing, 23(4--5):601--631, 1997. Google ScholarDigital Library
- F. Bellosa. The benefits of event-driven enery accounting in power-sensitive systems. In Proc. SIGOPS European Workshop, 2000. Google ScholarDigital Library
- M. A. Bender, G. S. Brodal, R. Fagerberg, R. Jacob, and E. Vicari. Optimal sparse matrix dense vector multiplication in the i/o-model. Theory Comput. Syst., 47(4):934--962, 2010. Google ScholarDigital Library
- J. Chase, D. Anderson, P. Thakar, A. Vahdat, and R. Doyle. Managing energy and server resources in hosting centers. In Proc. ACM SOSP, 2001. Google ScholarDigital Library
- M. Frigo, C. E. Leiserson, H. Prokop, and S. Ramachandran. Cache-oblivious algorithms. In Proceedings of the 40th Annual Symposium on Foundations of Computer Science, FOCS '99, pages 285--297, Washington, DC, USA, 1999. IEEE Computer Society. Google ScholarDigital Library
- M. Goodrich. Data-oblivious external-memory algorithms for the compaction, selection, and sorting of outsourced data. In Proceedings of SPAA, 2011. Google ScholarDigital Library
- A. Gupta. Balls and bins and the power of 2 choices, Spring 2009. http://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/\\15859m-s11/www/lectures/lect0202.pdf.Google Scholar
- T. Horvath, T. Abdelzaher, K. Skadron, and X. Liu. Dynamic voltage scaling in multitier web servers with end-to-end delay control. IEEE Trans. Comput., 56(4):444--458, 2007. Google ScholarDigital Library
- S. Irani, G. Singh, S. K. Shukla, and R. K. Gupta. An overview of the competitive and adversarial approaches to designing dynamic power management strategies. IEEE Trans. Very Large Scale Integr. Syst., 13:1349--1361, December 2005. Google ScholarDigital Library
- E. Kaplan, M. Naor, and O. Reingold. Derandomized constructions of k-wise (almost) independent permutations. Algorithmica, 55(1):113--133, 2009. Google ScholarDigital Library
- K. S. Kedlaya and C. Umans. Fast polynomial factorization and modular composition. SIAM Journal on Computing, 40(6):1767--1802, 2011. Google ScholarDigital Library
- W. Kim, M. S. Gupta, G.-Y. Wei, , and D. Brooks. System level analysis of fast, per-core dvfs using on-chip switching regulators. In Proc. HPCA, 2008.Google Scholar
- D. E. Knuth. The Art of Computer Programming, Volume II: Seminumerical Algorithms. Addison-Wesley, 1969.Google ScholarDigital Library
- R. Koller, A. Verma, and A. Neogi. Wattapp: An application aware power meter for shared data centers. In ICAC, 2010. Google ScholarDigital Library
- V. A. Korthikanti and G. Agha. Towards optimizing energy costs of algorithms for shared memory architectures. In Proc. SPAA, 2010. Google ScholarDigital Library
- V. A. Korthikanti, G. Agha, and M. Greenstreet. On the energy complexity of parallel algorithms. In Proc. ICPP, 2011. Google ScholarDigital Library
- K. Mehlhorn and P. Sanders. Scanning multiple sequences via cache memory. In Algorithmica, 2003.Google Scholar
- M. Mitzenmacher, A. W. Richa, and R. Sitaraman. The power of two random choices: A survey of techniques and results. In in Handbook of Randomized Computing, pages 255--312. Kluwer, 2000.Google Scholar
- S. Muthukrishnan. Data streams: Algorithms and applications. Foundations and Trends in Theoretical Computer Science, 1(2), 2005. Google ScholarDigital Library
- R. Nathuji and K. Schwan. Virtualpower: coordinated power management in virtualized enterprise systems. In Proc. ACM SOSP, 2007. Google ScholarDigital Library
- P. Ranganathan, P. Leech, D. Irwin, and J. Chase. Ensemble-level power management for dense blade servers. In Proc. ISCA, 2006. Google ScholarDigital Library
- M. Thorup. Integer priority queues with decrease key in constant time and the single source shortest paths problem. J. Comput. Syst. Sci., 69(3):330--353, 2004. Google ScholarDigital Library
- A. Vahdat, A. Lebeck, and C. S. Ellis. Every joule is precious: the case for revisiting operating system design for energy efficiency. In Proc. of ACM SIGOPS European workshop, New York, NY, USA, 2000. ACM. Google ScholarDigital Library
- A. Verma, G. Dasgupta, T. Nayak, P. De, and R. Kothari. Server workload analysis for power minimization using consolidation. In Proc. Usenix ATC, 2009. Google ScholarDigital Library
- A. Verma, R. Koller, L. Useche, and R. Rangaswami. Srcmap: energy proportional storage using dynamic consolidation. In Proc. of Usenix FAST, 2010. Google ScholarDigital Library
- J. S. Vitter. Algorithms and data structures for external memory, 2008. Google ScholarDigital Library
- J. S. Vitter and E. A. M. Shriver. Algorithms for parallel memory I: Two-level memories. Algorithmica, 12(2/3):110--147, 1994.Google ScholarDigital Library
- J. S. Vitter and E. A. M. Shriver. Algorithms for parallel memory II: Hierarchical multilevel memories. Algorithmica, 12(2/3):148--169, 1994.Google ScholarDigital Library
- F. F. Yao, A. J. Demers, and S. Shenker. A scheduling model for reduced cpu energy. In FOCS, pages 374--382, 1995. Google ScholarDigital Library
- H. Zeng, C. Ellis, A. Lebeck, and A. Vahdat. Ecosystem: Managing energy as a first class operating system resource. In ASPLOS, 2002. Google ScholarDigital Library
Index Terms
- An energy complexity model for algorithms
Recommendations
On the construction of energy-efficient maximum residual battery capacity broadcast trees in static ad hoc wireless networks
This work considers the problem of broadcast routing in a wireless ad hoc network from the viewpoint of energy efficiency. Each node in a wireless ad hoc network runs on a local energy source which has a limited energy life span. Thus, energy ...
An Energy Efficient Middleware Architecture for Processing Spatial Alarms on Mobile Clients
Time based alarms are used by many on a daily basis. Spatial alarms extend the very same idea to location based triggers, which are fired whenever a mobile user enters the spatial region of the location alarms. Spatial alarms provide critical ...
Perfect Strong Scaling Using No Additional Energy
IPDPS '13: Proceedings of the 2013 IEEE 27th International Symposium on Parallel and Distributed ProcessingEnergy efficiency of computing devices has become a dominant area of research interest in recent years. Most previous work has focused on architectural techniques to improve power and energy efficiency, only a few consider saving energy at the ...
Comments