Mars: a MapReduce framework on graphics processors

ABSTRACT

We design and implement Mars, a MapReduce framework, on graphics processors (GPUs). MapReduce is a distributed programming framework originally proposed by Google for the ease of development of web search applications on a large number of commodity CPUs. Compared with CPUs, GPUs have an order of magnitude higher computation power and memory bandwidth, but are harder to program since their architectures are designed as a special-purpose co-processor and their programming interfaces are typically for graphics applications. As the first attempt to harness GPU's power for MapReduce, we developed Mars on an NVIDIA G80 GPU, which contains over one hundred processors, and evaluated it in comparison with Phoenix, the state-of-the-art MapReduce framework on multi-core CPUs. Mars hides the programming complexity of the GPU behind the simple and familiar MapReduce interface. It is up to 16 times faster than its CPU-based counterpart for six common web applications on a quad-core machine.

REFERENCES

• 1: Anastassia Ailamaki , Naga K. Govindaraju , Stavros Harizopoulos , Dinesh Manocha, Query co-processing on commodity processors, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 2: AMD CTM. http://ati.amd.com/products/streamprocessor/, 2007.
• 3: Apache Hadoop. http://lucene.apache.org/hadoop/, 2006.
• 4: David Blythe, The Direct3D 10 system, ACM Transactions on Graphics (TOG), v.25 n.3, July 2006
• 5: Ian Buck , Tim Foley , Daniel Horn , Jeremy Sugerman , Kayvon Fatahalian , Mike Houston , Pat Hanrahan, Brook for GPUs: stream computing on graphics hardware, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 6: B. Catanzaro, N. Sundaram, and K. Keutzer. A map reduce framework for programming graphics processors. In Workshop on Software Tools for MultiCore Systems, 2008.
• 7: Hung-chih Yang , Ali Dasdan , Ruey-Lung Hsiao , D. Stott Parker, Map-reduce-merge: simplified relational data processing on large clusters, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247602]
• 8: C. Chu, S. Kim, Y. Lin, Y. Yu, G. Bradski, A. Y. Ng, and K. Olukotun. Map-reduce for machine learning on multicore. In NIPS '07: Proceedings of Twenty-First Annual Conference on Neural Information Processing Systems. Neural Information Processing Systems Foundation, 2007.
• 9: Jeffrey Dean , Sanjay Ghemawat, MapReduce: simplified data processing on large clusters, Communications of the ACM, v.51 n.1, January 2008 [doi>10.1145/1327452.1327492]
• 10: Jimin Feng , Samarjit Chakraborty , Bertil Schmidt , Weiguo Liu , Unmesh D. Bordoloi, Fast Schedulability Analysis Using Commodity Graphics Hardware, Proceedings of the 13th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, p.400-408, August 21-24, 2007 [doi>10.1109/RTCSA.2007.40]
• 11: Folding@home. http://www.scei.co.jp/folding, 2007.
• 12: Naga Govindaraju , Jim Gray , Ritesh Kumar , Dinesh Manocha, GPUTeraSort: high performance graphics co-processor sorting for large database management, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142511]
• 13: Naga K. Govindaraju , Brandon Lloyd , Wei Wang , Ming Lin , Dinesh Manocha, Fast computation of database operations using graphics processors, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007594]
• 14: M. Harris, J. Owens, S. Sengupta, Y. Zhang, and A. Davidson. Cudpp: Cuda data parallel primitives library. 2007.
• 15: Bingsheng He , Naga K. Govindaraju , Qiong Luo , Burton Smith, Efficient gather and scatter operations on graphics processors, Proceedings of the 2007 ACM/IEEE conference on Supercomputing, November 10-16, 2007, Reno, Nevada [doi>10.1145/1362622.1362684]
• 16: Bingsheng He , Ke Yang , Rui Fang , Mian Lu , Naga Govindaraju , Qiong Luo , Pedro Sander, Relational joins on graphics processors, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376670]
• 17: D. Horn. Lib GPU FFT, 2006.
• 18: Changhao Jiang , Marc Snir, Automatic Tuning Matrix Multiplication Performance on Graphics Hardware, Proceedings of the 14th International Conference on Parallel Architectures and Compilation Techniques, p.185-196, September 17-21, 2005 [doi>10.1109/PACT.2005.10]
• 19: E. Scott Larsen , David McAllister, Fast matrix multiplies using graphics hardware, Proceedings of the 2001 ACM/IEEE conference on Supercomputing (CDROM), p.55-55, November 10-16, 2001, Denver, Colorado [doi>10.1145/582034.582089]
• 20: Michael D. Linderman , Jamison D. Collins , Hong Wang , Teresa H. Meng, Merge: a programming model for heterogeneous multi-core systems, Proceedings of the 13th international conference on Architectural support for programming languages and operating systems, March 01-05, 2008, Seattle, WA, USA
• 21: Weiguo Liu , Bertil Schmidt , Gerrit Voss , Wolfgang Muller-Wittig, Streaming Algorithms for Biological Sequence Alignment on GPUs, IEEE Transactions on Parallel and Distributed Systems, v.18 n.9, p.1270-1281, September 2007 [doi>10.1109/TPDS.2007.1069]
• 22: Hubert Nguyen, Gpu gems 3, Addison-Wesley Professional, 2007
• 23: NVIDIA Corp. . CUDA Occupancy Calculator, 2007.
• 24: NVIDIA CUDA. http://developer.nvidia.com/object/cuda.html, 2007.
• 25: OpenGL. http://www.opengl.org/, 2007.
• 26: J. D. Owens, D. Luebke, N. Govindaraju, M. Harris, J. Kruger, A. E. Lefohn, and T. J. Purcell. A survey of general-purpose computation on graphics hardware. Computer Graphics Forum, 26, 2007.
• 27: Colby Ranger , Ramanan Raghuraman , Arun Penmetsa , Gary Bradski , Christos Kozyrakis, Evaluating MapReduce for Multi-core and Multiprocessor Systems, Proceedings of the 2007 IEEE 13th International Symposium on High Performance Computer Architecture, p.13-24, February 10-14, 2007 [doi>10.1109/HPCA.2007.346181]
• 28: Shubhabrata Sengupta , Mark Harris , Yao Zhang , John D. Owens, Scan primitives for GPU computing, Proceedings of the 22nd ACM SIGGRAPH/EUROGRAPHICS symposium on Graphics hardware, August 04-05, 2007, San Diego, California
• 29: SETI@home. http://setiathome.berkeley.edu/, 2007.
• 30: David Tarditi , Sidd Puri , Jose Oglesby, Accelerator: using data parallelism to program GPUs for general-purpose uses, Proceedings of the 12th international conference on Architectural support for programming languages and operating systems, October 21-25, 2006, San Jose, California, USA
• 31: Ricardo A. Baeza-Yates , Berthier Ribeiro-Neto, Modern Information Retrieval, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999

INDEX TERMS

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

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Frameworks

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.1 Hardware architecture
          Subjects: Parallel processing; Graphics processors

General Terms:
Design, Performance

Keywords:
GPGPU, MapReduce, data parallelism, graphics processor, multi-core processors, web analysis