The regression analysis of large data sets by parallelization is investigated in the work. Different approaches to parallel computing are proposed. The parallelization of the gradient descent method and the stochastic gradient descent using OpenMP and MPI technologies, as well as their hybrid, is performed. The efficiency of the proposed parallel algorithms is analyzed. A number of numerical experiments were performed. Acceleration of 5 times was achieved using the six-core architecture of a personal computer. By varying the number of threads and processor cores, the possibility of further optimization of the computational process is established. The problem of erroneous exchange is considered, which often has a negative effect on acceleration during parallelization using OpenMP. The advantages and disadvantages of using each of the technologies are analyzed. generality, the software product is developed in the work, which can be used in the regression analysis of big data processing in a wide range of economic problems. Gradient descent algorithm, multicore, OpenMP technology, MPI technology, acceleration When processing large amounts of information, a large number of calculations are implemented, which consumes significant resources and time for its processing. Moreover, the construction of systems that perform the necessary operations depends on the type of data received and describes each specific situation. Due to the variety of data that can simultaneously characterize the task, there is a problem of creating techniques that will universalize the processing of large amounts of information, regardless of its type [1].
Conducting
2021 Copyright for this paper by its authors.
In the work [7] the authors expanded the stochastic gradient descent for support vector machines in several ways to develop the new multiclass SVM-SGD for efficiently classifying large image datasets into many classes. ages with very-high-dimensional signatures into thousands of classes.
In the work [8] the authors created optimized implementations of gradient descent on both GPU and multi-core CPU platforms, and perform a detailed analysis of both systems’ performance characteristics. The GPU implementation was done using CUDA, whereas the multi-core CPU implementation was done with OpenMP.
In the work [9] the authors presented the results of an empirical study of stochastic projection and stochastic gradient descent methods as means of obtaining approximate inverses and preconditioners for iterative methods. But the results are preliminary due to the code being not yet fully optimized.
Big data is a field that considers methods of analysis, systematic extraction of information, work with data sets that are too large or complex to be analyzed by traditional data processing software [10, 11]. There are problems when regression analysis needs to be performed on big data.
"Big Data" as a concept is becoming increasingly popular in the world. It is used in marketing research, in the analysis of world markets, sociological research and even elections [12]. Thus, large amounts of data can contain important information that requires efficient processing. It is usually performed using machine learning algorithms that study the available data. However, as a rule, such calculations require duration and complexity at the stages of learning or forecasting, which makes it impossible to use implementations of sequential algorithms, because they are unable to cope with the current data. Therefore, the aim of this work is to study the performance of regression analysis on large data sets by parallelization. Parallel approaches to increase processing speed are proposed.
The main contribution of this article can be summarized as follows: • A simple yet accurate and computationally efficient method is developed, which combines the gradient descent method and the stochastic gradient descent using OpenMP and MPI technologies and their hybrid. It is especially relevant in modern trends in the development of the multi-core architecture of modern computers.
• The main advantage of the proposed technique is that I have received an acceleration that goes to the number of cores of the appropriate computing system; I have investigated the problem of false exchange, which often negatively affects acceleration with parallel with OpenMP.
( X Т X )1 X T y, y 0 1x1 ... n xn , h(x) 0 1x1 ... n xn , where y – dependent variable, x – property vector (independent variables), n – number of independent variables, – vector of linear regression coefficients.
Hypothesis is a function that best describes the purpose of machine learning (see formula (
I will use the least squares method to estimate the unknown parameters. It takes as an estimate of
the parameter values that minimize the sum of the squares of the residues for all observations. Thus,
the cost function takes the form:
(
As is known [15], this method has advantages over the method of gradient descent, because it does
not require a learning step and does not require iterations. As can be seen from formula (
The research of the gradient descent method and the possibility of its parallelization is carried out in the work. This method requires a large number of iterations, but works well even with a significant amount of properties. The difficulty in parallelizing this method is that the algorithm is quite consistent. Each subsequent update of the coefficients depends on their previous values. Gradient descent algorithm: j : j j : j j
J ( 0 ,1), j 0 1, 1 m
(h (x(i) ) y(i) )x(i) , m i1 j j – j regression coefficient, learning step, m the number of elements in the data set, h – hypothesis, x(i) – i string in the data set, x(i) – j element in the i string of the data set, y(i) – i j dependent variable. It is necessary to iterate to a certain stop condition while updating the coefficients j .
The gradient descent has a known optimization – stochastic gradient descent (
j
Similarly, as in formula (
Therefore, in order to solve this problem, the gradient descent method and the stochastic gradient descent method were parallelized using OpenMP [18, 19] and MPI [20] technologies.
Regarding the choice of OpenMP technology, the advantages are: Due to the idea of "incremental parallelization", OpenMP is ideal for developers who want to quickly parallelize their computing programs with large parallel loops. The developer does not create a new parallel program, but simply consistently adds OpenMP directives to the text of the program. At the same time, OpenMP is a fairly flexible mechanism that gives the developer great control over the behavior of the parallel program. It is assumed that the OpenMP program on a single-processor platform can be used as a serial program, ie there is no need to support serial and parallel versions.
As for MPI technology, in the MPI programming model, the program generates several processes that interact with each other by calling routines for receiving and transmitting messages. Usually, when initializing an MPI program, a fixed set of processes is created, and (which, however, is optional) each of them runs on its own processor. These programs can run different programs, so the MPI model is sometimes called the MIMD model (Multiple Instruction, Multiple Data), in contrast to the SIMD model, where each processor performs only the same tasks. MPI supports two-point and global, synchronous and asynchronous, blocking and non-blocking types of communications. A special mechanism – a communicator – hides from the programmer internal communication structures. The structure of communications can change over the life of the process, but the number of tasks must remain constant (MPI-2 supports a dynamic change in the number of tasks). The MPI specification provides program portability at the source code level. Work on heterogeneous clusters and symmetric multiprocessor systems is supported. Process startup during MPI program execution is not supported. The specification does not describe parallel I/O and program debugging – these features can be included in a specific MPI implementation in the form of additional packages or utilities. Compatibility of different implementations is not guaranteed.
Without reducing the generality, the paper considers the problem of simulating the temperature of the stator and rotor in real time. Due to the complex structure of the electric traction drive, direct measurements with thermal sensors are not possible for the rotor temperature. In addition, accurate thermal modeling is becoming increasingly important with increasing relevance of functional safety. Therefore, it is necessary to create a model that estimates the stator temperature based on the input data.
The main task is to find the regression equation of the form (
Selected sample (dataset contains 500,000 data, 7 properties and the dependent variable [21]): 1. The ambient temperature measured by a thermal sensor located close to the stator; 2. Coolant temperature (water cooling motor); 3. d–component; 4. q–component; 5. Engine speed; 6. The d–current component; 7. The q–current component.
Dependent variable is the stator temperature measured by a thermal sensor.
The paper parallels the gradient descent algorithm and stochastic gradient descent using OpenMP technology.
Stages of parallelization of the gradient descent algorithm (
Code snippet:
double* hypothesisP(double **X, double *Q, int m, int n) {
double* result = new double[m];
#pragma omp parallel for num_threads(
result[i] += X[i][j] * Q[j];
}
}
return result; }
2. At this stage, the parallelization of the calculations required to find the result of the cost
function (
sum += (hQ[i] - Y[i]) * X[i][k];
}
return sum / m;
}
double* hypothesisP(double **X, double *Q, int m, int n) {
double* result = new double[m];
#pragma omp parallel for num_threads(
result[i] += X[i][j] * Q[j]; }}
return result;}
The time spent on the second stage of the parallel gradient descent algorithm with different number of iterations and flows on a 2-core processor is given in Table 1 and Table 2, and the visualization of the results is presented in Figure 1 and Figure 2.
10 20 30
execution time, sec
2
Number of threads 4
Similar numerical experiments were performed when tested on a 6-core processor. The results are given in Table 3 and Table 4 and in Figure 3 and Figure 4. When using a 6-core processor we obtained acceleration equal to 2 and when choosing the number of streams to more than six, we observe a significant reduction in efficiency, which confirms the reliability of the results.
Sometimes significant benefits cannot be achieved through false sharing. Simultaneous updates of individual items in the same cache line coming from different processors invalidate entire lines of the cache, although these updates are logically independent of each other. Each update of an individual cache line item marks the line as invalid. Other processors that access another item on the same line see the string marked as invalid. They have to get a newer copy of the string from memory or elsewhere, even if the item they accessed has not been changed. This is because cache coherence is maintained based on the cache line, not for individual elements.
As a result, there will be an increase in the relationship between traffic and overhead costs. Also, while the cache line is being updated, access to items in the line is denied. This situation is called false exchange. If this happens often, the performance and scalability of OpenMP will be significantly affected. Therefore it is necessary to use various ways of distribution of iterations: We can conclude that on average the parallel algorithm works much faster with different iteration distributions.
Similarly, the execution time when tested on a 6-core processor is given in Table 6, and the visualization of the results in Figure 5.
The parallelization algorithm of stochastic gradient descent is also performed in the work. The parallelization of this algorithm can occur by blocking the change of coefficients by each process, but this approach obviously does not allow to obtain significant advantages. However, there is an interesting Hogwild algorithm! [23, 24], which allows you to change the coefficients without synchronization. This method works without any negative impact on the mathematical efficiency of the algorithm. The description of the algorithm is as follows:
Each thread draws a random example i from the training data.
Thread reads current state of . Thread updates.
( L( f (xi ), yi )).
Code snippet for two threads:
#pragma omp parallel for num_threads(
tempQ[j] = Q[j] - alpha * (h(X[i], Q, n) - Y[i]) * X[i][j]; } } for (int k = 0; k < n; k++) {
Q[k] = tempQ[k]; }
When the sample size is large enough (in this case 500,000) then one iteration is enough. Execution time for testing on 6 cores is given in Table 7 and Table 8 and data visualization in Figure 6. Sequential algorithm execution time, sec
Next, we present the results of parallelization of the gradient descent algorithm and stochastic gradient descent using MPI technology.
1. Parallelization of the gradient descent algorithm.
The parallelization occurs by the fact that the rows of the matrix X[i] are distributed between the threads. Each thread calculates the result of the cost function on an equal amount of data allocated to it, then sends a calculation from each data selection and the main thread based on this data makes changes to the model. The disadvantage of this method is that it requires the exchange of information between threads, which can slow down the parallelization.
DWORD Start = GetTickCount(); if (ProcRank == 0) { double* tempQ = new double[n]; for (int iter = 0; iter < 20; iter++) { for (int qiter = 0; qiter < n; qiter++) { for (int p = 1; p < ProcNum; p++) {
MPI_Send(Q, n, MPI_DOUBLE, p, 1, MPI_COMM_WORLD);
MPI_Send(&qiter, 1, MPI_INT, p, 1, MPI_COMM_WORLD); } double procSum = costMpi(X, Y, Q, m, n, qiter, ProcNum, ProcRank); double allSum = procSum; for (int pr = 1; pr < ProcNum; pr++) { double curSum = 0; MPI_Recv(&curSum, 1, MPI_DOUBLE, pr, MPI_ANY_TAG, MPI_COMM_WORLD,
allSum += curSum; } tempQ[qiter] = Q[qiter] - alpha * (allSum / m); } for (int qiter = 0; qiter < n; qiter++) {
Q[qiter] = tempQ[qiter]; } for (int t = 0; t < n * 20; t++) { int k = 0; MPI_Recv(Q, n, MPI_DOUBLE, 0, 1, MPI_COMM_WORLD, &Status); MPI_Recv(&k, 1, MPI_INT, 0, 1, MPI_COMM_WORLD, &Status); double procSum = costMpi(X, Y, Q, m, n, k, ProcNum, ProcRank);
MPI_Send(&procSum, 1, MPI_DOUBLE, 0, ProcRank, MPI_COMM_WORLD); }} MPI_Finalize();
DWORD dwRunTime = GetTickCount() - Start;
Execution time for testing on a 6-core processor is given in Table 9 and Table 10, and visualization of results Figure 7 and Figure 8. Time spent performing the gradient descent algorithm using MPI technology (6-core processor) Number of iterations
Sequential algorithm execution time, sec 10.1
Execution time of parallel algorithm,
sec
Number of threads
As you can see from the results, MPI technology allows you to significantly improve the results of parallelization of gradient descent. Acceleration is equal to 5 on 6-core processor.
Gradient descent MPI 6 2. Parallelization of the stochastic gradient descent algorithm.
The parallelization occurs by the fact that the rows of the matrix – X[i] are distributed between the threads. Each thread searches for a local model, then sends the found model to the main thread, where all local models are averaged and we get a global model. The disadvantage of this method is that it requires additional calculations to find the model.
DWORD Start = GetTickCount(); double* tempQ = new double[n]; int start = ProcRank * (m / ProcNum); int end = ProcRank * (m / ProcNum) + (m / ProcNum); for (int i = start; i < end; i++) { for (int j = 0; j < n; j++) { tempQ[j] = Q[j] - alpha * (h(X[i], Q, n) - Y[i]) * X[i][j]; } for (int k = 0; k < n; k++) {
Q[k] = tempQ[k]; }
MPI_Send(Q, n, MPI_DOUBLE, 0, 1, MPI_COMM_WORLD); double* localQ = new double[n]; if (ProcRank == 0) {
Execution time for testing on a 6-core processor is given in Table 11 and Table 12, and visualization of results Figure 9.
Table 11 Time spent performing the stochastic gradient descent algorithm using MPI technology (6-core processor)
Sequential algorithm execution time, sec 0.10
The execution time of the parallel algorithm,
sec
Number of threads To the parallel algorithm of the stochastic gradient descent, acceleration equals 4.5 when using MPI technology.
Stochastic gradient descent MPI 6
Execution time when tested on a 2-core processor using hybrid technology for parallelization of the method of stochastic gradient descent is given in Table 14.
Table 14
execution time, sec 2 omp parallel for
Number of threads
4 omp parallel for 8 omp parallel for 2 4 2 4 2 4 0.38 0.14 0.18 5.7 8.15 3.0 10.15 As you see the hybrid of OpenMP and MPI technologies allows for both methods when parallel to get accelerated to the number of a core of a multi-core computing system. This is especially relevant in a modern tendency to develop such architectures. 5. Conclusions
In this work, to optimize the regression analysis, the methods of gradient descent and stochastic gradient descent based on OpenMP and MPI technologies are paralleled. Without reducing the generality, a number of numerical experiments were performed on one network date. On the basis of which the efficiency of the proposed approach is analyzed in detail. Acceleration was achieved three times when parallelizing the algorithm and gradient descent using OpenMP for two consecutive cycles with the number of threads 2 and 4 on a six-core processor. The problem of erroneous exchange is considered, which often has a negative effect on acceleration during parallelization using OpenMP. Acceleration can be achieved twice with different distribution of iterations static, dynamic, guided and chunk_size. The Hogwild algorithm! was an interesting discovery and its application to parallelize the task.
The advantage was obtained by using MPI technology, but only with two parallel threads (when tested on a 2-core processor), because with the increase in the number of threads increases the need for more frequent communication, which begins to slow down the program. Significant acceleration of almost 5 times was achieved by parallelization of the algorithm of gradient and stochastic gradient descent on a 6-core processor.
It is also worth noting that each of the technologies has its advantages and disadvantages. With the help of OpenMP it is easy to programmatically implement parallelism, based on MPI technology the program is more difficult to develop and difficult to perform error finding. When using OpenMP technology, communication between threads is implicit, while on MPI it is explicit, so you need to think about how to implement communication between threads. MPI is portable to machines with shared and shared memory, OpenMP only for those with shared memory. In OpenMP there can be a problem with data placement, in MPI – no.
Thus, the problem was completely solved, the algorithm was parallelized by using different technologies.
With minor modifications depending on the requirements, the software implementation can be used in other big data processing tasks and tested on other data sets.