Swift/T: Scalable Data Flow Programming for Many …

1 swift /T: Scalable data Flow Programmingfor many -Task ApplicationsJustin M. WozniakArgonne National Laboratory &University of G. ArmstrongUniversity of WildeArgonne National Laboratory &University of S. KatzUniversity of Chicago & ArgonneNational LuskArgonne National T. FosterArgonne National Laboratory &University of a novel Programming language implementation for highlyscalable data flow programs, is and Subject [ Programming Lan-guages]: language Classifications Concurrent, distributed, andparallel languages; data -flow languagesGeneral TermsLanguagesKeywordsMPI; ADLB; swift ; Turbine; exascale; concurrency;dataflow; futures1. IntroductionMany important application classes that are driving the require-ments for extreme-scale systems branch and bound, stochasticprogramming, materials by design, uncertainty quantification canbe productively expressed as many -task data flow programs.

2 Thedata flow Programming model of the swift parallel scripting lan-guage [6] can elegantly express, through implicit parallelism, themassive concurrency demanded by these applications while retain-ing the productivity benefits of a high-level , the centralized single-node evaluation model ofthe previously developed swift implementation limits this important limitation is difficult, as evidenced bythe absence of any massively- Scalable data flow languages in cur-rent present here swift /T, a new data flow language implemen-tation designed for extreme scalability. Its technical innovations in-clude a distributed data flow engine that balances program eval-uation across massive numbers of nodes using data -flow-driventask execution and a distributed data store for global data extends the swift data flow Programming model of exter-nal executables with file-based data passing to finer-grained appli-cations using in-memory functions and in-memory to make digital or hard copies of all or part of this work for personal orclassroom use is granted without fee provided that copies are not made or distributedfor profit or commercial advantage and that copies bear this notice and the full citationon the first page.

3 To copy otherwise, to republish, to post on servers or to redistributeto lists, requires prior specific permission and/or a 13,February 23 27, 2013, Shenzhen, 2013 ACM 978-1-4503-1922/13/02.. $ have evaluated the performance and programmability ofSwift/T for a collaboration graph analysis and optimization ap-plication, a branch-and-bound game solver, and synthetic stresstests of language constructs. Our tests show that swift /T can al-ready scale to 128K compute cores with 85% efficiency for 100-second tasks . Thus, swift /T provides a Scalable parallel program-ming model for productively expressing the outer levels of highly-parallel many -task applications . The benefits of these advances areillustrated by considering the swift code fragment in Figure X = 1000, Y = 1000;2int A[][];3int B[];4foreach x in [0:X-1]{5foreach y in [0:Y-1]{6if (check(x, y)){7A[x][y] = g(f(x), f(y));8}else{9A[x][y] = 0;10}}11B[x] = sum(A[x]);12}StartOuter Loops Inner Loopscheck()then / elsef().

4 TF Spawn TaskTaskData wait/writeDatag()sum()Figure data flow implicit parallelism of this code generates 1 million concur-rent executions of the inner block of expressions, invoking as manyas 4M function calls (3M within conditional logic). Previously, thesingle-node swift engine would perform the work of sending theseleaf function tasks to distributed CPUs at<500 tasks /sec. The newSwift/T architecture, in contrast, can distribute the evaluation of theouter loop tomanyCPUs, each of which can in turn distribute theinner loop to many additional CPUs. The diagram on the right illus-trates how evaluation of the entire program not just the externaltasks at the leaves of the call graph can utilize many nodes torapidly generate massive numbers of leaf tasks . tasks in this modelare managed by Turbine and ADLB, described ApplicationsEnsemble studies involving different methodologies such as un-certainty quantification, parameter estimation, graph pruning, andinverse modeling all require the ability to generate and dispatchtasks on the order of millions to the distributed analysis and hydrologyare investigated by the Soil andWater Assessment Tool (SWAT), which analyzes hundreds of thou-sands of data files via MATLAB scripts on hundreds of cores.

5 Thisapplication will utilize tens of thousands of cores and more data inthe future. SWAT is a motivator for our work because of the largenumber of data analysisby using ModFTDockresults in a large quantity of available tasks [3], and represents acomplex, multi-stage Programming ModelWe seek to provide a system that allows code written by non-experts to run at extreme scale. This goal may be infeasible in ageneral model for computation. However, we focus on many -taskapplications, which exhibit simpler coordination Programming :We assume that much performance-critical code will remain in lower level languages such as C, For-tran, or even assembly, using threads or MPI for fine-grained par-allelism. data flow scripting provides a powerful mechanism forcoordinating these high-performance components, as it enablesfault-tolerance, dynamic load balancing and flexible, rapid com-position of components.

