Algorithm 897: VTDIRECT95: Serial and parallel codes for the global optimization algorithm direct

ABSTRACT

VTDIRECT95 is a Fortran 95 implementation of D. R. Jones' deterministic global optimization algorithm called DIRECT, which is widely used in multidisciplinary engineering design, biological science, and physical science applications. The package includes both a serial code and a data-distributed massively parallel code for different problem scales and optimization (exploration vs. exploitation) goals. Dynamic data structures are used to organize local data, handle unpredictable memory requirements, reduce the memory usage, and share the data across multiple processors. The parallel code employs a multilevel functional and data parallelism to boost concurrency and mitigate the data dependency, thus improving the load balancing and scalability. In addition, checkpointing features are integrated into both versions to provide fault tolerance and hot restarts. Important algorithm modifications and design considerations are discussed regarding data structures, parallel schemes, error handling, and portability. Using several benchmark functions and real-world applications, the software is evaluated on different systems in terms of optimization effectiveness, data structure efficiency, parallel performance, and checkpointing overhead. The package organization and usage are also described in detail.

REFERENCES

• 1: Baker, C. A., Watson, L. T., Grossman, B., Haftka, R. T., and Mason, W. H. 2000. Parallel global aircraft configuration design space exploration. In Proceedings of the High Performance Computing Symposium, A. Tentner, Ed. Society for Computer Simulation International, San Diego, 101--106.
• 2: Bartholomew-Biggs, M. C., Parkhurst, S. C., and Wilson, S. P. 2003. Global optimization approaches to an aircraft routing problem. European J. Operat. Res. 146, 2, 417--431.
• 3: Rajanikanth Batchu , Yoginder S. Dandass , Anthony Skjellum , Murali Beddhu, MPI/FT: A Model-Based Approach to Low-Overhead Fault Tolerant Message-Passing Middleware, Cluster Computing, v.7 n.4, p.303-315, October 2004 [doi>10.1023/B:CLUS.0000039491.64560.8a]
• 4: Bouteiller, A., Herault, T., Krawezik, G., Lemarinier, P., and Cappello, F. 2006. MPICH-V project: A multiprotocol automatic fault-tolerant MPI. Int. J. High-Perform. Comput. Appl. 20, 3, 319--333.
• 5: Carter, R. G., Gablonsky, J. M., Patrick, A., Kelly, C. T., and Eslinger, O. J. 2001. Algorithms for noisy problems in gas transmission pipeline optimization. Optimiz. Eng. 2, 2, 139--157.
• 6: Graham E. Fagg , Antonin Bukovsky , Jack J. Dongarra, HARNESS and fault tolerant MPI, Parallel Computing, v.27 n.11, p.1479-1495, October 2001 [doi>10.1016/S0167-8191(01)00100-4]
• 7: Finkel, D. E. and Kelly, C. T. 2004. An adaptive restart implementation of DIRECT. Tech. Rep. CRCS-TR04-30. Center for Research in Scientific Computation, North Carolina State University, Raleigh.
• 8: Jorg Maximilian Xaver Gablonsky , Carl Timothy Kelley, Modifications of the direct algorithm, 2001
• 9: William Gropp , Ewing Lusk, Fault Tolerance in Message Passing Interface Programs, International Journal of High Performance Computing Applications, v.18 n.3, p.363-372, August 2004 [doi>10.1177/1094342004046045]
• 10: He, J., Verstak, A., Sosonkina, M., and Watson, L. T. 2007a. Performance modeling and analysis of a massively parallel DIRECT: Part 2. Tech. rep. TR-07-02. Department of Computer Science, Virginia Polytechnic Institute&State University, Blacksburg.
• 11: He, J., Verstak, A., Watson, L. T., and Sosonkina, M. 2007b. Performance modeling and analysis of a massively parallel DIRECT: Part 1. Tech. rep. TR-07-01. Department of Computer Science, Virginia Polytechnic Institute&State University, Blacksburg.
• 12: Jian He , Alex Verstak , Layne T. Watson , Masha Sosonkina, Design and implementation of a massively parallel version of DIRECT, Computational Optimization and Applications, v.40 n.2, p.217-245, June 2008 [doi>10.1007/s10589-007-9092-2]
• 13: He, J., Verstak, A., Watson, L. T., Stinson, C. A., Ramakrishnan, N., Shaffer, C. A., Rappaport, T. S., Anderson, C. R., Bae, K., Jiang, J., and Tranter, W. H. 2004. Globally optimal transmitter placement for indoor wireless communication systems. IEEE Trans. Wireless Commun. 3, 6, 1906--1911.
• 14: Jian He , Layne T. Watson , Naren Ramakrishnan , Clifford A. Shaffer , Alex Verstak , Jing Jiang , Kyung Bae , William H. Tranter, Dynamic Data Structures for a Direct Search Algorithm, Computational Optimization and Applications, v.23 n.1, p.5-25, October 2002 [doi>10.1023/A:1019992822938]
• 15: Reiner Horst, Introduction to Global Optimization (Nonconvex Optimization and Its Applications), Springer-Verlag New York, Inc., Secaucus, NJ, 2002
• 16: Horst, R. and Tuy, H. 1996. Global Optimization: Deterministic Approaches. Springer Verlag, Berlin, Germany.
• 17: D. R. Jones , C. D. Perttunen , B. E. Stuckman, Lipschitzian optimization without the Lipschitz constant, Journal of Optimization Theory and Applications, v.79 n.1, p.157-181, Oct. 1993 [doi>10.1007/BF00941892]
• 18: K. Ljungberg , S. Holmgren , Ö. Carlborg, Simultaneous search for multiple QTL using the global optimization algorithm DIRECT, Bioinformatics, v.20 n.12, p.1887-1895, August 2004 [doi>10.1093/bioinformatics/bth175]
• 19: Louca, S., Neophytou, N., Lachanas, A., and Evripidou, P. 2000. MPI-FT: Portable fault tolerance scheme for MPI. Parall. Proc. Lett. 10, 4, 371--382.
• 20: Meza, J. C., Judson, R. S., Faulkner, T. R., and Treasurywala, A. M. 1996. A comparison of a direct search method and a genetic algorithm for conformational searching. J. Comput. Chem. 17, 9, 1142--1151.
• 21: Thomas D. Panning , Layne T. Watson , Nicholas A. Allen , Katherine C. Chen , Clifford A. Shaffer , John J. Tyson, Deterministic parallel global parameter estimation for a model of the budding yeast cell cycle, Journal of Global Optimization, v.40 n.4, p.719-738, April 2008 [doi>10.1007/s10898-007-9273-7]
• 22: Pinter, J. D. 1996. Global Optimization In Action. Kluwer Academic Publishers, Boston.
• 23: James S. Plank, An Overview of Checkpointing in Uniprocessor and DistributedSystems, Focusing on Implementation and Performance, University of Tennessee, Knoxville, TN, 1997
• 24: Michael J. Quinn, Parallel Programming in C with MPI and OpenMP, McGraw-Hill Education Group, 2003
• 25: Watson, L. T. and Baker, C. A. 2001. A fully-distributed parallel global search algorithm. Eng. Comput. 18, 1/2, 155--169.
• 26: Layne T. Watson , Maria Sosonkina , Robert C. Melville , Alexander P. Morgan , Homer F. Walker, Algorithm 777: HOMPACK90: a suite of Fortran 90 codes for globally convergent homotopy algorithms, ACM Transactions on Mathematical Software (TOMS), v.23 n.4, p.514-549, Dec. 1997 [doi>10.1145/279232.279235]
• 27: Zhu, H. and Bogy, D. B. 2002. DIRECT algorithm and its application to slider air-bearing surface optimization. IEEE Trans. Magnet. 38, 5, 2168--2170.
• 28: Zwolak, J. W., Tyson, J. J., and Watson, L. T. 2005. Globally optimised parameters for a model of mitotic control in frog egg extracts. IEE Syst. Biol. 152, 2, 81--92.

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.2 PHYSICAL SCIENCES AND ENGINEERING
      Subjects: Mathematics and statistics

Additional Classification:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE

General Terms:
Algorithms, Design, Documentation

Keywords:
DIRECT, checkpointing, data structures, global optimization, parallel schemes