Comparing memory systems for chip multiprocessors

ABSTRACT

There are two basic models for the on-chip memory in CMP systems:hardware-managed coherent caches and software-managed streaming memory. This paper performs a direct comparison of the two modelsunder the same set of assumptions about technology, area, and computational capabilities. The goal is to quantify how and when they differ in terms of performance, energy consumption, bandwidth requirements, and latency tolerance for general-purpose CMPs. We demonstrate that for data-parallel applications, the cache-based and streaming models perform and scale equally well. For certain applications with little data reuse, streaming scales better due to better bandwidth use and macroscopic software prefetching. However, the introduction of techniques such as hardware prefetching and non-allocating stores to the cache-based model eliminates the streaming advantage. Overall, our results indicate that there is not sufficient advantage in building streaming memory systems where all on-chip memory structures are explicitly managed. On the other hand, we show that streaming at the programming model level is particularly beneficial, even with the cache-based model, as it enhances locality and creates opportunities for bandwidth optimizations. Moreover, we observe that stream programming is actually easier with the cache-based model because the hardware guarantees correct, best-effort execution even when the programmer cannot fully regularize an application's code.

REFERENCES

• 1: Sarita V. Adve , Kourosh Gharachorloo, Shared Memory Consistency Models: A Tutorial, Computer, v.29 n.12, p.66-76, December 1996 [doi>10.1109/2.546611]
• 2: Vikas Agarwal , M. S. Hrishikesh , Stephen W. Keckler , Doug Burger, Clock rate versus IPC: the end of the road for conventional microarchitectures, Proceedings of the 27th annual international symposium on Computer architecture, p.248-259, June 2000, Vancouver, British Columbia, Canada
• 3: Jung Ho Ahn , William J. Dally , Brucek Khailany , Ujval J. Kapasi , Abhishek Das, Evaluating the Imagine Stream Architecture, Proceedings of the 31st annual international symposium on Computer architecture, p.14, June 19-23, 2004, München, Germany
• 4: J. Andrews and N. Backer. Xbox360 System Architecture. In Conf. Record of Hot Chips 17, Stanford, CA, Aug. 2005.
• 5: Luiz André Barroso , Kourosh Gharachorloo , Robert McNamara , Andreas Nowatzyk , Shaz Qadeer , Barton Sano , Scott Smith , Robert Stets , Ben Verghese, Piranha: a scalable architecture based on single-chip multiprocessing, Proceedings of the 27th annual international symposium on Computer architecture, p.282-293, June 2000, Vancouver, British Columbia, Canada
• 6: Ian Buck, GPU Computing: Programming a Massively Parallel Processor, Proceedings of the International Symposium on Code Generation and Optimization, p.17, March 11-14, 2007 [doi>10.1109/CGO.2007.13]
• 7: Tzi-cker Chiueh, A Generational Algorithm to Multiprocessor Cache Coherence, Proceedings of the 1993 International Conference on Parallel Processing, p.20-24, August 16-20, 1993 [doi>10.1109/ICPP.1993.24]
• 8: David E. Culler , Anoop Gupta , Jaswinder Pal Singh, Parallel Computer Architecture: A Hardware/Software Approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1997
• 9: William J. Dally , Francois Labonte , Abhishek Das , Patrick Hanrahan , Jung-Ho Ahn , Jayanth Gummaraju , Mattan Erez , Nuwan Jayasena , Ian Buck , Timothy J. Knight , Ujval J. Kapasi, Merrimac: Supercomputing with Streams, Proceedings of the 2003 ACM/IEEE conference on Supercomputing, p.35, November 15-21, 2003
• 10: John D. Davis , James Laudon , Kunle Olukotun, Maximizing CMP Throughput with Mediocre Cores, Proceedings of the 14th International Conference on Parallel Architectures and Compilation Techniques, p.51-62, September 17-21, 2005 [doi>10.1109/PACT.2005.42]
• 11: M. Drake, H. Hoffmann, R. Rabbah, and S. Amarasinghe. MPEG-2 Decoding in a Stream Programming Language. In Proceedings of the 20th IEEE International Parallel & Distributed Processing Symposium, Rhodes Island (IPDPS), Apr. 2006.
• 12: W. Eatherton. The Push of Network Processing to the Top of the Pyramid, Oct. 2005. Keynote presentation at the Symposium on Architectures for Networking and Communication Systems, Princeton, NJ.
• 13: Kayvon Fatahalian , Daniel Reiter Horn , Timothy J. Knight , Larkhoon Leem , Mike Houston , Ji Young Park , Mattan Erez , Manman Ren , Alex Aiken , William J. Dally , Pat Hanrahan, Sequoia: programming the memory hierarchy, Proceedings of the 2006 ACM/IEEE conference on Supercomputing, November 11-17, 2006, Tampa, Florida [doi>10.1145/1188455.1188543]
• 14: Tim Foley , Jeremy Sugerman, KD-tree acceleration structures for a GPU raytracer, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware, July 30-31, 2005, Los Angeles, California [doi>10.1145/1071866.1071869]
• 15: Michael I. Gordon , William Thies , Michal Karczmarek , Jasper Lin , Ali S. Meli , Andrew A. Lamb , Chris Leger , Jeremy Wong , Henry Hoffmann , David Maze , Saman Amarasinghe, A stream compiler for communication-exposed architectures, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California
• 16: M. Gschwind et al. A Novel SIMD Architecture for the Cell Heterogeneous Chip-Multiprocessor. In Conf. Record of Hot Chips 17, Stanford, CA, Aug. 2005.
• 17: Jayanth Gummaraju , Mendel Rosenblum, Stream Programming on General-Purpose Processors, Proceedings of the 38th annual IEEE/ACM International Symposium on Microarchitecture, p.343-354, November 12-16, 2005, Barcelona, Spain [doi>10.1109/MICRO.2005.32]
• 18: R. Ho, K. Mai, and M. Horowitz. The Future of Wires. Proceedings of the IEEE, 89(4), Apr. 2001.
• 19: R. Ho, K. Mai, and M. Horowitz. Efficient On-chip Global Interconnects, June 2003.
• 20: M. Horowitz and W. Dally. How Scaling Will Change Processor Architecture. In International Solid-State Circuits Conference, pages 132--133, Feb. 2004.
• 21: Independent JPEG Group. IJG's JPEG Software Release 6b, 1998.
• 22: D. Jani, G. Ezer, and J. Kim. Long Words and Wide Ports: Reinventing the Configurable Processor. In Conf. Record of Hot Chips 16, Stanford, CA, Aug. 2004.
• 23: Nuwan S. Jayasena , William J. Dally, Memory hierarchy design for stream computing, Stanford University, Stanford, CA, 2005
• 24: A. C. Klaiber , H. M. Levy, A comparison of message passing and shared memory architectures for data parallel programs, Proceedings of the 21st annual international symposium on Computer architecture, p.94-105, April 18-21, 1994, Chicago, Illinois, United States
• 25: P. Kongetira. A 32-way Multithreaded Sparc Processor. In Conf. Record of Hot Chips 16, Stanford, CA, Aug. 2004.
• 26: Rakesh Kumar , Victor Zyuban , Dean M. Tullsen, Interconnections in Multi-Core Architectures: Understanding Mechanisms, Overheads and Scaling, Proceedings of the 32nd annual international symposium on Computer Architecture, p.408-419, June 04-08, 2005
• 27: Bil Lewis , Daniel J. Berg, Multithreaded programming with Pthreads, Prentice-Hall, Inc., Upper Saddle River, NJ, 1998
• 28: M. Li et al. ALP: Efficient Support for All Levels of Parallelism for Complex Media Applications. Technical Report UIUCDCS-R-2005-2605, UIUC CS, July 2005.
• 29: Amy W. Lim , Shih-Wei Liao , Monica S. Lam, Blocking and array contraction across arbitrarily nested loops using affine partitioning, ACM SIGPLAN Notices, v.36 n.7, p.103-112, July 2001
• 30: Y. Lin. A Programmable Vector Coprocessor Architecture for Wireless Applications. In Proceedings of the 3rd Workshop on Application Specific Processors, Sept. 2004.
• 31: Mirko Loghi , Massimo Poncino, Exploring Energy/Performance Tradeoffs in Shared Memory MPSoCs: Snoop-Based Cache Coherence vs. Software Solutions, Proceedings of the conference on Design, Automation and Test in Europe, p.508-513, March 07-11, 2005 [doi>10.1109/DATE.2005.148]
• 32: E. Machnicki. Ultra High Performance Scalable DSP Family for Multimedia. In Conf. Record of Hot Chips 17, Stanford, CA, Aug. 2005.
• 33: Ken Mai , Tim Paaske , Nuwan Jayasena , Ron Ho , William J. Dally , Mark Horowitz, Smart Memories: a modular reconfigurable architecture, Proceedings of the 27th annual international symposium on Computer architecture, p.161-171, June 2000, Vancouver, British Columbia, Canada
• 34: MIPS32 Architecture For Programmers Volume II: The MIPS32 Instruction Set. MIPS Technologies, Inc., 2001.
• 35: Andreas Moshovos, RegionScout: Exploiting Coarse Grain Sharing in Snoop-Based Coherence, Proceedings of the 32nd annual international symposium on Computer Architecture, p.234-245, June 04-08, 2005
• 36: Karthikeyan Sankaralingam , Ramadass Nagarajan , Haiming Liu , Changkyu Kim , Jaehyuk Huh , Nitya Ranganathan , Doug Burger , Stephen W. Keckler , Robert G. McDonald , Charles R. Moore, TRIPS: A polymorphous architecture for exploiting ILP, TLP, and DLP, ACM Transactions on Architecture and Code Optimization (TACO), v.1 n.1, p.62-93, March 2004 [doi>10.1145/980152.980156]
• 37: Jinwoo Suh , Eun-Gyu Kim , Stephen P. Crago , Lakshmi Srinivasan , Matthew C. French, A performance analysis of PIM, stream processing, and tiled processing on memory-intensive signal processing kernels, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 38: D. Tarjan, S. Thoziyoor, and N. P. Jouppi. CACTI 4.0. Technical Report HPL-2006-86, HP Labs, 2006.
• 39: Michael Bedford Taylor , Walter Lee , Jason Miller , David Wentzlaff , Ian Bratt , Ben Greenwald , Henry Hoffmann , Paul Johnson , Jason Kim , James Psota , Arvind Saraf , Nathan Shnidman , Volker Strumpen , Matt Frank , Saman Amarasinghe , Anant Agarwal, Evaluation of the Raw Microprocessor: An Exposed-Wire-Delay Architecture for ILP and Streams, Proceedings of the 31st annual international symposium on Computer architecture, p.2, June 19-23, 2004, München, Germany
• 40: Tensilica Software Tools. http://www.tensilica.com/products/software.htm.
• 41: Steven P. Vanderwiel , David J. Lilja, Data prefetch mechanisms, ACM Computing Surveys (CSUR), v.32 n.2, p.174-199, June 2000 [doi>10.1145/358923.358939]
• 42: David Wang , Brinda Ganesh , Nuengwong Tuaycharoen , Kathleen Baynes , Aamer Jaleel , Bruce Jacob, DRAMsim: a memory system simulator, ACM SIGARCH Computer Architecture News, v.33 n.4, November 2005 [doi>10.1145/1105734.1105748]
• 43: Zhenlin Wang , Kathryn S. McKinley , Arnold L. Rosenberg , Charles C. Weems, Using the Compiler to Improve Cache Replacement Decisions, Proceedings of the 2002 International Conference on Parallel Architectures and Compilation Techniques, p.199, September 22-25, 2002
• 44: Zhenlin Wang , Doug Burger , Kathryn S. McKinley , Steven K. Reinhardt , Charles C. Weems, Guided region prefetching: a cooperative hardware/software approach, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 45: T.-Y. Yeh. The Low-Power High-Performance Architecture of the PWRficient Processor Family. In Conf. Record of Hot Chips 17, Stanford, CA, Aug. 2005.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Multiple-instruction-stream, multiple-data-stream processors (MIMD)

Additional Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Cache memories

  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Parallel programming

General Terms:
Design, Performance

Keywords:
chip multiprocessors, coherent caches, locality optimizations, parallel programming, streaming memory