Scheduling Finite Difference Approximations for DAG-Modeled Large Scale Applications

ABSTRACT

An increasing number of scientific domains are confronted with the arduous task of managing large scale applications. For such applications, gradient estimations come at a large computational cost. Despite notable advances in automatic differentiation during the last years, its use in this context may reveal too costly in memory, inadequate for parallel architecture or require expert knowledge. For these reasons, we investigate an alternative approach that uses the finite difference method to evaluate the gradient of functions modeled as a directed acyclic graph. This approach enables the reuse of partial results from previous partial derivatives evaluations and thus reduces the computational cost.

We identify a discrete optimization problem arising in the limited-memory context of large scale applications that aims to maximize the computational efficiency of the gradient approximation by scheduling the partial derivatives. This optimization problem is extended to consider the partitioning of the computations on multiple processors. We further derive some properties of these optimization problems, such as their upper bound on performance gains.

Following a brief description of algorithms designed to obtain sensible solutions for both problems, we study the increase in performance resulting from sequential and parallel schedules obtained for synthetic DAGs. Finally, we employ this approach to accelerate the gradient evaluation of DAGs representing real evolutionary biology models. For one of these large scale applications, our approach is shown to be nearly 400 times faster than a state-of-the-art software in sequential, and more than 11,000 times faster when using 256 processors.

References

