| Autor: |
Arturo Garza, Kyu Seon Yum, Claudio A. Parra, Isaac D. Scherson, Travis Yu |
| Rok vydání: |
2020 |
| Předmět: |
|
| Zdroj: |
2020 International Conference on Computational Science and Computational Intelligence (CSCI). |
| DOI: |
10.1109/csci51800.2020.00228 |
| Popis: |
An in situ rectangular matrix transposition algorithm is presented based on recursively partitioning an original rectangular matrix into a maximum size square matrix and a remaining rectangular sub-matrix. To transpose the maximum size square sub-matrix, a novel cache-friendly, parallel (multithreaded) and scalable in-place square matrix transposition procedure is proposed: it requires a total of Θ(n2/2) simple memory swaps, a single element temporary storage per thread, and does not make use of complex index arithmetic in the main transposition loop. Recursion is used to transpose the remaining rectangular sub-matrix. Dubbed Recursive MaxSquare, the novel proposed rectangular matrix in-place transposition algorithm uses a generalization of the perfect shuffle/unshuffle data permutation to stitch together the recursively transposed square matrices. The shuffle/unshuffle permutations are shown to be efficiently decomposed using basic vector/segment swaps, exchanges and/or cyclic shifts (rotations). A balanced parallel cycles-based transposition is also proposed for comparison. |
| Databáze: |
OpenAIRE |
| Externí odkaz: |
|
