Parallelization of stochastic bounds for Markov chains on multicore and manycore platforms

Modeling real complex systems with the use of Markov chains is a well-known and recognized method giving good results [20]. However, in spite of its numerous merits, it also has some disadvantages. One of them is the size of the model—to achieve needed accuracy we often have to create a large model (that is, a huge matrix) and such models require quite a lot of computation time [5]. There are some ways to reduce the number of investigated states (at the expense of some accuracy, of course) or to change the structure of the matrix (to make it more convenient to computations). Some of the methods [2, 9‐11, 16] could use the Abu-Amsha–Vincent’s (AAV) Algorithm [1, 12]. In previous work [3], we focused on finding stochastic bounds for Markov chains with the use only of the loop parallelism from OpenMP on Intel Xeon Phi coprocessor. A known algorithm was adapted to study the potential of the MIC architecture in algorithms needing a lot of memory access and exploit it in the best way. This work is an extension of that previous work [3].

In this paper, we present parallel implementations of AVV algorithm designed for x86 based multicore manycore architecture such as Haswell CPU and Intel Knight Corner (KNC). We want to create approaches that are sufficiently general to be applied to implementations of other similar algorithms for sparse matrices which need a lot of irregular memory access. Our contribution consists of applying two C++ language extensions, namely OpenMP and the Intel Cilk Plus [8] framework for parallelization of the application. OpenMP is an API that supports multi-platform shared memory multiprocessing programming on most processor architectures and operating systems. It consists of a set of compiler directives, library routines, and environment variables Intel Cilk Plus is an extension to the C++ language to support loop parallelization and task parallelism using work-stealing policy. For these two extensions, we exploit two programming models, namely task parallelism and loop parallelism. In this work, we evaluate the suitability of OpenMP and Cilk Plus for both parallel programming models: task parallelism and loop parallelism. We want to know how the task model compares to loop parallelism model in terms of the time execution and scalability. We try to select the most suitable programming model, framework, and architecture for the algorithm for the sparse matrix to achieve the best performance.

The outline of the article is following. Section 2 gives some mathematical background of the problem and presents the original version of AAV Algorithm and shows its parallel version (for dense matrices). Section 3 discusses some aspects of the matrix representations and the parallel implementations that allow us to achieve better performance in our parallel version of the algorithm. Section 4 describes our experiments and Sect. 5 analyzes its results. Finally, Sect. 6 concludes the paper and gives some perspectives for further works.

Finding stochastic bounds is an idea widely used in modeling with Markov chains [7, 14, 17, 19, 21]. Some of its basics and examples can be found also in [3, 7].

The main problem is to find a lower (upper) stochastic bound \({\mathbf {V}}\) of a probabilistic matrix \({\mathbf {P}}\)—that is, a matrix \({\mathbf {V}}\) which is less (greater) in the stochastic sense than \({\mathbf {P}}\).

The crucial operation in the sequential AAV algorithm is the stochastic maximum function defined as (\({\mathbf {p}}\), \({\mathbf {q}}\), \({\mathbf {r}}\) are stochastic vectors of the size N):With the use of this function, we can obtain the upper stochastic bound in a straightforward manner—the sequential AAV algorithm—see Fig. 1 (both the matrices are stochastic ones of the size \(N\times N\) and \(\mathbf {M}_{k,*}\) is the kth row of a matrix).

The sequential AAV algorithm is also quite easy to parallelize when we divide it into three steps defined as the following operations—see Fig. 2 which shows these operations as in-place algorithms. Two of these routines can be parallelized row-wise (D and S) and the third one—column-wise (M) as they work on rows or on columns, respectively.

The whole AAV algorithm consists of the three steps (S, M, and D). In the work [3], we had shown the tests for the first step only, namely S steps on coprocessor Intel Xeon Phi. The results of the numerical experiments of the first and the third steps are presented here. We investigated the execution time and the scalability of our parallel implementations on CPU and coprocessor Intel Xeon Phi under Linux. We used two metrics to compare the computing performance: time and relative speedup. Time is the time spent in the first and the third steps of the AAV algorithm. Relative speedups are calculated by dividing the time of work with a single thread by the time with n threads.

We compared five parallel implementations of the first and the third step of the AAV algorithm (and a sequential implementation as a baseline), namely:Table 1 shows details of the specification of the hardware and software used in the numerical experiment.

The tested implementations were written in the language C++ language (with the use of the OpenMP pragmas and Intel Cilk Plus framework for parallelization) and compiled with Intel C++ Compiler (icc) with optimization flag -O3. All the results are presented for the double data type and the native mode for MIC. Carrying out the numerical experiments, we were changing the number of available threads. For CPU, we studied the number of the threads from 1 to 24 (the number of the physical cores). For MIC in our tests, we used 60 cores in native mode. In case of native execution model, when the application is started directly on Xeon Phi card, we can use 60 cores (with all 4 threads on each). For MIC, the numbers of threads studied were up to 120—bigger numbers of threads degraded the performance.

The tests were performed with the use of random matrices. Their size was 40000 \(\times \) 40000 with different numbers of nonzero elements on CPU and MIC. There were also some other tests (not presented here) for other sizes and densities of the matrix; however, their results were very similar to the results shown below—the number of the nonzero elements was crucial.

A single run of our operations was quite short, so to measure the performance time accurately we run every test repeatedly and average the time. Every run covered every action needed in the algorithm from the very beginning—initialization, allocation, etc., to the very end.

In this article, we have presented an approach for parallelization of stochastic bounds for Markov chains on CPU and Intel Xeon Phi. The parallelization of the matrix operations, where matrices are sparse and there is a lot of irregular memory access, is the difficult issue. We have shown the abilities of two parallel extensions of C++ language, namely OpenMP and Cilk Plus in the terms of the loop parallelism and task parallelization. Based on the conducted experiments, we can clearly state that:This paper presents the strength of the OpenMP standard for parallelizing with the use of #pragma omp parallel for. While the Intel Cilk Plus standard offers similar functionality, in our applications we were not able to achieve satisfactory performance results with Cilk Plus despite investing a greater development effort than we did with OpenMP. The results depend on the number of nonzeros elements in sparse matrices for Intel Cilk Plus.

MIC (KNC) performed worse than CPU, so we should focus on the ways to exploit the performance potential of not only many cores but also wide vector units in each core and data locality [13]. We are also going to utilize other extensions like OmpSs [18] and Intel Threading Building Blocks (TBB) [22] and then to compare new results with the current ones.