PB-LRU: a self-tuning power aware storage cache replacement algorithm for conserving disk energy

ABSTRACT

Energy consumption is an important concern at data centers, where storage systems consume a significant fraction of the total energy. A recent study proposed power-aware storage cache management to provide more opportunities for the underlying disk power management scheme to save energy. However, the on-line algorithm proposed in that study requires cumbersome parameter tuning for each workload and is therefore difficult to apply to real systems.This paper presents a new power-aware on-line algorithm called PB-LRU (Partition-Based LRU) that requires little parameter tuning. Our results with both real system and synthetic workloads show that PB-LRU without any parameter tuning provides similar or even better performance and energy savings than the previous power-aware algorithm with the best parameter setting for each workload.

REFERENCES

• 1: Power, heat, and sledgehammer. White paper, Maximum Institution Inc., http://www.max-t.com/downloads/ whitepapers/ SledgehammerPowerHeat20411.pdf, 2002.
• 2: Pat Bohrer , Elmootazbellah N. Elnozahy , Tom Keller , Michael Kistler , Charles Lefurgy , Chandler McDowell , Ram Rajamony, The case for power management in web servers, Power aware computing, Kluwer Academic Publishers, Norwell, MA, 2002
• 3: Enrique V. Carrera , Eduardo Pinheiro , Ricardo Bianchini, Conserving disk energy in network servers, Proceedings of the 17th annual international conference on Supercomputing, June 23-26, 2003, San Francisco, CA, USA [doi>10.1145/782814.782829]
• 4: Z. Chen, Y. Zhou, and K. Li. Eviction-based cache placement for storage caches. In Usenix Technical Conference, 2003.
• 5: Dennis Colarelli , Dirk Grunwald, Massive arrays of idle disks for storage archives, Proceedings of the 2002 ACM/IEEE conference on Supercomputing, p.1-11, November 16, 2002, Baltimore, Maryland
• 6: F. Douglis, R. Caceres, M. F. Kaashoek, K. Li, B. Marsh, and J. A. Tauber. Storage alternatives for mobile computers. In OSDI, pages 25--37, 1994.
• 7: Fred Douglis , P. Krishnan , Brian N. Bershad, Adaptive Disk Spin-down Policies for Mobile Computers, Proceedings of the 2nd Symposium on Mobile and Location-Independent Computing, p.121-137, April 10-11, 1995
• 8: F. Douglis, P. Krishnan, and B. Marsh. Thwarting the power-hungry disk. In USENIX Winter, pages 292--306, 1994.
• 9: E. N. Elnozahy, M. Kistler, and R. Rajamony. Energy-efficient server clusters. In the Second Workshop on Power Aware Computing Systems(held in conjunction with HPCA-2002), Feb 2002.
• 10: EMC Corporation. Symmetrix 3000 and 5000 Enterprise Storage Systems product description guide. http://www.emc.com/products/product pdfs/pdg/symm_3_5_pdg.pdf, 1999.
• 11: G. R. Ganger, B. L. Worthington, and Y. N. Patt. The DiskSim simulation environment - version 2.0 reference manual.
• 12: Chris Gniady , Y Charlie Hu , Yung-Hsiang Lu, Program Counter Based Techniques for Dynamic Power Management, Proceedings of the 10th International Symposium on High Performance Computer Architecture, p.24, February 14-18, 2004 [doi>10.1109/HPCA.2004.10021]
• 13: R. A. Golding, P. B. II, C. Staelin, T. Sullivan, and J. Wilkes. Idleness is not sloth. In USENIX Winter, pages 201--212, 1995.
• 14: Paul M. Greenawalt, Modeling Power Management for Hard Disks, Proceedings of the Second International Workshop on Modeling, Analysis, and Simulation On Computer and Telecommunication Systems, p.62-66, January 31-February 02, 1994
• 15: Sudhanva Gurumurthi , Anand Sivasubramaniam , Mahmut Kandemir , Hubertus Franke, DRPM: dynamic speed control for power management in server class disks, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 16: S. Gurumurthi, J. Zhang, A. Sivasubramaniam, M. Kandemir, H. Franke, N. Vijaykrishnan, and M. Irwin. Interplay of energy and performance for disk arrays running transaction processing workloads. In Proceedings of the International Symposium on Performance Analysis of Systems and Software (ISPASS), pages 123--132, Mar. 2003.
• 17: T. Heath, B. Diniz, E. V. Carrera, W. M. Jr., and R. Bianchini. Self-configuring heterogeneous server clusters. In COLP'03, Sept. 2003.
• 18: Taliver Heath , Eduardo Pinheiro , Jerry Hom , Ulrich Kremer , Ricardo Bianchini, Application Transformations for Energy and Performance-Aware Device Management, Proceedings of the 2002 International Conference on Parallel Architectures and Compilation Techniques, p.121-130, September 22-25, 2002
• 19: David P. Helmbold , Darrell D. E. Long , Tracey L. Sconyers , Bruce Sherrod, Adaptive disk spin—down for mobile computers, Mobile Networks and Applications, v.5 n.4, p.285-297, Dec. 2000 [doi>10.1023/A:1019129116852]
• 20: Mark Donald Hill , Alan Jay Smith, Aspects of cache memory and instruction buffer performance, 1987
• 21: M. D. Hill , A. J. Smith, Evaluating Associativity in CPU Caches, IEEE Transactions on Computers, v.38 n.12, p.1612-1630, December 1989 [doi>10.1109/12.40842]
• 22: IBM. IBM Enterprise Storage Server. www.storage.ibm.com/hardsoft/products/ess/ess.htm IBM Corporation, 1999.
• 23: S. Irani, S. Shukla, and R. Gupta. Competitive analysis of dynamic power management strategies for systems with multiple power saving states. Technical report, UCI-ICS, Sept 2001.
• 24: Theodore Johnson , Dennis Shasha, 2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm, Proceedings of the 20th International Conference on Very Large Data Bases, p.439-450, September 12-15, 1994
• 25: J. Kim, J. Choi, J. Kim, S. Noh, S. Min, Y. Cho, and C. Kim. A low-overhead high-performance unified buffer management scheme that exploits sequential and looping references. OSDI, 2000.
• 26: P. Krishnan, P. M. Long, and J. S. Vitter. Adaptive disk spindown via optimal rent-to-buy in probabilistic environments. In 12th International Conference on Machine Learning, 1995.
• 27: Scott T. Leutenegger , Daniel Dias, A modeling study of the TPC-C benchmark, ACM SIGMOD Record, v.22 n.2, p.22-31, June 1, 1993
• 28: K. Li, R.Kumpf, P.Horton, and T.E. Anderson. A quantitative analysis of disk drive power management in portable computers. In USENIX Winter, 1994.
• 29: Yung-Hsiang Lu , Giovanni De Micheli, Comparing System-Level Power Management Policies, IEEE Design & Test, v.18 n.2, p.10-19, March 2001 [doi>10.1109/54.914592]
• 30: Silvano Martello , Paolo Toth, Knapsack problems: algorithms and computer implementations, John Wiley & Sons, Inc., New York, NY, 1990
• 31: R.L. Mattson, J.Gecsei, D.R. Slutz, and I.L. Traiger. Evaluation techniques for storage hierarchies. IBM Systems Journal, 9(2):78--117, 1970.
• 32: Nimrod Megiddo , Dharmendra S. Modha, ARC: A Self-Tuning, Low Overhead Replacement Cache, Proceedings of the 2nd USENIX Conference on File and Storage Technologies, March 31-31, 2003, San Francisco, CA
• 33: B.Moore. Taking the data center power and cooling challenge. Energy User News, August 27th, 2002.
• 34: F.Moore. More power needed. Energy User News, Nov 25th, 2002.
• 35: A. E. Papathanasiou , M. L. Scott, Increasing Disk Burstiness for Energy Efficiency, University of Rochester, Rochester, NY, 2002
• 36: R. H. Patterson , G. A. Gibson , E. Ginting , D. Stodolsky , J. Zelenka, Informed prefetching and caching, Proceedings of the fifteenth ACM symposium on Operating systems principles, p.79-95, December 03-06, 1995, Copper Mountain, Colorado, United States
• 37: Eduardo Pinheiro , Ricardo Bianchini, Energy conservation techniques for disk array-based servers, Proceedings of the 18th annual international conference on Supercomputing, June 26-July 01, 2004, Malo, France [doi>10.1145/1006209.1006220]
• 38: E. Pinheiro, R. Bianchini, E. V. Carrera, and T. Heath. Load balancing and unbalancing for power and performance in cluster-based systems. COLP'01, 2001.
• 39: Wen-Hann Wang , Jean-Loup Baer, Efficient trace-driven simulation method for cache performance analysis, Proceedings of the 1990 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.27-36, April 1990, Univ. of Colorado, Boulder, Colorado, United States
• 40: Andreas Weissel , Björn Beutel , Frank Bellosa, Cooperative I/O: a novel I/O semantics for energy-aware applications, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060301]
• 41: Theodore M. Wong , John Wilkes, My Cache or Yours? Making Storage More Exclusive, Proceedings of the General Track: 2002 USENIX Annual Technical Conference, p.161-175, June 10-15, 2002
• 42: John Zedlewski , Sumeet Sobti , Nitin Garg , Fengzhou Zheng , Arvind Krishnamurthy , Randolph Wang, Modeling Hard-Disk Power Consumption, Proceedings of the 2nd USENIX Conference on File and Storage Technologies, March 31-31, 2003, San Francisco, CA
• 43: Yuanyuan Zhou , Angelos Bilas , Suresh Jagannathan , Cezary Dubnicki , James F. Philbin , Kai Li, Experiences with VI communication for database storage, Proceedings of the 29th annual international symposium on Computer architecture, p.257, May 25-29, 2002, Anchorage, Alaska
• 44: Yuanyuan Zhou , James Philbin , Kai Li, The Multi-Queue Replacement Algorithm for Second Level Buffer Caches, Proceedings of the General Track: 2002 USENIX Annual Technical Conference, p.91-104, June 25-30, 2001
• 45: Qingbo Zhu , Francis M. David , Christo F. Devaraj , Zhenmin Li , Yuanyuan Zhou , Pei Cao, Reducing Energy Consumption of Disk Storage Using Power-Aware Cache Management, Proceedings of the 10th International Symposium on High Performance Computer Architecture, p.118, February 14-18, 2004 [doi>10.1109/HPCA.2004.10022]

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS

General Terms:
Algorithms, Experimentation

Keywords:
cache management, disk storage, power management