Automatic analysis of electroencephalograms (EEGs) is one of the promising areas of research, which results can be used, in particular, to build systems of mental control of objects. The Dynamic Time Warping procedure (DTW) is used in this work for comparing signals representing EEG. An important feature of the problem we are considering is the need for multiple comparison of signals at the stage of machine learning, which requires enormous computational costs. We propose a parallel algorithm that was implemented in C++ using the MPI technology and tested using the resources of the supercomputer complex of Moscow State University “Lomonosov”. The results of its testing on real data showed that the proposed method allows achieving an almost linear speedup and reducing the total calculation time from 29 days to 3.5 hours using 128 processes, which opens the possibility of improving the quality of automatic analysis of electroencephalograms.
a) b) c) Fig. 1. a) The process of registering electroencephalograms, b) an example of a target object (mammograms with pathology), c) an example of an un-target object (mammograms without pathologies).
Figure 2 shows examples of signals recorded from two of the 66 electrodes during viewing target (solid lines) and non-target (dashed lines) objects. The signals are subjected to preprocessing (filtration, scaling and smoothing by a sliding window), used by us to improve the quality of target objects recognition.
High-Performance Computing / A.I. Makarova , V.V. Sulimova
From a mathematical point of view, the electroencephalograms, which need to be analyzed for each of the 66 electrodes, fixed in different parts of the head are single-component discrete signals.
Obviously, the analysis of electroencephalograms must inevitably be based on comparing the signals representing them.
Since the form of the response to the stimulus and the time of its onset can vary, in this work, for the comparison of signals an
adapted version of Dynamic Time Warping (DTW) procedure is used. This algorithm based on the search for optimal pairwise
alignment of compared signals by local compression and stretching of their axes. Initially, the DTW method was proposed to
compare speech signals [
The task of analyzing electroencephalograms within the framework of this work is formulated in the form of a two-class
pattern recognition problem, which solution is carried out in two stages - training and recognition [
Modern methods of machine learning in the construction of decision rules are based on measures of object comparison and
allow us to automatically choose the most suitable ones in the training process, improving the quality of the solution of the
problem [
In accordance with the above, an extremely topical task is to increase the productivity of the electroencephalogram comparison.
There are a number of ways to speed up the Dynamic Time Warping procedure, however, they either do not guarantee the
finding of the optimal solution [
In this paper, we propose a parallel algorithm that significantly improves the performance of calculating the matrix of pairwise comparisons for any signals representing fragments of an electroencephalogram. Increase in productivity is performed without loss of accuracy of calculations due to taking into account the features of the task, allowing to implement parallelization at a higher level.
The proposed algorithm is implemented in C ++ programming language using the MPI technology [
High-Performance Computing / A.I. Makarova , V.V. Sulimova
2.1. The mathematical formulation of the problem of comparing two signals
Let x = (x1, x2 ,..., xNx ) and y = ( y1 , y2 , ..., yNy ) - are two single-component discrete signals, which length are Nx and N y , respectively, and which consists of xi , y j О R , i = 1,..., Nx , j = 1, ..., Ny elements.
Specific pairwise warping of two signals x and y uniquely determines the correspondence of signal's elements and has a length Nw , equal to the number of such pairwise correspondences. At that first and last elements of signals are certainly corresponded to each other: w1,1 = w1,2 = 1, wNw ,1 = Nx , w Nw ,2 = Ny .
A warping of two signals is considered as optimal one if it ensures the minimum value of the following optimality criterion: where (1) b і 0 - penalty for non-parallel references between elements of signals, corresponded to local warping axes.
The optimal value of the criterion can be considered as a dissimilarity of the signals: r( x, y) =
J (x, y, wˆ ) . 2.2. A sequential algorithm for computing the dissimilarity of two signals
The minimum of the optimality criterion (1) can be found by means of the dynamic programming procedure [
The algorithm of finding the optimal pairwise warping consists in consecutive passing through all the vertices of the graph, beginning with the upper left and ending with the bottom right vertex. An incomplete value of the optimality criterion ̅ ,1 is calculated at each vertex on the basis of the initial parts of the signals x1..i = (x1,..., xi ) , y1.. j = ( y1,..., y j ) :
The sought value of the dissimilarity of two signals: ( , ) = √ ̃ .
High-Performance Computing / A.I. Makarova , V.V. Sulimova 2.3. Calculation of the matrix of values of dissimilarity of electroencephalograms
As already mentioned above, at the stage of learning the computer algorithms for data analysis, it is necessary to calculate the matrices of the values of dissimilarity for all pairs of signals representing fragments of electroencephalograms from a certain training set X = {x1 , x2 , ..., xK } .
The matrix of pairwise dissimilarities calculated in accordance with the algorithm given in Section 2.2 is symmetric and contains zero values on the main diagonal, so it is sufficient to calculate only the values belonging to the upper (or lower) triangle (Figure 4), the number of which can be determined according to the expression K (K - 1)/ 2 .
Since the number of computations has a quadratic dependence on the number of signals compared, even for a small volume of training set. In this work the training set consists of K = 755 fragments of electroencephalograms (for each electrode) and so it is necessary to perform 284635 pairwise comparisons of signals to calculate one matrix. Thus, it is necessary to perform 56357730 pairwise comparisons of signals to calculate such matrices for all 66 electrodes and for three different values of the penalty for warping signal's axes. Since the time of one pairwise comparison requires, on average, 0.045 seconds, the calculation of all the matrices takes about 29 days, which makes it impossible to carry out experiments on real data and requires taking special measures to improve computing performance.
The task of computing several matrices of pairwise dissimilarity of fragments of electroencephalograms has several levels of data parallelism. Independently from each other can be calculated: 1) the incomplete values of the criterion, located on one minor diagonal of the graph of pairwise correspondences, 2) all elements belonging to the upper (or lower) triangle of the matrix of values of pairwise dissimilarity (Figure 4), 3) all matrices of pairwise dissimilarity.
Parallelization at the first level requires frequent interaction of processes or threads and is associated with the costs of
synchronization, what can also lead to inefficient use of the cache [
Parallelization at the third level obviously makes sense only if the number of matrices that need to be calculated is greater
than the number of available calculators. It also seems inappropriate, since in this study we focus on the computational
capabilities provided by the supercomputer complex “Lomonosov” of Moscow State University [
High-Performance Computing / A.I. Makarova , V.V. Sulimova
So, in the framework of this paper, parallelization is performed at the second level, i.e. the tasks of calculating the elements of a single matrix of pair-wise dissimilarity for a set of signals are identified as parallel tasks. In this case, if it is necessary to calculate several matrices, then they are computed sequentially.
MPI technology [
In this case, since even for the Lomonosov supercomputer, the number of elements of each calculated matrix turns out to be much larger than the number of processors, then the parallel tasks are aggregated by means of a one -time distribution of the matrix elements between the processes.
In this paper the following scheme is used to distribute M = K (K - 1) / 2 elements between the P processes: the first M mod P processes receive the (M - M mod P) / P + 1 elements, and the remaining M - M mod P processes receive the (M - M mod P) / P elements, where mod is the modulo operation which gives the remainder after division of one integer by another.
This scheme allows us to distribute the work between processes as evenly as possible. The one-time even distribution of elements between the processes proves to be the most effective in this situation, since all compared signals have the same length and, accordingly, the comparison of any pairs of signals takes approximately the same time. As a result,this scheme allows to ensure the most efficient use of the resources of the computer system.
Graphical representation of the scheme of data distribution by processes is shown in Fig. 5.
According to the proposed scheme of parallel computing, each process independently of the others: 1) reads the original signals representing fragments of electroencephalograms from the input file, 2) determines the number of matrix's elements that it must process and the linear index of the initial element belonging to its range, according to the above-mentioned principle of uniform distribution of elements between processes, 3) calculates the row and column number determining the position of the given element in the matrix from the found linear index,
4) performs a sequential search of the consecutive elements of the matrix belonging to the upper triangle starting from the element defined in clause 2, at that performs for each element of its range a comparison of the corresponded signals (according to the sequential algorithm described in Section 2.2) and stores the calculated values in their copy of the dissimilarity matrix. Calculations continue until the number of elements obtained in step 2 is processed.
All results are merged on the process with the number 0 using the function MPI_Reduce, after each process computes its elements of the dissimilarity matrix.
Brain electroencephalograms obtained in the course of the study described in [
In total, it is required to calculate three matrices (for different values of the penalty) of a pairwise dissimilarity of 755 signals for each of the 66 electrodes. I.e. it is required to calculate 198 matrices. However, the calculation of all matrices of dissimilarity takes approximately the same time and in this connection, it is enough to perform testing for one of the matrices.
The performance study was implemented using the resources of the MSU supercomputer complex “Lomonosov” [
The acceleration, which was obtained for each case, was calculated as the ratio of the sequential computation time to the calculation time on P processes. The results are shown in Table 2. 1,12535 4,61894 18,7533 117,278 472,307 1083,46 3010,1 6864,46 2 1,909788 1,958477 1,98204 1,981105 1,997965 1,960663 1,964194 1,992247 4 0,701826 2,38828 9,42092 58,3369 238,218 541,713 1498,6 3418,42 4 3,062269 3,787701 3,945453 3,982728 3,9613 3,921449 3,945296 4,000591 8 0,48118 1,15214 4,82778 29,1305 117,96 268,855 736,2 1700,52 8 4,466478 7,851554 7,69915 7,975833 7,999771 7,901285 8,030997 8,042069 Running time of the algorithm (sec)
Number of processes Acceleration of the algorithm
Number of processes 16 0,21083 0,619012 2,34974 14,696 59,0047 133,068 371,859 847,277 16 10,1939 14,61376 15,81869 15,80974 15,99284 15,96402 15,89963 16,14077 32
As expected, the acceleration achieved by using the proposed parallel algorithm increases with the size of the calculated matrix of signal dissimilarity. And the acceleration is almost linear in the calculation of the total matrix.
Thus, the proposed approach launched on 128 processes of “Lomonosov” supercomputer complex allowed us to reduce the time of calculating one complete matrix of dissimilarity of fragments of electroencephalograms by 127.89 times. The calculation time for one matrix was reduced from 3.8 hours to 1.78 minutes, and the total calculation time of all 198 matrices was reduced from 29 days to 3.5 hours.
In this paper, a high-performance algorithm is proposed which calculates the matrix of the dissimilarity of signals representing fragments of brain electroencephalograms. The proposed algorithm was implemented in C++ programming language with using MPI parallel programming technology. It was tested using the resources of “Lomonosov” supercomputer 64 0,205418
High-Performance Computing / A.I. Makarova , V.V. Sulimova
complex at Moscow State University [
This work is supported by the Russian Fund for Basic Research, grant 15-07-08967.
The authors would like to thank rector of Lomonosov Moscow State University Viktor Sadovnichiy and Moscow State University Supercomputing Center for providing “Lomonosov” supercomputer complex to perform experimental study.