nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

Stochastic Bounds for Markov Chains on Intel Xeon Phi Coprocessor

verfasst von : Jarosław Bylina

Erschienen in: Parallel Processing and Applied Mathematics

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

The author presents an approach to find stochastic bounds for Markov chains with the use of Intel Xeon Phi coprocessor. A known algorithm is adapted to study the potential of the MIC architecture in algorithms needing a lot of memory access and exploit it in the best way.

The paper also discusses possible sparse matrices storage schemes suitable to the investigated algorithm on Intel Xeon Phi coprocessor.

The article shows also results of the experiments with the algorithm with different compile-time and runtime parameters (like scheduling, different number of threads, threads to cores mapping).

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Parallel Assembly of ACA BEM Matrices on Xeon Phi Clusters

Nächstes Kapitel Fast DEM Collision Checks on Multicore Nodes

Abu-Amsha, O., Vincent, J.-M.: An algorithm to bound functionals on Markov chains with large state space. In: 4th INFORMS Conference on Telecommunications, Boca Raton, Floride, E.U. INFORMS (1998)

Ben Mamoun, M., Busic, A., Pekergin, N.: Generalized class C Markov chains and computation of closed-form bounding distributions. Prob. Eng. Inf. Sci. 21, 235–260 (2007)MathSciNetMATH

Busic, A., Fourneau, J.-M.: A matrix pattern compliant strong stochastic bound. In: 2005 IEEE/IPSJ International Symposium on Applications and the Internet Workshops (SAINT 2005 Workshops), Trento, Italy, pp. 260–263. IEEE Computer Society (2005)

Bylina, B., Bylina, J.: Strategies of parallelizing nested loops on the multicore architectures on the example of the WZ factorization for the dense matrices. In: Proceedings of the 2015 Federated Conference on Computer Science and Information Systems (FedCSIS 2015); Annals of Computer Science and Information Systems, vol. 5, pp. 629–639 (2015). https://doi.org/10.15439/2015F354

Bylina, B., Bylina, J., Karwacki, M.: Computational aspects of GPU-accelerated sparse matrix-vector multiplication for solving Markov models. Theor. Appl. Inform. 23(2), 127–145 (2011). ISSN 1896–5334CrossRef

Bylina, B., Karwacki, M., Bylina, J.: A CPU-GPU hybrid approach to the uniformization method for solving Markovian models – a case study of a wireless network. In: Kwiecień, A., Gaj, P., Stera, P. (eds.) CN 2012. CCIS, vol. 291, pp. 401–410. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-31217-5_42 CrossRef

Bylina, B., Potiopa, J.: Explicit fourth-order Runge–Kutta method on Intel Xeon Phi coprocessor. Int. J. Parallel Prog. 45, 1073–1090 (2017). https://doi.org/10.1007/s10766-016-0458-x CrossRef

Bylina, J., Bylina, B., Karwacki, M.: A Markovian model of a network of two wireless devices. In: Kwiecień, A., Gaj, P., Stera, P. (eds.) CN 2012. CCIS, vol. 291, pp. 411–420. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-31217-5_43 CrossRef

Bylina, J., Bylina, B., Karwacki, M.: An efficient representation on GPU for transition rate matrices for Markov chains. In: Wyrzykowski, R., Dongarra, J., Karczewski, K., Waśniewski, J. (eds.) PPAM 2013. LNCS, vol. 8384, pp. 663–672. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-642-55224-3_62 CrossRef

10.

Bylina, J., Fourneau, J.-M., Karwacki, M., Pekergin, N., Quessette, F.: Stochastic bounds for Markov chains with the use of GPU. In: Gaj, P., Kwiecień, A., Stera, P. (eds.) CN 2015. CCIS, vol. 522, pp. 357–370. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-19419-6_34 CrossRef

11.

Dayar, T., Pekergin, N., Younès, S.: Conditional steady-state bounds for a subset of states in Markov chains. In: Structured Markov Chain (SMCTools) Workshop in the 1st International Conference on Performance Evaluation Methodolgies and Tools, VALUETOOLS 2006, Pisa, Italy. ACM (2006)

12.

Fourneau, J.-M., Le Coz, M., Pekergin N., Quessette, F.: An open tool to compute stochastic bounds on steady-state distributions and rewards. In: 11th International Workshop on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems (MASCOTS 2003), Orlando, FL. IEEE Computer Society (2003)

13.

Fourneau, J.-M., Le Coz, M., Quessette, F.: Algorithms for an irreducible and lumpable strong stochastic bound. Linear Algebra Appl. 386, 167–185 (2004)MathSciNetCrossRefMATH

14.

Fourneau, J.M., Pekergin, N.: An algorithmic approach to stochastic bounds. In: Calzarossa, M.C., Tucci, S. (eds.) Performance 2002. LNCS, vol. 2459, pp. 64–88. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-45798-4_4 CrossRef

15.

Jeffers, J., Reinders, J.: Intel Xeon Phi Coprocessor High Performance Programming, 1st edn. Morgan Kaufmann Publishers Inc., San Francisco (2013)

16.

Kijima, M.: Markov Processes for Stochastic Modeling. Chapman & Hall, London (1997)CrossRefMATH

17.

Memeti, S., Pllana, S., Kołodziej, J.: Optimal worksharing of DNA sequence analysis on accelerated platforms. In: Pop, F., Kołodziej, J., Di Martino, B. (eds.) Resource Management for Big Data Platforms. CCN, pp. 279–309. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-44881-7_14

18.

Merta, M., Riha, L., Meca, O., Markopoulos, A., Brzobohaty, T., Kozubek, T., Vondrak, V.: Intel Xeon Phi acceleration of hybrid total FETI solver. Adv. Eng. Softw. 112, 124–135 (2017). https://doi.org/10.1016/j.advengsoft.2017.05.001. ISSN 0965–9978CrossRef

19.

Muller, A., Stoyan, D.: Comparison Methods for Stochastic Models and Risks. Wiley, New York (2002)MATH

20.

Shaked, M., Shantikumar, J.G.: Stochastic Orders and their Applications. Academic Press, San Diego (1994)MATH

21.

Stewart, W.J.: Introduction to the Numerical Solution of Markov Chains. Princeton University Press, Princeton (1995)

22.

Stoyan, D.: Comparison Methods for Queues and Other Stochastic Models. Wiley, Berlin (1983)MATH

23.

Tobin, J., Breuer, A., Heinecke, A., Yount, C., Cui, Y.: Accelerating seismic simulations using the Intel Xeon Phi knights landing processor. In: Kunkel, J.M., Yokota, R., Balaji, P., Keyes, D. (eds.) ISC 2017. LNCS, vol. 10266, pp. 139–157. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-58667-0_8 CrossRef

Titel: Stochastic Bounds for Markov Chains on Intel Xeon Phi Coprocessor
verfasst von: Jarosław Bylina
Verlag: Springer International Publishing
Buch: Parallel Processing and Applied Mathematics
Print ISBN: 978-3-319-78023-8

Electronic ISBN: 978-3-319-78024-5

Copyright-Jahr: 2018
DOI: https://doi.org/10.1007/978-3-319-78024-5_11

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"