A High-Performance Parallel CONOP Program Based on a Hybrid Strategy of Simulated Annealing and Genetic Algorithm

HOU Xudong1, FAN Junxuan2,3, YANG Jiao2& HUANG Zhihao4

1 CAS Key Laboratory of Economic Stratigraphy and Palaeogeography, Nanjing Institute of Geology and Palaeontology, Nanjing 210008, China; xdhou@nigpas.ac.cn;

2 State Key Laboratory of Palaeobiology and Stratigraphy, Nanjing Institute of Geology and Palaeontology, Chinese Academy of Sciences, Nanjing 210008, China; fanjunxuan@gmail.com, yangjiaosun@163.com;

3 Laboratory for Marine Geology, Qingdao National Laboratory for Marine Science and Technology, Qingdao 266061, China;

4 Jiangsu Sugon Information Technology Co. Ltd, Nanjing 211100, China; huangzhh@sugon.com.

1 Introduction

In the fossil record there are 2 basic kinds of bio-events: first and last appearances (FAD and LAD) of a specific taxon. By correlating and sequencing tens of thousands of FADs and LADs, a high-resolution geological timescale can be achieved, which is useful for a more precise understanding of the evolution of life during Earth history. However, reconstruction of the regional or global sequence of fossils based on such a huge number of FADs and LADs is a tough, tremendous task. It is almost impossible to handle such large datasets manually without the help of computer technology. Numerous types of quantitative stratigraphic software emerged with modern computer technology and numerical algorithms during the past half-century; these can automatically sort, space and calibrate tens of thousands of bio-events from hundreds of sections, and make it possible to establish high-resolution timescales. At present, the major examples of quantitative stratigraphic software include CONOP (Constrained Optimization) (Sadler et al., 2003; Sadler, 2004), SinoCor (Fan et al., 2013), HA (Sheets et al., 2012), and UA (Guex, 1977; Monnet et al., 2011).

CONOP was originally designed based on the simulated annealing algorithm in computer science. The program can correlate the FADs and LADs from all sections automatically, thus seeking out their global or local optimal sequence. However, as the number of species increases, the time required for CONOP calculation grows dramatically. For a big dataset containing tens of thousands of bio-events, the original CONOP program, which was coded using the Fortran programming language, may require several years of processing. This is definitely unacceptable for regular research tasks. In order to solve this computational time-consuming problem, we rewrote and optimized the CONOP program in 3 stages in the past 3 years. First, we used the C# programming language to rewrite the program with a preliminary parallel function integrated in it (Hou & Fan, 2014), which is 3—5 times faster than the Fortran version when running on a quad-core-equipped personal computer. In the second stage, in 2014, we cooperated with a technical team from the SAP Nanjing Innovation Center and developed a new version based on the SAP's HANA memory database: CONOP.HANA. This version is about 33 times faster than the Fortran version. Although the computing performance has been improved remarkably, it still takes a few months to finish the analysis of a large dataset. Therefore, in the third stage, we decided to take advantage of supercomputers and parallel algorithms to completely solve the bottleneck of calculating big datasets. We redesigned the CONOP program with an efficient, combined parallel algorithm. This algorithm can fully utilize the capacity of a supercomputer system. As the number of the CPU cores increases, the computing speed can be thousands of times faster than the original CONOP program.

2 The hybrid strategy of simulated annealing and genetic algorithm

The essence of the CONOP program is searching for the sequence of FADs and LADs that best fits the fossil record of each section, i.e., the best sequence. This optimization problem is similar to the typical travelling salesman problem in combinatorial optimization. The Simulated Annealing (SA; Holland, 1975) and Genetic Algorithm (GA; Kirkpatrick et al., 1983) methods are 2 major ways of solving this kind of problem. The original CONOP program is based on simulated annealing, which shows apparent serializability. At any time, only one solution is created and evaluated, and the next solution must be created based on a mutation of the previous one. The characteristics of the Simulated Annealing algorithm make it difficult to speed up the original CONOP program on a parallel system.

It has recently been revealed that hybrid approaches combining simulated annealing and a genetic algorithm exhibit good parallelism and convergence (Mahfoud & Goldberg, 1995; Chen et al., 1998; Wang et al., 2005). Therefore, we designed a new hybrid method combining the annealing schedule of SA and the recombinative power of GA taking account of the characteristics of the bio-event data, and successfully integrated it into the CONOP program. This new parallel program was developed with the MPI (Message Passing Interface) technique and the C++ programming language, which are both widely used in high-performance computing, and the master-slave paradigm, one of the most common parallel programming paradigms.

