The article describes parallel implementations of two parametric identification algorithms. The first algorithm is based on the estimation of Bravais unit cell parameters, and the second one estimates Wigner-Seitz cell volumes. The developed parallel implementations are based on the two-tier model of concurrency. An external tier of concurrency uses Message Passing Interface (MPI) technique to distribute parametric identification tasks between computing nodes. An internal tier uses Open Multi-Processing (OpenMP) technique to split single steps of the parametric identification algorithms into independent subtasks. Experimental results on multi-processor / multi-core systems have demonstrated almost linear speedup of the parallel implementations, confirmed the effectiveness of the two-tier concurrency model and proved the stability of the identification approach under lattice distortion.
Structural identification of crystal lattices in three-dimensional space is one of the
basic problems of X-ray diffraction analysis [
Therefore, the reverse side of the proposed approach is its high computational complexity. To overcome this drawback, we decided to develop the parallel implementations of parametric identification algorithms that would use the computing power of modern multi-processor / multi-core systems with maximum efficiency. The main requirement for the developed parallel implementations was scaling efficiency. Consequently, it was necessary to provide a large number of independent computing tasks that could be executed in parallel. To solve the problem of scaling, we proposed a two-tier concurrency model, described in the article.
The developed methods of crystal lattice parametric identification estimate and compare parameters of the unit cells that form the entire lattice. It is obvious that these methods have a high degree of locality: the initial data they require are coordinates of a few, the most closely located, lattice points (Fig. 1.). It should be noted that the estimation of parameters for each unit cell can process independently. The necessity of data exchange appears only at the final stage, when the analysis of unit cell parameters and the calculation of the entire lattice parameters take place.
Hence, the proposed allocation of parameter estimation tasks called the external tier of concurrency is universal for all parametric identification method. It can be described by the following algorithm: 1. Find all lattice points that do not belong to any lattice face – the step executes on the master node. 2. Scatter uniformly the found lattice points in conjunction with the nearest points that lies inside the sphere of a given radius among the computing nodes. 3. Calculate parameters for each set of lattice points – the step executes by all computing nodes in parallel. 4. Gather all calculated parameters and estimate final ones for the entire lattice – the step executes one the master node.
It is obvious that the described algorithm of parallel implementation corresponds to
the MPI technique [
The proposed approach allows to avoid unbalanced load distribution (the number of tasks on each computing nodes will not differ by more than one task).
However, in case of using a large amount of multi-core processors, the number of independent tasks that calculate unit cell parameters may be insufficient to load all available computing cores. Due to the lack of independent tasks on the external concurrency tier, we decided to organize an additional internal tier of concurrency for both parametric identification method by parallelizing the steps of parameter estimations.
Parallel implementation of the Bravais unit cell parameter estimation
An algorithm of the Bravais unit cell parameter estimation is a sequence of steps that
must be carried out strictly one by one [
The computational complexity of the algorithm steps for a lattice with N lattice points are as follows: 1. Select the first nearest node – O (N). 2. Exclude nodes that lie on the same line with the selected node – O (N). 3. Select the second nearest node – O (N). 4. Exclude nodes that lie in the same plane with the two selected nodes – O (N). 5. Select the third nearest node – O (N). 6. Calculate the parameters of the Bravais unit cell – O (1).
The first five steps have the maximum computational complexity. Consequently, the
parallel execution of these steps will allow to achieve the maximum scalability.
Figure 2 demonstrates the scheme of the proposed parallel implementation.
Parallel implementation of the Wigner-Seitz unit cell volume estimation
An algorithm of the Wigner-Seitz unit cell volume estimation is a sequence of steps
that must be carried out strictly one by one [
Due to the fact that the second and the third steps have the greatly higher computational complexity (the minimum number of scattered points to ensure a sufficient level of volume calculation accuracy is 100 000 points), the parallel execution should be organized within these steps, leaving other steps sequential.
Common features of the developed parallel implementations of the both algorithms
are data dependence and a large number of communications at each step and between
the steps. Thus, the most appropriate model for the parallel implementation is an
OpenMP model [
T S p 1 ,
Tp (1)
The aim of this experiment was an investigation of the dependence between the speedup of the developed parallel implementations and the number of computing nodes / identification tasks.
The speedup obtained using a parallel implementation for p cores compared with a
sequential algorithm was determined by the following equation [
According to the equation (1), the best value of the speedup is a linear speedup when the execution time of parallel implementation growths linearly with the increase of core number.
A two triclinic lattices were used as an analyzed lattices: small (s) and big (b). Lattice sizes were chosen in order to provide the following time of parameter estimation computing on a single core: about 1 second for the small lattice; about 5 minutes for the big one. This selection allows to estimate speedup at a small number of concurrent tasks when the overhead of parallel computing prevails, as well as predict the speedup growth with the increase of the lattice size, the number of cores and the task complexity.
The experiment was conducted on a desktop computer based on a quad-core processor Intel Core i5 3470 (base frequency 3.8 GHz).
Lattice size for each parametric identification method were as follows: the method of Bravais unit cell parameters estimation – 24 and 51 translations in each direction; the method of Wigner-Seitz unit cell volume estimation – 8 and 17 translations in each direction.
The obtained data are presented in the form of then diagram showing the speedup of the parallel implementations for different numbers of cores (Fig. 4). The results confirm that the parallel implementations of both parametric identification methods provide almost linear speedup over the whole range of used lattice sizes and core configurations. The difference between the obtained values of speedup for small and big lattice is less than 5%.
Investigation of the speedup on multiprocessor / multicore cluster system The experiment was conducted on 16 cluster nodes of supercomputer “Sergey Korolev”. Each node contained two quad-core Intel Xeon X5560 processor (base frequency 2.80 GHz).
Lattice size for each parametric identification method were as follows: the method of Bravais unit cell parameters estimation – 19 and 37 translations in each direction; the method of Wigner-Seitz cell volume estimation – 4 and 13 translations in each direction.
It should be noted that the lattice of 4 translations cannot provide a sufficient number of parameter calculation tasks that is necessary for the uniform loading of all computing cores of the cluster (only 27 parallel tasks). In this case, the internal concurrency tier begins to play the leading role balancing the processing load on each core. The obtained data are presented in the form of the diagram showing the speedup of parallel implementations for different numbers of computing nodes (Fig. 5). From the presented diagram it can be seen, the parallel implementations provide almost linear speedup on a single octa-core node of the cluster. These results indirectly confirms the results from the previous section. As expected for the small lattices, the worst speedup was shown by the parallel implementation of the Wigner-Seitz cell volume estimation. However, even in the case of small lattice, the parallel implementation provides the speedup significantly higher than the number of the cluster nodes. This result confirms the effectiveness of the two-tier model of concurrency.
An ideal lattice is only a mathematical simplification, since real lattices always contains some dislocations and impurities in their structure. This fact can crucially affect the accuracy of parameter estimation, especially if we analyze not the whole lattice structure but only a single unit cell. The example of a distorted lattice and incorrectly estimated parameters of Brave and Wigner-Seitz unit cells are shown in Figure 6. a) b) c) In the last experiment, we investigated the stability of the proposed parameter estimation algorithms under lattice distortion implemented by randomly added/removed lattice points in the lattice structure. A cubic lattice contained 1000 lattice points (10 translations in each direction) was a sample. The number of randomly added/removed lattice points varied from 10 to 100 points. The proposed parallel algorithms was used to estimate unit cell parameters whereas the similarity measures determined the accuracy of corresponding parameter estimations. Results of the experiment are presented in Figure 7. According to the graph, the edge similarity showed the maximum stability. Its value did not fall below 0.98 at 10 % of added/removed lattice points. On the contrary, the volumes similarity measure demonstrated the lowest stability among other measures. However, even at the maximum level of distortion, its value was more than 0.9. The obtained results prove high stability of the developed parameter estimation algorithms to random distortion of the lattice structure.
The developed parallel implementations of parametric identification algorithms for crystal lattices in three-dimensional space effectively combine the two basic approaches to parallel programming: MPI at the external concurrency tier and OpenMP at the internal concurrency tier.
The experiments have shown that the developed parallel implementations achieves almost linear speedup on both a desktop computer and a cluster. Therefore, the use of a two-tier concurrency model allows to load the computing powers of multiprocessor / multicore systems with maximum efficiency.
In addition, the developed parallel implementation helped to prove the stability of the proposed approach of crystal lattice parameter estimation to random distortion of the lattice structure.
This work was partially supported by the Ministry of education and science of the Russian Federation in the framework of the implementation of the Program of increasing the competitiveness of SSAU among the world’s leading scientific and educational centers for 2013-2020 years; by the Russian Foundation for Basic Research grants (# 14-07-97040, # 15-29-03823, # 15-29-07077, # 16-57-48006); by the ONIT RAS program # 6 “Bioinformatics, modern information technologies and mathematical methods in medicine” 2016.