Transactional Memory Scheduling Using Machine Learning Techniques

	International Journal of P2P Network Trends and Technology (IJPTT)
	© 2019 by IJPTT Journal
	Volume-9 Issue-4
	Year of Publication : 2019
	Authors : Basem Assiri, Costas Busch, Mansour Al Ghanim
	DOI :  10.14445/22492615/IJPTT-V9I4P404

Citation

MLA Style: Basem Assiri, Costas Busch, Mansour Al Ghanim. Altaha "Transactional Memory Scheduling Using Machine Learning Techniques" International Journal of P2P Network Trends and Technology 9.4 (2019): 19-33.

APA Style:Basem Assiri, Costas Busch, Mansour Al Ghanim(2019).Transactional Memory Scheduling Using Machine Learning Techniques International Journal of P2P Network Trends and Technology, 9(4),19-33.

Abstract

Current shared memory multi-core systems require powerful software and hardware techniques to support the performance parallel computation and consistency simultaneously. The use of transactional memory results in significant improvement of performance by avoiding thread synchronization and locks overhead. Also, transactions scheduling apparently influences the performance of transactional memory. In this paper, we study the fairness of transactions’ scheduling using Lazy Snapshot Algorithm. The fairness of transactions’ scheduling aims to balance between transactions types which are read-only and update transactions. In the article, we support the fairness of the scheduling procedure by a machine learning technique, which improves the fairness decisions according to transactions history. The experiments in this paper show that the throughput of the Lazy Snapshot Algorithm is improved with a machine learning support. Indeed, our experiments show that the learning significantly affects the performance if the durations of update transactions are much longer than read-only ones or when the cost of abort is very high. We also study several machine learning techniques to investigate the fairness decisions accuracy. In fact, K-Nearest Neighbor machine learning technique shows more accuracy and more suitability, for our problem, than Support Vector Machine Model, Decision Tree Model and Hidden Markov Model.

References

[1] Alfred V Aho, John E Hopcroft, and Jeffrey D Ullman. Data structures and algorithms, 1983.
[2] Naomi S Altman. An introduction to kernel and nearest-neighbor nonparametric regression. The American Statistician, 46(3):175–185, 1992.
[3] SS Arya and S Lavanya. A comparative study of machine learning approaches-svm and ls-svm using a web search engine based application. International Journal on Computer Science & Engineering, 4(5), 2012.
[4] HagitAttiya and Eshcar Hillel. Single-version stms can be multi-version permissive. In Distributed Computing and Networking, pages 83–94. Springer, 2011.
[5] Joseph Devietti, Brandon Lucia, Luis Ceze, and Mark Oskin. Dmp: deterministic shared memory multiprocessing. In ACM Sigplan Notices, volume 44, pages 85–96. ACM, 2009.
[6] Pierangelo Di Sanzo, Marco Sannicandro, Bruno Ciciani, and Francesco Quaglia. On exploring markov chains for transaction scheduling optimization in transactional memory. 7th Workshop on the Theory of Transactional Memory (WTTM 2015).
[7] Pascal Felber, Christof Fetzer, and TorvaldRiegel. Dynamic performance tuning of word-based software transactional memory. In Proceedings of the 13th ACM SIGPLAN Symposium on Principles and practice of parallel programming, pages 237–246. ACM, 2008.
[8] Trevor Hastie, Robert Tibshirani, Jerome Friedman, and James Franklin. The elements of statistical learning: data mining, inference and prediction. The Mathematical Intelligencer, 27(2):83–85, 2005.
[9] Maurice Herlihy and J Eliot B Moss. Transactional memory: Architectural support for lock-free data structures, volume 21. ACM, 1993.
[10] Xuedong D Huang, Yasuo Ariki, and Mervyn A Jack. Hidden Markov models for speech recognition, volume 2004. Edinburgh University Press Edinburgh, 1990.
[11] Stephen Cole Kleene. Introduction to metamathematics. 1952.
[12] Leonid AryehKontorovich, Corinna Cortes, and MehryarMohri. Kernel methods for learning languages. Theoretical Computer Science, 405(3):223–236, 2008.
[13] Priyanka Kumar and Sathya Peri. A timestamp based multi-version stm protocol that satisfies opacity and multi-version permissiveness. arXiv preprint arXiv:1305.6624, 2013.
[14] Karl Ljungkvist, Martin Tillenius, Sverker Holmgren, Martin Karlsson, and Elisabeth Larsson. Early results using hardware transactional memory for high-performance computing applications. In Proc. 3rd Swedish Workshop on Multi-Core Computing, pages 93–97. Go ?teborg, Sweden: Chalmers University of Technology, 2010.
[15] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825–2830, 2011.
[16] Dmitri Perelman, Rui Fan, and IditKeidar. On maintaining multiple versions in stm. In Proceedings of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computing, pages 16–25. ACM, 2010.
[17] J. Ross Quinlan. Induction of decision trees. Machine learning, 1(1):81–106, 1986.
[18] TorvaldRiegel, Pascal Felber, and Christof Fetzer. A lazy snapshot algorithm with eager validation. In Distributed Computing, pages 284–298. Springer, 2006.
[19] EkoSetiawan and AdharulMuttaqin. Implementation of k-nearest neightbors face recognition on low-power processor. TELKOMNIKA (Telecommunication Computing Electronics and Control), 13(3), 2015.
[20] NirShavit and Dan Touitou. Software transactional memory. Distributed Computing, 10(2):99–116, 1997.
[21] Mukul K. Sinha. Nonsensitive data and approximate transactions. IEEE Transactions on Software Engineering, (3):314–322, 1983.
[22] Qingping Wang, Sameer Kulkarni, John Cavazos, and Michael Spear. A transactional memory with automatic performance tuning. ACM Transactions on Architecture and Code Optimization (TACO), 8(4):54, 2012.
[23] Neelamegam, S., and E. Ramaraj. "Classification algorithm in data mining: An overview." International Journal of P2P Network Trends and Technology (IJPTT) 4.8 (2013): 369-374.
[24] Gaur, Manas, ShrutiGoel, and Eshaan Jain. "Comparison between Nearest Neighbours and Bayesian Network for demand forecasting in supply chain management." 2015 2nd International Conference on Computing for Sustainable

Keywords
Lazy Snapshot Algorithm, Transactional Memory, Fairness Values, Support Vector Machine, K-Nearest Neighbor, Decision Tree Model, Hidden Markov Model