Operational analysis of processor speed scaling

ABSTRACT

This brief announcement presents a pair of performance laws that bound the change in aggregate job queueing time that results when the processor speed changes in a parallel computing system. Our laws require only lightweight passive external observations of a black-box system and they apply to many commonly employed scheduling policies. By predicting the application-level performance impact of processing speed adjustments in parallel processors, including traditional SMPs and now increasingly ubiquitous multicore processors, our laws address problems ranging from capacity planning to dynamic resource allocation. Finally, our results show that operational analysis---an approach to performance analysis traditionally associated with commercial transaction processing systems---usefully complements existing parallel performance analysis techniques.

REFERENCES

• 1: ACM Digital Library, January 2008. Extensive full-text keyword searches of all past SPAA proceedings for "operational," "Little," "Buzen," etc. yield only a handful of passing references to operational laws. Tracing back-pointers from classic papers such as {7} yields similar results.
• 2: Paul Barham , Boris Dragovic , Keir Fraser , Steven Hand , Tim Harris , Alex Ho , Rolf Neugebauer , Ian Pratt , Andrew Warfield, Xen and the art of virtualization, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
• 3: Gunter Bolch , Stefan Greiner , Hermann de Meer , Kishor Shridharbhai Trivedi, Queueing Networks and Markov Chains, Wiley-Interscience, 2005
• 4: The Condor Project. http://www.cs.wisc.edu/condor/.
• 5: Hewlett-Packard Corp. HP Real User Monitor, January 2008. Search for "Real User Monitor" at http://www.hp.com/.
• 6: VMWare Corporat. VMWare ESX Server 3, January 2008. http://www.vmware.com/products/vi/esx/.
• 7: Peter J. Denning , Jeffrey P. Buzen, The Operational Analysis of Queueing Network Models, ACM Computing Surveys (CSUR), v.10 n.3, p.225-261, Sept. 1978 [doi>10.1145/356733.356735]
• 8: HP, Intel, Microsoft, Phoenix Technologies Ltd., and Toshiba. Advanced configuration and power interface specification (ACPI), October 2006. http://www.acpi.info/spec.htm.
• 9: Ravi Iyer, Ramesh Illikkal, Li Zhao, Srihari Makineni, Don Newell, Jaideep Moses, and Padma Apparao. Datacenter-on-chip architectures: Tera-scale opportunities and challenges. Intel Technical Journal, 11(3):227--238, August 2007.
• 10: Raj Jain. The Art of Computer Systems Performance Analysis. John Wiley & Sons, 1991.
• 11: Terence Kelly, Kai Shen, Alex Zhang, and Christopher Stewart. Operational analysis of parallel servers, April 2008.
• 12: Poonacha Kongetira , Kathirgamar Aingaran , Kunle Olukotun, Niagara: A 32-Way Multithreaded Sparc Processor, IEEE Micro, v.25 n.2, p.21-29, March 2005 [doi>10.1109/MM.2005.35]
• 13: Jim Larus , Ravi Rajwar, Transactional Memory (Synthesis Lectures on Computer Architecture), Morgan & Claypool Publishers, 2007
• 14: Edward D. Lazowska , John Zahorjan , G. Scott Graham , Kenneth C. Sevcik, Quantitative system performance: computer system analysis using queueing network models, Prentice-Hall, Inc., Upper Saddle River, NJ, 1984
• 15: John D.C. Little. A Proof of the Queueing Formula: L = W. Operations Research, 9(3):383--387, May 1961.
• 16: Platform Computing. LSF Scheduler. http://www.platform.com/Products/platform-lsf-family/.
• 17: Christopher Stewart, Terence Kelly, Alex Zhang, and Kai Shen. A dollar from 15 cents: Cross-platform management for internet services. In Proc. USENIX Annual Technical Conference, June 2008.
• 18: Christopher Stewart , Kai Shen, Performance modeling and system management for multi-component online services, Proceedings of the 2nd conference on Symposium on Networked Systems Design & Implementation, p.71-84, May 02-04, 2005
• 19: Texas Memory Systems. RamSan-400 Solid State Disk, January 2008. http://www.superssd.com/products/ramsan-400/.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Modeling techniques

General Terms:
Management, Performance, Theory

Keywords:
acpi, capacity planning, datacenter-on-chip, dynamic resource allocation, internet servers, multi-processor, multicore, operational analysis, p-states, performance modeling, power, queuing, scheduling