1. Kunal Agrawal, Jing Li, Kefu Lu, and Benjamin Moseley. 2016. Scheduling parallel DAG jobs online to minimize average flow time. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 176--189.
2. Ishfaq Ahmad and Yu-Kwong Kwok. 1998. On Exploiting Task Duplication in Parallel Program Scheduling. IEEE Trans. Parallel Distrib. Syst. 9, 9 (Sept. 1998), 872--892.
3. Enrique Alba and José M. Troya. 1999. A survey of parallel distributed genetic algorithms. Complexity 4, 4 (mar 1999), 31--52.
4. David L Applegate, Robert E Bixby, Vasek Chvatal, and William J Cook. 2011. The traveling salesman problem: a computational study. Princeton university press.
5. Michael Bartholomew-Biggs, Steven Brown, Bruce Christianson, and Laurence Dixon. 2000. Automatic differentiation of algorithms. J. Comput. Appl. Math. 124, 1--2 (dec 2000), 171--190.
6. Tolga Bektas. 2006. The multiple traveling salesman problem: an overview of formulations and solution procedures. Omega 34, 3 (jun 2006), 209--219.
7. C. H. Bennett. 1973. Logical Reversibility of Computation. IBM J. Res. Dev. 17, 6 (Nov. 1973), 525--532.
8. Christian H. Bischof, H. Martin Bücker, and Arno Rasch. 2010. Enabling Technologies for Robust High-Performance Simulations in Computational Fluid Dynamics. Springer Berlin Heidelberg, Berlin, Heidelberg, 153--180.
9. Erin N. Bodine, Suzanne Lenhart, and Louis J. Gross. 2014. Mathematics for the Life Sciences. (aug 2014).
10. Yesnier Bravo, Gabriel Luque, and Enrique Alba. 2013. Migrants Selection and Replacement in Distributed Evolutionary Algorithms for Dynamic Optimization. 217 (2013), 155--162.
11. Erick Cantú-Paz. 1998. A survey of parallel genetic algorithms. Calculateurs paralleles, reseaux et systems repartis 10, 2 (1998), 141--171.
12. Daniel Cordeiro, Grégory Mounié, Swann Perarnau, Denis Trystram, Jean-Marc Vincent, and Frédéric Wagner. 2010. Random Graph Generation for Scheduling Simulations. (2010), 60:1--60:10.
13. Benjamin Dauvergne and Laurent Hascoët. 2006. The data-flow equations of checkpointing in reverse automatic differentiation. In International Conference on Computational Science. Springer, 566--573.
14. Andreas Griewank and Andrea Walther. 2008. Evaluating derivatives: principles and techniques of algorithmic differentiation. Siam.
15. L. Hascoët and V. Pascual. 2013. The Tapenade Automatic Differentiation tool: Principles, Model, and Specification. ACM Trans. Math. Software 39, 3 (2013), 20:1--20:43.
16. Laurent Hascoët and Ala Taftaf. 2016. On the correct application of AD checkpointing to adjoint MPI-parallel programs. Research Report RR-8864. Inria Sophia Antipolis. https://hal.inria.fr/hal-01277449
17. Ibrahim Abaker Targio Hashem, Ibrar Yaqoob, Nor Badrul Anuar, Salimah Mokhtar, Abdullah Gani, and Samee Ullah Khan. 2015. The rise of "big data" on cloud computing: Review and open research issues. Information Systems 47 (jan 2015), 98--115.
18. Keld Helsgaun. 2000. An effective implementation of the Lin--Kernighan traveling salesman heuristic. European Journal of Operational Research 126, 1 (2000), 106-- 130.
19. Sebastian Höhna, Tracy A. Heath, Bastien Boussau, Michael J. Landis, Fredrik Ronquist, and John P. Huelsenbeck. 2014. Probabilistic Graphical Model Representation in Phylogenetics. Systematic Biology 63, 5 (sep 2014), 753--771.
20. Michael I. Jordan. 2004. Graphical Models. Statist. Sci. 19, 1 (feb 2004), 140--155.
21. Slawomir Koziel, Leifur Leifsson, Michael Lees, Valeria V.Krzhizhanovskaya, Jack Dongarra, Peter M.A. Sloot, Markus Towara, Michel Schanen, and Uwe Naumann. 2015. International Conference On Computational Science, ICCS 2015MPI-Parallel Discrete Adjoint OpenFOAM. Procedia Computer Science 51 (jan 2015), 19--28.
22. Suresh Nanda Kumar and Ramasamy Panneerselvam. 2012. A survey on the vehicle routing problem and its variants. Intelligent Information Management 4, 3 (2012), 66.
23. Yu-Kwong Kwok and Ishfaq Ahmad. 1999. Static Scheduling Algorithms for Allocating Directed Task Graphs to Multiprocessors. ACM Comput. Surv. 31, 4 (dec 1999), 406--471.
24. Joaquim Martins, John Hwang, John Hwang, and John Hwang. 2013. Review and Unification of Methods for Computing Derivatives of Multidisciplinary Computational Models. AIAA Journal 51, 11 (2013), 2582--2599.
25. Vivien Marx. 2013. Biology: The big challenges of big data. Nature 498, 7453 (jun 2013), 255--260.
26. Uwe Naumann. 2012. The Art of Differentiating Computer Programs: An Introduction to Algorithmic Differentiation. 24 (2012).
27. Uwe Naumann, Laurent Hascoët, Chris Hill, Paul Hovland, Jan Riehme, and Jean Utke. 2008. A Framework for Proving Correctness of Adjoint Message-Passing Programs. (2008), 316--321.
28. Rasmus Nielsen and Ziheng Yang. 1998. Likelihood models for detecting positively selected amino acid sites and applications to the HIV-1 envelope gene. Genetics 148, 3 (1998), 929--936.
29. Jorge Nocedal and Stephen J. Wright. 2006. Numerical optimization. (2006).
30. IM Oliver, DJd Smith, and John RC Holland. 1987. Study of permutation crossover operators on the traveling salesman problem. In Genetic algorithms and their applications: proceedings of the second International Conference on Genetic Algorithms: July 28-31, 1987 at the Massachusetts Institute of Technology, Cambridge, MA. Hillsdale, NJ: L. Erlhaum Associates, 1987.
31. Beatrice Ombuki-Berman and Franklin T. Hanshar. 2009. Using Genetic Algorithms for Multi-depot Vehicle Routing. 161 (2009), 77--99.
32. Sergei L. Kosakovsky Pond, Ben Murrell, Mathieu Fourment, Simon D. W. Frost, Wayne Delport, and Konrad Scheffler. 2011. A Random Effects Branch-Site Model for Detecting Episodic Diversifying Selection. Molecular Biology and Evolution 28, 11 (Nov. 2011), 3033--3043.
33. Sergei L Kosakovsky Pond and Spencer V Muse. 2005. HyPhy: hypothesis testing using phylogenies. In Statistical methods in molecular evolution. Springer, 125-- 181.
34. Jean-Yves Potvin. 1996. Genetic algorithms for the traveling salesman problem. Annals of Operations Research 63, 3 (jun 1996), 337--370.
35. R. Alexander Pyron, Frank T. Burbrink, and John J. Wiens. 2013. A phylogeny and revised classification of Squamata, including 4161 species of lizards and snakes. BMC Evolutionary Biology 13 (2013), 93.
36. Le Si Quang, Olivier Gascuel, and Nicolas Lartillot. 2008. Empirical profile mixture models for phylogenetic reconstruction. Bioinformatics 24, 20 (2008), 2317--2323.
37. Louis B Rall and George F Corliss. 1996. An introduction to automatic differentiation. Computational Differentiation: Techniques, Applications, and Tools (1996), 1--17.
38. Arno Rasch, H Martin Bucker, and Christian H Bischof. 2008. Automatic computation of sensitivities for a parallel aerodynamic simulation. Parallel Computing: Architectures, Algorithms and Applications. Advances in Parallel Computing 15 (2008), 303--310.
39. Colin R. Reeves. 2010. Genetic Algorithms. 146 (2010), 109--139.
40. César Rego, Dorabela Gamboa, Fred Glover, and Colin Osterman. 2011. Traveling salesman problem heuristics: Leading methods implementations and latest advances. European Journal of Operational Research 211, 3 (jun 2011), 427--441.
41. Sartaj K. Sahni. 1976. Algorithms for Scheduling Independent Tasks. J. ACM 23, 1 (jan 1976), 116--127.
42. Michel Schanen, Uwe Naumann, Laurent Hascoët, and Jean Utke. 2010. ICCS 2010 Interpretative adjoints for numerical simulation codes using MPI. Procedia Computer Science 1, 1 (2010), 1825--1833.
43. Zachary D. Stephens, Skylar Y. Lee, Faraz Faghri, Roy H. Campbell, Chengxiang Zhai, Miles J. Efron, Ravishankar Iyer, Michael C. Schatz, Saurabh Sinha, and Gene E. Robinson. 2015. Big Data: Astronomical or Genomical? PLoS Biol 13, 7 (jul 2015), e1002195.
44. Jean Utke, Laurent Hascoët, Patrick Heimbach, Chris Hill, Paul Hovland, and Uwe Naumann. 2009. Toward adjoinable MPI. In Parallel & Distributed Processing, 2009. IPDPS 2009. IEEE International Symposium on. IEEE, 1--8.
45. Mario Valle, Hannes Schabauer, Christoph Pacher, Heinz Stockinger, Alexandros Stamatakis, Marc Robinson-Rechavi, and Nicolas Salamin. 2014. Optimization strategies for fast detection of positive selection on phylogenetic trees. Bioinformatics (jan 2014), btt760.
46. C. Voglis, P. E. Hadjidoukas, I. E. Lagaris, and D. G. Papageorgiou. 2009. A numerical differentiation library exploiting parallel architectures. Computer Physics Communications 180, 8 (aug 2009), 1404--1415.
47. Yu. M. Volin and G. M. Ostrovskii. 1985. Automatic computation of derivatives with the use of the multilevel differentiating technique---1. Algorithmic basis. Computers & Mathematics with Applications 11 (nov 1985), 1099--1114.
48. Martin J. Wainwright and Michael I. Jordan. 2007. Graphical Models, Exponential Families, and Variational Inference. Foundations and Trends® in Machine Learning 1, 1--2 (2007), 1--305.
49. Andrea Walther and Andreas Griewank. Getting Started with ADOL-C.. In Combinatorial scientific computing. 181--202.
50. Wei Xu, Xi Chen, and Thomas F Coleman. 2014. The efficient application of automatic differentiation for computing gradients in financial applications. J. Comput. Finance (2014). name number (url).
51. Ziheng Yang. 1993. PAML: Phylogenetic Analysis by Maximum Likelihood. Molecular Biology and Evolution 24 (1993), 1586--1591.
52. Ziheng Yang. 2007. PAML 4: phylogenetic analysis by maximum likelihood. Molecular biology and evolution 24, 8 (2007), 1586--1591.
53. Ziheng Yang and Rasmus Nielsen. 2002. Codon-Substitution Models for Detecting Molecular Adaptation at Individual Sites Along Specific Lineages. Molecular Biology and Evolution 19, 6 (jun 2002), 908--917.

Index Terms

• Applied computing

  • Life and medical sciences

    • Computational biology

      • Molecular sequence analysis

• Computing methodologies

  • Parallel computing methodologies

    • Parallel algorithms

• Mathematics of computing

  • Discrete mathematics

    • Combinatorics

      • Combinatorial optimization

      • Combinatoric problems

  • Mathematical analysis

    • Numerical analysis

      • Numerical differentiation

• Theory of computation

  • Design and analysis of algorithms

    • Mathematical optimization

      • Discrete optimization

        • Optimization with randomized search heuristics

          • Evolutionary algorithms

  • Models of computation

    • Concurrency

      • Parallel computing models