Atomic Vector Operations on Chip Multiprocessors

ABSTRACT

The current trend is for processors to deliver dramatic improvements in parallel performance while only modestly improving serial performance. Parallel performance is harvested through vector/SIMD instructions as well as multithreading (through both multithreaded cores and chip multiprocessors). Vector parallelism can be more efficiently supported than multithreading, but is often harder for software to exploit. In particular, code with sparse data access patterns cannot easily utilize the vector/SIMD instructions of mainstream processors. Hardware to scatter and gather sparse data has previously been proposed to enable vector execution for these codes. However, on multithreaded architectures, a number of applications spend significant time on atomic operations (e.g., parallel reductions), which cannot be vectorized using previously proposed schemes. This paper proposes architectural support for atomic vector operations (referred to as GLSC) that addresses this limitation. GLSC extends scatter-gather hardware to support atomic memory operations. Our experiments show that the GLSC provides an average performance improvement on a set of important RMS kernels of 54% for 4-wide SIMD.

REFERENCES

• 1: AMD Opteron Processor Family. http://www.amd.com/.
• 2: CRAY-2 Engineering Maintenance Manual. Cray Research Inc., Publication No. HM-2032, 1985.
• 3: IBM, IBM system/360 principles of operation, IBM Press, 1964
• 4: Intel Pentium/Core/Core 2 Processors. http://www.intel.com/.
• 5: NVIDIA CUDA (Compute Unified Device Architecture). http://www.nvidia.com/, 2007.
• 6: PowerPC User Instruction Set Architecture (Book I). 2003.
• 7: Dennis Abts , Abdulla Bataineh , Steve Scott , Greg Faanes , Jim Schwarzmeier , Eric Lundberg , Tim Johnson , Mike Bye , Gerald Schwoerer, The Cray BlackWidow: a highly scalable vector multiprocessor, Proceedings of the 2007 ACM/IEEE conference on Supercomputing, November 10-16, 2007, Reno, Nevada [doi>10.1145/1362622.1362646]
• 8: Jung Ho Ahn , Mattan Erez , William J. Dally, Scatter-Add in Data Parallel Architectures, Proceedings of the 11th International Symposium on High-Performance Computer Architecture, p.132-142, February 12-16, 2005 [doi>10.1109/HPCA.2005.30]
• 9: C. Bienia, S. Kumar, J. P. Singh, and K. Li. The PARSEC benchmark suite: Characterization and architectural implications. Princeton University Technical Report TR-811-08, 2008.
• 10: Siddhartha Chatterjee , Guy E. Blelloch , Marco Zagha, Scan primitives for vector computers, Proceedings of the 1990 ACM/IEEE conference on Supercomputing, p.666-675, November 12-16, 1990, New York, New York
• 11: P. Dubey. Recognition, Mining and Synthesis Moves Computers to the Era of Tera. Technology@Intel Magazine, February 2005.
• 12: Christer Ericson, Real-Time Collision Detection (The Morgan Kaufmann Series in Interactive 3-D Technology) (The Morgan Kaufmann Series in Interactive 3D Technology), Morgan Kaufmann Publishers Inc., San Francisco, CA, 2004
• 13: Zhen Fang , Lixin Zhang , John B. Carter , Ali Ibrahim , Michael A. Parker, Active memory operations, Proceedings of the 21st annual international conference on Supercomputing, June 17-21, 2007, Seattle, Washington [doi>10.1145/1274971.1275004]
• 14: Andrew V. Goldberg , Robert E. Tarjan, A new approach to the maximum-flow problem, Journal of the ACM (JACM), v.35 n.4, p.921-940, Oct. 1988 [doi>10.1145/48014.61051]
• 15: Allan Gottlieb , Boris D. Lubachevsky , Larry Rudolph, Basic Techniques for the Efficient Coordination of Very Large Numbers of Cooperating Sequential Processors, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.2, p.164-189, April 1983 [doi>10.1145/69624.357206]
• 16: Michael Gschwind, Chip multiprocessing and the cell broadband engine, Proceedings of the 3rd conference on Computing frontiers, p.1-8, May 03-05, 2006, Ischia, Italy [doi>10.1145/1128022.1128023]
• 17: Jayanth Gummaraju , Mattan Erez , Joel Coburn , Mendel Rosenblum , William J. Dally, Architectural Support for the Stream Execution Model on General-Purpose Processors, Proceedings of the 16th International Conference on Parallel Architecture and Compilation Techniques, p.3-12, September 15-19, 2007 [doi>10.1109/PACT.2007.15]
• 18: Maurice Herlihy , J. Eliot B. Moss, Transactional memory: architectural support for lock-free data structures, Proceedings of the 20th annual international symposium on Computer architecture, p.289-300, May 16-19, 1993, San Diego, California, United States
• 19: Gerry Kane , Joe Heinrich, MIPS RISC architectures, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• 20: J. R. Larus and R. Rajwar. Transactional Memory. Morgan and Claypool, 2006.
• 21: James Laudon , Daniel Lenoski, The SGI Origin: a ccNUMA highly scalable server, Proceedings of the 24th annual international symposium on Computer architecture, p.241-251, June 01-04, 1997, Denver, Colorado, United States
• 22: William E. Lorensen , Harvey E. Cline, Marching cubes: A high resolution 3D surface construction algorithm, ACM SIGGRAPH Computer Graphics, v.21 n.4, p.163-169, July 1987
• 23: J. Rattner. Cool Codes for Hot Chips: A Quantitative Basis for Multi-Core Design. HotChips Keynote, 2006.
• 24: O. Schenk. Scalable Parallel Sparse LU Factorization Methods on Shared Memory Multiprocessors. PhD thesis, ETH Zurich, Zurich, Switzerland, 2005.
• 25: Steven L. Scott, Synchronization and communication in the T3E multiprocessor, Proceedings of the seventh international conference on Architectural support for programming languages and operating systems, p.26-36, October 01-04, 1996, Cambridge, Massachusetts, United States
• 26: R. Smith. Open dynamics engine v0.5 user guide. http://www.ode.org/ode-latest-userguide.html, 2006.
• 27: James Z. Wang, Integrated Region-Based Image Retrieval, Kluwer Academic Publishers, Norwell, MA, 2001

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.4 Parallel Architectures
  C.4 PERFORMANCE OF SYSTEMS

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

General Terms:
Algorithms, Design, Performance

Keywords:
locks, reductions, vector, SIMD, multiprocessors