Processing-in-memory technology for knowledge discovery algorithms

ABSTRACT

The goal of this work is to gain insight into whether processing-in-memory (PIM) technology can be used to accelerate the performance of link discovery algorithms, which represent an important class of emerging knowledge discovery techniques. PIM chips that integrate processor logic into memory devices offer a new opportunity for bridging the growing gap between processor and memory speeds, especially for applications with high memory-bandwidth requirements. As LD algorithms are data-intensive and highly parallel, involving read-only queries over large data sets, parallel computing power extremely close (physically) to the data has the potential of providing dramatic computing speedups. For this reason, we evaluated the mapping of LD algorithms to a processing-in-memory (PIM) workstation-class architecture, the DIVA/Godiva hardware testbeds developed by USC/ISI. Accounting for differences in clock speed and data scaling, our analysis shows a performance gain on a single PIM, with the potential for greater improvement when multiple PIMs are used. Measured speedups of 8x are shown on two additional bandwidth benchmarks, even though the Itanium-2 has a clock rate 6X faster.

REFERENCES

• 1: J. Adibi, H. Chalupsky, E. Melz and A. Valente. The KOJAK Group Finder: Connecting the Dots via Integrated Knowledge-Based and Statistical Reasoning. Innovative Applications of Artificial Intelligence Conf., IAAI 2004.
• 2: Doug Burger , James R. Goodman , Alain Kägi, Memory bandwidth limitations of future microprocessors, Proceedings of the 23rd annual international symposium on Computer architecture, p.78-89, May 22-24, 1996, Philadelphia, Pennsylvania, United States
• 3: Jeff Draper , Jacqueline Chame , Mary Hall , Craig Steele , Tim Barrett , Jeff LaCoss , John Granacki , Jaewook Shin , Chun Chen , Chang Woo Kang , Ihn Kim , Gokhan Daglikoca, The architecture of the DIVA processing-in-memory chip, Proceedings of the 16th international conference on Supercomputing, June 22-26, 2002, New York, New York, USA [doi>10.1145/514191.514197]
• 4: Duncan Elliott , Michael Stumm , W. Martin Snelgrove , Christian Cojocaru , Robert McKenzie, Computational RAM: Implementing Processors in Memory, IEEE Design & Test, v.16 n.1, p.32-41, January 1999 [doi>10.1109/54.748803]
• 5: Maya Gokhale , Bill Holmes , Ken Iobst, Processing in Memory: The Terasys Massively Parallel PIM Array, Computer, v.28 n.4, p.23-31, April 1995 [doi>10.1109/2.375174]
• 6: Mary Hall , Peter Kogge , Jeff Koller , Pedro Diniz , Jacqueline Chame , Jeff Draper , Jeff LaCoss , John Granacki , Jay Brockman , Apoorv Srivastava , William Athas , Vincent Freeh , Jaewook Shin , Joonseok Park, Mapping irregular applications to DIVA, a PIM-based data-intensive architecture, Proceedings of the 1999 ACM/IEEE conference on Supercomputing (CDROM), p.57-es, November 14-19, 1999, Portland, Oregon, United States [doi>10.1145/331532.331589]
• 7: P. Kogge, "The EXECUBE Approach to Massively Parallel Processing", Proc. of the International Conference on Parallel Processing", Aug, 1994.
• 8: Shou-de Lin , Hans Chalupsky, Unsupervised Link Discovery in Multi-relational Data via Rarity Analysis, Proceedings of the Third IEEE International Conference on Data Mining, p.171, November 19-22, 2003
• 9: J. Shin, J. Chame and M. W. Hall, "Compiler-Controlled Caching in Superword Register Files for Multimedia Extension Architectures," Journal of Instruction-Level Parallelism, 2003.
• 10: Jaewook Shin , Mary Hall , Jacqueline Chame, Superword-Level Parallelism in the Presence of Control Flow, Proceedings of the international symposium on Code generation and optimization, p.165-175, March 20-23, 2005 [doi>10.1109/CGO.2005.33]
• 11: H. Chalupsky and R. M. MacGregor. STELLA - a Lisp-like language for symbolic programming with delivery in Common Lisp, C++ and Java. In Proc. of the Lisp User Group Meeting, Berkeley, CA, 1999. Franz Inc.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.4 Knowledge Representation Formalisms and Methods

General Terms:
Algorithms, Design, Theory