The scalability and efficiency of graph applications are significantly constrained by conventional systems and their supporting programming models. Technology trends such as multicore, manycore, and heterogeneous system architectures are introducing further challenges and possibilities for emerging application domains such as graph applications. This paper explores the parallel execution of graphs that are generated using the Barnes–Hut algorithm to exemplify dynamic workloads. The workloads are expressed using the semantics of an exascale computing execution model called ParalleX. For comparison, results using conventional execution model semantics are also presented. We find improved load balancing during runtime and automatic parallelism discovery by using the advanced semantics for exascale computing.
AarsethSJHenonMWielenR (1974) A comparison of numerical methods for the study of star cluster dynamics. Astronomy and Astrophysics Journal37: 183–187.
2.
AlfieriRA (1994) An efficient kernel-based implementation of posix threads. In Proceedings of the USENIX Summer 1994 Technical Conference on USENIX Summer 1994 Technical Conference - Volume 1, USTC’94. Berkele, CA: USENIX Association.
3.
AppelAWJimT (1989) Continuation-passing, closure-passing style. In POPL ’89: Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages. New York: ACM Press, pp. 293–302.
4.
BakerHCJrHewittC (1977) The incremental garbage collection of processes. In Proceedings of the 1977 Symposium on Artificial Intelligence and Programming Languages. New York: ACM Press, pp. 55–59.
del RosarioJMBordawekarRChoudharyA (1993) Improved parallel I/O via a two-phase run-time access strategy. SIGARCH Computer Architecture News21: 31–38.
15.
DennisJB (1980) Data flow supercomputers. Computer13(11): 48–56.
16.
DikaiakosMDStadelJ (1996) A performance study of cosmological simulations on message-passing and shared-memory multiprocessors. In Proceedings of the 10th international conference on Supercomputing, ICS ’96. New York: ACM Press, pp. 94–101.
17.
DubinskiJ (1996) A parallel tree code. New Astronomy1: 133–147.
18.
EickenTCullerDGoldsteinSSchauserK (1992) Active messages: A mechanism for integrated communication and computation. Proceedings of the 19th Annual International Symposium on Computer Architecture, pp. 256–266.
19.
El-GhazawiTCarlsonWSterlingTYelickK (2003) UPC: Distributed Shared-Memory Programming. New York: Wiley-Interscience.
20.
El-GhazawiTSmithL (2006) UPC: Unified Parallel C. In SC ’06: Proceedings of the 2006 ACM/IEEE Conference on Supercomputing, 27. New York: ACM Press.
21.
FryxellBOlsonKRickerPTimmesFXZingaleMLambDQ. (2000) Flash: An adaptive mesh hydrodynamics code for modeling astrophysical thermonuclear flashes. The Astrophysical Journal Supplement Series131: 273.
22.
GreengardLHuangJ (2002) A new version of the fast multipole method for screened Coulomb interactions in three dimensions. Journal of Computational Physics180: 642–658.
23.
HewittCBakerHG (1978) Actors and Continuous Functionals. Technical report, MIT, Cambridge, MA, USA.
24.
JetleyPGioachinFMendesCLKaléLVQuinnT (2008) Massively parallel cosmological simulations with changa. In IPDPS’08, pp. 1–12.
25.
KaiserHBrodowiczMSterlingT (2009) ParalleX: An advanced parallel execution model for scaling-impaired applications. In Parallel Processing Workshops. Los Alamitos, CA: IEEE Computer Society Press, pp. 394–401.
26.
KaleL (2011) Charm++. In PaduaD (ed.), Encyclopedia of Parallel Computing. New York: Springer-Verlag.
27.
KamalHWagnerA (2010) FG-MPI: Fine-grain MPI for multicore and clusters. In 2010 IEEE International Symposium on Parallel Distributed Processing, Workshops and PhD Forum (IPDPSW), pp. 1–8.
28.
LiuPBhattSN (1994) Experiences with parallel N-body simulation. In Proceedings of the Sixth Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA ’94. New York: ACM Press, pp. 122–131.
29.
MakinoJHirakiKInabaM (2007) GRAPE-DR: 2-PFLOPs massively-parallel computer with 512-core, 512-GFLOPs processor chips for scientific computing. In SC, p. 18.
30.
Message Passing Interface Forum (2009) MPI: A Message-Passing Interface Standard, Version 2.2. High Performance Computing Center Stuttgart (HLRS), Stuttgart, Germany.
31.
O’SheaBWBryanGBordnerJNormanMLAbelTHarknessR. (2004) Introducing ENZO, An AMR Cosmology Application. Preprint astro-ph/0403044.
PlummerHC (1911) On the problem of distribution in globular star clusters. Monthly Notices of the Royal Astronomical Society71: 460–470.
34.
SalmonJK (1991) Parallel Hierarchical N-body Methods. PhD thesis, California Institute of Technology, Pasadena, CA, USA.
35.
SinghJP (1993) Parallel Hierarchical N-body Methods and Their Implications for Multiprocessors. PhD thesis, Stanford University, Stanford, CA, USA.
36.
SinghJPHoltCTotsukaTGuptaAHennessyJ (1995) Load balancing and data locality in adaptive hierarchical N-body methods: Barnes–Hut, fast multipole, and radiosity. Journal of Parallel and Distributed Computing27: 118–141.
37.
TabbalAAndersonMBrodowicsMKaiserTSterlingH (2011) Preliminary design examination of the ParalleX system from a software and hardware perspective. SIGMETRICS Performance Evaluation Review38: 4.
ValiantLG (1990) A bridging model for parallel computation. Communications of the ACM33: 103–111.
40.
WarrenMSSalmonJK (1993). A parallel hashed oct-tree N-body algorithm. In Proceedings of the 1993 ACM/IEEE conference on Supercomputing, Supercomputing ’93. New York: ACM Press, pp. 12–21.
41.
WillhalmTPopoviciN (2008) Putting Intel threading building blocks to work. In IWMSE ’08: Proceedings of the 1st International Workshop on Multicore Software Engineering. New York: ACM Press, pp. 3–4.
