Performance prediction for random write reductions: a case study in modeling shared memory programs

ABSTRACT

In this paper, we revisit the problem of performance prediction on shared memory parallel machines, motivated by the need for selecting parallelization strategy for random write reductions. Such reductions frequently arise in data mining algorithms.In our previous work, we have developed a number of techniques for parallelizing this class of reductions. Our previous work has shown that each of the three techniques, full replication, optimized full locking, and cache-sensitive, can outperform others depending upon problem, dataset, and machine parameters. Therefore, an important question is, "Can we predict the performance of these techniques for a given problem, dataset, and machine?".This paper addresses this question by developing an analytical performance model that captures a two-level cache, coherence cache misses, TLB misses, locking overheads, and contention for memory. Analytical model is combined with results from micro-benchmarking to predict performance on real machines. We have validated our model on two different SMP machines. Our results show that our model effectively captures the impact of memory hierarchy (two-level cache and TLB) as well as the factors that limit parallelism (contention for locks, memory contention, and coherence cache misses). The difference between predicted and measured performance is within 20% in almost all cases. Moreover, the model is quite accurate in predicting the relative performance of the three parallelization techniques.

REFERENCES

• 1: A. Agarwal , J. Hennessy , M. Horowitz, An analytical cache model, ACM Transactions on Computer Systems (TOCS), v.7 n.2, p.184-215, May 1989 [doi>10.1145/63404.63407]
• 2: David H. Albonesi , Israel Koren, An analytical model of high performance superscalar-based multiprocessors, Proceedings of the IFIP WG10.3 working conference on Parallel architectures and compilation techniques, p.194-203, June 27-29, 1995, Limassol, Cyprus
• 3: Siddhartha Chatterjee , Erin Parker , Philip J. Hanlon , Alvin R. Lebeck, Exact analysis of the cache behavior of nested loops, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.286-297, June 2001, Snowbird, Utah, United States
• 4: David Culler , Richard Karp , David Patterson , Abhijit Sahay , Klaus Erik Schauser , Eunice Santos , Ramesh Subramonian , Thorsten von Eicken, LogP: towards a realistic model of parallel computation, Proceedings of the fourth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.1-12, May 19-22, 1993, San Diego, California, United States
• 5: Phillip M. Dickens , Philip Heidelberger , David M. Nicol, Parallelized Direct Execution Simulation of Message-Passing Parallel Programs, IEEE Transactions on Parallel and Distributed Systems, v.7 n.10, p.1090-1105, October 1996 [doi>10.1109/71.539740]
• 6: Matthew I. Frank , Anant Agarwal , Mary K. Vernon, LoPC: modeling contention in parallel algorithms, Proceedings of the sixth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.276-287, June 18-21, 1997, Las Vegas, Nevada, United States
• 7: Somnath Ghosh , Margaret Martonosi , Sharad Malik, Cache miss equations: a compiler framework for analyzing and tuning memory behavior, ACM Transactions on Programming Languages and Systems (TOPLAS), v.21 n.4, p.703-746, July 1999 [doi>10.1145/325478.325479]
• 8: John L. Hennessy , David A. Patterson, Computer architecture (2nd ed.): a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• 9: Cristina Hristea , Daniel Lenoski , John Keen, Measuring memory hierarchy performance of cache-coherent multiprocessors using micro benchmarks, Proceedings of the 1997 ACM/IEEE conference on Supercomputing (CDROM), p.1-12, November 15-21, 1997, San Jose, CA [doi>10.1145/509593.509638]
• 10: Ruoming Jin and Gagan Agrawal. A middleware for developing parallel data mining implementations. In Proceedings of the first SIAM conference on Data Mining, April 2001.
• 11: Ruoming Jin and Gagan Agrawal. Shared Memory Parallelization of Data Mining Algorithms: Techniques, Programming Interface, and Performance. In Proceedings of the second SIAM conference on Data Mining, April 2002.
• 12: Magnus Karlsson , Per Stenström, An analytical model of the working-set sizes in decision-support systems, Proceedings of the 2000 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.275-285, June 18-21, 2000, Santa Clara, California, United States
• 13: Leonard Kleinrock, Theory, Volume 1, Queueing Systems, Wiley-Interscience, 1975
• 14: Larry W. McVoy and Carl Staelin. lmbench: Portable tools for performance analysis. In USENIX Annual Technical Conference, pages 279-294, 1996.
• 15: David Ofelt , John L. Hennessy, Efficient performance prediction for modern microprocessors, Proceedings of the 2000 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.229-239, June 18-21, 2000, Santa Clara, California, United States
• 16: Alan Jay Smith , Rafael H. Saavedra, Measuring Cache and TLB Performance and Their Effect on Benchmark Runtimes, IEEE Transactions on Computers, v.44 n.10, p.1223-1235, October 1995 [doi>10.1109/12.467697]
• 17: Rafael H. Saavedra , Alan J. Smith, Analysis of benchmark characteristics and benchmark performance prediction, ACM Transactions on Computer Systems (TOCS), v.14 n.4, p.344-384, Nov. 1996 [doi>10.1145/235543.235545]
• 18: Daniel J. Sorin , Vijay S. Pai , Sarita V. Adve , Mary K. Vernon , David A. Wood, Analytic evaluation of shared-memory systems with ILP processors, Proceedings of the 25th annual international symposium on Computer architecture, p.380-391, June 27-July 02, 1998, Barcelona, Spain
• 19: David Sundaram-Stukel , Mary K. Vernon, Predictive analysis of a wavefront application using LogGP, Proceedings of the seventh ACM SIGPLAN symposium on Principles and practice of parallel programming, p.141-150, May 04-06, 1999, Atlanta, Georgia, United States
• 20: Jory Tsai , Anant Agarwal, Analyzing multiprocessor cache behavior through data reference modeling, Proceedings of the 1993 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.236-247, May 10-14, 1993, Santa Clara, California, United States
• 21: M. K. Vernon , E. D. Lazowska , J. Zahorjan, An accurate and efficient performance analysis technique for multiprocessor snooping cache-consistency protocols, Proceedings of the 15th Annual International Symposium on Computer architecture, p.308-315, May 30-June 02, 1988, Honolulu, Hawaii, United States
• 22: Stephen J. Von Worley , Alan J. Smith, Microbenchmarking and Performance Prediction for Parallel, University of California at Berkeley, Berkeley, CA, 1995