3 Results

We conducted a comprehensive test of the new parallel program on the ‘Tianhe-2' supercomputer, the second fastest supercomputer in the world (https://www.top500.org/). The results show that the convergence tendency of the new program is as good as the original one (Fig. 1a), while its computing speed is much faster (Fig. 1b). When the new program is run with 1200 CPU cores, it is about 300 to 600 times faster than the original CONOP. The new parallel program also exhibits excellent parallelism. As the number of processes (or CPU cores) increases, the time costs decrease significantly (Fig. 1c) and the penalty (which reflects the solution quality) still remains stable (Fig. 1d).

Figure 1 Evaluation of the performance of the new parallel CONOP program. The new parallel program was tested in the Tianhe-2 supercomputer; the original CONOP program used as comparison was set up in a personal computer equipped with a 3.4-GHz CPU. All the tests used the same dataset (131 sections and 8866 bio-events). Major annealing parameters were as follows: initial temprature 800, cooling rate 0.98, and number of outer loops 600. In (a) and (b), all the tests of the parallel program were carried out with 1200 CPU cores, but the number of inner loops increased from 1200 to 6000. In (c) and (d), the number of inner loops was fixed at 7200, but the number of parallel processes increased from 120 to 2400. The ‘Penalty' parameter shown in (a) and (d) represents the misfit of a solution (or permutation): a smaller penalty generally indicates a better solution.

Acknowledgements This work was supported by the National Natural Science Foundation of China (Nos. 41521061, 41290260, 41202004) and the Chinese Academy of Sciences (No. XDPB05). This is a contribution to the IGCP Project 653 and the Geobiodiversity Database project (www.geobiodiversity.com).


References

Chen, H., Flann, N. S., Watson, D. W. 1998. Parallel genetic simulated annealing: a massively parallel SIMD algorithm. IEEE Transactions on Parallel and Distributed Systems, 9(2):126—136.

Fan, J. X., Chen, Q., Melchin, M. J., Sheets, H. D., Chen, Z. Y., Zhang, L. N., Hou, X. D. 2013. Quantitative stratigraphy of the Wufeng and Lungmachi black shales and graptolite evolution during and after the Late Ordovician mass extinction. Palaeogeography, Palaeoclimatology, Palaeoecology, 389: 96—114.

Guex, J. 1977. Une nouvelle méthode d'analyse chronologique. Bulletin de la Société Vaudoise des Sciences Naturelles, 73/3(351): 224.

Hou, X. D., Fan, J. X. 2014. CONOP — A quantitative stratigraphic software and an approach to its parallelization. In: Zhan, R. B., Huang, B. (eds.), Extended Summary (IGCP Project 591 Field Workshop), pp. 61—63.

Holland, J. H. 1975. Adaptation in Natural and Artificial Systems. Cambridge, Mass.: MIT Press.

Kirkpatrick, S., Gelatt, Jr. C. D., Vecchi, M. P. 1983. Optimization by simulated annealing. Science, 220 (4598): 671—679.

Mahfoud, S. W., Goldberg, D. E. 1995. Parallel recombinative simulated annealing: a genetic algorithm. Parallel Computing, 21: 1—28.

Monnet, C., Klug, C., Goudemand, N., Baets, K. D., Bucher, H. 2011. Quantitative biochronology of Devonian ammonoids from Morocco and proposals for a refined unitary association method. Lethaia, 44(4): 469—489.

Sheets, H. D., Mitchell, C. E., Izard, Z. T., Wills, J. M., Melchin, M. J., Holmden, C. 2012. Horizon annealing: a collection-based approach to automated sequencing of the fossil record. Lethaia, 45(4): 532—547.

Sadler, P. M. 2004. Quantitative biostratigraphy — achieving finer resolution in global correlation. Annual Review of Earth and Planetary Sciences, 32: 187—213.

Sadler, P. M., Kemple, W. G., Kooser, M. A. 2003. Contents of the compact disk — CONOP 9 programs for solving the stratigraphic correlation and seriation problems as constrained optimization. In: Harries, P. J. (ed.), High Resolution Approaches in Stratigraphic Paleontology, Topics in Geobiology, v. 21. Dordrecht: Kluwer Academic Publishers, pp. 461—465.

Wang, Z. G., Wong, Y. S., Rahman, M. 2005. Development of a parallel optimization method based on genetic simulated annealing algorithm. Parallel Computing, 31: 839—857.

上一章目录下一章