Analyzing memory access intensity in parallel programs on multicore

ABSTRACT

As the shared memory bus becomes a major performance bottleneck for many numerical applications on multicore chips, understanding how the increased parallelism on chip strains the memory bandwidth and hence affects the efficiency of parallel codes becomes a critical issue. This paper introduces the notion of memory access intensity to facilitate quantitative analysis of program's memory behavior on multicores which employ state-of-the-art prefetching hardware. Three numerical solvers for large scale sparse linear systems are used to demonstrate the estimation of memory access intensity and its effect on program performance.

REFERENCES

• 1: Monica D. Lam , Edward E. Rothberg , Michael E. Wolf, The cache performance and optimizations of blocked algorithms, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.63-74, April 08-11, 1991, Santa Clara, California, United States
• 2: Michael E. Wolf , Monica S. Lam, A data locality optimizing algorithm, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.30-44, June 24-28, 1991, Toronto, Ontario, Canada
• 3: Zhiyuan Li , Yonghong Song, Automatic tiling of iterative stencil loops, ACM Transactions on Programming Languages and Systems (TOPLAS), v.26 n.6, p.975-1028, November 2004 [doi>10.1145/1034774.1034777]
• 4: Alan Jay Smith, Cache Memories, ACM Computing Surveys (CSUR), v.14 n.3, p.473-530, Sept. 1982 [doi>10.1145/356887.356892]
• 5: Dean M. Tullsen , Susan J. Eggers, Limitations of cache prefetching on a bus-based multiprocessor, Proceedings of the 20th annual international symposium on Computer architecture, p.278-288, May 16-19, 1993, San Diego, California, United States
• 6: Santhosh Srinath , Onur Mutlu , Hyesoon Kim , Yale N. Patt, Feedback Directed Prefetching: Improving the Performance and Bandwidth-Efficiency of Hardware Prefetchers, Proceedings of the 2007 IEEE 13th International Symposium on High Performance Computer Architecture, p.63-74, February 10-14, 2007 [doi>10.1109/HPCA.2007.346185]
• 7: Steve Carr , Ken Kennedy, Improving the ratio of memory operations to floating-point operations in loops, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.6, p.1768-1810, Nov. 1994 [doi>10.1145/197320.197366]
• 8: K. Asanovic and et al. "The Landscape of Parallel Computing Research: A View from Berkeley," EECS Department University of California, Berkeley Technical Report No. UCB/EECS-2006-183 December 18, 2006.
• 9: Jack J. Dongarra , L. S. Blackford , J. Choi , A. Cleary , E. D'Azeuedo , J. Demmel , I. Dhillon , S. Hammarling , G. Henry , A. Petitet , K. Stanley , D. Walker , R. C. Whaley, ScaLAPACK user's guide, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1997
• 10: Andy Cleary , Jack Dongarra, Implementation in ScaLAPACK of Divide-and-Conquer Algorithms forBanded and Tridiagonal Linear Systems, University of Tennessee, Knoxville, TN, 1997
• 11: Intel® Math Kernel Library, http://www.intel.com/software/products/mkl/.
• 12: Eric Polizzi , Ahmed H. Sameh, A parallel hybrid banded system solver: the SPIKE algorithm, Parallel Computing, v.32 n.2, p.177-194, February 2006 [doi>10.1016/j.parco.2005.07.005]
• 13: Qi Zhang , Yurong Chen , Jianguo Li , Yimin Zhang , Yinlong Xu, Parallelization and Performance Analysis of Video Feature Extractions on Multi-Core Based Systems, Proceedings of the 2007 International Conference on Parallel Processing, p.1, September 10-14, 2007 [doi>10.1109/ICPP.2007.65]
• 14: Sadaf R. Alam, et al. Characterization of Scientific Workloads on Systems with Multi-Core Processors. In International Symposium on Workload Characterization, 2006.
• 15: Figure 14 Spike NEW: performance for wide banded system
• 16: Lei Chai , Qi Gao , Dhabaleswar K. Panda, Understanding the Impact of Multi-Core Architecture in Cluster Computing: A Case Study with Intel Dual-Core System, Proceedings of the Seventh IEEE International Symposium on Cluster Computing and the Grid, p.471-478, May 14-17, 2007 [doi>10.1109/CCGRID.2007.119]
• 17: John L. Hennessy , David A. Patterson, Computer architecture (2nd ed.): a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

General Terms:
Design, Measurement, Performance

Keywords:
intensity, linear system, memory bandwidth, multicore, parallel