Global trees: a framework for linked data structures on distributed memory parallel systems

ABSTRACT

This paper describes the Global Trees (GT) system that provides a multi-layered interface to a global address space view of distributed tree data structures, while providing scalable performance on distributed memory systems. The Global Trees system utilizes coarse-grained data movement to enhance locality and communication efficiency. We describe the design and implementation of GT, illustrate its use in the context of a gravitational simulation application, and provide experimental results that demonstrate the effectiveness of the approach. The key benefits of using this system include efficient shared-memory style programming of distributed trees, tree-specific optimizations for data access and computation, and the ability to customize many aspects of GT to optimize application performance.

REFERENCES

• 1: J. Barnes and P. Hut, "A Hierarchical O(N log N) Force Calculation Algorithm," Nature, vol. 324, pp. 446--449, 1986.
• 2: J. Carrier, L. Greengard, and V. Rokhlin, "A Fast Adaptive Multi-pole Algorithm for Particle Simulations," SIAM Journal of Scientific and Statistical Computing, vol. 9, no. 4, 1988, yale University Technical Report, YALEU/DCS/RR-496 (1986).
• 3: R. J. Harrison, G. I. Fann, T. Yanai, and G. Beylkin, "Multiresolution Quantum Chemistry in Multiwavelet Bases," in International Conference on Computational Science, 2003, pp. 103--110.
• 4: Gregory Buehrer , Srinivasan Parthasarathy , Yen-Kuang Chen, Adaptive Parallel Graph Mining for CMP Architectures, Proceedings of the Sixth International Conference on Data Mining, p.97-106, December 18-22, 2006 [doi>10.1109/ICDM.2006.15]
• 5: Message P Forum, MPI: A Message-Passing Interface Standard, University of Tennessee, Knoxville, TN, 1994
• 6: D. Callahan, B. Chamberlain, and H. Zima, "The Cascade High Productivity Language," High-Level Parallel Programming Models and Supportive Environments, 2004. Proceedings. Ninth International Workshop on, pp. 52--60, 26 April 2004.
• 7: Philippe Charles , Christian Grothoff , Vijay Saraswat , Christopher Donawa , Allan Kielstra , Kemal Ebcioglu , Christoph von Praun , Vivek Sarkar, X10: an object-oriented approach to non-uniform cluster computing, Proceedings of the 20th annual ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, October 16-20, 2005, San Diego, CA, USA
• 8: Guy Steele, Parallel Programming and Parallel Abstractions in Fortress, Proceedings of the 14th International Conference on Parallel Architectures and Compilation Techniques, p.157, September 17-21, 2005 [doi>10.1109/PACT.2005.34]
• 9: Jarek Nieplocha , Bryan Carpenter, ARMCI: A Portable Remote Memory Copy Libray for Ditributed Array Libraries and Compiler Run-Time Systems, Proceedings of the 11 IPPS/SPDP'99 Workshops Held in Conjunction with the 13th International Parallel Processing Symposium and 10th Symposium on Parallel and Distributed Processing, p.533-546, April 12-16, 1999
• 10: Dan Bonachea, GASNet Specification, v1.1, University of California at Berkeley, Berkeley, CA, 2002
• 11: MPI Forum, "MPI-2: Extensions to the Message-Passing Interface," Technical Report, University of Tennessee, Knoxville, 1996.
• 12: R. Bariuso and A. Knies, "SHMEM User's Guide," 1994.
• 13: UPC Consortium, "UPC Language Specifications, vl. 2," Lawrence Berkeley National Lab, Tech. Rep. LBNL-59208, 2005.
• 14: Steven Cameron Woo , Moriyoshi Ohara , Evan Torrie , Jaswinder Pal Singh , Anoop Gupta, The SPLASH-2 programs: characterization and methodological considerations, Proceedings of the 22nd annual international symposium on Computer architecture, p.24-36, June 22-24, 1995, S. Margherita Ligure, Italy
• 15: James Dinan , Sriram Krishnamoorthy , D. Brian Larkins , Jarek Nieplocha , P. Sadayappan, Scioto: A Framework for Global-View Task Parallelism, Proceedings of the 2008 37th International Conference on Parallel Processing, p.586-593, September 09-11, 2008 [doi>10.1109/ICPP.2008.44]
• 16: Jaroslaw Nieplocha , Robert J. Harrison , Richard J. Littlefield, Global arrays: a nonuniform memory access programming model for high-performance computers, The Journal of Supercomputing, v.10 n.2, p.169-189, June 1996
• 17: Intel Corporation, "Cluster OpenMP User's Guide v9.1," no. 309096--002 US, 2005--2006.
• 18: Leonardo Dagum , Ramesh Menon, OpenMP: An Industry-Standard API for Shared-Memory Programming, IEEE Computational Science & Engineering, v.5 n.1, p.46-55, January 1998 [doi>10.1109/99.660313]
• 19: Cristiana Amza , Alan L. Cox , Sandhya Dwarkadas , Pete Keleher , Honghui Lu , Ramakrishnan Rajamony , Weimin Yu , Willy Zwaenepoel, TreadMarks: Shared Memory Computing on Networks of Workstations, Computer, v.29 n.2, p.18-28, February 1996 [doi>10.1109/2.485843]
• 20: Pete Keleher , Alan L. Cox , Willy Zwaenepoel, Lazy release consistency for software distributed shared memory, Proceedings of the 19th annual international symposium on Computer architecture, p.13-21, May 19-21, 1992, Queensland, Australia
• 21: Pete Keleher , Alan L. Cox , Sandhya Dwarkadas , Willy Zwaenepoel, TreadMarks: distributed shared memory on standard workstations and operating systems, Proceedings of the USENIX Winter 1994 Technical Conference on USENIX Winter 1994 Technical Conference, p.10-10, January 17-21, 1994, San Francisco, California
• 22: Peter John Keleher, Lazy release consistency for distributed shared memory, Rice University, Houston, TX, 1996
• 23: R. J. Stets , D. Chen , S. Dwarkadas , N. Hardavellas , G. C. Hunt , L. Kontothanassis , G. Magklis , S. Parthasarathy , U. Rencuzogullari , M. L. Scott, The Implementation of Cashmere, University of Rochester, Rochester, NY, 1999
• 24: A. Singla and U. Ramachandran, "The Beehive Cluster System."
• 25: Daniel J. Scales , Kourosh Gharachorloo, Design and performance of the Shasta distributed shared memory protocol, Proceedings of the 11th international conference on Supercomputing, p.245-252, July 07-11, 1997, Vienna, Austria [doi>10.1145/263580.263643]
• 26: Ioannis Schoinas , Babak Falsafi , Alvin R. Lebeck , Steven K. Reinhardt , James R. Larus , David A. Wood, Fine-grain access control for distributed shared memory, ACM SIGPLAN Notices, v.29 n.11, p.297-306, Nov. 1994
• 27: Liviu Iftode , Matthias Blumrich , Cezary Dubnicki , David L. Oppenheimer , Jaswinder Pal Singh , Kai Li, Shared virtual memory with automatic update support, Proceedings of the 13th international conference on Supercomputing, p.175-183, June 20-25, 1999, Rhodes, Greece [doi>10.1145/305138.305191]
• 28: Rishiyur S. Nikhil, Cid: A Parallel, "Shared-Memory" C for Distributed-Memory Machines, Proceedings of the 7th International Workshop on Languages and Compilers for Parallel Computing, p.376-390, August 08-10, 1994
• 29: K. L. Johnson, M. F. Kaashoek, and D. A. Wallach, "CRL: High-Performance All-Software Distributed Shared Memory," in Proc. of the Fifth Workshop on Scalable Shared Memory Multiprocessors, Jun. 1995.
• 30: B. N. Bershad and M. J. Zekauskas, "Midway: Shared Memory Parallel Programming with Entry Consistency for Distributed Memory Multiprocessors," School of Computer Science, Carnegie-Mellon University, Tech. Rep. CMU-CS-91-170, Sep. 1991.
• 31: B. N. Bershad, M. J. Zekauskas, and W. A. Sawdon, "The Midway Distributed Shared Memory System," in Proc. of the 38th IEEE Int'l Computer Conf. (COMPCON Spring '93), Feb. 1993, pp. 528--537.
• 32: B. N. Bershad, "Practical Considerations for Non-Blocking Concurrent Objects," in Proc. of the 13th Int'l Conf. on Distributed Computing Systems (ICDCS-13), May 1993, pp. 264--273.
• 33: Sudhir Ahuja , Nicholas Carriero , David Gelernter, Linda and Friends, Computer, v.19 n.8, p.26-34, August 1986 [doi>10.1109/MC.1986.1663305]
• 34: Nicholas Carriero , David Gelernter, The S/Net's Linda kernel, ACM Transactions on Computer Systems (TOCS), v.4 n.2, p.110-129, May 1986 [doi>10.1145/214419.214420]
• 35: Eric Jul , Henry Levy , Norman Hutchinson , Andrew Black, Fine-grained mobility in the Emerald system, ACM Transactions on Computer Systems (TOCS), v.6 n.1, p.109-133, Feb. 1988 [doi>10.1145/35037.42182]
• 36: Laxmikant V. Kale , Sanjeev Krishnan, CHARM++: a portable concurrent object oriented system based on C++, Proceedings of the eighth annual conference on Object-oriented programming systems, languages, and applications, p.91-108, September 26-October 01, 1993, Washington, D.C., United States
• 37: C. Chang, A. Sussman, and J. Saltz, Parallel Programming Using C++, P. Lu and G. V. Wilson, Eds. Cambridge, MA, USA: MIT Press, 1996.
• 38: H. E. Bal, M. F. Kaashoek, and A. S. Tanenbaum, "Experience with Distributed Programming in Orca," in Proc. of the 1990 Int'l Conf. on Computer Languages, Mar. 1990, pp. 79--89.
• 39: Henri E. Bal, Orca: a language for distributed programming, ACM SIGPLAN Notices, v.25 n.5, p.17-24, May 1990 [doi>10.1145/382080.382082]
• 40: Robert W. Numrich , John Reid, Co-array Fortran for parallel programming, ACM SIGPLAN Fortran Forum, v.17 n.2, p.1-31, Aug. 1998 [doi>10.1145/289918.289920]
• 41: K. Yelick, L. Semenzato, G. Pike, C. Miyamoto, B. Liblit, A. Krishnamurthy, P. Hilfinger, S. Graham, D. Gay, P. Colella, and A. Aiken, "Titanium: A high-performance Java dialect," in ACM 1998 Workshop on Java for High-Performance Network Computing, ACM, Ed. New York, NY 10036, USA: ACM Press, 1998.
• 42: Fabrizio Baiardi , Paolo Mori , Laura Ricci, PIT: A Library for the Parallelization of Irregular Problems, Proceedings of the 6th International Conference on Applied Parallel Computing Advanced Scientific Computing, p.185-194, June 15-18, 2002
• 43: F. Baiardi, P. Mori, and L. Ricci, "Solving irregular problems through parallel irregular trees." in Parallel and Distributed Computing and Networks, 2005, pp. 246--251.
• 44: Anne Rogers , Martin C. Carlisle , John H. Reppy , Laurie J. Hendren, Supporting dynamic data structures on distributed-memory machines, ACM Transactions on Programming Languages and Systems (TOPLAS), v.17 n.2, p.233-263, March 1995 [doi>10.1145/201059.201065]
• 45: S. Parthasarathy, M. J. Zaki, and W. Li, "Memory placement techniques for parallel association mining," in In 4th Intl. Conf. Knowledge Discovery and Data Mining, 1998.

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Trees

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

General Terms:
Design, Experimentation, Measurement, Performance