Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

We report on a model of the distribution of job submission interarrival times in supercomputers.Interarrival times are modeled as a consequence of a complicated set of decisions between users, the queuing algorithm, and other policies.This cascading hierarchy of decision-making processes leads to a particular kind of heavy-tailed distribution.Specifically, hierarchically constrained systems suggest that fatter tails are due to more levels coming into play in the overall decision-making process.The key contribution of this paper is that heavier tials resulting from more complex decision-making processes, that ismore hierarchical levels, will lead to overall worse performance, even when the average interarrival time is the same.Finally, we offer some suggestions for how to overcome these issues and the tradeoffs involved.

REFERENCES

• 1: [1] http://www.llnl.gov/asci/
• 2: [2] J. Beran, R. Sherman, M. S. Taqqu, and W. Willinger, "Long-Range Dependence in variable-Bit-Rate Video Traffic", IEEE Transactions on communication, vol. 43, no. 2/3/4 Feb./Mar./Apr. 1995, pp. 1566-1579.
• 3: Scott H. Clearwater , Stephen D. Kleban, ASCI Queuing Systems: Overview and Comparisons, Proceedings of the 16th International Parallel and Distributed Processing Symposium, p.49, April 15-19, 2002
• 4: [4] DPCS Manual (unpublished) and Moe Jette and Bob Wood private communication, 2001-2002.
• 5: [5] D. Feitelson, "Sensitivity of parallel Job Scheduling to Fat-Tailed Distribution", Technical Report 2000-44, Inst. Computer Science, The Hebrew University of Jerusalem, Oct 2000 and http://www/cs/huji/ac.il/-feit/pub.html.
• 6: [6] U. Frisch and D. Sornette, "Extreme Deviations and Application", Phys. I France, vol. 7, 1997, pp. 1155-1171.
• 7: Steven D. Gribble , Gurmeet Singh Manku , Drew Roselli , Eric A. Brewer , Timothy J. Gibson , Ethan L. Miller, Self-similarity in file systems, Proceedings of the 1998 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, p.141-150, June 22-26, 1998, Madison, Wisconsin, United States
• 8: [8] M. Harchol-Balter, "The Effect of Heavy-Tailed Job Size Distribution on Computer System Design", Proceedings of ASA-IMS Conference on Application of Heavy Tailed Distribution in Economics, Engineering and Statistics, June, 1999.
• 9: J. Kay , P. Lauder, A fair share scheduler, Communications of the ACM, v.31 n.1, p.44-55, Jan. 1988 [doi>10.1145/35043.35047]
• 10: [10] J. Klafter and M. F. Shelsigner, "On the relationship among three theories of relaxation in disordered systems", Proceeding of the National Academy of Science, vol. 83, Feb. 1986, pp. 848-851.
• 11: Stephen D. Kleban , Scott H. Clearwater, Quelling Queue Storms, Proceedings of the 12th IEEE International Symposium on High Performance Distributed Computing, p.162, June 22-24, 2003
• 12: [12] S. Kleban and S. Clearwater, "A Market-Based Architecture for Supercomputer Resource Management", Proceedings of the ACM/IEEE Super Computing 2001 (SC-2001). 2001.
• 13: [13] R. Kohlrausch, "Theories des electrischen Rückstandes in der Leidner Flasche", Pogg. Ann Phys., vol. 91, 1854, pp. 179- 214 (in German).
• 14: [14] J. Laherrere and D. Sornette, "Stretched exponential distributions in Nature and Economy: 'Fat tails' with characteristic tails", European Physics Journal B, vol. 2, 1998, pp. 525-539.
• 15: [15] "LSF Batch Administrator's Guide, Sixth Edition", Platform Computing Corporation, 1998.
• 16: [16] http://umbc7.umbc.edu/nqs/nqsguide.html.
• 17: [17] R. G. Palmer, D. L. Stein, E. Abrahams, and P. W. Anderson, "Models of Hierarchically Constrained Dynamics for Glassy Systems", Phy. Rev. Lett. vol. 53, no. 10, Sep. 1984, pp. 958-961.
• 18: 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]
• 19: Joseph Skovira , Waiman Chan , Honbo Zhou , David A. Lifka, The EASY - LoadLeveler API Project, Proceedings of the Workshop on Job Scheduling Strategies for Parallel Processing, p.41-47, April 16, 1996
• 20: [20] J. Voldman, B.B. Mandelbrot, L.W. Hoevel, J. Knight, and P. Rosenfeld, "Fractal Nature of Software-Cache Interaction", IBM Journal of Research and Development, vol. 27, no. 6, Nov. 1981, pp. 164-170.
• 21: [21] W. Willinger, R. Govindan, S. Jamin, V. Paxson, and S. Shenker, "Scaling phenomena in the Internet: Critically examination criticality", Proceeding of the National Academy of Science, vol. 99, Feb. 2002, pp. 2573-2580.
• 22: [22] W. Willinger, M. Taqqu, and A. Erramilli, "A bibliographical guide to self-similiar traffic and performance modeling for modern high-speed networks", Stochastic Networks, F. P. Kelly, S. Zachary and I. Ziedins (eds.), Oxford University Press, Oxford, 1996, pp. 339-366.

INDEX TERMS

Keywords:
hierarchy, relaxation process, interarrival, ASCI queuing, dynamics