6 In swift , each lower-level component isviewed as a black box with well-defined inputs and parallelism: swift makes parallelism implicit, simi-larly to other data flow Programming languages such as Sisal [2]and Id [5]. When control enters a code block, any swift state-ment in that block can execute concurrently with other concurrent execution is feasible because of the functional na-ture of swift , where we avoid mutable state and use write-oncevariables pervasively to schedule execution based on data depen-dencies. Each operation, down to basic arithmetic, can be realizedas an asynchronous task, eligible to be executed anywhere in thedistributed-memory implicit and pervasive parallelism to be manageable, weneed a simple model for language semantics. It has been argued [1]that parallel languages should have a deterministic sequential inter-pretation for most language features, with non-determinism intro-duced only through explicit non-deterministic constructs.

7 All coredata types in swift ,including arrays, are guaranteed to be deter-ministic and referentially execution model:Turbine enables distributed execu-tion of large numbers of user functions and of control logic usedto compose them. Turbine requires the compiler to break user pro-gram code into many discretefragments, to enable all work to beload balanced as discrete tasks . These fragments are either user-definedleaf functions, such as external compiled procedures orexecutables, orcontrol fragmentsfor data flow coordination engines execute control tasks , while workers execute leaffunctions, as shown in Figure 2. Execution of a Turbine controllogic fragment may produce additional control fragments that areredistributed via ADLB. Turbine tracks data dependencies betweentasks in order to know when each is eligible to run.

8 Turbine pro-vides a globally-addressabledistributed future store[7], whichdrives data -dependent execution and allows typed data Asynchronous Dynamic Load Balancer (ADLB)is anMPI library for distributing tasks (work units) among worker pro-cesses [4]. ADLB is a highly Scalable system without a single bot-tleneck, and has been successfully used physics swift functions onto Turbine tasks :Computation-ally intensive non- swift functions such as compiled functions orcommand-line applications execute as Turbine leaf functions, whilecontrol flow in the swift language is implemented by using Turbinecontrol tasks . If, as is often the case, control flow in a swift func-tion requires multiple waits for data , that swift function must becompiled to multiple control Scalable load balancer / data storeADLB Scalable load balancer / data storeWorkerWorkerWorkerWorkerWorkerWorke rWorkerWorkerWorkerWorkerWorkerWorkerWor kerWorkerWorkerWorkerWorkerWorkerWorkerW orkerLeaf functionsOutput dataEngineEngineEngineEngineEngineEngine EngineEngineTurbinecodeTurbinecodeContro l fragmentsFigure of swift /T runtime: Engines evaluate Swiftlanguage semantics; workers execute leaf-task non-determinism:Some patterns are difficult to ex-press efficiently with write-once variables, for example, branchpruning in branch and bound algorithms and shared can better support such patterns.

9 An updatablevariable is initialized to a fixed number, and can then be updatedwith one of several commutative update operations. The value re-trieved by each read will not be deterministic, but the commutativ-ity property makes the non-determinism more usable than a vari-able supporting arbitrary extension functions:Since swift /T is a many -taskcomputing language , making external code callable from swift iscrucial. Currently we support applications that call C/C++/Fortranfunctions from swift scripts, by using SWIG to automatically gen-erate Future WorkWe are aware of many potential optimizations to improve swift /Tperformance, such as caching, relaxing consistency, and coalescingTurbine operations at compile or run time. We intend to exploreother load balancing methods and data -aware scheduling and ex-pect that advances in this area will yield many research is supported by the DOE Office of Science un-der contract DE-AC02-06CH11357, FWP-57810.

10 Computing re-sources were provided by the Argonne Leadership Computing Fa-cility. Some work by DSK was supported by the National ScienceFoundation, while working at the Foundation. Any opinion, find-ing, and conclusions or recommendations expressed in this mate-rial are those of the authors and do not necessarily reflect the viewsof the National Science [1] R. L. Bocchino, Jr., V. S. Adve, S. V. Adve,, M. Snir. Parallel pro-gramming must be deterministic by default. InWorkshop Hot Topics inParallelism: HotPar 09.[2] J. T. Feo, D. C. Cann,, R. R. Oldehoeft. A report on the Sisal Parallel and Distributed Computing, 1990.[3] M. Hategan, J. Wozniak,, K. Maheshwari. Coasters: uniform resourceprovisioning and access for scientific computing on clouds and Utility and Cloud Computing.