Locality of sampling and diversity in parallel system workloads

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Locality of sampling and diversity in parallel system workloads

Full text

Pdf (635 KB)

Source

International Conference on Supercomputing archive
Proceedings of the 21st annual international conference on Supercomputing table of contents

Seattle, Washington

SESSION: Workload characterization table of contents

Pages: 53 - 63

Year of Publication: 2007

ISBN:978-1-59593-768-1

Author

Dror G. Feitelson

The Hebrew University, Jerusalem, Israel

Sponsor

SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 41, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1274971.1274982 What is a DOI?

ABSTRACT

Observing the workload on a computer system during a short (but not too short) time interval may lead to distributions that are significantly different from those that would be observed over much longer intervals. Rather than describing such phenomena using involved non-stationary models, we propose a simple global distribution coupled with a localized sampling process. We quantify the effect by the maximal deviation between the global distribution and the distribution as observed over a limited slice of time, and find that in real workload data from parallel supercomputers this deviation is significantly larger than would be observed at random. Likewise, we find that the workloads at different sites also differ from each other. These findings motivate the development of adaptive systems, which adjust their parameters as they learn about their workloads, and also the development of parametrized workload models that exhibit such locality of sampling, which are required in order to evaluate adaptive systems.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Arnold O. Allen, Probability, Statistics, and Queueing Theory with Computer Science Applications, Academic Press, Inc., Orlando, FL, 1978
	2	Virgílio Almeida , Azer Bestavros , Mark Crovella , Adriana de Oliveira, Characterizing reference locality in the WWW, Proceedings of the fourth international conference on on Parallel and distributed information systems, p.92-107, December 18-20, 1996, Miami Beach, Florida, United States
	3	M. F. Arlitt and C. L. Williamson, "A synthetic workload model for Internet Mosaic traffic". In Summer Computer Simulation Conf., pp. 852--857, Jul 1995.
	4	Maria Calzarossa , Giuseppe Serazzi, Construction and use of multiclass workload models, Performance Evaluation, v.19 n.4, p.341-352, April 1994 [doi>10.1016/0166-5316(94)90046-9]
	5	W. Cirne , F. Berman, A comprehensive model of the supercomputer workload, Proceedings of the Workload Characterization, 2001. WWC-4. 2001 IEEE International Workshop on, p.140-148, December 02-02, 2001 [doi>10.1109/WWC.2001.2]
	6	Peter J. Denning, The locality principle, Communications of the ACM, v.48 n.7, July 2005 [doi>10.1145/1070838.1070856]
	7	Allen B. Downey, A parallel workload model and its implications for processor allocation, Cluster Computing, v.1 n.1, p.133-145, 1998 [doi>10.1023/A:1019077214124]
	8	B. Efron, "Computers and the theory of statistics: thinking the unthinkable". SIAM Rev. <b>21(4)</b>, pp. 460--480, Oct 1979.
	9	B. Efron and G. Gong, "A leisurely look at the bootstrap, the jackknife, and cross-validation". The American Statistician <b>37(1)</b>, pp. 36--48, Feb 1983.
	10	Dror G. Feitelson, Packing Schemes for Gang Scheduling, Proceedings of the Workshop on Job Scheduling Strategies for Parallel Processing, p.89-110, April 16, 1996
	11	Dror G. Feitelson , Michael Naaman, Self-Tuning Systems, IEEE Software, v.16 n.2, p.52-60, March 1999 [doi>10.1109/52.754053]
	12	D. G. Feitelson and D. Tsafrir, "Workload sanitation for performance evaluation". In IEEE Intl. Symp. Performance Analysis Syst. & Software., pp. 221--230, Mar 2006.
	13	Domenico Ferrari, On the foundations of artificial workload design, Proceedings of the 1984 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.8-14, January 1984
	14	Richard Gibbons, A Historical Application Profiler for Use by Parallel Schedulers, Proceedings of the Job Scheduling Strategies for Parallel Processing, p.58-77, April 05, 1997
	15	F. Hernández-Campos, K. Jeffay, and F. D. Smith, "Tracking the evolution of web traffic: 1995-2003". In 11th Modeling, Anal. & Simulation of Comput. & Telecomm. Syst., pp. 16--25, Oct 2003.
	16	Steven Hotovy, Workload Evolution on the Cornell Theory Center IBM SP2, Proceedings of the Workshop on Job Scheduling Strategies for Parallel Processing, p.27-40, April 16, 1996
	17	R. Jain, The Art of Computer Systems Performance Analysis. John Wiley & Sons, 1991.
	18	Joefon Jann , Pratap Pattnaik , Hubertus Franke , Fang Wang , Joseph Skovira , Joseph Riordan, Modeling of Workload in MPPs, Proceedings of the Job Scheduling Strategies for Parallel Processing, p.95-116, April 05, 1997
	19	L. Kleinrock, Queueing Systems, Vol II: Computer Applications. John Wiley & Sons, 1976.
	20	Averill M. Law , W. David Kelton, Simulation Modeling and Analysis, McGraw-Hill Higher Education, 1997
	21	Will E. Leland , Murad S. Taqqu , Walter Willinger , Daniel V. Wilson, On the self-similar nature of Ethernet traffic (extended version), IEEE/ACM Transactions on Networking (TON), v.2 n.1, p.1-15, Feb. 1994 [doi>10.1109/90.282603]
	22	Uri Lublin , Dror G. Feitelson, The workload on parallel supercomputers: modeling the characteristics of rigid jobs, Journal of Parallel and Distributed Computing, v.63 n.11, p.1105-1122, November 2003 [doi>10.1016/S0743-7315(03)00108-4]
	23	D. Michie, "Memo functions and machine learning". Nature <b>218(5136)</b>, pp. 19--22, Apr 6 1968.
	24	Thu D. Nguyen , Raj Vaswani , John Zahorjan, Parallel Application Characteristics for Multiprocessor Scheduling Policy Design, Proceedings of the Workshop on Job Scheduling Strategies for Parallel Processing, p.175-199, April 16, 1996
	25	Vern Paxson , Sally Floyd, Wide area traffic: the failure of Poisson modeling, IEEE/ACM Transactions on Networking (TON), v.3 n.3, p.226-244, June 1995 [doi>10.1109/90.392383]
	26	L. R. Rabiner, "A tutorial on hidden Markov models and selected applications in speech recognition". Proc. IEEE <b>77(2)</b>, pp. 257--286, Feb 1989.
	27	S. V. Raghavan , N. Swaminathan , J. Srinivasan, Predicting Behavior Patterns Using Adaptive Workload Models, Proceedings of the 7th International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems, p.226, March 24-28, 1999
	28	W. Shi, M. H. MacGregor, and P. Gburzynski, "Synthetic trace generation for the Internet: an integrated model". In Intl. Symp. Performance Evaluation of Computer and Telecommunication Syst., pp. 471--477, Jul 2004.
	29	Warren Smith , Ian T. Foster , Valerie E. Taylor, Predicting Application Run Times Using Historical Information, Proceedings of the Workshop on Job Scheduling Strategies for Parallel Processing, p.122-142, March 30, 1998
	30	B. Song, C. Ernemann, and R. Yahyapour, "Parallel computer workload modeling with Markov chains". In Job Scheduling Strategies for Parallel Processing, pp. 47--62, Springer Verlag LNCS vol. 3277, 2004.
	31	Jeffrey R. Spirn, Program Behavior: Models and Measurements, Elsevier Science Inc., New York, NY, 1977
	32	Achim Streit, A Self-Tuning Job Scheduler Family with Dynamic Policy Switching, Revised Papers from the 8th International Workshop on Job Scheduling Strategies for Parallel Processing, p.1-23, July 24, 2002
	33	David Talby , Dror G. Feitelson, Improving and Stabilizing Parallel Computer Performance Using Adaptive Backfilling, Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS'05) - Papers, p.84.1, April 04-08, 2005 [doi>10.1109/IPDPS.2005.252]
	34	D. Thiebaut , J. Wolf , H. Stone, Corrigendum to "Synthetic Traces for Trace-Driven Simulation of Cache Memories", IEEE Transactions on Computers, v.42 n.5, p.635-636, May 1993 [doi>10.1109/12.223685]
	35	Mengzhi Wang , Anastassia Ailamaki , Christos Faloutsos, Capturing the spatio-temporal behavior of real traffic data, Performance Evaluation, v.49 n.1-4, p.147-163, September 2002 [doi>10.1016/S0166-5316(02)00108-6]
	36	Paul R. Wilson , Mark S. Johnstone , Michael Neely , David Boles, Dynamic Storage Allocation: A Survey and Critical Review, Proceedings of the International Workshop on Memory Management, p.1-116, September 27-29, 1995
	37	L. Zhang, Z. Liu, A. Riabov, M. Schulman, C. Xia, and F. Zhang, "A comprehensive toolset for workload characterization, performance modeling, and online control". In Computer Performance Evaluations, Modelling Techniques and Tools, P. Kemper and W. H. Sanders (eds.), pp. 63--77, Springer-Verlag LNCS vol. 2794, Sep 2003.
	38	Qi Zhang , Alma Riska , Wei Sun , Evgenia Smirni , Gianfranco Ciardo, Workload-Aware Load Balancing for Clustered Web Servers, IEEE Transactions on Parallel and Distributed Systems, v.16 n.3, p.219-233, March 2005 [doi>10.1109/TPDS.2005.38]