We take a historical approach to our presentation of self-scheduled task parallelism, a programming model with its origins in early irregular and nondeterministic computations encountered in automated theorem proving and logic programming. We show how an extremely simple task model has evolved into a system, asynchronous dynamic load balancing (ADLB), and a scalable implementation capable of supporting sophisticated applications on today’s (and tomorrow’s) largest supercomputers; and we illustrate the use of ADLB with a Green’s function Monte Carlo application, a modern, mature nuclear physics code in production use. Our lesson is that by surrendering a certain amount of generality and thus applicability, a minimal programming model (in terms of its basic concepts and the size of its application programmer interface) can achieve extreme scalability without introducing complexity.
AcunBGuptaAJainNLangerAMenonHMikidaENiXRobsonMSunYTotoniEWesolowskiLKaleL (2014) Parallel programming with migratable objects: Charm++ in practice, In: Proceedings of the international conference for high performance computing, networking, storage and analysis, New Orleans, Louisana, 16–21 November 2014. DOI:10.1109/SC.2014.58.
AhujaSCarrieroNGelernterD (1986) Linda and friends. IEEE Computer19(8): 26–34.
4.
ArmstrongTJustinMWildeWM (2015) Swift: extreme-scale, implicitly parallel scripting. In: BalajiP (ed), Programming Models for Parallel Computing, Scientific and Engineering Computation Series, Chapter 11. Cambridge: MIT Press, pp. 219–203.
5.
BalajiPChanAThakurR. (2009) Toward message passing for a million processes: characterizing MPI on a massive scale Blue Gene/P. Computer Science-Research and Development24(1–2): 11–19.
6.
BauerMTreichlerSSlaughterE. (2012) Legion: expressing locality and independence with logical regions. In: Proceedings of the International Conference on Supercomputing. ACM/IEEE.
7.
BoyleJButlerRDiszT. (1987) Portable Programs for Parallel Processors. New York: Holt, Rinehart, and Winston.
8.
ButlerRDiszTLuskE. (1990) The Aurora OR-parallel Prolog system. New Generation Computing7: 243–271.
9.
ButlerRDiszTLuskE. (1988) Scheduling OR-parallelism: an Argonne perspective. In: KowalskiRBowenK (ed), Proceedings of the Fifth International Conference and Symposium on Logic Programming. Cambridge: MIT Press, pp. 1590–1608.
10.
ButlerRLevetonALuskE (1993, July) p4-Linda: a portable implementation of linda. In: Proceedings of the Second International Symposium on High-Performance Distributed Computing. Piscataway: IEEE, pp. 50–58.
11.
ButlerRLuskE (1994) Monitors, messages, and clusters: the p4 parallel programming system. Parallel Computing20: 547–564.
12.
CarlsonJGandolfiSPederivaF. (2015) Quantum monte carlo methods for nuclear physics. Reviews of Modern Physics87: 1067–1118.
13.
DinanJ (2015) Scalable collections of task objects. In: BalajiP (ed), Programming Models for Parallel Computing, Scientific and Engineering Computation Series, chapter 11. Cambridge: MIT Press, pp. 247–279.
14.
DinanJKrishnamoorthySLarkinsDB. (2008) Scioto: a framework for global-view task parallelism. In: Proceedings of the 2008 37th International Converence on Parallel Processing ICPP ‘08.
15.
HansenPB (1977) The Architecture of Concurrent Programs. New Jersey: Prentice-Hall, Inc.
16.
HoareCAR (1974) Monitors: an operating system structuring concept. Communications of the ACM17(10): 549–557.
17.
KaleLJainNLifflanderJ (2015) Charm++. In: BalajiP (ed), Programming Models for Parallel Computing, Scientific and Engineering Computation Series, chapter 7, Cambridge: MIT Press, pp 161–186.
18.
KaléLVKrishnanS (1993, 9) CHARM++: a portable concurrent object oriented system based on C++. In: PaepckeA (ed), Proceedings of OOPSLA’93. Cambridge: ACM Press, pp. 91–108.
19.
KnobeKBurkeMGSchlimbachF (2015) Concurrent collections. In: BalajiP (ed), Programming Models for Parallel Computing, Scientific and Engineering Computation Series, chapter 11. Massachusetts, Boston: MIT Press, pp.247–279.
20.
LaGroneJAribukiAAddisonC. (2011) A runtime implementation of openmp tasks. In: ChapmanBMGroppWDKumaranK. (eds), OpenMP in the Petascale Era, Volume 6665 of Lecture Notes in Computer Science. . Berlin: Springer, pp. 165–178.
21.
LovatoAGandolfiSButlerR. (2015) Charge form factor and sum rules of electromagnetic response functions in C 12. Physical Review Letters111: 092501.
22.
LuskEButlerRPieperSC (2015) Asynchronous dynamic load balancing. In: BalajiP (ed), Programming Models for Parallel Computing, Scientific and Engineering Computation Serieschapter 8, pp. 186–203. Cambridge: MIT Press.
23.
LuskEMcCuneW (1992) Experiments with ROO, a parallel automated deduction system. In: FronhofferEWrightsonG (eds.) Proceedings of Parallelization in Inference Systems, Volume 590 of Lecture Notes in Computer Science, Dagstuhl, Germany. Berlin: Springer-Verlag, pp. 139–162.
24.
LuskEOverbeekRA (1982) Experiments with resolution-based theorem-proving algorithms. Computers and Mathematics with Applications8(3):141–152.
25.
LuskEPieperSCButlerR (2010) More scalability, less pain: a simple programming model and its implementation for extreme scale computing. SciDAC Review17: 30–37.
PieperSCVargaKWiringaRB (2002) Quantum monte carlo calculations of A=9,10 nuclei. Physical Review C66: 044310.
28.
PLASMA–parallel linear algebra software for multicore architectures. Available at:www.netlib.org/plasma(accessed on April 8, 2017)
29.
WildeMHateganMWozniakJM. (2011) Swift: a language for distributed parallel scripting. Parallel Computing37(9): 633–652.
30.
WiringaRBPieperSCCarlsonJ. (2000) Quantum monte carlo calculations of A=8 nuclei. Physical Review C62: 014001.
31.
WosLWinkerSLuskE (1981) An automated reasoning system. Proceedings of the National Computer Conference50: 697–702.
32.
WozniakJMArmstrongTGMaheshwariK. (2013) Turbine: a distributed-memory dataflow engine for high performance many-task applications. Fundamenta Informaticae28(3): 337–366.
