A unified model for multicore architectures

ABSTRACT

With the advent of multicore and many core architectures, we are facing a problem that is new to parallel computing, namely, the management of hierarchical parallel caches. One major limitation of all earlier models is their inability to model multicore processors with varying degrees of sharing of caches at different levels. We propose a unified memory hierarchy model that addresses these limitations and is an extension of the MHG model developed for a single processor with multi-memory hierarchy. We demonstrate that our unified framework can be applied to a number of multicore architectures for a variety of applications. In particular, we derive lower bounds on memory traffic between different levels in the hierarchy for financial and scientific computations. We also give a multicore algorithms for a financial application that exhibits a constant-factor optimal amount of memory traffic between different cache levels. We implemented the algorithm on a multicore system with two Quad-Core Intel Xeon 5310 1.6GHz processors having a total of 8 cores. Our algorithms outperform compiler optimized and auto-parallelized code by a factor of up to 7.3.

REFERENCES

• 1: Intel's multicore architecture briefing, 2008. http://www.intel.com/pressroom/archive/releases/20080317fact.htm.
• 2: Terflops research chip, 2008. http://techresearch.intel.com/articles/Tera-Scale/1449.htm.
• 3: TILE64 processor family, 2008. http://www.tilera.com/products/processors.php.
• 4: UltraSPARC T2 Processor -- Overview, 2008. http://www.sun.com/processors/UltraSPARC-T2/.
• 5: R. C. Agarwal , F. G. Gustavson , M. Zubair, Exploiting functional parallelism of POWER2 to design high-performance numerical algorithms, IBM Journal of Research and Development, v.38 n.5, p.563-576, Sept. 1994
• 6: A. Aggarwal , B. Alpern , A. Chandra , M. Snir, A model for hierarchical memory, Proceedings of the nineteenth annual ACM symposium on Theory of computing, p.305-314, January 1987, New York, New York, United States [doi>10.1145/28395.28428]
• 7: Alok Aggarwal , Ashok K. Chandra , Marc Snir, Hierarchical memory with block transfer, Proceedings of the 28th Annual Symposium on Foundations of Computer Science (sfcs 1987), p.204-216, October 12-14, 1987 [doi>10.1109/SFCS.1987.31]
• 8: Alok Aggarwal , Ashok K. Chandra , Marc Snir, Communication complexity of PRAMs, Theoretical Computer Science, v.71 n.1, p.3-28, 13 March 1990 [doi>10.1016/0304-3975(90)90188-N]
• 9: Alok Aggarwal , Jeffrey,S. Vitter, The input/output complexity of sorting and related problems, Communications of the ACM, v.31 n.9, p.1116-1127, Sept. 1988 [doi>10.1145/48529.48535]
• 10: B. Alpern, L. Carter, E. Feig, and T. Selker. The uniform memory hierarchy model of computation. Algorithmica, 12(2/3):72--109, 1994.
• 11: B. Alpern, L. Carter, and J. Ferrante. Modeling parallel computers as memory hierarchies. In Proceedings of the 1993 Conference on Programming Models for Massively Parallel Computers, pages 116--123, 1993.
• 12: A. Bar-Noy , S. Kipnis, Designing broadcasting algorithms in the Postal Model for message-passing systems, Mathematical Systems Theory, v.27 n.5, p.431-452, Sept./Oct. 1994
• 13: J. C. Cox, S. A. Ross, and M. Rubinstein. Option pricing: A simplified approach. Journal of Financial Economics, 7(3):229--263, September 1979.
• 14: 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, ACM SIGPLAN Notices, v.28 n.7, p.1-12, July 1993
• 15: Jack J. Dongarra , Jeremy Du Croz , Sven Hammarling , Richard J. Hanson, An extended set of FORTRAN basic linear algebra subprograms, ACM Transactions on Mathematical Software (TOMS), v.14 n.1, p.1-17, March 1988 [doi>10.1145/42288.42291]
• 16: Jack J. Dongarra , Jeremy Du Croz , Sven Hammarling , Richard J. Hanson, Algorithm 656: an extended set of basic linear algebra subprograms: model implementation and test programs, ACM Transactions on Mathematical Software (TOMS), v.14 n.1, p.18-32, March 1988 [doi>10.1145/42288.42292]
• 17: Steven Fortune , James Wyllie, Parallelism in random access machines, Proceedings of the tenth annual ACM symposium on Theory of computing, p.114-118, May 01-03, 1978, San Diego, California, United States [doi>10.1145/800133.804339]
• 18: Kazushige Goto , Robert A. van de Geijn, Anatomy of high-performance matrix multiplication, ACM Transactions on Mathematical Software (TOMS), v.34 n.3, p.1-25, May 2008 [doi>10.1145/1356052.1356053]
• 19: Michael Gschwind , H. Peter Hofstee , Brian Flachs , Martin Hopkins , Yukio Watanabe , Takeshi Yamazaki, Synergistic Processing in Cell's Multicore Architecture, IEEE Micro, v.26 n.2, p.10-24, March 2006 [doi>10.1109/MM.2006.41]
• 20: Anshul Gupta , Fred G. Gustavson , Mahesh Joshi , Sivan Toledo, The design, implementation, and evaluation of a symmetric banded linear solver for distributed-memory parallel computers, ACM Transactions on Mathematical Software (TOMS), v.24 n.1, p.74-101, March 1998 [doi>10.1145/285861.285865]
• 21: F. G. Gustavson, High-performance linear algebra algorithms using new generalized data structures for matrices, IBM Journal of Research and Development, v.47 n.1, p.31-55, January 2003
• 22: John L. Hennessy , David A. Patterson, Computer architecture (2nd ed.): a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• 23: Hong Jia-Wei , H. T. Kung, I/O complexity: The red-blue pebble game, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.326-333, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802486]
• 24: Dror Irony , Sivan Toledo , Alexander Tiskin, Communication lower bounds for distributed-memory matrix multiplication, Journal of Parallel and Distributed Computing, v.64 n.9, p.1017-1026, September 2004 [doi>10.1016/j.jpdc.2004.03.021]
• 25: Ben H. H. Juurlink , Harry A. G. Wijshoff, The Parallel Hierarchical Memory Model, Proceedings of the 4th Scandinavian Workshop on Algorithm Theory, p.240-251, July 06-08, 1994
• 26: Bo Kågström , Per Ling , Charles van Loan, GEMM-based level 3 BLAS: high-performance model implementations and performance evaluation benchmark, ACM Transactions on Mathematical Software (TOMS), v.24 n.3, p.268-302, Sept. 1998 [doi>10.1145/292395.292412]
• 27: Y. Kwok. Mathematical Models of Financial Derivatives. Springer-Verlag, Singapore, 1998.
• 28: Zhiyong Li , P. H. Mills , J. H. Reif, Models and resource metrics for parallel and distributed computation, Proceedings of the 28th Hawaii International Conference on System Sciences (HICSS'95), p.51, January 04-07, 1995
• 29: John E. Savage, Extending the Hong-Kung Model to Memory Hierarchies, Proceedings of the First Annual International Conference on Computing and Combinatorics, p.270-281, August 24-26, 1995
• 30: John E. Savage, Models of Computation: Exploring the Power of Computing, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 31: J. E. Savage and M. Zubair. Cache-optimal algorithms for option pricing, 2008. Submitted for publication.
• 32: J. E. Savage and M. Zubair. Memory hierarchy issues in multicore architectures. Technical Report CS-08-08, Department of Computer Science, Brown University, 2008.
• 33: M. Tremblay and S. Chaudhry. A third-generation 65nm 16-core 32-thread plus 32-scout-thread CMT SPARC© processor, 2008. http://blogs.sun.com/HPC/resource/RockISSCC08.pdf.
• 34: Leslie G. Valiant, A bridging model for parallel computation, Communications of the ACM, v.33 n.8, p.103-111, Aug. 1990 [doi>10.1145/79173.79181]
• 35: J. S. Vitter , E. A. M. Shriver, Optimal disk I/O with parallel block transfer, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.159-169, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100234]
• 36: J. S. Vitter and E. A. M. Shriver. Algorithms for parallel memory I: two-level memories. Algorithmica, 12(2/3):110--147, 1994.
• 37: J. S. Vitter and E. A. M. Shriver. Algorithms for parallel memory II: hierarchical multilevel memories. Algorithmica, 12(2/3):148--169, 1994.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE

General Terms:
Algorithms, Experimentation, Performance

Keywords:
memory hierarchy, multicore