Matrix transposition algorithm using cache oblivious

• Autorzy: Guzmán López Samuel , San Gil Santana Adolfo Javier , Cuba Alonso del Rivero Jorge Alberto , Pérez Lovelle Sonia , Díaz Pando Humberto

Identyfikatory

DOI

10.14313/JAMRIS/4‐2023/25

• Języki publikacji: EN

Abstrakty

EN

The Parallel and Distributed Computing group belonging to the Integrated Technological Research Complex (CITI). has been engaged in the creation of general-purpose components that support the processing of large volumes of information that characterize the problems involved in parallel computing. Using the oblivious cache model, which works independently of the computer architecture, and the divide and conquer principle, an algorithm for matrix transposition is implemented to reduce the execution time of this algebraic operation. The algorithm ensures that most of the data content is loaded to the cache for fast processing, and makes the most of its stay in the cache to minimize missed reads and achieve greater speed. The work includes conclusions and statistical tests carried out from experiments on computers with different architectures, reflecting the superiority of the algorithm that uses oblivious cache from an order of matrix determined according to the characteristics of each PC.

Słowa kluczowe

EN

cache oblivious; Matrix transposition; missed readings

• Wydawca: Łukasiewicz Industrial Research Institute for Automation and Measurements PIAP
• Czasopismo: Journal of Automation Mobile Robotics and Intelligent Systems
• Rocznik: 2023
• Tom: Vol. 17, No. 4
• Strony: 1--7
• Opis fizyczny: Bibliogr. 14 poz., rys.

Twórcy

autor

Guzmán López Samuel

• Technological University of Havana José Antonio Echeverría, Cuba

• https://orcid.org/0000-0002-3696-6830

autor

San Gil Santana Adolfo Javier

• Technological University of Havana José Antonio Echeverría, Cuba

• https://orcid.org/0000-0002-5146-3094

autor

Cuba Alonso del Rivero Jorge Alberto

• Technological University of Havana José Antonio Echeverría, Cuba

• https://orcid.org/0000-0002-1015-8237

autor

Pérez Lovelle Sonia

• Technological University of Havana José Antonio Echeverría, Cuba

• https://orcid.org/0000-0002-4197-2856

autor

Díaz Pando Humberto

• Technological University of Havana José Antonio Echeverría, Cuba

• https://orcid.org/0000-0003-1591-8781

Bibliografia

• [1] www.portal.citi.cu. (accessed 4/6/2019).
• [2] C. Mayer. “Cache oblivious matrix operations using Peano curves,” Department of Computer Science Technische University Munchen, Germany, 2006.
• [3] M. Frigo, Leiserson, H. Prokop, and Ramachandran. “Cache Oblivious Algorithms”, MIT Laboratory for Computer Science, Cambridge, USA, 1999.
• [4] H. Prokop. “Cache‐Oblivious Algorithms,”Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology., Massachusetts 1999.
• [5] A. J. San Gil Santana, S. Guzmán López, and J. A. Cuba Alonso del Rivero. “Algoritmo de multiplicación de matrices utilizando cach inconsciente y curva de Peano,” XVIII Convención y Feria internacional Informática 2020, 2020.
• [6] T. M. Chilimbi. “Cache Conscious Data Structues Desing and Implementation,” University Of Wisconsin 1999.
• [7] M. Frigo, C. E. Leiserson, H. Prokop, and S. Ramachandran. “Cache-Oblivious Algorithms,” ACM Transactions on Algorithms, 2012.
• [8] Ritika. “Cache‐aware and cache-oblivious algorithms,” Master of Engineering Computer science and engineering, Thapar University Patiala 2011.
• [9] S. Neeraj and S. Sandeeep. “Effcient cache oblivious algorithms for randomized divide-and-conquer on the multicore model,” 2018.
• [10] S. Chatterjee and S. Sen. “Cache Efficient Matrix Transposition,” Department of Computer Sciense, University of North Carolina Chapel Hill, NC 27599‐3175, USA – Indian Institute of Technology New Delhi 110016, India, 2005.
• [11] M. Palacios. “Matrices,” Departamento de Matemática Aplicada Universidad de Zaragoza, 2018.
• [12] D. Tsifakis, P. Alistair, Rendell, and P. E. Strazdins. “Cache Oblivious Matrix Transposition: Simulation and Experiment,” Department of Computer Science, Australian National University Canberra, Australian, 2004.
• [13] V. M. Weaver et al.. “PAPI 5: Measuring Power, Energy and the Cloud,”International- Symposium on Performace Analysis of Systems and Software, 2013.
• [14] P. J. Mucci, S. Browne, C. Deane, and G. HO. “PAPI: A Portable Interface to Hadware Performance Counters,” University of Tennessee, Knoxville, Tennessee, 199

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2024).